采用链路聚类的动态网络社团发现算法

董哲; 伊鹏

doi:10.7652/xjtuxb201408013

您当前的位置：

首页 >

文章列表页 >

采用链路聚类的动态网络社团发现算法

更新时间：2025-07-09

- 采用链路聚类的动态网络社团发现算法
- A Community Detection Algorithm for Dynamic Networks Using Link Clustering
- 西安交通大学学报 2014年48卷第8期页码：73-79
- 作者机构：
  
  国家数字交换系统工程技术研究中心,郑州,450002
- 作者简介：
- 基金信息：
  
  : 2014-01-03。作者简介: 董哲(1989—),男,硕士生;伊鹏(通信作者),男,教授。基金项目: 国家“973计划”资助项目(2012CB315901,2013CB329104);国家“863计划”资助项目(2011AA01A103,2011AA01A101);国家科技支撑计划资助项目(2011BAH19B01)
- DOI：10.7652/xjtuxb201408013
  中图分类号： TP393
- 网络首发：2014-08-10，
  
  纸质出版：2014
- 稿件说明：
移动端阅览
董哲, 伊鹏. 采用链路聚类的动态网络社团发现算法[J]. 西安交通大学学报, 2014,48(8):73-79.

A Community Detection Algorithm for Dynamic Networks Using Link Clustering[J]. 2014, 48(8): 73-79.
董哲, 伊鹏. 采用链路聚类的动态网络社团发现算法[J]. 西安交通大学学报, 2014,48(8):73-79. DOI： 10.7652/xjtuxb201408013.

A Community Detection Algorithm for Dynamic Networks Using Link Clustering[J]. 2014, 48(8): 73-79. DOI： 10.7652/xjtuxb201408013.

摘要

针对当前基于节点的动态网络社团结构发现算法难以发现稳定的社团结构的问题

提出了一种采用链路聚类的动态网络社团发现算法(LDC)。该算法首先从链路的角度得到网络的链路图结构; 然后对比不同时刻的链路图结构

将动态网络中节点的添加与移除以及边的添加与移除等复杂的变化信息简化为链路添加和链路移除2种增量变化信息; 再在前一时刻社团结构的基础上以改进的链路划分密度函数对增量变化信息中变化的链路进行处理

判断该链路是否加入到社团中从而得到最优的社团结构; 最后将得到的链路社团转化成为最终的节点社团结构。实验结果表明

相比于当前基于节点的动态社团发现算法

LDC算法能够有效地发现网络中结构稳定的社团结构

其模块度值和标准化互信息值至少提高了0.19和0.13

且算法的运行效率要明显优于基于节点的动态社团发现算法。

Abstract

A community detection algorithm for dynamic networks is proposed to overcome the limitation that the current node-based dynamic community detection algorithm is difficult to identify the stable community structure. The algorithm uses link clustering technique and gets a link graph structure of the network

and then the complex incremental information in the dynamic network such as addition and removing of nodes and edges are simplified into addition and removing of links. An improved link partition density function is proposed to process a link in the incremental information and decide whether the link should be joined into the community based on the existing community structure to get the optimal community structure. At the end

the algorithm transforms the optimal link community structure into a node-based community structure. Experimental results and comparisons with the node-based community detection algorithm show that the algorithm can get the stable community structure and the modularity and NMI can raise at least 0.19 and 0.13

respectively

and that the efficiency of the algorithm is superior to the dynamic node-based community detection algorithms.

关键词

Keywords

references

汪小帆. 复杂网络中的社团结构分析算法研究综述[J]. 复杂系统与复杂性科学, 2008, 5(3): 1-12.

WANG Xiaofan. An overview of algorithms for analyzing community structure in complex networks[J]. Complex Systems and Complexity Science, 2008, 5(3): 1-12.

李晓佳, 张鹏, 狄增如, 等. 复杂网络中的社团结构[J]. 复杂系统与复杂性科学, 2008, 5(3): 19-42.

LI Xiaojia. ZHANG Peng, DI Zengru, et al. Community structure in complex networks[J]. Complex Systems and Complexity Science, 2008, 5(3): 19-42.

陈国强, 王宇平. 采用离散粒子群算法的复杂网络重叠社团检测[J]. 西安交通大学学报, 2013, 47(1): 107-113.

CHEN Guoqiang, WANG Yuping. Overlapping community detection of complex networks based on discrete particle swarm algorithm[J]. Journal of Xi'an Jiaotong University, 2013, 47(1): 107-113.

TANG L, LIU H, ZHANG J. Identifying evolving groups in dynamic multimode networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(1): 72-85.

TANTIPATHANANANDH C, BERGER-WOLF T, KEMNE D. A framework for community identification in dynamic social networks[C]∥Proceedings of the 13th ACM International Conference on Knowledge discovery and Data Mining. New York, USA: ACM, 2007: 717-726.

GONG M G, ZHANG L J, MA J, et al. Community detection in dynamic social networks based on multi-objective immune algorithm[J]. Journal of Computer Science and Technology, 2012, 27(3): 455-467.

NGUYEN N P, DINH T N, XUAN Y, et al. Adaptive algorithms for detecting community structure in dynamic social networks[C]∥Proceedings IEEE INFOCOM. Piscataway, NJ, USA: IEEE, 2011: 2282-2290.

LI D, DING Y, SHUAI X, et al. Adding community and dynamics to topic models[J]. Journal of Informetrics, 2012, 6(2): 237-253.

单波, 姜守旭, 张硕, 等. IC: 动态社会关系网络社区结构的增量识别算法[J]. 软件学报, 2009, 20(1): 184-192.

SHAN Bo, JIANG Shouxu, ZHANG Shuo, et al. IC: incremental algorithm for community identification in dynamic social network[J]. Journal of Software, 2009, 20(1): 184-192.

BASSETT D S, PORTER M A, WYMBS N F, et al. Robust detection of dynamic community structure in networks[EB/OL].[2013-03-14]. http:∥dx.doi.org/10.1063/1.4790830.

AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity in networks[J]. Nature, 2010, 466(7307): 761-764.

SHI C, CAI Y, FU D, et al. A link clustering based overlapping community detection algorithm[J]. Data Knowledge Engineering, 2013, 87(1): 394-404.

DINH T N, XUAN Y, THAI M T. Towards social-aware routing in dynamic communication networks[C]∥Proceedings of IEEE 28th International Conference on Performance Computing and Communications. Piscataway, NJ, USA: IEEE, 2009: 161-168.

YANG T, CHI Y, ZHU S, et al. Detecting communities and their evolutions in dynamic social networks: a Bayesian approach[J]. Machine Learning, 2011, 82(2): 157-189.

浏览量

下载量

CSCD

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

提交

工具集

关联资源

隧道内燃料电池汽车氢气泄漏扩散特性及影响因素

超临界水异常区域热力学特性研究

采用机器学习的大规模并行程序I/O性能建模与预测方法

EBSILON软件在热电联产系统优化中的应用综述

水蒸气掺混对氨裂解气旋流燃烧与排放特性的影响研究