›› 2014, Vol. 23 ›› Issue (9): 98902-098902.doi: 10.1088/1674-1056/23/9/098902

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇    下一篇

Detecting community structure using label propagation with consensus weight in complex network

梁宗文a b, 李建平a, 杨帆a, Athina Petropulub   

  1. a School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China;
    b Electrical and Computer Engineering Department, Rutgers, The State University of New Jersey, NJ 08854, USA
  • 收稿日期:2014-01-13 修回日期:2014-03-26 出版日期:2014-09-15 发布日期:2014-09-15
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant No. 61370073) and the China Scholarship Council, China (Grant No. 201306070037).

Detecting community structure using label propagation with consensus weight in complex network

Liang Zong-Wen (梁宗文)a b, Li Jian-Ping (李建平)a, Yang Fan (杨帆)a, Athina Petropulub   

  1. a School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China;
    b Electrical and Computer Engineering Department, Rutgers, The State University of New Jersey, NJ 08854, USA
  • Received:2014-01-13 Revised:2014-03-26 Online:2014-09-15 Published:2014-09-15
  • Contact: Liang Zong-Wen E-mail:zongwen-liang@hotmail.com
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant No. 61370073) and the China Scholarship Council, China (Grant No. 201306070037).

PDF (PC)

1206

赞

摘要： Community detection is a fundamental work to analyse the structural and functional properties of complex networks. The label propagation algorithm (LPA) is a near linear time algorithm to find a good community structure. Despite various subsequent advances, an important issue of this algorithm has not yet been properly addressed. Random update orders within the algorithm severely hamper the stability of the identified community structure. In this paper, we executed the basic label propagation algorithm on networks multiple times, to obtain a set of consensus partitions. Based on these consensus partitions, we created a consensus weighted graph. In this consensus weighted graph, the weight value of the edge was the proportion value that the number of node pairs allocated in the same cluster was divided by the total number of partitions. Then, we introduced consensus weight to indicate the direction of label propagation. In label update steps, by computing the mixing value of consensus weight and label frequency, a node adopted the label which has the maximum mixing value instead of the most frequent one. For extending to different networks, we introduced a proportion parameter to adjust the proportion of consensus weight and label frequency in computing mixing value. Finally, we proposed an approach named the label propagation algorithm with consensus weight (LPAcw), and the experimental results showed that the LPAcw could enhance considerably both the stability and the accuracy of community partitions.

关键词: label propagation algorithm, community detection, consensus cluster, complex network

Abstract: Community detection is a fundamental work to analyse the structural and functional properties of complex networks. The label propagation algorithm (LPA) is a near linear time algorithm to find a good community structure. Despite various subsequent advances, an important issue of this algorithm has not yet been properly addressed. Random update orders within the algorithm severely hamper the stability of the identified community structure. In this paper, we executed the basic label propagation algorithm on networks multiple times, to obtain a set of consensus partitions. Based on these consensus partitions, we created a consensus weighted graph. In this consensus weighted graph, the weight value of the edge was the proportion value that the number of node pairs allocated in the same cluster was divided by the total number of partitions. Then, we introduced consensus weight to indicate the direction of label propagation. In label update steps, by computing the mixing value of consensus weight and label frequency, a node adopted the label which has the maximum mixing value instead of the most frequent one. For extending to different networks, we introduced a proportion parameter to adjust the proportion of consensus weight and label frequency in computing mixing value. Finally, we proposed an approach named the label propagation algorithm with consensus weight (LPAcw), and the experimental results showed that the LPAcw could enhance considerably both the stability and the accuracy of community partitions.

Key words: label propagation algorithm, community detection, consensus cluster, complex network

中图分类号:  (Structures and organization in complex systems)

  • 89.75.Fb
89.75.Hc (Networks and genealogical trees)