Overlapping Community Detection of Complex Networks Based on Discrete Particle Swarm Algorithm

doi:10.7652/xjtuxb201301021

您当前的位置：

首页 >

文章列表页 >

Overlapping Community Detection of Complex Networks Based on Discrete Particle Swarm Algorithm

更新时间：2025-07-09

- Overlapping Community Detection of Complex Networks Based on Discrete Particle Swarm Algorithm
- Vol. 47, Issue 1, Pages: 107-113(2013)
- 作者机构：
  
  1. 西安电子科技大学计算机学院,西安,710071
  2. 河南大学计算机与信息工程学院,河南,开封,475004
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201301021
  CLC： TP393
- Online First：10 January 2013，
  
  Published：2013
- 稿件说明：
移动端阅览
Overlapping Community Detection of Complex Networks Based on Discrete Particle Swarm Algorithm[J]. 2013, 47(1): 107-113.
DOI：

Overlapping Community Detection of Complex Networks Based on Discrete Particle Swarm Algorithm[J]. 2013, 47(1): 107-113. DOI： 10.7652/xjtuxb201301021.

摘要

针对复杂网络重叠社团检测的问题

建立了衡量重叠社团划分优劣的评判函数

并基于该函数提出了一种采用混沌量子粒子群优化的复杂网络重叠社团检测算法。该算法采用量子编码

利用Logistic映射初始化粒子种群

并以粒子群速度改变方式更新转角的大小

以概率为1收敛。实验结果表明

所提算法具有较高的检测正确率

能更好地反映实际社团划分情况。

Abstract

An evaluation function of overlapping community is proposed to solve overlapping community detection of complex networks. A chaos quantum discrete particle swarm algorithm is presented to detect overlapping community structure based on the proposed function. The quantum coding and the logistic mapping are used to generate an initial particle population

and the particle swarm speed changing method is used to update the size of the corner. It is shown that the algorithm converges with probability 1. Experimental results show that the algorithm has higher detection accuracy and can better reflect the real situation of the community divided.

关键词

Keywords

references

SHI Chuan, YAN Zhenyu, CAI Yanan, et al. Multi-objective community detection in complex networks [J]. Applied Soft Computing, 2012, 12(2): 850-859.

WU Jianshe, JIAO Licheng, JIN Chao, et al. Overlapping community detection via network dynamics [J]. Phys Rev: E, 2012, 85: 016115.

GIRVAN M, NEWMAN M E J. Community structure in social and biological networks [J]. Proc Natl Acad Sci USA, 2002, 99(12): 7821-7826.

NGUYEN N P, XUAN Ying, THAI M T. On detection of community structure in dynamic social networks [J]. Mathematics and Statistics, 2012, 58(3): 307-347.

沈毅, 徐焕良. 加权网络权重自相似评判函数及其社团结构检测 [J]. 物理学报, 2010, 59(9): 6022-6028.

SHEN Yi, XU Huanliang. The evaluation function of weight similarity and its application in community detection in weighted networks [J]. Acta Physica Sinica, 2012, 59(9): 6022-6028.

黄健斌, 孙鹤立, BORTNER D, 等. 从链接密度遍历序列中挖掘网络社团的层次结构 [J], 软件学报, 2011, 22(5): 951-961.

HUANG Jianbin, SUN Heli, BORTNER D, et al. Mining hierarchical community structure within networks from density-connected traveling orders [J]. Journal of Software, 2011, 22(5): 951-961.

PALLA G, DERENYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435(9): 814-818.

NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks [J]. Phys Rev: E, 2004, 69: 026113.

SHEN Huawei, CHENG Xueqi,GUO Jiafeng. Quantifying and identifying the overlapping community structure in networks [J/OL]. J Stat Mech, 2009. http: ∥10.1088/1742-5468/2009/07/P07042.

NICOSIA V, MANGIONI G, CARCHIOLO V, et al. Extending the definition of modularity to directed graphs with overlapping communities [J/OL]. J Stat Mech, 2009. http∥10.1088/1742-4468/2009/03/P03024.

FORTUNATO S, BARTHELEMY M. Resolution limit in community detection [J]. Proc Natl Acad Sci USA, 2007, 104(1): 36-41.

ROSVAL L M, BERGSTROM C T. An information-theoretic framework for resolving community structure in complex networks [J]. Proc Natl Acad Sci USA, 2007, 104(18): 7327-7331.

MUFF S, RAO F, CAflISCH A. Local modularity measure for network clusterizations [J]. Phys Rev: E, 2005, 72(5): 056107.

LI Z P, ZHANG S H, WANG R S, et al. Quantitative function for community detection [J]. Phys Rev: E, 2008, 77(3): 036106.

WANG Yan, FENG Xiaoyue, HUANG Yanxin, et al. A novel quantum swarm evolutionary algorithm and its applications [J]. Neurocomputing, 2007, 70: 633-640.

BACK T. Evolutionary algorithm in theory and practice [M]. Oxford, UK: Oxford University Press, 1996: 129.

LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities [J]. Phys Rev: E, 2009, 80(1): 016118.

GREGORY S. Finding overlapping communities in networks by label propagation [J]. New Journal of Physics, 2010, 12(10): 103018.

LANCICHINETTI A, FORTUNATO S, KERTESZ J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New Journal of Physics, 2009, 11(3): 033015.

ZACHARY W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropological Research, 1977, 33(4): 452-473.

MAZUMDER R, HASTIE T, TIBSHIRANI R. Spectral regularization algorithms for learning large incomplete matrices [J]. J Mach Learn Res, 2010, 11(3): 2287-2322.

MA X K, GAO L, YONG X R, et al. Semi-supervised clustering algorithm for community structure detection in complex networks [J]. Physica: A, 2010, 389(1): 187-197.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Study on Indices of Network Structure Robustness and Their Application

Security Scheduling of Grid Tasks Based on the Discrete Particle Swarm Algorithm

A Local Community Detection Method Using Expansion of Influential Nodes Set

A Visibility Graph Information Fusion Method with Weighted Average

Bi-Level Multi-Obj ective Optimization of a Wind-Solar Coupled Hydrogen Production System Based on the Synergy of Hybrid Electrolyzer Arrays

Related Author

杜巍 1

蔡萌 1

杜海峰 2

朱海

王宇平

权义宁

王晓丽

Related Institution

School of Management, Xi'an Jiaotong University

Center for Administration and Complexity Science, Xi'an Jiaotong University

国家数字交换系统工程技术研究中心

School of Electronics and Information, Northwestern Polytechnical University

⁰