本站原创摘 要 ：针对标签传播算法（LPA）存在大量随机性、算法稳定性差的问题,提出了基于数据场势函数的标签传播算法（LPAP）.该算法计算所有节点的势值,搜索势值极值点.初始化时仅赋予势值极值点以标签,迭代过程中根据邻接节点中相同标签节点势值之和更新标签,所有节点标签不再改变时迭代结束.实验结果表明：该算法得到的社区划分方式平均是LPA的4.0%,是平衡传播算法（BPA）的12.9%；信息变化参数平均是LPA的45.1%,是BPA的73.3%.具有更好的稳定性,适用于大型网络的社区发现.
关 键 词 ：社区发现；标签传播算法；数据场；势函数；稳定性
中图分类号： TP391.1； TP18
文献标志码：A
Abstract：
Because of randomness, the robustness of Label Propagation Algorithm （LPA） is severely hampered. To improve the robustness, a LPA based on potential function of data field （LPAP） was proposed. The potential of every node was calculated, and local extreme potential was searched. Only the node with extreme potential was labeled initially, and the label was updated according to the sum potential of its neighbors with equal label during iteration. When there were no nodes changing its label, iteration stopped. The experimental results show that the erage distinct munity partition of LPAP is 4.0% of that of LPA, 12.9% of that of Balanced Propagation Algorithm （BPA）, and the erage Variation of Information （VOI） of LPAP is 45.1% of that of LPA, 73.3% of that of BPA. LPAP is significantly more robust, and is suitable for munity detection in large work.
Key words： munity detection； Label Propagation Algorithm （LPA）； data field； potential function； robustness
0引言
现实网络不仅具有小世界和无标度等特性,还呈现明显的社区结构.社区结构在现实网络中发挥着重要作用,可以用来揭示社会网络中具有相同兴趣、爱好以及社会背景的社会团体,可以用来发现生物系统中功能相关的组织单元,可以用来提高万维网的搜索效率和准确性.因此,各种社区发现算法不断地被提了出来.典型的算法包括递归去除连接边的分裂算法[1]、重复地合并小部分的聚合算法[2-3]以及极值优化的模块度算法[4-7]等.
由于算法时间复杂度原因,只有少数算法适合大型现实网络.Raghan等[8]提出了标签传播算法（Label Propagation Algorithm, LPA）.初始时每个节点被赋予唯一的数字标签,迭代过程中选择邻接节点标签出现频率最高的标签来更新当前节点的标签.经过几次迭代,密集连接的节点拥有相同的标签,形成一个社区.近年来,标签传播算法又被不断地改进提高.Barber等[9]为了避免LPA中所有节点划分到同一社区,提出了一种模块化标签传播算法；Liu等[10]将模块化标签传播算法与多步贪婪凝聚算法融合,能够避免陷入局部极大值,更加准确识别社区；Leung等[11]采用启发式方法提高算法性能,通过简单参数调整使算法适应于不同规模网络.
尽管取得了一定的改进,LPA的一个重要问题还没有很好的解决.由于更新顺序是随机的、邻接节点标签频率相同时标签选择也是随机的,算法的鲁棒性受到严重损坏,社区结构的稳定性也就受到严重损伤.为了得到稳定的社区结构,Kato等[12]通过整合多种网络结构信息,降低不相干网络结构的重要性,来提高标签传播算法的稳定性.ubelj等[13]提出了一种平衡传播算法,利用节点的平衡因子来抵消LPA的随机性.上述算法中,权重因子与节点内在属性无关,无助于发现合理的网络社区.为了减少随机性,本文引入数据场势函数,以节点的势值这一内在属性作为权重因子,并根据势值之和更新标签.
2基于势函数的LPA
既然随机性严重破坏了算法的稳定性,就应该尽可能避免或减少随机性.如果按照预先定义好的顺序更新,算法稳定性明显得到提高.尽管没有哪一种顺序对所有网络都有效,不过对于某一网络确实存在一些可以得到正确而稳定的更新顺序[13].如果一个节点充当其社区的抽象中心,那么在该社区中只赋予该节点以初始标签即可,而其他节点在初始化阶段并不赋予标签.这种情况下,其他节点趋于从其靠近的抽象中心获取标签,最终加入该社区.
2.1势函数
数据场的基本思想来源于物理场的概念,用于描述空间数据之间的相互作用.空间数据通过向外辐射数据能量形成虚拟的数据场,数据场中某点的势定义为作用于该点所有能量之和.物理场通常分为长程场和短程场.重力场和静电场是长程场,势值与作用距离成反比.核子的中心势场是短程场,势值随着距离的增加而急剧下降.引入长程场描述网络节点之间的相互作用,算法的收敛性很差.因此,本文引入代表短程场的高斯势函数来计算数据场的幅值强度. LPAP得到的平均社区数显著少于LPA和BPA的,同时也避免了划分过小社区或过大社区.尽管DBLP子集存在着确定的社区结构,但却没有明确的社区划分方式.每次实验,节点划归的社区可能都不同,以100次实验里节点最可能的划归方式作为已知的社区划分,计算VOI.LPAP得到的VOI远小于LPA的,略小于BPA的,说明LPAP比LPA稳定得多,比BPA也稳定.比较两种算法的模块度Q,LPAP得到的Q值略高于LPA和BPA的,社区划分质量有一定的提高.另外,LPAP标签更新的迭代次数只有LPA的一半多.但由于势值估算也花费了相当的时间,LPAP只是略快于LPA.
4结语
由于LPA中存在大量的随机性,严重破坏了算法的鲁棒性,进而破坏了所识别的社区结构的稳定性.为了减少随机性的影响,提出了基于势函数的标签传播算法.该算法将势值极值点作为社区的抽象中心,并赋予初始标签,其他节点根据邻接节点中同一标签的势值之和更新标签.迭代过程中,虽然节点的选取是随机的,但标签的更新大致是有序的.节点标签的更新是依据势值之和,而非简单数量,较少出现相等的情况,也就降低了随机性.将LPAP应用到基准网络,社区划分方式稳定、集中,收敛快.应用到DBLP大型网络,社区划分的种类显著减少,Q值也有一定程度提升.可见,LPAP既保持了LPA简单快速适合大型网络的优点,又明显提升了算法的稳定性.