Community detection method based on tensor modeling and evolutionary K-means clustering

doi:10.11772/j.issn.1001-9081.2021010043

Abstract

Abstract:

Most traditional community detection methods are limited to single relational network， and their applicability and accuracy are relatively poor. In order to solve the problems， a community detection method for multiple relationship networks was proposed. Firstly， for modeling the multiple relational network， the third-order adjacency tensor was used， in which each slice of the tensor represented an adjacency matrix corresponding to a type of relationship between participants. From the perspective of data representation， by interpreting the multiple relational network as a third-order tensor is helpful to use the factorization method as a learning method. Then， RESCAL decomposition was used as a relational learning tool to reveal the unique implicit representation of participants. Finally， the evolutionary K-means clustering algorithm was applied to the results obtained in the previous step to determine the community structure in multiple dimensions. The experiments were conducted on a synthetic dataset and two public datasets. The experimental results show that， compared with Contextual Information-based Community Detection （CICD） method， Memetic method and Local Spectral Clustering （LSC） method， the proposed method has the purity at least 5 percentage points higher， the Overlapping Normalized Mutual Information （ONMI） at least 2 percentage points higher， and the F score at least 3 percentage points higher. And it is proved that the proposed method has fast convergence speed.

Key words: community detection, multiple relational network, RESCAL decomposition, evolutionary K-means clustering, third-order adjacency tensor

摘要：

很多传统社区检测方法大多局限于单关系网络，适用性和准确性均较弱。针对此问题，提出了一种针对多关系网络的社区检测方法。首先，为进行多关系网络建模，使用了三阶邻接张量，其中张量的每个切片表示与参与者之间一种类型的关系相对应的邻接矩阵。从数据表示的角度，将多关系网络解读为三阶张量利于将因子分解方法作为学习方法使用。然后，应用RESCAL分解作为关系学习的工具，从而揭示参与者的唯一隐性表征。最后，在上一步得到的结果上应用进化K均值聚类算法，以确定多维度上的社区结构。在一个合成数据集和两个公开数据集上进行实验。实验结果表明，与基于上下文信息的社区检测（CICD）方法、Memetic方法和局部谱聚类（LSC）方法相比，所提方法的纯度最少提高了5个百分点，重叠归一化互信息（ONMI）最少提高了2个百分点，F得分最少提高了3个百分点，并且验证了该方法具有较快的收敛速度。

关键词: 社区检测, 多关系网络, RESCAL分解, 进化K均值聚类, 三阶邻接张量

CLC Number:

TP391

Jicheng CHEN, Hongchang CHEN. Community detection method based on tensor modeling and evolutionary K-means clustering[J]. Journal of Computer Applications, 2021, 41(11): 3120-3126.

陈吉成, 陈鸿昶. 基于张量建模和进化K均值聚类的社区检测方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3120-3126.

Figures/Tables 13

References 24

1	秦宏超.大规模动态社会网络社区检测算法的研究与实现［D］.沈阳：东北大学，2015：15-27.
	QIN H C. Research and implementation of community detection algorithm in large scale dynamic social network ［D］. Shenyang： Northeastern University， 2015： 15-27.
2	LIZORKIN D， MEDELYAN O， GRINEVA M. Analysis of community structure in Wikipedia ［C］// Proceedings of the 2009 18th International World Wide Web Conference. New York： ACM， 2009： 1221-1222. 10.1145/1526709.1526938
3	李艳红，赵宏伟，王素格，等.面向微博文本流的负面情感突发话题检测［J］.计算机应用，2020，40（12）：52-58. 10.11772/j.issn.1001-9081.2020060880
	LI Y H， ZHAO H W， WANG S G， et al. Detection of negative emotion burst topic in microblog text stream ［J］. Journal of Computer Applications， 2020， 40（12）： 3458-3464. 10.11772/j.issn.1001-9081.2020060880
4	周雨佳，窦志成，葛松玮，等.基于递归神经网络与注意力机制的动态个性化搜索算法［J］.计算机学报，2020，43（5）：812-826. 10.11897/SP.J.1016.2020.00812
	ZHOU Y J， DOU Z C， GE S W， et al. Dynamic personalized search based on RNN with attention mechanism ［J］. Chinese Journal of Computers， 2020， 43（5）： 812-826. 10.11897/SP.J.1016.2020.00812
5	DIAS M， BRAZ P， BEZERRA E， et al. Contextual information based community detection in attributed heterogeneous networks ［J］. IEEE Latin America Transactions， 2019， 17（2）： 236-244. 10.1109/tla.2019.8863169
6	郭杨志.复杂网络社区结构的重叠社区发现和鲁棒性分析［D］.西安：西安电子科技大学，2018：11-18. 10.52547/crpase.7.3.2393
	GUO Y Z. Overlapping community detection and robustness analysis of complex network community structure ［D］. Xi’an： Xidian University， 2018：11-18. 10.52547/crpase.7.3.2393
7	楚杨杰，洪叶，杨忠保，等.改进蚁群算法优化重叠社区发现方法［J］.计算机工程与设计，2019，40（4）：1022-1026，1098.
	CHU Y J， HONG Y， YANG Z B， et al. Local extension approach through ant colony algorithm for overlapping community detection ［J］. Computer Engineering and Design， 2019， 40（4）： 1022-1026， 1098.
8	WU Z， YIN W P， CAO J， et al. Community detection in multi-relational social networks ［C］// Proceedings of the 2013 International Conference on Web Information Systems Engineering， LNCS8181. Berlin： Springer， 2013： 43-56.
9	LI Y X， HE K， KLOSTER K， et al. Local spectral clustering for overlapping community detection ［J］. ACM Transactions on Knowledge Discovery from Data， 2018， 12（2）： Article No.17. 10.1145/3106370
10	陈吉成，陈鸿昶，李邵梅.利用非重叠CD生成解的集成重叠社区检测［J］.电子技术应用，2019，45（12）：96-100，105.
	CHEN J C， CHEN H C， LI S M. Integrated overlapping CD method using existing solutions of non-overlapping CD ［J］. Application of Electronic Technique， 2019， 45（12）： 96-100， 105.
11	LIN Y R， CHI Y， ZHU S H， et al. FacetNet： a framework for analyzing communities and their evolutions in dynamic networks ［C］// Proceedings of the 2008 17th International World Wide Web Conference. New York： ACM， 2008： 685-694. 10.1145/1367497.1367590
12	王洪峰，陈立勇.云计算环境下基于张量分解的缺失关联规则挖掘算法［J］.重庆邮电大学学报（自然科学版），2015，27（3）：397-403. 10.3979/j.issn.1673-825X.2015.03.018
	WANG H F， CHEN L Y. Missing association rule mining algorithm using tensor decomposition in cloud computing environment ［J］. Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition）， 2015， 27（3）： 397-403. 10.3979/j.issn.1673-825X.2015.03.018
13	GAYANI TENNAKOON T M， LUONG K， MOHOTTI W， et al. Multi-type relational data clustering for community detection by exploiting content and structure information in social networks ［C］// Proceedings of the 2019 Pacific Rim International Conference on Artificial Intelligence， LNCS11671. Cham： Springer， 2019： 541-554. 10.1007/978-3-030-29911-8_42
14	詹建州.基于张量分解的多关系网络社区发现算法研究［D］.汕头：汕头大学，2017：21-29. 10.26420/jpsychiatrymentaldisord.2021.1036
	ZHAN J Z. Research on community discovery algorithm of multiple relational network based on tensor decomposition ［D］. Shantou： Shantou University， 2017： 21-29. 10.26420/jpsychiatrymentaldisord.2021.1036
15	周琦，柴小丽，马克杰，等.基于CUDA与CUBLAS的Tucker分解模块设计与实现［J］.计算机工程，2019，45（3）：41-46. 10.19678/j.issn.1000-3428.0052189
	ZHOU Q， CHAI X L， MA K J， et al. Design and implementation of Tucker decomposition module based on CUDA and CUBLAS ［J］. Computer Engineering， 2019， 45（3）： 41-46. 10.19678/j.issn.1000-3428.0052189
16	BHARADWAJ K K， AL-SHAMRI M Y H. Fuzzy computational models for trust and reputation systems ［J］. Electronic Commerce Research and Applications， 2009， 8（1）： 37-47. 10.1016/j.elerap.2008.08.001
17	马晨光，刘庆国，李亚雄.基于遗传K均值算法的军事装备试验数据分组模型［J］.兵器装备工程学报，2018，39（4）：105-107. 10.11809/bqzbgcxb2018.04.023
	MA C G， LIU Q G， LI Y X. A military equipment test data grouping model based on genetic K-means algorithm ［J］. Journal of Ordnance Equipment Engineering， 2018， 39（4）： 105-107. 10.11809/bqzbgcxb2018.04.023
18	BROCKMEIER A J， MU T T， ANANIADOU S， et al. Self-tuned descriptive document clustering using a predictive network ［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（10）： 1929-1942. 10.1109/tkde.2017.2781721
19	HAJIABADI M， ZARE H， BOBARSHAD H. IEDC： an integrated approach for overlapping and non-overlapping community detection ［J］. Knowledge-Based Systems， 2017， 123： 188-199. 10.1016/j.knosys.2017.02.018
20	CHAKRABORTY T， PARK N， SUBRAHMANIAN V S. Ensemble-based algorithms to detect disjoint and overlapping communities in networks ［C］// Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway： IEEE， 2016： 73-80. 10.1109/asonam.2016.7752216
21	GREENE D， CUNNINGHAM P. Producing a unified graph representation from multiple social network views ［C］// Proceedings of the 2013 5th Annual ACM Web Science Conference. New York： ACM， 2013： 118-121. 10.1145/2464464.2464471
22	TANG F Q， WANG C N， SU J X， et al. Spectral clustering-based community detection using graph distance and node attributes ［J］. Computational Statistics， 2020， 35（1）： 69-94. 10.1007/s00180-019-00909-8
23	马振宇，吴纬，张威，等.基于非参数的软件可靠性验证测试方法［J］.华中科技大学学报（自然科学版），2020，48（2）：108-113. 10.13245/j.hust.200218
	MA Z Y， WU W， ZHANG W， et al. Research on software reliability demonstration testing method based on non-parameter ［J］. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2020， 48（2）： 108-113. 10.13245/j.hust.200218
24	陈晓，郭景峰，张春英.社会网络顶点间相似性度量及其应用［J］.计算机科学与探索，2017，11（10）：1629-1641. 10.3778/j.issn.1673-9418.1607025
	CHEN X， GUO J F， ZHANG C Y. Measuring similarity between vertices and its application in social network ［J］. Journal of Frontiers of Computer Science and Technology， 2017， 11（10）： 1629-1641. 10.3778/j.issn.1673-9418.1607025

方法	合成数据集LFR	Coauthorship数据集	Twitter数据集
CICD	0.85	0.82	0.81
Memetic	0.82	0.83	0.87
LSC	0.80	0.80	0.83
本文方法	0.94	0.88	0.92

方法	合成数据集LFR	Coauthorship数据集	Twitter数据集
CICD	0.85	0.82	0.81
Memetic	0.82	0.83	0.87
LSC	0.80	0.80	0.83
本文方法	0.94	0.88	0.92

方法	合成数据集LFR	Coauthorship数据集	Twitter数据集
CICD	0.88	0.67	0.72
Memetic	0.86	0.66	0.65
LSC	0.87	0.65	0.69
本文方法	0.90	0.73	0.80

方法	合成数据集LFR	Coauthorship数据集	Twitter数据集
CICD	0.88	0.67	0.72
Memetic	0.86	0.66	0.65
LSC	0.87	0.65	0.69
本文方法	0.90	0.73	0.80

方法	合成数据集LFR	Coauthorship数据集	Twitter数据集
CICD	0.82	0.68	0.73
Memetic	0.83	0.76	0.74
LSC	0.88	0.75	0.76
本文方法	0.91	0.81	0.81