从社区共生矩阵到每个节点的社区索引

Question

我有一个矩阵，其中如果图中的节点I和节点j属于同一集群，则第I-j项为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]

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

Answer 1

假设这个关系是对称的（X_{ij}=X_{ji}）和传递的（X_{ij}=1，X_{jk}==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