从群落共生矩阵到每个节点的群落指数

Question

我有一个n x n矩阵X_{ij}，如果图中的节点i和节点j属于同一个集群，则i-j-th条目为1，否则为0。该矩阵是在图中寻找社区的优化算法的结果。

我想用n条目在列表中转换该矩阵，其中对于每个i-th条目，我可以关联一个整数，该整数表示i-th节点所属的单独集群。

例如，在python中，我的矩阵如下(在本例中，节点0和1属于社区A，而节点2和3属于社区B)

matrix([[ 0.,  1.,  0.,  0.],
    [ 1.,  0.,  0.,  0.],
    [ 0.,  0.,  0.,  1.],
    [ 0.,  0.,  1.,  0.]])

这意味着节点0属于同一个社区(节点从0到n-1)，如何从该矩阵中提取出如下列表：

[A,A,B,B]

列表的第一个元素代表节点所属的社区的索引？(我使用A和B只是为了更清楚，但这些指数实际上是整数)

Answer 1

假设这种关系是http://en.wikipedia.org/wiki/Symmetric_relation (X_{ij} = X_{ji})和http://en.wikipedia.org/wiki/Transitive_relation (X_{ij} = 1, X_{jk}= = 1 -> X_{ik} = 1)，您可以将矩阵看作一个图G=(V,E)，其中每个索引i=1,...,n都是一个节点，(i,j)在E中是当且仅当X_{ij} = 1。

因此，您的“社区”实际上是图中的连通组件。

使用任何图发现/遍历算法(如BFS和DFS )，使用以下高级伪代码查找连接组件相当容易：

X = V //all nodes initially in X
count = 1
while X is not empty:
   choose random x in X 
   do BFS from x, let the set of discovered nodes be U
   for each node u in U:
        yield (u,count) //u is in the community labeled as count
   count = count + 1
   X = X \ U //remove all nodes in U from X