在图中是否有用于社区检测的算法实现？

Question

我正在寻找社区检测算法的实现,例如Girvan-Newman算法(2002).我访问了该领域的几位研究人员的网站(Newman,Santo等)但无法找到任何代码.我想有人在那里发布了这些算法的实现(甚至可能是一个工具包？),但我似乎无法找到它.

Answer 1

社区检测算法有时是库的一部分(例如JUNG for java)或工具(参见Gephi).当作者发布新方法时,他们有时会使他们的代码可用.例如,Louvain和Infomap方法.

旁注:Girvan-Newman算法有时仍在使用,但它主要被更快更准确的方法所取代.为了更好地概述该主题,我建议使用社区检测算法:比较分析或图表中较长的社区检测(103页).

Answer 2

你应该看一下igraph库:

• 7个社区检测算法(包括上面提到的那些):
  • Edgebetweenness(基于Girvan-Newman链接中心性的方法),
  • Walktrap(Pons-Latapy随机步行方法),
  • 领先的特征向量(纽曼光谱方法),
  • Fast Greedy(Clauset等人模块化优化),
  • 标签传播(Raghavan等人),
  • Louvain(Blondel等人,模块化优化),
  • Spinglass(Reichardt-Bornholdt,模块化优化),
  • InfoMap(Rosvall-Bergstrom,基于压缩的方法).
• 其他相关功能:流程模块化,处理层次结构等.
• 提供R,C和Python
• 开源

我认为,社区检测最完整的工具.有关更多详细信息,还要检查:igraph中社区检测算法之间的区别是什么？

Answer 3

您可以尝试SNAP库(斯坦福大学网络分析平台,http://snap.stanford.edu/),其中包括模块化,格文-纽曼和Clauset纽曼-穆尔算法.它是用C++编写的,并且是BSD许可证.有很多论文使用它(参见http://snap.stanford.edu/papers.html),它应该是好的.