我想知道在具有加权无向边的图上执行社区检测/图分区/聚类时，是否有人可以建议什么是好的起点。有问题的图有大约 300 万条边，每条边表示它连接的两个顶点之间的相似程度。特别是，在这个数据集中，边是个体，顶点是衡量他们观察到的行为的相似性。
过去，我遵循了我在 stats.stackexchange.com 上获得的建议，并使用了 igraph 的 Newman 模块化聚类实现，并对结果感到满意，但这是在未加权的数据集上。
有没有我应该看的特定算法？
如何在加权社交网络/图中进行社区检测？
机器算法验证
聚类
数据可视化
网络
分区
模块化
2022-02-05 11:33:04
4个回答
纽曼模块化聚类（fastgreedy 函数）的 igraph 实现也可以与加权边一起使用。只需将权重属性添加到边缘并照常分析。以我的经验，它使用重量跑得更快，因为有更少的关系。
我知道Gephi可以处理无向加权图，但我似乎记得它必须存储在GDF中，它非常接近 CSV 或 Ucinet DL。请注意，它仍然是 alpha 版本。现在，关于对图形进行聚类，Gephi 似乎缺少聚类管道，除了现在在最新版本中可用的 MCL 算法。2009 年有一个Google 代码项目，Gephi Network Statistics（以 Newman 的模块化度量为特色），但我不知道是否在这个方向上发布了一些东西。无论如何，它似乎允许某种模块化/聚类计算，但另见Social Network Analysis using R and Gephi and使用 R 和 Gephi 进行社交网络分析的数据准备（非常感谢 @Tal）。
如果您习惯了 Python，那么值得尝试NetworkX（这里是一个带有相应代码的加权图示例）。那么你有很多方法来进行你的分析。
您还应该查看INSNA - 社交网络分析软件或 Tim Evans 关于复杂网络和复杂性的网页。
Gephi 实现了 Louvain Modularity 方法：http ://wiki.gephi.org/index.php/Modularity
干杯
Louvain 模块化算法在 C++ 中可用： https ://sites.google.com/site/findcommunities/
它处理数百万个节点和边的加权网络，并且已被证明比 Newman 算法快得多。