[科普中国]-在线社交网络社区发现

在线社交网络社区发现涵盖了多方面的内容，核心内容是挖掘出社交网络中存在的模块结构，外延内容包含了社交网络社区发现算法及评价指标。

在线社交网络社区发现涵盖了多方面的内容，包括在线社交网络表示模型、在线社交网络社区发现算法和在线社交网络社区发现评价指标等等内容。

从本质上讲，在线社交网络中的虚拟社区发现就是将网络节点按照其内在的拓扑结构连接紧密程度划分成若干子图的过程，在计算机科学领域，该问题一般被称作图分割问题。对于图分割问题的研究可以追溯到上世纪，其中两个最重要的算法即Kernighan-Lin算法1和谱平分法2。进入21世纪以来，随着复杂网络科学的发展，网络社区结构的发现问题获得了各领域专家的更多重视。Michelle Girvan和Mark Newman在2002年提出了一个新的分裂算法，即GN算法3。在该算法中，为了衡量网络社区结构划分的好坏，他们基于复杂网络和随机网络结构特征的比较，提出了模块度的概念，拉开了社区发现蓬勃发展的序幕。针对网络拓扑结构中若干节点同时隶属于多个社区的现象，Gergely Palla等在2005年提出了重叠社区概念，利用派系和团的定义去发现网络中的重叠社区和处于社区边界位置的桥节点4。通过研究真实网络拓扑结构特性和假设的网络模型之间的差异，借用贝叶斯推断等数学工具，Mark Newman等人提出了基于概率模型的社区结构发现算法，通过最大化似然概率，实现重叠结构的社区的发现。

本词条内容贡献者为:

吴斌 - 教授 - 北京邮电大学