基于最小割图分割的社区发现算法

Community Detection Based on Minimum-Cut Graph Partitioning

该文证明了模块度最大化问题可以被转换成为原网络上的最小割图分割问题,并且基于该证明提出了一种高效的社区发现算法。同时,该文创新性地将模块度理论与当今比较流行的统计推理模型相结合:首先,这些统计推理模型被转化为模块度最大化问题中的零模型;其次,统计推理模型中的目标函数被修改并应用于本文的最优化算法中。实验结果显示,无论是在真实世界网络还是在人工生成网络中,该文提出的算法均具有高效和稳定的发现社区的能力。

This article demonstrated that modularity maximization issue could be transformed into minimum-cut graph partitioning problem, and proposed an efficient algorithm for detecting community structure. Meanwhile, we combined the modularity theory with popular statistical inference method in two aspects： （i） transforming such statistical model into null model in modularity maximization; （ii） adapting the objective function of statistical inference method for our optimization. The experiments we conducted show that the proposed algorithm is highly effective and stable in discovering community structure from both real-world networks and synthetic networks.