Vas*_*ass 2 math search matlab graph social-networking
我有大约10K到100K节点的网络都连接在一起.这些节点通常被分组为社区集群,这些集群与它们之间的许多边缘紧密连接,并且存在集线器等.在社区之间存在具有一些边缘的节点,这些节点将社区桥接/连接在一起.这些数据集位于邻接矩阵中
我已经尝试过光谱聚类(Ding et al 2001),但它在大型数据集上确实很慢,并且在存在很多模糊性时似乎停止工作(桥梁不是通往另一个集群的唯一桥梁路径 - 其他社区可以充当替代代理路线).
我尝试过一些来自martelot的方法,例如用于模块化优化的Newman算法,但没有将稳定性优化函数纳入该工作中(这可能是至关重要的吗？).在通过随机图(ER图)创建聚类的合成数据集上,这些方法可以工作,但是在存在嵌套层次结构的实际数据集中,结果是分散的.使用独立的可视化应用程序/工具,桥梁很明显.
你会推荐/建议尝试哪些方法？我正在使用MATLAB.
你到底想做什么？检测社区或它们之间的桥梁？这是两个不同的问题.一旦拥有了社区,就可以直接识别连接两个不同社区的节点的边缘.所以,我猜你想要探测社区.
实际上有数千种方法用于此目的,其中一些方法在Matlab中实现,例如您引用的方法,或广义的Louvain算法(也基于模块化优化).但是,它们中的大多数可用作C或C++程序,例如InfoMap(基于数据压缩范例),WalkTrap(使用基于随机游走的距离进行聚类),Markov Cluster(模拟某些传播机制)和列表继续...
这些工具将社区结构的概念或多或少地形式化,在应用于同一网络时可能导致不同的(估计的)社区结构.当然,不同的社区也意味着不同的桥梁.所以问题是要知道如何为数据选择合适的方法.您似乎对所学的网络有先验知识,因此您应该使用它来做出选择(而不是编程语言).例如,即使您没有明确说明,您似乎也在寻找一种分层的社区结构:并非所有工具都能够检测到这种结构.同样,如果您认为一个节点可以同时属于多个社区,那么您应该考虑寻找重叠社区,例如使用CFinder(基于clique percolation).
我建议你看看这个社区检测的优秀评论,你可能会发现一些有趣的信息,允许你选择一种方法:图中的社区检测.此外,从编程的角度来看,我建议你使用igraph库(可用于C,R和Python):它包含几个标准的社区检测工具.您可以在数据上试用它们,看看你得到了什么.