基于节点重要性排序的局部社区检测算法

摘要/Abstract

参考文献

多维度评价

doi:10.6040/j.issn.1672-3961.0.2023.266

摘要： 针对目前应用广泛的社区检测算法存在时间复杂性过高、精度低、结果不稳定等缺点,提出一种基于节点重要性排序的局部社区检测算法(local community detection algorithm based on the node importance ranking, LCDIR)。根据节点重要性顺序选择核心节点,通过节点强度和网络拓扑结构特征对网络进行社区检测形成初步社区,利用内外边比例和模块化度量最大化合并弱小社区,形成最终的社区。在真实网络和人工合成网络上和7种社区检测算法进行对比试验,结果表明,该算法在这些网络上形成了较高质量的社区,解决现有局部社区检测算法存在核心节点选择不当的问题,具有较高模块化度量值和标准化互信息值,相较于其他社区检测算法更准确有效、性能更好、时间复杂度较低。

关键词: 复杂网络, 社区检测, 节点重要性排序, 核心节点, 节点相似性

中图分类号:

O157.6

武凯丽,陈京荣. 基于节点重要性排序的局部社区检测算法[J]. 山东大学学报 (工学版), 2025, 55(1): 77-85.

WU Kaili, CHEN Jingrong. Local community detection algorithm based on the node importance ranking[J]. Journal of Shandong University(Engineering Science), 2025, 55(1): 77-85.

[1] MAZZA M, COLA G, TESCONI M. Modularity-based approach for tracking communities in dynamic social networks[J]. Knowledge-Based Systems, 2023, 281: 111067.
[2] LI W, WANG J, CAI J. New label propagation algorithms based on the law of universal gravitation for community detection[J]. Physica A: Statistical Mechanics and Its Applications, 2023, 627: 129140.
[3] CHENG S, YANG S, CHENG X, et al. An effective overlapping community merging method oriented to multidimensional attribute social networks[J]. Expert Systems, 2023, 40(10): 13433.
[4] RANI S, KUMAR M. Ranking community detection algorithms for complex social networks using multilayer network design approach[J]. International Journal of Web Information Systems, 2022, 18(5): 310-341.
[5] FANG C, LIN Z Z. Overlapping communities detection based on cluster-ability optimization[J]. Neuro-computing, 2022, 494:336-345.
[6] YOU X, MA Y, LIU Z. A three-stage algorithm on community detection in social networks[J]. Knowledge-Based Systems, 2020, 187(1):104822.
[7] 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.
[8] XU G Q, MENG L, TU D Q, et al. LCH: a local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks[J]. Chinese Physics B, 2021, 30(8): 566-574.
[9] ZHANG J, ZHANG G, YANG J, et al. Local community detection algorithm based on hierarchical clustering[J]. Journal of Information & Computational Science, 2015, 12(7): 2805-2813.
[10] AGHAALIZADEH S, AFSHORD S T, BOUYER A, et al. A three-stage algorithm for local community detection based on the high node importance ranking in social networks[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 563:125420.
[11] 杨旭华,沈敏. 基于特征向量局部相似性的社区检测算法[J]. 计算机科学, 2020, 47(2):56-64. YANG Xuhua, SHEN Min. Community detection algorithm based on local similarity of feature vectors[J]. Computer Science, 2020, 47(2): 56-64.
[12] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2008, 2008(3): 10008.
[13] BERGSTROM C T, ROSVALL M. Maps of random walks on complex networks reveal community structure [J]. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(4): 1118-1123.
[14] 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(9): 036106.
[15] LIU X, MURATA T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A: Statal Mechanics and its Applications, 2010, 389(7): 1493-1500.
[16] XING Y, MENG F, ZHOU Y, et al. A node influence based label propagation algorithm for community detection in networks[J]. The scientific world journal, 2014, 2014: 627581.
[17] XU X, YURUK N, FENG Z, et al. Scan: a structural clustering algorithm for networks[C] //Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA, Association for Computing Machinery, 2007: 824-833.
[18] HU F, LIU Y. A new algorithm CNM-Centrality of detecting communities based on node centrality[J].Physica A: Statistical Mechanics and Its Applications, 2016, 446:138-151.
[19] BERAHMAND K, BOUYER A, VASIGHI M. Community detection in complex networks by detecting and expanding core nodes through extended local similarity of nodes[J]. IEEE Transactions on Computational Social Systems, 2018, 5(4): 1021-1033.
[20] 蔡威林,葛斌.基于影响度的标签传播算法[J].佳木斯大学学报:自然科学版, 2022, 40(1):38-40. CAI Weilin, GE Bin. Label propagation algorithm based on influence degree[J]. Journal of Jiamusi University: Natural Science Edition, 2022, 40(1): 38-40.
[21] SORENSEN T. A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons[J]. Biologiske Skrifter, 1948, 5: 1-5.
[22] WU H, DONG S, RAO B. Latitudinal trends in the structure, similarity and beta diversity of plant communities invaded by Alternantheraphiloxeroides in heterogeneous habitats[J]. Frontiers in Plant Science, 2022, 13: 1021337.
[23] BOUYER A, SABAVAND MONFARED M, NOURANI E, et al. Discovering overlapping communities using a new diffusion approach based on core expanding and local depth traveling in social networks[J]. International Journal of General Systems, 2023, 52(8): 991-1019.
[24] WANG T,YIN L,WANG X. A community detection method based on local similarity and degree clustering information[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 490: 1344-1354.
[25] FORTUNATO S, HRIC D. Community detection in networks: a user guide[J]. Physics Reports, 2016, 659:1-44.
[26] GIRVAN M, NEWMAN M J. Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826.
[27] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. PhysicalReview E, 2004, 70(6): 066111.
[28] ZENG A, ZHANG C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14): 1031-1035.
[29] ZHANG X Z, ZHANG Y B, CHEN Z L, et al. Community extraction algorithm for large-scale online social networks[J].Journal of Northeastern University, 2015, 36(3): 342-345.
[30] YANG J, LESKOVEC J. Defining and evaluating network communities based on ground-truth[J].Knowledge & Information Systems, 2012, 42(1): 181-213.
[31] LI C, TANG Y, LIN H, et al. Parallel overlapping community detection algorithm in complex networks based on label propagation[J]. Scientia Sinica Informationis, 2016, 46(2): 212-227.

Just accepted

Online first

Just accepted

Online first

Viewed

Full text

	From	local

	Times	18
	Rate	100%

Abstract

Just accepted	Online first	Issue

0	0	68

From	Others	local

Times	67	1
Rate	99%	1%

Cited

Web of Science	Crossref	ScienceDirect	Search for Citations in Google Scholar >>


This page requires you have already subscribed to WoS.

Shared

Discussed