兰州理工大学学报 ›› 2024, Vol. 50 ›› Issue (4): 86-93.

• 自动化技术与计算机技术 • 上一篇    下一篇

基于网络节点极大团的社团检测算法

卢鹏丽*, 杨亚磊   

  1. 兰州理工大学 计算机与通信学院, 甘肃 兰州 730050
  • 收稿日期:2022-05-10 出版日期:2024-08-28 发布日期:2024-08-30
  • 通讯作者: 卢鹏丽(1973-),女,甘肃酒泉人,博士,教授,博导.Email:lupengli88@163.com
  • 基金资助:
    甘肃省自然科学基金 (23JRRA770),甘肃省高校产业支撑项目(2023CYZC-25)

Community detection algorithm based on maximal clique of network nodes

LU Peng-li, YANG Ya-lei   

  1. School of Computer and Communication, Lanzhou Univ. of Tech., Lanzhou 730050, China
  • Received:2022-05-10 Online:2024-08-28 Published:2024-08-30

摘要: 社团结构检测有助于揭示复杂网络的结构-功能特性,目前已有的社团检测算法在其研究过程中存在着分辨率限制、节点不确定性以及需要先验参数等问题.为了解决此类问题,提出了一种基于网络节点极大团的社团检测算法(BMC).BMC算法将网络中的节点极大团设为初始节点群组,依据提出的极大团局部相似度和局部团组关系对节点群组进行分级聚类合并,以此挖掘出网络中的社团结构.针对在社团结构挖掘过程中出现的节点不确定性问题,通过模块度矩阵提出了模块隶属度对网络中的单邻居节点和重叠节点进行优化.为了验证BMC算法对网络社团结构挖掘的准确性,在5个真实网络数据集上与5种算法进行实验对比.通过3种衡量指标得到的实验结果表明,BMC算法能够准确地检测出网络中的社团结构.

关键词: 复杂网络, 社团检测, 极大团, 模块度矩阵

Abstract: Community structure detection is instrumental in revealing the structure-function properties of complex networks. The existing community detection algorithms suffer from resolution limitations, node uncertainty, and the need for prior parameters in their research process. A community detection algorithm based on the maximal clique of network nodes (BMC) is proposed to solve these problems. The BMC algorithm sets the maximal clique of nodes in the network as the initial node cluster, and merges the node clusters by hierarchical clustering based on the proposed local similarity of the maximal clique and the local clique relationship, so as to mine the community structure in the network. Aiming at tackling the issue of node uncertainty in the mining process of community structure, the module membership degree is proposed through the modularity matrix to optimize the single neighbor nodes and overlapping nodes in the network. In order to verify the accuracy of the BMC algorithm for network community structure mining, experiments are conducted on five real network datasets with five algorithms for comparison. The experimental results obtained by the three measures show that the BMC algorithm accurately detects the community structure in the network.

Key words: complex network, community detection, maximal clique, modularity matrix

中图分类号: