Two-stage community detection algorithm based on label propagation

Xueliang SUN; Wei WANG; Junheng HUANG; Guodong XIN; Bailing WANG

doi:10.11959/j.issn.2096-109x.2021099

您当前的位置：

首页 >

文章列表页 >

Two-stage community detection algorithm based on label propagation

Papers | 更新时间：2024-06-03

- Two-stage community detection algorithm based on label propagation
- Chinese Journal of Network and Information Security Vol. 8, Issue 2, Pages: 139-149(2022)
- 作者机构：
  
  1. 哈尔滨工业大学计算学部，黑龙江哈尔滨 150001
  2. 哈尔滨工业大学（威海）计算机科学与技术学院，山东威海 264209
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2021099
  CLC： TP311
- Online First：2022-04，
  
  Published：15 April 2022
- 稿件说明：
移动端阅览
Xueliang SUN, Wei WANG, Junheng HUANG, et al. Two-stage community detection algorithm based on label propagation[J]. Chinese Journal of Network and Information Security, 2022, 8(2): 139-149.
DOI：

Xueliang SUN, Wei WANG, Junheng HUANG, et al. Two-stage community detection algorithm based on label propagation[J]. Chinese Journal of Network and Information Security, 2022, 8(2): 139-149. DOI： 10.11959/j.issn.2096-109x.2021099.

摘要

社区检测是复杂网络分析的重要研究任务之一，其检测结果有助于人们深入理解复杂网络的社区结构，同时为下游任务提供支持，如内容推荐、链路检测等。针对复杂网络的社区检测问题，提出了一种基于标签传播的两阶段社区检测算法—— TS-LPA。TS-LPA采用扩展邻域的思想来量化节点的传播能力，并在此基础上，利用节点信息和网络中边的权重等信息，提出了新的评价指标来衡量节点的中心性和节点之间的影响力。所提算法在计算节点中心性的基础上确定了节点标签更新的顺序和种子节点的选择策略，消除了算法在更新过程中的不稳定。在节点标签更新的过程中，为了更好地利用邻居节点标签类别来进行标签更新，TS-LPA 采用广度优先传播的思想，提出了第二阶段标签传播方式。当标签开始传播的时候，待更新节点的所有邻居节点都对该节点的类别标签产生影响，同时，为了减轻周围邻居节点对待更新节点的支配程度，除邻居节点的影响外，加入附近种子节点对待更新节点的影响，共同完成节点的标签更新。在不同的真实数据集和人工合成数据集的实验结果分析表明，TS-LPA 在消除随机性、表现出较强稳定性的同时，有效提高了社区检测的质量。

Abstract

Community detection is an important research topic of complex network analysis.The detection results help to understand the community structure of complex networks and provide support for downstream tasks

such as content recommendation

link detection.Considering the challenge of community detection in complex networks

a two-stage community detection algorithm based on label propagation (TS-LPA) was proposed.The TS-LPA algorithm quantified the propagation capability of nodes based on the extended neighborhood.Then a new evaluation index was proposed to measure the probability of influence between nodes using the information of nodes and the weight of edges in the network.Based on the calculation of node centrality

the algorithm determined the updating sequence of node labels and the selection strategy of seed nodes

which eliminated the instability of the algorithm in the updating process.The TS-LPA algorithm used the breadth-first propagation idea and introduced the second-stage label propagation method to improve the quality of community detection.When label began to spread

all neighboring nodes had an influence on the label of the related node.Meanwhile

the influence of neighboring seed nodes was added to complete label updating

in order to reduce the dominance of neighboring nodes on the updated node.The experimental results of different real data sets and synthetic data sets show that TS-LPA algorithm can eliminate randomness and show strong stability while effectively improving the quality of community detection.

关键词

Keywords

references

SOURAVLAS S , SIFALERAS A , TSINTOGIANNI M , et al . A classification of community detection methods in social networks:a survey [J ] . International Journal of General Systems , 2021 , 50 ( 1 ): 63 - 91 .

RAGHAVAN U N , ALBERT R , KUMARA S . Near linear time algorithm to detect community structures in large-scale networks [J ] . Physical Review E , 2007 , 76 ( 3 ): 036106 .

GARZA S E , SCHAEFFER S E . Community detection with the label propagation algorithm:a survey [J ] . Physica A:Statistical Mechanics and Its Applications , 2019 ,534:122058.

PRAT-PÉREZ A , DOMINGUEZ-SAL D , BRUNAT J M , et al . Shaping communities out of triangles [C ] // Proceedings of the 21st ACM International Conference on Information and Knowledge Management . 2012 : 1677 - 1681 .

QIAO S J , HAN N , GAO Y J , et al . A fast parallel community discovery model on complex networks through approximate optimization [J ] . IEEE Transactions on Knowledge and Data Engineering , 2018 , 30 ( 9 ): 1638 - 1651 .

CHUNAEV P . Community detection in node-attributed social networks:a survey [J ] . Computer Science Review , 2020 ( 37 ): 100286 .

CAO J , BU Z , GAO G L , et al . Weighted modularity optimization for crisp and fuzzy community detection in large-scale networks [J ] . Physica A:Statistical Mechanics and Its Applications , 2016 ( 462 ): 386 - 395 .

WEIR W H , EMMONS S , GIBSON R , et al . Post-processing partitions to identify domains of modularity optimization [J ] . Algorithms , 2017 , 10 ( 3 ): 93 .

LEE J , GROSS S P , LEE J . Modularity optimization by conformational space annealing [J ] . Physical Review E , 2012 , 85 ( 5 ): 056702 .

NEWMAN M E J . Community detection in networks:modularity optimization and maximum likelihood are equivalent [J ] . arXiv preprint arXiv:1606.02319 , 2016 .

CLAUSET A , NEWMAN M E J , MOORE C . Finding community structure in very large networks [J ] . Physical Review E,Statistical,Nonlinear,and Soft Matter Physics , 2004 , 70 ( 6 ): 066111 .

BLONDEL V D , GUILLAUME J L , LAMBIOTTE R , et al . Fast unfolding of communities in large networks [J ] . Journal of Statistical Mechanics:Theory and Experiment , 2008 , 2008 ( 10 ): P10008 .

BERAHMAND K , BOUYER A . A link-based similarity for improving community detection based on label propagation algorithm [J ] . Journal of Systems Science and Complexity , 2019 , 32 ( 3 ): 737 - 758 .

GDRZA S E , SCHAEFFER S E . Community detection with the Label Propagation Algorithm [J ] . Physica A , 2019 , 534 ( 15 ): 122058 .

郑文萍 , 车晨浩 , 钱宇华 , 等 . 一种基于标签传播的两阶段社区发现算法 [J ] . 计算机研究与发展 , 2018 , 55 ( 9 ): 1959 - 1971 .

ZHENG W P , CHE C H , QIAN Y H , et al . A two-stage community detection algorithm based on label propagation [J ] . Journal of Computer Research and Development , 2018 , 55 ( 9 ): 1959 - 1971 .

CHEN N Y , LIU Y , CHEN H Q , et al . Detecting communities in social networks using label propagation with information entropy [J ] . Physica A:Statistical Mechanics and Its Applications , 2017 , 471 : 788 - 798 .

於志勇 , 陈基杰 , 郭昆 , 等 . 基于影响力与种子扩展的重叠社区发现 [J ] . 电子学报 , 2019 , 47 ( 1 ): 153 - 160 .

YU Z Y , CHEN J J , GUO K , et al . Overlapping community detection based on influence and seeds extension [J ] . Acta Electronica Sinica , 2019 , 47 ( 1 ): 153 - 160 .

ZHOU H H . Research on community detection algorithm based on a small number of selected point [D ] . Lanzhou:Lanzhou University , 2015 .

BARBER M J , CLARK J W . Detecting network communities by propagating labels under constraints [J ] . Physical Review E,Statistical,Nonlinear,and Soft Matter Physics , 2009 , 80 ( 2 ): 026129 .

LIU X , MURATA T . Advanced modularity-specialized label propagation algorithm for detecting communities in networks [J ] . Physica A:Statistical Mechanics and Its Applications , 2010 , 389 ( 7 ): 1493 - 1500 .

LI X . Directed LPA:propagating labels in directed networks [J ] . Physics Letters A , 2019 , 383 ( 8 ): 732 - 737 .

ZHANG X K , REN J , SONG C , et al . Label propagation algorithm for community detection based on node importance and label influence [J ] . Physics Letters A , 2017 , 381 ( 33 ): 2691 - 2698 .

WU T , GUO Y X , CHEN L T , et al . Integrated structure investigation in complex networks by label propagation [J ] . Physica A:Statistical Mechanics and Its Applications , 2016 , 448 : 68 - 80 .

DANON L , DÍAZ-GUILERA A , DUCH J , et al . Comparing community structure identification [J ] . Journal of Statistical Mechanics:Theory and Experiment , 2005 , 2005 ( 9 ): P09008 .

马秀 . 基于节点影响力的标签传播算法的稳定性研究 [D ] . 太原:中北大学 , 2019 .

MA X . Stability study of tag propagation algorithm based on node influence [D ] . Taiyuan:North University of China , 2019 .

WEI F F , YAN S J , YAN S K . Research on semi-supervised comm-unity discovery algorithm based on label propagation [J ] . Software Guide , 2019 ( 7 ): 92 - 95 .

Views

313

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰