Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (11): 3396-3402.DOI: 10.11772/j.issn.1001-9081.2023101536
• Data science and technology • Previous Articles Next Articles
Shiliang LIU, Yi WANG, Yinglong MA()
Received:
2023-11-10
Revised:
2024-01-11
Accepted:
2024-01-19
Online:
2024-01-01
Published:
2024-11-10
Contact:
Yinglong MA
About author:
LIU Shiliang, born in 1998, M. S. candidate. His research interests include community detection.Supported by:
通讯作者:
马应龙
作者简介:
刘世梁(1998—),男,甘肃武威人,硕士研究生,主要研究方向:社区检测基金资助:
CLC Number:
Shiliang LIU, Yi WANG, Yinglong MA. Non-overlapping community detection with imbalanced community sizes[J]. Journal of Computer Applications, 2024, 44(11): 3396-3402.
刘世梁, 王义, 马应龙. 考虑社区规模不平衡的非重叠社区检测[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3396-3402.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2023101536
真实世界网络 | 节点数 | 边数 | 真实社区数 |
---|---|---|---|
Karate Club | 34 | 78 | 2 |
Dolphins | 62 | 159 | 2 |
Plobooks | 105 | 441 | 3 |
Football | 115 | 613 | 12 |
1 005 | 25 571 | 42 | |
Polblogs | 1 490 | 19 025 | 2 |
DBLP | 317 080 | 1 049 866 | 13 477 |
YouTube | 1 134 890 | 2 987 624 | 78 385 |
Tab. 1 Information of real-world networks
真实世界网络 | 节点数 | 边数 | 真实社区数 |
---|---|---|---|
Karate Club | 34 | 78 | 2 |
Dolphins | 62 | 159 | 2 |
Plobooks | 105 | 441 | 3 |
Football | 115 | 613 | 12 |
1 005 | 25 571 | 42 | |
Polblogs | 1 490 | 19 025 | 2 |
DBLP | 317 080 | 1 049 866 | 13 477 |
YouTube | 1 134 890 | 2 987 624 | 78 385 |
网络 | N/103 | AvgK | MaxK | MinC | MaxC | |
---|---|---|---|---|---|---|
LFR1 | 1 | 7 | 30 | 10 | 30 | [0.1,0.8] |
LFR2 | 5 | 10 | 30 | 10 | 50 | [0.1,0.8] |
LFR3 | 10 | 10 | 50 | 10 | 50 | [0.1,0.8] |
LFR4 | 50 | 15 | 50 | 10 | 100 | [0.1,0.8] |
Tab. 2 Information of LFR networks
网络 | N/103 | AvgK | MaxK | MinC | MaxC | |
---|---|---|---|---|---|---|
LFR1 | 1 | 7 | 30 | 10 | 30 | [0.1,0.8] |
LFR2 | 5 | 10 | 30 | 10 | 50 | [0.1,0.8] |
LFR3 | 10 | 10 | 50 | 10 | 50 | [0.1,0.8] |
LFR4 | 50 | 15 | 50 | 10 | 100 | [0.1,0.8] |
网络 | LPA | Infomap | Louvain | Leiden | LGIEM | LBLD | LEICS |
---|---|---|---|---|---|---|---|
Karate Club | 0.68 | 0.64 | 0.68 | 0.69 | 1.00 | 1.00 | 1.00 |
Dolphins | 0.67 | 0.40 | 0.47 | 0.55 | 0.89 | 1.00 | 1.00 |
Polbooks | 0.44 | 0.39 | 0.56 | 0.52 | 0.57 | 0.60 | 0.67 |
Football | 0.85 | 0.79 | 0.82 | 0.89 | 0.65 | 0.91 | 0.92 |
E‑mail | 0.09 | 0.53 | 0.63 | 0.59 | 0.51 | 0.03 | 0.33 |
Polblogs | 0.02 | 0.28 | 0.67 | 0.64 | 0.03 | 0.02 | 0.72 |
DBLP | 0.48 | 0.58 | 0.16 | 0.18 | 0.48 | 0.74 | 0.55 |
YouTube | — | 0.48 | — | 0.22 | — | 0.55 | 0.61 |
Tab. 3 NMI comparison on real-world networks
网络 | LPA | Infomap | Louvain | Leiden | LGIEM | LBLD | LEICS |
---|---|---|---|---|---|---|---|
Karate Club | 0.68 | 0.64 | 0.68 | 0.69 | 1.00 | 1.00 | 1.00 |
Dolphins | 0.67 | 0.40 | 0.47 | 0.55 | 0.89 | 1.00 | 1.00 |
Polbooks | 0.44 | 0.39 | 0.56 | 0.52 | 0.57 | 0.60 | 0.67 |
Football | 0.85 | 0.79 | 0.82 | 0.89 | 0.65 | 0.91 | 0.92 |
E‑mail | 0.09 | 0.53 | 0.63 | 0.59 | 0.51 | 0.03 | 0.33 |
Polblogs | 0.02 | 0.28 | 0.67 | 0.64 | 0.03 | 0.02 | 0.72 |
DBLP | 0.48 | 0.58 | 0.16 | 0.18 | 0.48 | 0.74 | 0.55 |
YouTube | — | 0.48 | — | 0.22 | — | 0.55 | 0.61 |
网络 | LPA | Infomap | Louvain | Leiden | LGIEM | LBLD | LEICS |
---|---|---|---|---|---|---|---|
Karate Club | 0.69 | 0.48 | 0.65 | 0.54 | 1.00 | 1.00 | 1.00 |
Dolphins | 0.59 | 0.22 | 0.32 | 0.38 | 0.92 | 1.00 | 1.00 |
Polbooks | 0.51 | 0.30 | 0.63 | 0.54 | 0.64 | 0.67 | 0.73 |
Football | 0.66 | 0.63 | 0.62 | 0.81 | 0.47 | 0.85 | 0.88 |
0.01 | 0.09 | 0.41 | 0.34 | 0.23 | 0.02 | 0.05 | |
Polblogs | 0.01 | 0.28 | 0.78 | 0.77 | 0.01 | 0.01 | 0.81 |
DBLP | 0.02 | 0.01 | 0.01 | 0.01 | 0.01 | 0.02 | 0.01 |
YouTube | — | 0.01 | — | 0.01 | — | 0.01 | 0.02 |
Tab.4 ARI comparison on real-world networks
网络 | LPA | Infomap | Louvain | Leiden | LGIEM | LBLD | LEICS |
---|---|---|---|---|---|---|---|
Karate Club | 0.69 | 0.48 | 0.65 | 0.54 | 1.00 | 1.00 | 1.00 |
Dolphins | 0.59 | 0.22 | 0.32 | 0.38 | 0.92 | 1.00 | 1.00 |
Polbooks | 0.51 | 0.30 | 0.63 | 0.54 | 0.64 | 0.67 | 0.73 |
Football | 0.66 | 0.63 | 0.62 | 0.81 | 0.47 | 0.85 | 0.88 |
0.01 | 0.09 | 0.41 | 0.34 | 0.23 | 0.02 | 0.05 | |
Polblogs | 0.01 | 0.28 | 0.78 | 0.77 | 0.01 | 0.01 | 0.81 |
DBLP | 0.02 | 0.01 | 0.01 | 0.01 | 0.01 | 0.02 | 0.01 |
YouTube | — | 0.01 | — | 0.01 | — | 0.01 | 0.02 |
网络 | LPA | Infomap | Louvain | Leiden | LGIEM | LBLD | LEICS |
---|---|---|---|---|---|---|---|
Karate Club | 0.35 | 0.39 | 0.39 | 0.42 | 0.37 | 0.37 | 0.37 |
Dolphins | 0.47 | 0.40 | 0.51 | 0.53 | 0.49 | 0.38 | 0.38 |
Polbooks | 0.39 | 0.42 | 0.52 | 0.53 | 0.57 | 0.46 | 0.44 |
Football | 0.58 | 0.49 | 0.60 | 0.61 | 0.56 | 0.58 | 0.60 |
0.06 | 0.20 | 0.40 | 0.42 | 0.28 | 0.02 | 0.13 | |
Polblogs | 0.01 | 0.30 | 0.42 | 0.43 | 0.01 | 0.01 | 0.42 |
DBLP | 0.71 | 0.68 | 0.81 | 0.83 | 0.58 | 0.70 | 0.63 |
YouTube | — | 0.48 | — | 0.73 | — | 0.01 | 0.42 |
Tab.5 Q comparison in real-world networks
网络 | LPA | Infomap | Louvain | Leiden | LGIEM | LBLD | LEICS |
---|---|---|---|---|---|---|---|
Karate Club | 0.35 | 0.39 | 0.39 | 0.42 | 0.37 | 0.37 | 0.37 |
Dolphins | 0.47 | 0.40 | 0.51 | 0.53 | 0.49 | 0.38 | 0.38 |
Polbooks | 0.39 | 0.42 | 0.52 | 0.53 | 0.57 | 0.46 | 0.44 |
Football | 0.58 | 0.49 | 0.60 | 0.61 | 0.56 | 0.58 | 0.60 |
0.06 | 0.20 | 0.40 | 0.42 | 0.28 | 0.02 | 0.13 | |
Polblogs | 0.01 | 0.30 | 0.42 | 0.43 | 0.01 | 0.01 | 0.42 |
DBLP | 0.71 | 0.68 | 0.81 | 0.83 | 0.58 | 0.70 | 0.63 |
YouTube | — | 0.48 | — | 0.73 | — | 0.01 | 0.42 |
1 | GIRVAN M, NEWMAN M E 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. |
2 | LIU L, XU L, WANG Z, et al. Community detection based on structure and content: a content propagation perspective[C]// Proceedings of the 2015 IEEE International Conference on Data Mining. Piscataway: IEEE, 2015: 271-280. |
3 | LI Z, LIU A, MIAO J, et al. A three-phase method for spherical fuzzy environment and application to community epidemic prevention management[J]. Expert Systems with Applications, 2023, 211: No.118601. |
4 | 林欣蕊,王晓菲,朱焱. 基于局部扩展社区发现的学术异常引用群体检测[J]. 计算机应用, 2024, 44(6): 1855-1861. |
LIN X R, WANG X F, ZHU Y. Academic abnormal citation group detection based on local extended community detection[J]. Journal of Computer Applications, 2024, 44(6): 1855-1861. | |
5 | SANGAIAH A K, REZAEI S, JAVADPOUR A, et al. Explainable AI in big data intelligence of community detection for digitalization e-healthcare services[J]. Applied Soft Computing, 2023, 136: No.110119. |
6 | RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 2007, 76(3): No.036106. |
7 | 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 IEEE 11th International Conference on Data Mining Workshops. Piscataway: IEEE, 2011: 344-349. |
8 | THAKARE S B, KIWELEKAR A W. SkipLPA: an efficient label propagation algorithm for community detection in sparse network[C]// Proceedings of the 9th Annual ACM India Conference. New York: ACM, 2016: 97-106. |
9 | LI P Z, HUANG L, WANG C D, et al. Community detection by motif-aware label propagation[J]. ACM Transactions on Knowledge Discovery from Data, 2020, 14(2): No.22. |
10 | BOUYER A, ROGHANI H. LSMD: a fast and robust local community detection starting from low degree nodes in social networks[J]. Future Generation Computer Systems, 2020, 113: 41-57. |
11 | 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): No.P10008. |
12 | TRAAG V A, WALTMAN L, VAN ECK N J. From Louvain to Leiden: guaranteeing well-connected communities[J]. Scientific Reports, 2019, 9: No.5233. |
13 | WANG P W, KOLTER J Z. Community detection using fast low-cardinality semidefinite programming[C/OL]// Proceedings of the 34th Conference on Neural Information Processing Systems. [S.l.]: NIPS, 2020 [2024-01-10].. |
14 | SHANG R, ZHANG W, ZHANG J, et al. Local community detection algorithm based on alternating strategy of strong fusion and weak fusion[J]. IEEE Transactions on Cybernetics, 2023, 53(2): 818-831. |
15 | ZHANG X, ZHOU K, PAN H, et al. A network reduction-based multiobjective evolutionary algorithm for community detection in large-scale complex networks[J]. IEEE Transactions on Cybernetics, 2020, 50(2): 703-716. |
16 | DING J, HE X, YUAN J, et al. Community detection by propagating the label of center[J]. Physica A: Statistical Mechanics and its Applications, 2018, 503: 675-686. |
17 | 汤胤,徐永欢,陈剑.社交网络中种子用户分布对产品扩散的影响[J].系统工程学报,2021,36(2):145-156. |
TANG Y, XU Y H, CHEN J. Influence of seed user distribution on social product diffusion in social network[J]. Journal of Systems Engineering, 2021, 36(2): 145-156. | |
18 | NIU Y, KONG D, LIU L, et al. Overlapping community detection with adaptive density peaks clustering and iterative partition strategy[J]. Expert Systems with Applications, 2023, 213(Pt C): No.119213. |
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 | 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, 2021, 563: No.125420. |
21 | MA T, LIU Q, CAO J, et al. LGIEM: global and local node influence based community detection[J]. Future Generation Computer Systems, 2020, 105: 533-546. |
22 | 薛磊,唐旭清. 基于中心团的重叠社区检测算法[J]. 计算机科学, 2020, 47(8):157-163. |
XUE L, TANG X Q. Algorithm for detecting overlapping communities based on centered cliques[J]. Computer Science, 2020, 47(8):157-163. | |
23 | ROGHANI H, BOUYER A. A fast local balanced label diffusion algorithm for community detection in social networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(6):5472-5484. |
24 | ARENAS A, DANON L, DÍAZ-GUILERA A, et al. Community analysis in social networks[J]. The European Physical Journal B, 2004, 38: 373-380. |
25 | ZHENG K, ZHANG J, YAO S, et al. Impacts of social relationships and inhomogeneous node distribution on the network performance[J]. IEEE Transactions on Wireless Communications, 2016, 15(8): 5467-5479. |
26 | KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893. |
27 | ROSVALL M, AXELSSON D, BERGSTROM C T. The map equation[J]. The European Physical Journal Special Topics, 2009, 178(1): 13-23. |
28 | LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 2008, 78(4): No.046110. |
[1] | Xinrui LIN, Xiaofei WANG, Yan ZHU. Academic anomaly citation group detection based on local extended community detection [J]. Journal of Computer Applications, 2024, 44(6): 1855-1861. |
[2] | Tao SUN, Zhangtian DUAN, Haonan ZHU, Peihao GUO, Heli SUN. Social event recommendation method based on unexpectedness metric [J]. Journal of Computer Applications, 2024, 44(3): 760-766. |
[3] | Rui GAO, Xuebin CHEN, Zucuan ZHANG. Dynamic social network privacy publishing method for partial graph updating [J]. Journal of Computer Applications, 2024, 44(12): 3831-3838. |
[4] | Li LI, Chunyan YANG, Jiangwen ZHU, Ronglei HU. User plagiarism identification scheme in social network under blockchain [J]. Journal of Computer Applications, 2024, 44(1): 242-251. |
[5] | Shijie PENG, Hongmei CHEN, Lizhen WANG, Qing XIAO. Hybrid point-of-interest recommendation model based on geographic preference ranking [J]. Journal of Computer Applications, 2023, 43(8): 2448-2455. |
[6] | Nannan SUN, Chunhui PIAO, Xinna MA. Group buying recommendation method based on social relationship and time-series information [J]. Journal of Computer Applications, 2023, 43(6): 1719-1729. |
[7] | Lin ZHOU, Yuzhi XIAO, Peng LIU, Youpeng QIN. Community mining algorithm based on multi-relationship of nodes and its application [J]. Journal of Computer Applications, 2023, 43(5): 1489-1496. |
[8] | Xiangyu LUO, Ke YAN, Yan LU, Tian WANG, Gang XIN. Nonuniform time slicing method based on prediction of community variance [J]. Journal of Computer Applications, 2023, 43(11): 3457-3463. |
[9] | Yu YANG, Weiwei DUAN. Spectral clustering based dynamic community discovery algorithm in social network [J]. Journal of Computer Applications, 2023, 43(10): 3129-3135. |
[10] | LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao. Local community detection algorithm based on Monte-Carlo iterative solving strategy [J]. Journal of Computer Applications, 2023, 43(1): 104-110. |
[11] | Liqing QIU, Fushuai QU. Emotional map of emergency based on sentiment analysis and influence evaluation [J]. Journal of Computer Applications, 2022, 42(5): 1330-1338. |
[12] | Jing CHEN, Jiangchuan LIU, Nana WEI. Overlapping community detection algorithm combining K-shell and label entropy [J]. Journal of Computer Applications, 2022, 42(4): 1162-1169. |
[13] | Jie YANG, Mingyang ZHANG, Xiaobin RUI, Zhixiao WANG. Influence maximization algorithm based on node coverage and structural hole [J]. Journal of Computer Applications, 2022, 42(4): 1155-1161. |
[14] | Jun HU, Zhengkang XU, Li LIU, Fujin ZHONG. Network embedding method based on multi-granularity community information [J]. Journal of Computer Applications, 2022, 42(3): 663-670. |
[15] | Qingqing WU, Lihua ZHOU, Xuanyi CUN, Guowang DU, Yiting JIANG. Influence maximization algorithm based on directed acyclic graph in heterogeneous information networks [J]. Journal of Computer Applications, 2022, 42(3): 895-903. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||