[1]张梦园,李玲娟.基于节点重要性和模块度优化的社团划分算法[J].计算机技术与发展,2023,33(04):126-131.[doi:10. 3969 / j. issn. 1673-629X. 2023. 04. 019]
　ZHANG Meng-yuan,LI Ling-juan.Community Division Algorithm Based on Node Importance and Modularity Optimization[J].,2023,33(04):126-131.[doi:10. 3969 / j. issn. 1673-629X. 2023. 04. 019]

点击复制

基于节点重要性和模块度优化的社团划分算法()

分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:

33

期数:

2023年04期

页码:

126-131

栏目:

人工智能

出版日期:

2023-04-10

文章信息/Info

Title:

Community Division Algorithm Based on Node Importance and Modularity Optimization

文章编号:

1673-629X(2023)04-0126-06

作者:

张梦园; 李玲娟

南京邮电大学 计算机学院,江苏 南京 210023

Author(s):

ZHANG Meng-yuan; LI Ling-juan

School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China

关键词:

加权网络; 社团划分; 节点重要性; 模块度优化; BGLL 算法

Keywords:

weighted network; community division; node importance; modularity optimization; BGLL algorithm

分类号:

TP311

DOI:

10. 3969 / j. issn. 1673-629X. 2023. 04. 019

摘要:

与无权网络相比,加权网络能够反映节点间关系的强弱,赋予复杂网络更加明确的物理意义,因此加权网络的社团划

分具有重要的现实意义。 为了提高加权网络社团划分的准确度,设计了一种基于节点重要性和模块度优化的加权

网络社团划分算法 IMWCD。 首先,将每个节点初始化为一个社团,并借鉴度中心性和 PageRank 的评价思想,综合节点自身信息及其邻居节点信息来计算节点重要性;然后,按节点重要性的升序遍历节点,以模块度增益最大为原则

将目标节点移入相应社团中,直至各节点不需要再移动;再以各个社团为节点重新构建网络,新网络中边的权重为两

个新节点对应社团的权重 之 和; 重 复 以 上 过 程, 直 至 网 络 的 模 块 度 不 再 变 化。 在 LFR 人 工 基 准 网 络 数 据 集 和 High - energy theory、Astrophysics 和 Condensed matter 等真实加权网络上的实验结果表明,IMWCD 算法的社团划分质量比同类型的算法有所提升,并且具有线性时间复杂度,能适用于大规模加权网络的社团划分。

Abstract:

Compared with unweighted networks, weighted networks can reflect strength of the relationship between?

nodes and givecomplex networks more clear physical meaning. Therefore, the community division of weighted networks has important practicalsignificance. In order to improve the accuracy of weighted network community division, a weighted network community divisionalgorithm IMWCD based on node importance and modularity optimization is designed. Firstly,each node is initialized as a community,and the node importance is calculated based on the information of the node itself and its neighbors by referencing the evaluation ideas ofdegree centrality and PageRank. Then the nodes are traversed according to the ascending order of node importance, and the target node ismoved into the corresponding community based on the principle of maximum modularity gain until each node does not need to be movedagain. Then,each community is taken as a node to reconstruct the network,and the weight of the edge in the new network is the sum ofthe weights of the corresponding communities of the two new nodes. Repeat the process until the modularity of the network does notchange.?

The experimental results on LFR artificial benchmark network data set and real weighted networks such as?

High-energy theory,Astrophysics and Condensed matter show that IMWCD algorithm improves the quality of community division compared with thealgorithms of the same type,and has linear time complexity. It is suitable for the community division of large-scale weighted networks.

常用功能