我有一个 n x n 矩阵 X_{ij} 其中 i-j 第一个条目是 1 如果节点 i 和图中的节点 j 属于同一簇，否则为 0。该矩阵是用于在图中查找社区的优化算法的结果。
我想将该矩阵转换为包含 n 条目的列表，其中对于每个 i 条目，我可以关联一个整数，该整数代表 i - 第一个节点属于。
例如，在 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 只是为了更清楚，但这些索引实际上是整数)
最佳答案
假设您拥有的关系是 symmetric (X_{ij} = X_{ji}) 和 transitive (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
关于python - 从社区共现矩阵到每个节点的社区索引，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24956639/