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

Community Detection Based on Minimum-Cut Graph Partitioning

作　　者：王亚珅 黄河燕[1] 冯冲[1] 

机构地区：[1]北京理工大学计算机学院北京市海量语言信息处理与云计算应用工程技术研究中心,北京100081

出　　处：《中文信息学报》2017年第3期213-222,共10页Journal of Chinese Information Processing

基　　金：国家高技术研究发展计划(863计划)(2015AA015404)

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

关 键 词：社区发现 模块度 最小割图分割 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]