采用离散粒子群算法的复杂网络重叠社团检测

陈国强 1; 2; 王宇平 1

doi:10.7652/xjtuxb201301021

您当前的位置：

首页 >

文章列表页 >

采用离散粒子群算法的复杂网络重叠社团检测

更新时间：2025-07-09

- 采用离散粒子群算法的复杂网络重叠社团检测
- Overlapping Community Detection of Complex Networks Based on Discrete Particle Swarm Algorithm
- 西安交通大学学报 2013年47卷第1期页码：107-113
- 作者机构：
  
  1. 西安电子科技大学计算机学院,西安,710071
  2. 河南大学计算机与信息工程学院,河南,开封,475004
- 作者简介：
- 基金信息：
  
  : 2012-03-21。作者简介: 陈国强(1977-), 男, 博士生, 副教授;王宇平(通信作者), 男, 教授, 博士生导师。基金项目: 国家自然科学基金资助项目(61272119,61203372)
- DOI：10.7652/xjtuxb201301021
  中图分类号： TP393
- 网络首发：2013-01-10，
  
  纸质出版：2013
- 稿件说明：
移动端阅览
陈国强 1, 2, 王宇平 1. 采用离散粒子群算法的复杂网络重叠社团检测[J]. 西安交通大学学报, 2013,47(1):107-113.

Overlapping Community Detection of Complex Networks Based on Discrete Particle Swarm Algorithm[J]. 2013, 47(1): 107-113.
陈国强 1, 2, 王宇平 1. 采用离散粒子群算法的复杂网络重叠社团检测[J]. 西安交通大学学报, 2013,47(1):107-113. DOI： 10.7652/xjtuxb201301021.

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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

网络结构鲁棒性指标及应用研究

采用离散粒子群算法的网格任务安全级调度

采用影响力节点集扩展的局部社团检测

一种可视化的加权平均信息融合算法

融合物理信息与深度算子网络的变压器绕组热-流场快速计算方法