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

在线社交网络社区发现算法是一系列能够在在线社交网络发现社区的算法。

在线社交网络1]的社区发现算法的思想是基于社交网络结构的拓扑结构，将网络划分成多个簇，簇内用户紧密连接，簇间用户连接稀疏。在计算机科学领域，该问题一般被称作图分割问题。Kernighan-Lin2是一种基于贪婪优化策略的算法，该算法通过定义一个目标收益函数，通过贪婪搜索的方式查找使得目标收益函数值最大的网络分割。谱平分法3从网络的拉普拉斯矩阵出发，通过研究该矩阵的特征值和特征向量从而达到对网络拓扑结构进行二分的目的，迭代使用该方法可以获取社区数目大于2的社区划分。GN4算法中，为了衡量网络社区结构划分的好坏，他们基于复杂网络和随机网络结构特征的比较，提出了模块度的概念，GN算法本质上讲是一种网络分裂算法，它通过自定义的边介数指标来标识社区之间的网络连边，通过迭代去除边介数最大的连边，从而将网络分裂为若干虚拟社区结构。针对某些需要细致刻画社区结构的应用，信息科学领域的专家也从信息论的角度出发，将网络拓扑结构映射为数据编码问题，通过构造编码长度最短的虚拟社区划分从而达到社区发现的目的。该类算法以Infomap5算法为代表，可以更高精度地发现网络社区，主要应用于需要精确分析社区结构的场合。针对网络拓扑结构中若干节点同时隶属于多个社区的现象，Gergely Palla6等在2005年提出了重叠社区概念，利用派系和团的定义去发现网络中的重叠社区和处于社区边界位置的桥节点。通过研究真实网络拓扑结构特性和假设的网络模型之间的差异，借用贝叶斯推断等数学工具，Mark Newman等人提出了基于概率模型的社区结构发现算法，通过最大化似然概率，实现重叠结构的社区的发现。以上算法更多地侧重于社团结构的精确度方面，较少考虑算法的时间复杂度，时间复杂度一般相对较高。就社交网络而言，上述方法只能适合于规模较小的社交网络中的虚拟社区发现。在现实情况下，也常需要分析具有规模大、节点信息种类繁多等特点的社交网络中的虚拟社区，如此就希望社区发现算法不但要具有较高准确度也需要具有较低的计算时间复杂度。同时考虑该两方面需求，学者们也从不同角度出发提出了一些新的社区发现算法，可适合于较准确较快速发现较大规模社交网络中的虚拟社区。从社区结构的局部结构特征出发，人们提出了基于局部扩展的社区发现算法。该类算法往往从一个或者几个网络核心节点出发，通过定义局部收益函数，采用贪婪策略将该节点周围的节点吸收入已存在的虚拟社区结构中。由于该类算法只利用了网络局部拓扑结构，因此可以在尚未构建全网拓扑结构图的情况下发现和分析用户关注区域的社区结构。为了提高网络社区发现的效率，Usha Nandini Raghavan7等人提出了一种基于标签传播的社区发现算法。该算法通过为每一个节点赋予唯一的标签，并按照节点邻居的多数标签迭代更新其自身的标签值，最终收敛到部分网络节点共享同一个标签的稳定状态，享有相同标签值的节点即为属于同一个社区的节点。该类算法可以在已知网络拓扑结构全貌的情况下，在线性时间内发现网络社区结构。

本词条内容贡献者为:

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