Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (11): 3120-3126.DOI: 10.11772/j.issn.1001-9081.2021010043

• Artificial intelligence • Previous Articles     Next Articles

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

Jicheng CHEN(), Hongchang CHEN   

  1. Institute of Information Technology,Information Engineering University,Zhengzhou Henan 450002,China
  • Received:2021-01-15 Revised:2021-03-25 Accepted:2021-04-01 Online:2021-04-15 Published:2021-11-10
  • Contact: Jicheng CHEN
  • About author:CHEN Jicheng,born in 1982,Ph. D. candidate,His research interests include complex network,community detection and discovery.
    CHEN Hongchang,born in 1964,Ph. D.,professor. His research interests.
  • Supported by:
    the Innovative Research Group Project of National Natural Science Foundation of China(61521003)

基于张量建模和进化K均值聚类的社区检测方法

陈吉成(), 陈鸿昶   

  1. 信息工程大学 信息技术研究所,郑州 450002
  • 通讯作者: 陈吉成
  • 作者简介:陈吉成(1982—),男,江苏淮安人,博士研究生,主要研究方向:复杂网络、社区检测与发现
    陈鸿昶(1964—),男,河南郑州人,教授,博士生导师,博士,主要研究方向:大数据分析、通信与信息系统。
  • 基金资助:
    国家自然科学基金创新研究群体项目(61521003)

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: