基于“邻域”结构洞的社团发现算法

沈文明　杜翠凤

【摘 要】为了解决传统社团发现算法仅考虑复杂网络的局部属性的问题，构建以移动用户之间的通话数据为基础的移动用户通信网络，通过采用“邻域”结构洞衡量用户之间的关系强度，利用模块度值寻找社团划分的最优“关系阈值”，提出了基于“邻域”结构洞的社团发现算法。经过实验证明，该算法具有一定的有效性和扩展性。

【关键词】复杂网络 社团结构 “邻域”结构洞 模块度值

1 引言

社团结构是描述社会网络具有一个共同的性质，即满足同一社团内部节点连接相对紧密、不同社团节点连接相对稀疏的特点[1]。目前社团发现的研究算法大致可以划分为图形分割和分级聚类两种。其中，图形分割的主要代表算法有：基于贪婪思想实现极小化簇间连接数目与簇内连接数目之差的Kernighan-Lin算法[2]；基于特征值的相似性实现社团划分的Laplace图特征值的谱平分算法[3]；基于边密度的CPM派系过滤算法[4]。分级聚类是根据网络中不同节点的连接强度实现社团的划分，该算法根据对网络的操作不同分为两种：分裂算法的典型代表是GN算法，通过删除网络中介数大的边获得社团结构；凝聚算法的典型代表是Newman快速算法，其思想是从空网络开始，逐步添加相似性的边，同时在计算相似性时通过模块度来标示社团分割的质量[5]。上述的社团发现算法仅仅考虑复杂网络的局部属性，如考虑节点自身的信息以及其邻居的信息而忽略邻居的邻域信息，会对节点与邻居的连接强度产生大的影响，因此本文提出了基于“邻域”结构洞的社团发现算法。该算法是利用节点以及其邻居的“邻域”结构洞来评价节点与邻居的关系强度，同时采用模块度值挖掘社团划分的最优“关系阈值”，实现在特定数据下大幅度提高社团划分的效率和精度。

2 复杂网络中的社团发现

2.1 社团结构的定义

在绝大多数的研究中，社团的定义是从功能角度上给出的，研究者们利用网络节点的拓扑结构试图找出社团的功能模块，并从拓扑结构给出了社团的定义，即：社团是一组内部连接紧密但与组外其他节点连接稀疏的节点的集合[6]。但是，高度重叠的社团违背了上述定义，因此Ahn于2010年将社团定义为一组紧密相关的链接，让节点继承与之相连接的社团的隶属关系，从划分链接的角度来解释复杂网络的重叠结构。

本文在参考Ahn划分社团思路的基础上，通过评价节点间的关系强度，采用模块度值作为寻找关系强度的最优“阈值”，在提升同类别数据社团划分效率的同时也符合复杂网络重叠社团划分的原则。

2.2 社团结构的应用场景

社团结构划分具有多个应用场景：通过社团发现获取道路网络的社团结构，可以更直观地展现每个区域的道路分布情况、道路密集区域和道路稀疏区域的具体分布；通过社团发现获取不同消费类型的用户社团结构，有利于运营商根据不同用户的消费水平进行有区别的市场推广；通过社团发现算法挖掘金融欺诈分子的社团结构，提高了反欺诈的识别率，从而保护了国家财产的安全，等等。

2.3 社团结构的评价

如何判断一个社团发现算法划分的社团结构好坏，一般可由以下指标来衡量：

（1）标准互信息是需要事先知道真实社团划分的结构，当社团发现算法得到的社团划分结构与真实社团划分结构越接近时，它们之间的标准互信息就越接近1，该值的取值范围为0至1。

（2）模块度是当前社团发现领域最认可的评价社团结构好坏的指标，它表示社团划分后社团内部的紧凑程度，当社团越紧凑时，模块度的取值就越接近1。当然，模块度的取值与社团划分的精度没有必然的关系。

（3）社团划分精度与标准互信息类似，需要事先知道真实社团划分的结构。它等于正确划分的节点个数与节点总数的占比。

2.4 基于“邻域”结构洞的用户关系评价

（1）结构洞理论

结构洞是学者Burt在研究社会网络的竞争关系时提出的经典社会学理论[7]。结构洞是指非冗余联系人之间存在的缺口，一旦结构洞存在，那么结构洞两边的联系人可以带来累加而非重叠的网络收益。结构洞示意图如图1所示：

从图1可知，节点A和节点B存在结构洞，而充当联系角色的中间人“E”获得了更多的网络收益，因为节点A和节点B之间的信息传播必须由中间人“E”来完成，所以在该网络中，中间人“E”的重要性大于其他节点。

（2）基于结构洞理论的节点重要性评价

在进行节点重要性评价之前，本文通过节点的度选取种子节点，因为只有选取种子节点后，结构洞的评价系数才能为社团发现带来实质的价值。节点重要性评价的计算示意图如图2所示：

从图2可知，I作为网络中度数最多的节点，本文将以I为种子节点，计算它与各节点的关系，以便划分以I为中心的社团。根据Burt对网络节点形成的结构洞的约束系数定义，CIA表示评价节点I和节点A之间的紧密程度，节点I的邻居数量为Г（I）={A， B， C， D， E， F， G， H}，pij表示节点i为维持节点j的邻居关系所投入的精力与总精力之比，piq、pqj分别表示节点i和节点j与共同邻居q维持关系投入的精力与总精力之比。

但是，上述公式仅仅衡量了节点与最邻近节点的紧密度关系，没有进一步考虑邻居节点与其他节点相连的拓扑结构会对该节点的影响程度，比如存在一些重要的“桥接”节点，那么作为种子节点，I很可能为了维持自身的地位，需要向“桥接”节点投入更多的“精力”，才能维持社团的稳定性。

（3）基于“邻域”结构洞理论的节點重要性评价[8]

根据上述约束系数的计算公式，CIF=CIG=

[1/8+（1/8）×（1/3）]2。那么，对于种子节点I来说，节点F与节点G对节点I来说同等重要。但是从图2得知，与G点相连的邻居以及邻居的拓扑结构使得I必须对G付出更多的“精力”才能稳定社团的结构，而上述约束系数无法体现这一点，因此需要改进该约束系数，可通过“邻域”结构洞约束系数来体现这一点。endprint

节点I与邻居节点的关系仍用公式（2）表示，则在新的约束系数定义下，CIF=[12/71+（14/71）×（12/44）]2，CIG=[15/71+（14/71）×（15/44）]2。很明显，节点I在一定精力的情况下，向G投入的“精力”比F更多，该约束系数在一定程度上更加真实地反映了节点与节点的紧密关系。

3 基于“邻域”结构洞的社团发现算法

3.1 算法的思路

基于“邻域”结构洞的社团发现算法的基本思路如下：

（1）根据前面改进的“邻域”结构洞约束系数得到节点与节点的关系评价值，粗略划分社团。

（2）针对上一步划分的结果，同时采用模块度值寻找关系强度的最优“阈值”，对数据进一步优化，从而对社团进行更精准的划分。

3.2 粗略划分社团

根据图3可知，每次设定的关系阈值θ都会输出一些不确定数量的社团数，由于社团的大小受到关系阈值的影响，如果关系阈值设置较大，则输出的社团个数较多，社团相对较小；相反，则输出的社团个数较少，社团相对较大。那么，如何确定关系阈值以便更好地进行社团划分，本文将通过模块度值来衡量不同的阈值划分社团的质量情况。

3.3 采用模块度值寻找最优“阈值”

模块度是评价一个社区划分好坏的度量方法，它是指社区内节点连边数与随机情况下的边数之差。首先把网络上每个节点看成独立的节点，并随机选取一个节点作为开始节点；然后采用每次并入一个节点的方式来计算两个并入节点的社区模块度值；最后根据模块度增加值的大小来决定该节点是否适合并入该社区。每个阈值下社区划分的模块度值计算公式为：

其中，Q为模块度值；Aij为节点i和节点j之间边的个数；ki、kj分别为节点i和节点j的度；m为拓扑结构图的总边数；δ（i， j）表示当社区划分结果中节点i和节点j属于同一社区时，则δ（i， j）=1，当社区划分结果中节点i和节点j不属于同一社区时，则δ（i， j）=0。

关系阈值θ的设定由数据集模块度值分布现状决定，也就是每个阈值都需要计算一个对应的模块度值，然后选取最大的模块度值对应的关系值作为阈值。根据约束系数的定义可知，关系阈值取值为0到1，因此本文在设定关系阈值的过程中，让θ从0到1，步长为0.005，逐渐增大，计算201个θ值对应的模块度，根据模块度值的变化来确定θ的取值范围。

上述改进能够适应移动运营商不同消费类型的用户社团划分，满足移动运营商的用户信息具有动态性和多样化的特点，利用该方法进行社区划分有利于运营商进行市场推广。

3.4 实验及结果分析

本次实验的数据来源是某地市3个村960名移动用户的通话数据，按照用户是否有通话关系分别建立三个无向通信网络，如果用户i和j之间有联系，那么i和j之间有边相连；否则，无边相连。

图4分别反映了三个网络数据集中关系阈值θ与社团划分模块度值的对应关系。

从图4可知，第一个数据集的最优关系阈值为0.060；第二个数据集的最优关系阈值为0.065；第三个数据集的最优关系阈值为0.055。对图形进一步分析可知，阈值是先单调递增后單调递减，最优的关系阈值出现在拐点位置，因此本文把阈值区间定为[0.055， 0.070]。

本文基于上述三个真实的社会网络进行社团发现的实验，通过对比这三个社会网络真实的社团划分情况，给出了实验划分结果的准确率对比，如图5所示。

从图5可知，除了第三个数据集的准确率较低外，其余数据集的准确率均达到95%以上，并且网络节点的数量与社团划分的准确率没有必然的联系。

4 结束语

本文基于真实的用户通信数据和所建立通信网络的拓扑结构，提出了基于“邻域”结构洞的社团发现算法，首先通过节点的度提取种子节点，然后采用改进的“邻域”结构洞约束系数计算节点与邻居的关系强度，最后通过采用模块度值确定社团划分的最优“关系阈值”。实验证明，基于“邻域”结构洞的社团发现算法具有较高精度。本文的方法仅适用于特定数量的网络节点，未来的研究将会针对特大型网络的社团发现算法进行优化，采用启发式算法进一步提升社团发现的效率和精度。

参考文献：

[1] M Girvan， M E J Newman. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America， 2002，99（12）： 7821-7826.

[2] Kernighan B W， Lin S. An Efficient Heuristic Procedure for Partitioning Graphs[J]. Bell System Technical Journal， 2014，49（2）： 291-307.

[3] A Pothen， H D Simon， K P Liou. Partitioning Sparse Matrices with Eigenvectors of Graphs[J]. SIAM Journal on Matrix Analysis and Applications， 1990，11（3）： 430-452.

[4] G Palla， I J Farkas， P Pollner， et al. Directed network modules[J]. New Journal of Physics， 2007，9（6）： 186-207.

[5] 张洋洋. 复杂网络中社团结构发现算法的研究与实现[D]. 南京： 南京理工大学， 2014.

[6] 何东晓. 复杂网络社团结构发现方法研究[D]. 长春： 吉林大学， 2014.

[7] Burt R S. Structural Holes： The Social Structure of Competition[M]. Boston： Harvard University Press， 1993.

[8] 苏晓萍，宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点[J]. 物理学报， 2015，64（2）： 1-11.

[9] 许鸿. 基于邻居相似性和半监督社团检测算法研究[D]. 兰州： 兰州大学， 2014.

[10] 华烨. 基于相对关系亲密度的局部社团发现算法研究[D]. 合肥： 中国科学技术大学， 2014.endprint