王亚珅，黄河燕，冯 冲

(北京理工大学 计算机学院北京市海量语言信息处理与云计算应用工程技术研究中心，北京 100081)

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

王亚珅，黄河燕，冯 冲

(北京理工大学 计算机学院北京市海量语言信息处理与云计算应用工程技术研究中心，北京 100081)

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

社区发现；模块度；最小割图分割

1 引言

作为网络的一种常见属性，社区结构(community structure)是一种对网络节点的分割，其中，同一个社区中的节点联系紧密，而隶属于不同社区的节点之间联系则相对松散[1-2]，社区发现(community detection)已经在诸多领域体现出其应用价值[3-5]。为了解决社区发现问题，我们首先讨论社区(community)的定义，学界目前存在很多全局化的社区定义，这些定义均将社区结构视为整个网络的一个属性[6]。

(1) 最为直观的社区定义与连接不同社区边的数量(在有权网络中，则为连接边的加权和)有关，这个数量通常被称为割规模(cut size)，旨在最小化割规模的问题一般被称为“最小割图分割(minimum-cut graph partitioning)”问题。……