Community Detection Algorithm Based on Density Peak Clustering and Label Propagation

ZHANG Xiaohan; TANG Feiyi; GU Wenjing; CHANG Chao; MAO Chengjie

doi:10.6054/j.jscnun.2023007

Journal of South China Normal University (Natural Science Edition) > 2023 > 55(1): 78-87. > DOI: 10.6054/j.jscnun.2023007

ZHANG Xiaohan, TANG Feiyi, GU Wenjing, CHANG Chao, MAO Chengjie. Community Detection Algorithm Based on Density Peak Clustering and Label Propagation[J]. Journal of South China Normal University (Natural Science Edition), 2023, 55(1): 78-87. DOI: 10.6054/j.jscnun.2023007

Citation:

PDF (1221 KB)

Community Detection Algorithm Based on Density Peak Clustering and Label Propagation

ZHANG Xiaohan^{1, 2},
TANG Feiyi^{2, 3},
GU Wenjing^{1, 2},
CHANG Chao^{1, 2},
MAO Chengjie^1, ,

1.
School of Computer Science, South China Normal University, Guangzhou 510631, China
2.
Pazhou Lab, Guangzhou 510330, China
3.
School of Information Engineering, Guangzhou Panyu Polytechnic, Guangzhou 511483, China

More Information

Received Date: September 22, 2022
Available Online: April 11, 2023

Graphical Abstract

Abstract

Abstract

The goal of community detection is to discover the structure, behavior and organization of complex networks. Label propagation algorithm is a fast and effective community detection algorithm. However, in the classic label propagation algorithm, the structural and feature information of the node is not fully utilized, and the label pro-pagation process is unstable. To address the above problems, a community detection algorithm DPC-LPA based on improved density peak clustering algorithm and label propagation algorithm in directed weighted complex network is proposed. The algorithm firstly weights the nodes according to their structure and features, which makes full use of the structural and feature information. Then it uses an improved density peak clustering algorithm to find the community center of the network and constructs the initial community accordingly, which improves the quality of community division. And then, based on node similarity and node weights, the update order of label propagation is reasonably determined, and the strength of label propagation between nodes is measured to complete label propagation, which solves the problem of unstable label propagation algorithm. Finally, on CiteSeer, Cora, WebKB, and SCHOLAT real-world datasets, the DPC-LPA algorithm is compared with DCN, WCF-LPA, and CLPE algorithms. The experimental results prove the feasibility and effectiveness of the DPC-LPA algorithm: in terms of modu-larity, the communities divided by the DPC-LPA algorithm have a more significant community structure; in terms of Adjusted Rand Index, the community division quality of the DPC-LPA algorithm is more stable; in terms of running time, the DPC-LPA algorithm has higher efficiency.
- community detection,
- label propagation,
- density peak,
- node weighting,
- complex networks

FullText(HTML)

References (39)

References

[1]	NEWMAN M, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113/1-16.
[2]	FENG Y F, CHEN H M, LI T R, et al. A novel community detection method based on whale optimization algorithm with evolutionary population[J]. Applied Intelligence, 2020, 50(2): 2503-2522.
[3]	GUO K, HE L, CHEN Y Z, et al. A local community detection algorithm based on internal force between nodes[J]. Applied Intelligence, 2020, 50(2): 328-340. doi: 10.1007/s10489-019-01541-1
[4]	HUANG X, CHENG H, YU J X. Dense community detection in multi-valued attributed networks[J]. Information Sciences, 2015, 314: 77-99. doi: 10.1016/j.ins.2015.03.075
[5]	LI H J, ZHAN B, LI A, et al. Fast and accurate mining the community structure: integrating center locating and membership optimization[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(9): 2349-2362.
[6]	贺超波, 沈玉利, 余建辉, 等. 基于学术社区的科技论文推荐方法[J]. 华南师范大学学报(自然科学版), 2012, 44(3): 55-58. doi: 10.6054/j.jscnun.2012.06.012 HE C B, SHEN Y L, YU J H, et al. Method for scientific paper recommendation based on academic community[J]. Journal of South China Normal University (Natural Science Edition), 2012, 44(3): 55-58. doi: 10.6054/j.jscnun.2012.06.012
[7]	TANG Z K, TANG Y, LI C Y, et al. A fast local community detection algorithm in complex networks[J]. World Wide Web, 2021(6): 1929-1955.
[8]	GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2009, 12(10): 2011-2024.
[9]	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/1-11.
[10]	SHANG R H, ZHANG W T, JIAO L C. Circularly searching core nodes based label propagation algorithm for community detection[J]. International Journal of Pattern Reco- gnition and Artificial Intelligence, 2016, 30(8): 1659024/1-22.
[11]	LIU S C, ZHU F X, LIU H J, et al. A core leader based label propagation algorithm for community detection[J]. China Communications, 2016, 13(12): 97-106. doi: 10.1109/CC.2016.7897535
[12]	LIU W, JIANG X P, PELLEGRINI M, et al. Discovering communities in complex networks by edge label propagation[J]. Scientific Reports, 2016, 6(1): 1-10. doi: 10.1038/s41598-016-0001-8
[13]	LI C Y, TANG Y, TANG Z K, et al. Motif-based embedding label propagation algorithm for community detection[J]. International Journal of Intelligent Systems, 2022, 37(3): 1880-1902. doi: 10.1002/int.22759
[14]	TANG Z K, LI C Y, TANG Y. An efficient method based on label propagation for overlapping community detection[C]//Proceedings of 2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design. New York: IEEE, 2021: 168-173.
[15]	GUI Q, DENG R, XUE P F, et al. A community discovery algorithm based on boundary nodes and label propagation[J]. Pattern Recognition Letters, 2018, 109: 103-109. doi: 10.1016/j.patrec.2017.12.018
[16]	ZHOU K, MARTIN A, PAN Q, et al. SELP: Semi-supervised evidential label propagation algorithm for graph data clustering[J]. International Journal of Approximate Reasoning, 2018, 92: 139-154. doi: 10.1016/j.ijar.2017.09.008
[17]	XIE J, SZYMANSKI B K, LIU X. SLPA: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining Workshops. Piscataway: IEEE, 2011: 344-349.
[18]	SUN H L, HUANG J B, TIAN Y Q, et al. Detecting overlapping communities in networks via dominant label propa-gation[J]. Chinese Physics B, 2015, 24(1): 555-563.
[19]	LEI Y, ZHOU Y, SHI J. Overlapping communities detection of social network based on hybrid C-means clustering algorithm[J]. Sustainable Cities and Society, 2019, 47: 101436/1-8.
[20]	张晓琴, 安晓丹, 曹付元. 基于谱聚类的二分网络社区发现算法[J]. 计算机科学, 2019, 46(4): 216-221. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201904034.htm ZHANG X Q, AN X D, CAO F Y. Detecting community from bipartite network based on spectral clustering[J]. Computer Science, 2019, 46(4): 216-221. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201904034.htm
[21]	郭昆, 彭胜波, 陈羽中, 等. 基于密度聚类的增量动态社区发现算法[J]. 模式识别与人工智能, 2018, 31(11): 965-978. doi: 10.16451/j.cnki.issn1003-6059.201811001 GUO K, PENG S B, CHEN Y Z, et al. Incremental dyanamic community detection algorithm based on density clustering[J]. Pattern Recognition and Aritificial Intelligence, 2018, 31(11): 965-978. doi: 10.16451/j.cnki.issn1003-6059.201811001
[22]	RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344: 1492-1496. doi: 10.1126/science.1242072
[23]	BAI X Y, YANG P L, SHI X H. An overlapping community detection algorithm based on density peaks[J]. Neurocomputing, 2017, 226: 7-15. doi: 10.1016/j.neucom.2016.11.019
[24]	ZHANG W T, ZHANG R, SHANG R H, et al. Weighted compactness function based label propagation algorithm for community detection[J]. Physica A: Statistical Mechanics and its Applications, 2018, 492: 767-780. doi: 10.1016/j.physa.2017.11.006
[25]	DING J J, HE X X, YUAN J Q, et al. Community detection by propagating the label of center[J]. Physica A: Statistical Mechanics and its Applications, 2018, 503: 675-686. doi: 10.1016/j.physa.2018.02.174
[26]	JIANG H, LIU Z J, LIU C L, et al. Community detection in complex networks with an ambiguous structure using central node based link prediction[J]. Knowledge-Based Systems, 2020, 195(12): 105626/1-13.
[27]	ARAL S, WALKER D. Identifying influential and susceptible members of social networks[J]. Science, 2012, 337: 337-341. doi: 10.1126/science.1215842
[28]	AVRACHENKOV K, HOFSTAD R V D, SOKOL M. Personalized PageRank with node-dependent restart[C]//Algorithms and Models for the Web Graph. Cham: Sprin-ger, 2014: 23-33.
[29]	PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the web[R]. [S. l. : s. n.], 1999.
[30]	ZHANG X C, YU L F, ZHANG Y H. Multi-feature fusion for short text similarity calculation base on LDA[J]. Computer Science, 2018, 45(9): 266-270.
[31]	LUO J, WANG Q L, LI Y. Word clustering based on word2vec and semantic similarity[C]//Proceedings of 2014 33th IEEE Control Conference. Nanjing: IEEE, 2014: 517-521.
[32]	黄承慧, 印鉴, 侯昉. 一种结合词项语义信息和TF-IDF方法的文本相似度量方法[J]. 计算机学报, 2011, 34(5): 856-864. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201105010.htm HUANG C H, YIN J, HOU F. A text similarity measurement combining word semantic information with TF-IDF method[J]. Chinese Journal of Computers, 2011, 34(5): 856-864. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201105010.htm
[33]	CHENG Q, ZHONG L, HUANG J C, et al. Community detection in hypernetwork via Density-Ordered Tree partition[J]. Applied Mathematics & Computation, 2016, 276: 384-393.
[34]	GILES C L, BOLLACKER K D, LAWRENCE S. CiteSeer: An automatic citation indexing system[C]//Proceedings of the Third ACM Conference on Digital Libraries. New York: ACM, 1998: 89-98.
[35]	MCCALLUM A K, NIGAM K, RENNIE J, et al. Automating the construction of internet portals with machine learning[J]. Information Retrieval, 2000, 3: 127-163. doi: 10.1023/A:1009953814988
[36]	CRAVEN M, DIPASQUO D, FREITAG D, et al. Learning to construct knowledge bases from the World Wide Web[J]. Artificial Intelligence, 2000, 118(1/2): 69-113.
[37]	XU Q, QIU L J, LIN R H, et al. An improved community detection algorithm via fusing topology and attribute information[C]//Proceedings of 2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design. New York: IEEE, 2021: 1069-1074.
[38]	HUANG L, ZHU Y, GAO Y F, et al. Hybrid-order ano- maly detection on attributed networks[J/OL]. IEEE Transactions on Knowledge and Data Engineering, (2021-10-06)[2022-09-23]. https://ieeexplore.ieee.org/document/9560054.
[39]	HUBERT L, ARABIE P. Comparing partitions[J]. Journal of Classification, 1985, 2(1): 193-218. doi: 10.1007/BF01908075

Cited By

Cited by

Periodical cited type(4)

1.	葛月英，葛琦. 一类非线性混合分数阶微分方程系统解的稳定性. 延边大学学报(自然科学版). 2024(01): 1-12 .
2.	戴振祥，薛益民，彭钟琪. 非线性耦合分数阶微分方程组正解的存在性. 徐州工程学院学报(自然科学版). 2024(03): 72-81 .
3.	朱鹏程. Caputo型线性分数阶常微分方程的一种新的高阶数值方法. 科学技术创新. 2022(34): 35-39 .
4.	薛益民，戴振祥，刘洁. 一类分数阶微分方程耦合系统正解的多重性. 徐州工程学院学报(自然科学版). 2020(03): 59-63 .

Other cited types(0)

Get Citation

PDF

XML

Article views (188) PDF downloads (120) Cited by(4)

Turn off MathJax

Article Contents

Abstract

References

Community Detection Algorithm Based on Density Peak Clustering and Label Propagation

Abstract

References

Cited by

Periodical cited type(4)

Other cited types(0)

Catalog

Export File

Citation

Format

Content