基于流式分析的大规模网络重叠社区发现算法

doi:10.12263/DZXB.20201422

电子学报 ›› 2022, Vol. 50 ›› Issue (8): 1951-1958.DOI: 10.12263/DZXB.20201422

基于流式分析的大规模网络重叠社区发现算法

李辉, 张建朋, 陈福才

信息工程大学信息技术研究所，河南郑州 450002

收稿日期:2020-12-11 修回日期:2021-06-17 出版日期:2022-08-25
- 通讯作者:
- 张建朋
- 作者简介:
- 李辉男，1996年出生，湖北丹江口人.国家数字交换系统工程技术研究中心硕士生.主要研究方向为社区发现.E-mail: lihui@alumni.hust.edu.cn
  张建朋男，1988年出生，河北廊坊人.国家数字交换系统工程技术研究中心助理研究员.主要研究方向为大数据分析、图聚类.E-mail: zjp@ndsc.com.cn
  陈福才男，1974年出生，江西南昌人.国家数字交换系统工程技术研究中心研究员.主要研究方向为网络安全.E-mail: fucai0309@163.com
- 基金资助:
- 国家自然基金青年基金 (62002384); 郑州市协同创新重大专项 (162/32410218); 中国博士后科学基金面上项目 (2020M683760)

A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network

LI Hui, ZHANG Jian-peng, CHEN Fu-cai

Institute of Information Technology，Information Engineering University，Zhengzhou，Henan 450002，China

Received:2020-12-11 Revised:2021-06-17 Online:2022-08-25 Published:2022-09-08
- Corresponding author:
- ZHANG Jian-peng

摘要/Abstract

摘要：

为了提高在大规模网络中发现社区的效率，提出一种基于流式分析的大规模网络重叠社区发现算法（Streaming-based Overlapping Community Detection algorithm，SOCD）.算法对网络中的边进行流式处理，每次只处理一条边且每条边仅被处理一次.根据节点的度、节点对社区的贡献度以及节点移动前后社区间连边数量的变化等信息对节点进行划分.在人工合成网络和真实大规模网络上的一系列实验表明，SOCD算法在时间消耗和内存占用上具有较大的优势，比传统方法快10倍以上，且具有较强的鲁棒性，能够在线性时间和空间复杂度下高效、准确地挖掘网络中的重叠社区结构.

关键词: 社区发现, 重叠社区, 大规模网络, 流式分析, 节点贡献度

Abstract:

To improve the efficiency of community detection in large-scale network, a streaming-based overlapping community detection algorithm(SOCD) is proposed. SOCD processes the edges in a streaming fashion and handles one edge at a time, and each edge is processed only once. The algorithm discovers the community based on the degree of node, the contribution of node to the community, and the change of the number of connected edges between communities. Extensive experiments on synthetic networks and real large-scale networks show that SOCD has great advantages in time consumptions and memory footprints. It is more than 10 times faster than traditional methods and has strong robustness. It can efficiently and accurately mine the overlapping community structures in the network under linear time and space complexity.

Key words: community detection, overlapping community, large-scale network, streaming analysis, node contribution

中图分类号:

TP311

李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.

LI Hui, ZHANG Jian-peng, CHEN Fu-cai. A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network[J]. Acta Electronica Sinica, 2022, 50(8): 1951-1958.

图/表 10

图1 一条新边到来时的处理示意图

表1 人工合成网络D1参数

N	$k$	on	$μ$
1 000	15	0.1	0.1
10 000	15	0.1	0.1
100 000	15	0.1	0.1
1 000 000	15	0.1	0.1

表1 人工合成网络D1参数

N	$k$	on	$μ$
1 000	15	0.1	0.1
10 000	15	0.1	0.1
100 000	15	0.1	0.1
1 000 000	15	0.1	0.1

表2 6个大规模真实网络的特征

数据集	节点数	连边数	平均度	平均集聚系数	社区数
Amazon	334 863	925 872	5.52	0.396 7	75 149
DBLP	317 080	1 049 866	6.62	0.632 4	13 477
YouTube	1 134 890	2 987 624	5.26	0.080 8	8 385
LiveJournal	3 997 962	34 681 189	17.34	0.284 3	287 512
Orkut	3 072 441	117 185 083	76.28	0.166 6	6 288 363
Friendster	65 608 366	1 806 067 135	55.06	0.162 3	957 154

图2 不同规模的合成网络上的准确度比较

图3 不同μ值下SOCD算法的精度

表3 算法在大规模真实网络上的运行时间

网络	SOCD	OCSC	Louvain	CoEuS	LCDNN	BigClam	CommunityGAN
Amazon	16.8 s	2.1 min	2.5 min	2.8 min	19.8 min	47.6 min	2.2 h
DBLP	18.3 s	2.5 min	4.7 min	33.4 s	26.2 min	1.0 h	3.1 h
YouTube	49.2 s	7.9 min	10.8 min	2.5 min	1.2 h	—	—
LiveJournal	10.0 min	1.3 h	3.6 h	6.4 h	—	—	—
Orkut	33.0 min	4.1 h	—	—	—	—	—
Friendster	7.2 h	—	—	—	—	—	—

图4 不同边规模下算法的运行时间

图5 算法在真实网络上的平均F1-Score

图6 算法在真实网络上的ENMI

图7 D的不同选择对应的相对质量Q

参考文献 16

1	VAN LIERDE H, CHOW T W S, CHEN G R. Scalable spectral clustering for overlapping community detection in large-scale networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(4): 754-767.
2	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.
3	HE K, SHI P, BINDEL D, et al. Krylov subspace approximation for local community detection in large networks[J]. ACM Transactions on Knowledge Discovery from Data, 2019, 13(5): 52(1-30.
4	LUO W J, LU N N, NI L, et al. Local community detection by the nearest nodes with greater centrality[J]. Information Sciences, 2020, 517: 377-392.
5	陈洁, 李锐, 赵姝, 等. 面向图表示社区检测的新型聚类覆盖算法[J]. 电子学报, 2020, 48(9): 1680-1687.
	CHEN J, LI R, ZHAO S, et al. A new clustering cover algorithm based on graph representation for community detection[J]. Acta Electronica Sinica, 2020, 48(9): 1680-1687. (in Chinese)
6	GHOSH S, HALAPPANAVAR M, TUMEO A, et al. Distributed Louvain algorithm for graph community detection[C]//2018 IEEE International Parallel and Distributed Processing Symposium. Vancouver, BC, Canada: IEEE, 2018: 885-895.
7	GHAFFARI M, LATTANZI S, MITROVIC S. Improved parallel algorithms for density-based network clustering[C]//International Conference on Machine Learning. Long Beach, California, USA: PMLR, 2019: 2201-2210.
8	LIAKOS P, PAPAKONSTANTINOPOULOU K, NTOULAS A, et al. Rapid detection of local communities in graph streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(5): 2375-2386.
9	HOLLOCOU A, MAUDET J, BONALD T, et al. A linear streaming algorithm for community detection in very large networks[EB/OL]. (2017-03-08)[2020-12-11]. .
10	李辉, 陈福才, 张建朋, 等. 一种基于流式分析的重叠社区发现方法及装置: CN202010780625.X[P]. 2020-12-22.
11	YUN S, LELARGE M, Streaming PROUTIERE A., memory limited algorithms for community detection[C]//NIPS'14: Proceedings of the 27th International Conference on Neural Information Processing Systems. Montreal Canada: MIT Press, 2014: 3167-3175.
12	YANG J, LESKOVEC J. Overlapping community detection at scale: A nonnegative matrix factorization approach[C]//WSDM'13: Proceedings of the sixth ACM international conference on Web search and data mining. Rome, Italy: ACM, 2013: 587-596.
13	潘剑飞, 董一鸿, 陈华辉, 等. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
	PAN J F, DONG Y H, CHEN H H, et al. The overlapping community discovery algorithm based on compact structure[J]. Acta Electronica Sinica, 2019, 47(1): 145-152. (in Chinese)
14	JIA Y T, ZHANG Q Q, ZHANG W N, et al. CommunityGAN: Community detection with generative adversarial nets[C]//WWW'19: The World Wide Web Conference. San Francisco, CA, USA: ACM, 2019: 784-794.
15	LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 046110.
16	EMMONS S, KOBOUROV S, GALLANT M, et al. Analysis of network clustering algorithms and cluster quality metrics at scale[J]. PLoS One, 2016, 11(7): e0159161.

[1]	陈洁, 李锐, 赵姝, 张燕平. 面向图表示社区检测的新型聚类覆盖算法[J]. 电子学报, 2020, 48(9): 1680-1687.
[2]	潘剑飞, 董一鸿, 陈华辉, 钱江波, 戴明洋. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
[3]	於志勇, 陈基杰, 郭昆, 陈羽中, 许倩. 基于影响力与种子扩展的重叠社区发现[J]. 电子学报, 2019, 47(1): 153-160.
[4]	马慧芳, 谢蒙, 何廷年, 蔺想红. 基于核心标签的可重叠微博网络社区划分方法[J]. 电子学报, 2017, 45(4): 769-776.
[5]	吴奇, 陈福才, 黄瑞阳, 常振超. 基于语义路径的异质网络社区发现方法[J]. 电子学报, 2016, 44(6): 1465-1471.
[6]	国琳, 左万利, 彭涛. 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016, 44(3): 587-594.
[7]	刘世超, 朱福喜, 冯曦. 复杂网络的重叠社区及社区间的结构洞识别[J]. 电子学报, 2016, 44(11): 2600-2606.
[8]	王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.
[9]	张桂杰, 张健沛, 杨静, 辛宇. 基于链接相似性聚类的重叠社区识别[J]. 电子学报, 2015, 43(7): 1329-1335.
[10]	张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.
[11]	冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723-729.
[12]	李泓波, 张健沛, 杨静, 白劲波, 初妍. 基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性[J]. 电子学报, 2014, 42(1): 62-69.
[13]	张健沛, 李泓波, 杨静, 白劲波, 张乐君, 初妍. 基于归属不确定性的变规模网络重叠社区识别[J]. 电子学报, 2012, 40(12): 2512-2518.
[14]	张伟哲, 王佰玲, 何慧, 谭卓鹏. 基于异质网络的意见领袖社区发现[J]. 电子学报, 2012, 40(10): 1927-1932.

基于流式分析的大规模网络重叠社区发现算法

A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 16

相关文章 14

编辑推荐

Metrics