一种基于增量式谱聚类的动态社区自适应发现算法

蒋盛益; 杨博泓; 王连喜

doi:10.16383/j.aas.2015.c150290

一种基于增量式谱聚类的动态社区自适应发现算法

doi: 10.16383/j.aas.2015.c150290

蒋盛益^1,3,
杨博泓^1, ,,
王连喜^2,3

1.
广东外语外贸大学思科信息学院广州 510006;
2.
广东外语外贸大学图书馆广州 510420;
3.
语言工程与计算广东省社会科学重点实验室广州 510006

基金项目:

国家自然科学基金(61572145),教育部人文社会科学研究青年项目(14YJC870021),广东省科技计划项目(2014A040401083,2015A030401093),广东省普通高校科技创新项目(2012KJCX0049),广东外语外贸大学研究生科研创新项目(15GWCXXM-40),广东大学生科技创新培育专项资金(308-GK151018)资助

详细信息

作者简介:
蒋盛益广东外语外贸大学思科信息学院教授. 主要研究方向为数据挖掘、文本挖掘和用户关系挖掘.E-mail: jaingshengyi@163.com

通讯作者:
杨博泓广东外语外贸大学思科信息学院硕士研究生.主要研究方向为用户关系挖掘和个性化推荐.本文通信作者.

计量
- 文章访问数: 1797
- HTML全文浏览量: 99
- PDF下载量: 1984
- 被引次数: 0
出版历程
- 收稿日期: 2015-05-15
- 修回日期: 2015-09-06
- 刊出日期: 2015-12-20

An Adaptive Dynamic Community Detection Algorithm Based on Incremental Spectral Clustering

1.
School of Informatics, Guangdong University of Foreign Studies, Guangzhou 510006;
2.
Guangdong University of Foreign Studies Library, Guangzhou 510420;
3.
Social Science Key Laboratory of Language Engineering and Computing of Guangdong Province, Guangzhou 510006

Funds:

Supported by National Natural Science Foundation of China (61572145), Youth Project of Humanities and Social Sciences of the Ministry of Education (14YJC870021), Science and Technology Project of Guangdong Province (2014A040401083, 2015A030401093), Science and Technology Innovation Project of Guangdong Province (2012KJCX0049), Guangdong University of Foreign Studies Graduate Student Research Innovation Project (15GWCXXM-40), Guangdong College Students' Scientific and Technological Innovation to Cultivate Special Funds (308-GK151018)

摘要

摘要: 针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.
- 谱聚类 /
- 拉普拉斯矩阵 /
- 拉普拉斯本征分析 /
- 增量聚类 /
- 社区检测 /
- 动态社区
Abstract: To tackle the hot issue of dynamic community detection in complex networks, this paper proposes an adaptive dynamic community detection algorithm based on the spectral clustering algorithm of linear link-related approach for static community detection and the incremental spectral clustering. The dynamic community detection algorithm uses the normalized Laplacian matrix to present the relationships of the complex network nodes, and then uses the Laplacian eigen map to map the node into the k-dimensional Euclidean space. In order to solve the problems of the outliers to nodes and the heuristics to identify the number of communities, this paper applies the spectral clustering algorithm of linear link-related approach to detect the community structure of the initial time slice, which makes the process of the complex community detection in an adaptive and computationally inexpensive way. For the subsequent adjacent time slices, the incremental spectral clustering algorithm of this paper aims to detect the dynamic community of complex network adaptively by clustering results for the next time slice based on the foundation of community characteristics of the previous time slice, and adjusting the spectral clustering algorithm of linear link-related approach. Experimental results on a series of datasets show that the spectral clustering algorithm of linear link-related approach can detect the community structure in the complex networks effectively and that the adaptive dynamic community detection algorithm based on incremental spectral clustering can also mine the evolution of dynamic communities effectively.
- Spectral clustering /
- Laplacian matrix /
- Laplacian eigen analysis /
- incremental clustering /
- community detection /
- dynamic community

HTML全文

参考文献(40)

[1]	Fortunato S. Community detection in graphs. Physics Reports, 2010, 486(3-5): 75-174
[2]	Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826
[3]	Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Physical Review E, 2004, 70(6): 066111
[4]	Blondel V D, Guillaume J L, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008
[5]	Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007, 76(3): 036106
[6]	Xin Yu, Yang Jing, Xie Zhi-Qiang. An overlapping semantic community structure detecting algorithm by label propagation. Acta Automatica Sinica, 2014, 40(10): 2262-2275(辛宇, 杨静, 谢志强. 基于标签传播的语义重叠社区发现算法. 自动化学报, 2014, 40(10): 2262-2275)
[7]	Palla G, Derényi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818
[8]	Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 2006, 74(3): 036104
[9]	Hopcroft J, Khan O, Kulis B, Selman B. Tracking evolving communities in large linked networks. Proceedings of the national academy of sciences of the United States of America, 2004, 101(Suppl 1): 5249-5253
[10]	Palla G, Barabási A L, Vicsek T. Quantifying social group evolution. Nature, 2007, 446(7136): 664-667
[11]	Mucha P J, Richardson T, Macon K, Porter M A, Onnela J P. Community structure in time-dependent, multiscale, and multiplex networks. Science, 2010, 328(5980): 876-878
[12]	Chi Y, Song X D, Zhou D Y, Hino K, Tseng B L. Evolutionary spectral clustering by incorporating temporal smoothness. In: Proceedings of the 13th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining. New York, NY, USA: ACM, 2007. 153-162
[13]	Kim M S, Han J W. A particle-and-density based evolutionary clustering method for dynamic networks. Proceedings of the VLDB Endowment, 2009, 2(1): 622-633
[14]	Sarkar P, Moore A W. Dynamic social network analysis using latent space models. ACM SIGKDD Explorations Newsletter, 2005, 7(2): 31-40
[15]	Lin Y R, Chi Y, Zhu S H, Sundaram H, Tseng B L. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In: Proceedings of the 17th International Conference on World Wide Web. New York, NY, USA: ACM, 2008. 685-694
[16]	Zhang H Z, Qiu B J, Giles C L, Foley H C, Yen J. An LDA-based community structure discovery approach for large-scale social networks. In: Proceedings of the 2007 IEEE Intelligence and Security Informatics. New Brunswick, NJ, Canada: IEEE, 2007. 200-207
[17]	Zhang H Z, Giles C L, Foley H C, Yen J. Probabilistic community discovery using hierarchical latent Gaussian mixture model. In: Proceedings of the 22nd AAAI Conference on Artificial Intelligence. Vancouver, British Columbia, Canada: AAAI, 2007. 663-668
[18]	Hofman J M, Wiggins C H. Bayesian approach to network modularity. Physical Review Letters, 2008, 100(25): 258701
[19]	Xu T B, Zhang Z F, Yu P S, Long B. Evolutionary clustering by hierarchical dirichlet process with hidden Markov state. In: Proceedings of the 8th IEEE International Conference on Data Mining, 2008 (ICDM'08). Pisa, Italy: IEEE, 2008. 658-667
[20]	Xu T B, Zhang Z F, Yu P S, Long B. Generative models for evolutionary clustering. ACM Transactions on Knowledge Discovery from Data, 2010, 6(2): 681-690
[21]	Airoldi E M, Blei D M, Fienberg S E, Xing E P. Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 2009, 9(5): 1981-2014
[22]	Ho Q R, Song L, Xing E P. Evolving cluster mixed-membership blockmodel for time-evolving networks. In: Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. Fort Lauderdale, FL, USA: AISTATS, 2011. 342-350
[23]	Hartmann T, Kappes A, Wagner D. Clustering evolving networks. arXiv preprint arXiv: 1401.3516, 2014.
[24]	Lee P, Lakshmanan L V S, Milios E E. Incremental cluster evolution tracking from highly dynamic network data. In: Proceedings of the 30th International Conference on Data Engineering (ICDE) . Chicago, IL, USA: IEEE, 2014. 3-14
[25]	Golub G H, van Loan C F. Matrix Computations (Fourth edition). Baltimore, USA: JHU Press, 2012.
[26]	Shen H W, Cheng X Q. Spectral methods for the detection of network community structure: a comparative analysis. Journal of Statistical Mechanics: Theory and Experiment, 2010, 2010(10): P10020
[27]	Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113
[28]	Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4): 452-473
[29]	Lusseau D. The emergent properties of a dolphin social network. Proceedings of the Royal Society of London. Series B: Biological Sciences, 2003, 270(Suppl 2): S186-S188
[30]	Gleiser P M, Danon L. Community structure in jazz. Advances in Complex Systems, 2003, 6(4): 565-573
[31]	He Dong-Xiao, Zhou Xu, Wang Zuo, Zhou Chun-Guang, Wang Zhe, Jin Di. Community mining in complex networks-clustering combination based genetic algorithm. Acta Automatica Sinica, 2010, 36(8): 1160-1170(何东晓, 周栩, 王佐, 周春光, 王喆, 金弟. 复杂网络社区挖掘—基于聚类融合的遗传算法. 自动化学报, 2010, 36(8): 1160-1170)
[32]	Adamic L A, Glance N. The political blogosphere and the 2004 U.S. election: divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery. New York, NY, USA: ACM, 2005. 36-43
[33]	Guimerá R, Danon L, Díaz-Guilera A, Giralt F, Arenas A. Self-similar community structure in a network of human interactions. Physical Review E, 2003, 68(6): 065103
[34]	Jeong H, Mason S P, Barabási A L, Oltvai Z N. Lethality and centrality in protein networks. Nature, 2001, 411(6833): 41-42
[35]	Sun J M, Faloutsos C, Papadimitriou S, Yu P S. GraphScope: parameter-free mining of large time-evolving graphs. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA: ACM, 2007. 687-696
[36]	Grinstein G, Plaisant C, Laskowski S, O'Connell T, Scholtz J, Whiting M. VAST 2008 challenge: introducing mini-challenges. In: Proceedings of 2008 IEEE Symposium on Visual Analytics Science and Technology (VAST'08). Columbus, OH, USA: IEEE, 2008.
[37]	Liu Xu, Yi Dong-Yun. Complex network community detection by local similarity. Acta Automatica Sinica, 2011, 37(12): 1520-1529(刘旭, 易东云. 基于局部相似性的复杂网络社区发现方法. 自动化学报, 2011, 37(12): 1520-1529)
[38]	Reichardt J, Bornholdt S. Statistical mechanics of community detection. Physical Review E, 2006, 74(1): 016110
[39]	Nguyen N P, Dinh T N, Xuan Y, Thai M T. Adaptive algorithms for detecting community structure in dynamic social networks. In: Proceedings of the 2011 Proceedings IEEE INFOCOM. Shanghai, China: IEEE, 2011. 2282-2290
[40]	Dinh T N, Xuan Y, Thai M T. Towards social-aware routing in dynamic communication networks. In: Proceedings of the 28th International Performance Computing and Communications Conference (IPCCC). Scottsdale, AZ, USA: IEEE, 2009. 161-168