计算机应用 ›› 2014, Vol. 34 ›› Issue (3): 738-741.DOI: 10.11772/j.issn.1001-9081.2014.03.0738

• 人工智能 • 上一篇    下一篇

基于势函数的标签传播社区发现算法

石立新,张俊星   

  1. 大连民族学院 信息与通信工程学院，辽宁 大连116600
  • 收稿日期:2013-09-11 修回日期:2013-11-07 出版日期:2014-03-01 发布日期:2014-04-01
  • 通讯作者: 石立新
  • 作者简介:石立新（1967-），男，黑龙江哈尔滨人，副教授，硕士，主用研究方向：智能信息处理、数据挖掘；张俊星（1969-），男，山东东营人，教授，博士，主用研究方向：智能检测。
  • 基金资助:

    国家自然科学基金资助项目;中央高校自主基金资助项目

Label propagation algorithm based on potential function for community detection

SHI Lixin,ZHANG Junxing   

  1. College of Information and Communication Engineering, Dalian Nationalities University, Dalian Liaoning 116600, China
  • Received:2013-09-11 Revised:2013-11-07 Online:2014-03-01 Published:2014-04-01
  • Contact: SHI Lixin
  • Supported by:

    National Natural Science Foundation

PDF

摘要：

针对标签传播算法(LPA)存在大量随机性、算法稳定性差的问题，提出了基于数据场势函数的标签传播算法(LPAP)。该算法计算所有节点的势值，搜索势值极值点。初始化时仅赋予势值极值点以标签，迭代过程中根据邻接节点中相同标签节点势值之和更新标签，所有节点标签不再改变时迭代结束。实验结果表明：该算法得到的社区划分方式平均是LPA的4.0%，是平衡传播算法(BPA)的12.9%；信息变化参数平均是LPA的45.1%，是BPA的73.3%。具有更好的稳定性，适用于大型网络的社区发现。

关键词: 社区发现, 标签传播, 数据场, 势函数, 稳定性

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 average distinct community partition of LPAP is 4.0% of that of LPA, 12.9% of that of Balanced Propagation Algorithm (BPA), and the average 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 community detection in large network.

Key words: Community detection, label propagation algorithm, data field, potential function, robustness

中图分类号: 

版权所有 © 2021 四川计算机应用杂志社有限公司
蜀ICP备 05010208 号-3　新出网证(川)字026号
技术支持：北京玛格泰克科技发展有限公司
访问总数：
今日访问：