考虑社区规模不平衡的非重叠社区检测

doi:10.11772/j.issn.1001-9081.2023101536

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (11): 3396-3402.DOI: 10.11772/j.issn.1001-9081.2023101536

考虑社区规模不平衡的非重叠社区检测

刘世梁, 王义, 马应龙()

华北电力大学控制与计算机工程学院，北京 102206

收稿日期:2023-11-10 修回日期:2024-01-11 接受日期:2024-01-19 发布日期:2024-01-01 出版日期:2024-11-10
通讯作者: 马应龙
作者简介:刘世梁（1998—），男，甘肃武威人，硕士研究生，主要研究方向：社区检测
王义（2000—），男，河北沧州人，硕士研究生，主要研究方向：社交推荐
基金资助:
国家自然科学基金资助项目(62072450);国家电网公司科技项目(SGGSXT00XMJS2250023)

Non-overlapping community detection with imbalanced community sizes

Shiliang LIU, Yi WANG, Yinglong MA()

School of Control and Computer Engineering，North China Electric Power University，Beijing 102206，China

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.
WANG Yi， born in 2000， M. S. candidate. His research interests include social recommendation.
Supported by:
National Natural Science Foundation of China(62072450);Science and Technology Project of State Grid(SGGSXT00XMJS2250023)

摘要/Abstract

摘要：

社区检测有助于理解社交网络错综复杂的结构，但现有的大部分社区检测方法并未考虑社交网络中社区规模的不平衡，发现的社区结构较为单一且准确率较低。为此，提出基于初始社区结构局部扩展的社区检测方法（LEICS）。LEICS分为3个阶段：第一阶段，充分利用网络的层次结构信息和局部结构信息发现不同规模的初始社区结构；第二阶段，通过计算节点与社区内节点的连接强度和节点对社区的模块度贡献扩展初始社区，再利用标签传播算法（LPA）处理剩余节点；第三阶段，重新分配小于平均社区大小的不稳定社区中的节点，以进一步优化社区检测的结果。在12个真实世界网络和兰奇基内蒂-福图纳托-拉迪奇（LFR）仿真网络上的实验结果表明，相较于次优的局部平衡标签扩散（LBLD）算法，LEICS在Polbooks和YouTube网络上的归一化互信息（NMI）提高了至少5个百分点，它的准确性和鲁棒性在小规模和大规模网络中得到充分验证，这表明LEICS可以适应社区规模的不平衡。

关键词: 社交网络, 社区检测, 初始社区结构, 扩展策略, 标签传播

Abstract:

Community detection helps to comprehend the complex structure of social networks， but most of the existing community detection methods do not consider the imbalanced sizes of communities to detect， and the discovered community structures are relatively single with low accuracy. Therefore， a non-overlapping community detection method based on Local Expansion of Initial Community Structure （LEICS） was proposed. LEICS was divided into three stages： in the first stage， the initial community structures with different scales were detected by utilizing the hierarchical structure information and local structure information of the network； in the second stage， the initial community was expanded by calculating the connection intensity between the node and the nodes in the community and the modularity contribution of the node， and then using the Label Propagation Algorithm （LPA） to deal with the rest of the nodes； in the third stage， for unstable communities with size smaller than the average community size， the nodes were redistributed to further optimize the results of community detection. Experimental results on twelve datasets of real-world networks and Lancichinetti-Fortunato-Radicchi （LFR） simulated networks show that compared to the suboptimal Local Balanced Label Diffusion （LBLD） algorithm， LEICS improves the Normalized Mutual Information （NMI） by at least 5 percentage points on Polbooks and YouTube networks， and the accuracy and robustness of LEICS in both small-size and large-size networks are fully validated， proving that LEICS can adapt to the imbalance of community size.

Key words: social network, community detection, initial community structure, expansion strategy, label propagation

中图分类号:

TP391.4

刘世梁, 王义, 马应龙. 考虑社区规模不平衡的非重叠社区检测[J]. 计算机应用, 2024, 44(11): 3396-3402.

Shiliang LIU, Yi WANG, Yinglong MA. Non-overlapping community detection with imbalanced community sizes[J]. Journal of Computer Applications, 2024, 44(11): 3396-3402.

图/表 7

图1 LEICS的总体框架

Fig.1 Overall framework of LEICS

表1 真实世界网络信息

Tab. 1 Information of real-world networks

真实世界网络	节点数	边数	真实社区数
Karate Club	34	78	2
Dolphins	62	159	2
Plobooks	105	441	3
Football	115	613	12
E-mail	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

表2 LFR网络信息

Tab. 2 Information of LFR networks

网络	N/10³	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］

表2 LFR网络信息

Tab. 2 Information of LFR networks

网络	N/10³	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］

表3 真实世界网络上的NMI值比较

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

表4 真实世界网络上的ARI值比较

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
E-mail	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

表5 真实世界网络上的Q值比较

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
E-mail	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

图2 LFR网络上的NMI值比较

Fig. 2 NMI comparison in LFR networks

参考文献 28

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]	林欣蕊, 王晓菲, 朱焱. 基于局部扩展社区发现的学术异常引用群体检测[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1855-1861.
[2]	高瑞, 陈学斌, 张祖篡. 面向部分图更新的动态社交网络隐私发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3831-3838.
[3]	李莉, 杨春艳, 朱江文, 胡荣磊. 区块链下社交网络用户抄袭识别方案[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 242-251.
[4]	彭诗杰, 陈红梅, 王丽珍, 肖清. 基于地理偏好排序的兴趣点混合推荐模型[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2448-2455.
[5]	孙男男, 朴春慧, 马新娜. 基于社交关系和时序信息的团购推荐方法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1719-1729.
[6]	杨煜, 段威威. 基于谱聚类的社交网络动态社区发现算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3129-3135.
[7]	仇丽青, 曲福帅. 基于情感分析和影响力评估的突发事件情感图谱[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1330-1338.
[8]	杨杰, 张名扬, 芮晓彬, 王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1155-1161.
[9]	陈晶, 刘江川, 魏娜娜. 融合K-shell和标签熵的重叠社区发现算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1162-1169.
[10]	解伟凡, 郭岩, 匡广生, 余智华, 薛源海, 沈华伟. 基于演化模式的推特话题流行度预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3364-3370.
[11]	李美子, 米一菲, 张倩, 张波. 社交网络中基于K核分解的意见领袖识别算法[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 26-35.
[12]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[13]	孙鹤立, 徐统, 何亮, 贾晓琳. 融合用户历史行为与社交关系的个性化社交事件推荐方法[J]. 计算机应用, 2021, 41(2): 324-329.
[14]	赵旭剑, 王崇伟. 基于图卷积网络的微博新闻故事线抽取方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3139-3144.
[15]	陈吉成, 陈鸿昶. 基于张量建模和进化K均值聚类的社区检测方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3120-3126.

考虑社区规模不平衡的非重叠社区检测

Non-overlapping community detection with imbalanced community sizes

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 28

相关文章 15

编辑推荐

Metrics