基于采样的大规模图聚类分析算法

doi:10.3969/j.issn.0372-2112.2019.08.017

电子学报 ›› 2019, Vol. 47 ›› Issue (8): 1731-1737.DOI: 10.3969/j.issn.0372-2112.2019.08.017

基于采样的大规模图聚类分析算法

张建朋^1,2, 陈鸿昶¹, 王凯¹, 祝凯捷^1,2, 王亚文¹

1. 国家数字交换系统工程技术研究中心, 河南郑州 450000;
2. 荷兰埃因霍温理工大学计算机系, 荷兰北布拉邦省 5600 MB

收稿日期:2017-10-09 修回日期:2018-06-10 出版日期:2019-08-25
- 作者简介:
- 张建朋 男,1988年3月出生于河北省廊坊市.现为国家数字交换系统工程技术研究中心助理研究员,埃因霍温理工大学博士研究生.主要研究方向为大数据分析.E-mail:j.zhang.4@tue.nl;陈鸿昶 男,1964年4月出生于河南省密县.国家数字交换系统工程技术研究中心教授.主要研究方向为电信网信息关防.E-mail:chenhongchang@ndsc.com.cn;王凯男,1980年01月出生于河南许昌.国家数字交换系统工程技术研究中心副研究员.主要研究方向为电信网信息关防.E-mail:wangkai@ndsc.com.cn;祝凯捷 男,1991年01月出生于河南省郑州市.现为埃因霍温理工大学博士研究生.主要研究方向为图数据库基础.E-mail:kaijie.ndsc@gmail.com;王亚文 男,1990年8月出生于河南省郑州市.现为国家数字交换系统工程技术研究中心博士研究生.主要研究方向为计算机视觉.E-mail:15738321455@163.com
- 基金资助:
- 国家自然科学基金群体项目 (No.61521003）; 国家重点研发计划项目 (No.2016YFB0800101）

A Sampling-Based Graph Clustering Algorithm for Large-Scale Networks

ZHANG Jian-peng^1,2, CHEN Hong-chang¹, WANG Kai¹, ZHU Kai-jie^1,2, WANG Ya-wen¹

1. National Digital Switching System Engineering & Technological R & D Center, Zhengzhou Henan 450000, China;
2. Dept of Computer Science, Technology University of Eindhoven, Eindhoven 5600 MB, Netherland

Received:2017-10-09 Revised:2018-06-10 Online:2019-08-25 Published:2019-08-25
- Supported by:
- NSFC Innovation Research Group (No.61521003); Program of National Key Research and Development Program of China (No.2016YFB0800101)

摘要/Abstract

摘要： 针对当前聚类方法（例如经典的GN算法）计算复杂度过高、难以适用于大规模图的聚类问题，本文首先对大规模图的采样算法展开研究，提出了能够有效保持原始图聚类结构的图采样算法（Clustering-structure Representative Sampling，CRS），它能在采样图中产生高质量的聚类代表点，并根据相应的扩张准则进行采样扩张.此采样算法能够很好地保持原始图的内在聚类结构.其次，提出快速的整体样本聚类推断（Population Clustering Inference，PCI）算法，它利用采样子图的聚类标签对整体图的聚类结构进行推断.实验结果表明本文算法对大规模图数据具有较高的聚类质量和处理效率，能够很好地完成大规模图的聚类任务.

关键词: 大规模图, 图采样, 图聚类, 整体推断, 聚类代表点, 扩张准则

Abstract: Since computational complexities of the existing methods such as classic GN algorithm are too costly to cluster large-scale graphs, this paper studies sampling algorithms of large-scale graphs, and proposes a clustering-structure representative sampling (CRS) which can effectively maintain the clustering structure of original graphs. It can produce high quality clustering-representative nodes in samples and expand according to the corresponding expansion criteria. Then, we propose a fast population clustering inference (PCI) method on the original graphs and deduce clustering assignments of the population using the clustering labels of the sampled subgraph. Experiment results show that in comparison with state-of-the-art methods, the proposed algorithm achieves better efficiency as well as clustering accuracy on large-scale graphs.

Key words: large-scale graphs, graph sampling, graph clustering, population inference, clustering representative nodes, expansion criteria

中图分类号:

TP181

张建朋, 陈鸿昶, 王凯, 等. 基于采样的大规模图聚类分析算法[J]. 电子学报, 2019, 47(8): 1731-1737.

ZHANG Jian-peng, CHEN Hong-chang, WANG Kai, et al. A Sampling-Based Graph Clustering Algorithm for Large-Scale Networks[J]. Acta Electronica Sinica, 2019, 47(8): 1731-1737.

参考文献

[1] Strogatz S H.Exploring complex networks[J].Nature,2001,410(6825):268-276.
[2] Boccaletti S,Ivanchenko M,Latora V,et al.Detecting complex network modularity by dynamical clustering[J].Physical Review E,2007,75(4):45102.
[3] Newman M E,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):26113.
[4] Newman M E.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):66133.
[5] Blondel V D,Guillaume J,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,no.10:P10008.
[6] Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):36106.
[7] Jeong H,Tombor B,Albert R,et al.The large-scale organization of metabolic networks[J].Nature,2000,407(6804):651-654.
[8] 崔颖安,李雪,王志晓,张德运.社会化媒体大数据多阶段整群抽样方法[J].软件学报,2014,(4):781-796. Cui Ying-An,Li Xue,Wang Zhi-Xiao,Zhang De-Yun.Sampling online social media big data based multi stage cluster method[J].Journal of Software,2014,(4):781-796.(in Chinese)
[9] 张新猛,蒋盛益.基于核心图增量聚类的复杂网络划分算法[J].自动化学报,2013,39(7):1117-1125. Zhang Xin-meng,Jiang Sheng-yi.Complex network community detection based on core graph incremental clustering[J].Acta Automatica Sinica,2013,39(7):1117-1125.(in Chinese)
[10] Hübler C,Kriegel H,Borgwardt K,et al.Metropolis algorithms for representative subgraph sampling[A].Eighth IEEE International Conference on Data Mining[C],Pisa,Italy:IEEE,2008.
[11] Hastings W K.Monte Carlo sampling methods using Markov chains and their applications[J].Biometrika,1970,57(1),97-109.
[12] Salehi M,Rabiee H R,Rajabi A.Sampling from complex networks with high community structures[J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2012,22(2):023126.
[13] Ahmed N K,Neville J,Kompella R.Network sampling:from static to streaming graphs[J].ACM Transactions on Knowledge Discovery from Data (TKDD),2014,8(2):7.
[14] Leskovec J,Faloutsos C.Sampling from large graphs[A].Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Philadelphia,USA:ACM,2006.
[15] Lovász L.Random walks on graphs[J].Combinatorics,PaulErdos is Eighty,1993,2(1-46):4.
[16] Fortunato S,Hric D.Community detection in networks:a user guide[J].Physics Reports,2016,659:1-44.
[17] Maiya A S,Berger-Wolf T Y.Sampling community structure[A].Proceedings of the 19th International Conference on World Wide Web[C].NC,USA:ACM,2010.
[18] Mall R,Langone R,Suykens J A.FURS:fast and unique representative subset selection retaining large-scale community structure[J].Social Network Analysis and Mining,2013,3(4):1075-1095.
[19] Khorasgani R R,Chen J,Zaiane O R.Top leaders community detection approach in information networks[A].4th SNA-KDD Workshop on Social Network Mining and Analysis[C].Washington DC,USA:ACM,2010.
[20] Yang J,Leskovec J.Overlapping community detection at scale:a nonnegative matrix factorization approach[A].Proceedings of the 6th ACM International Conference on Web Search and Data Mining[C].Rome,Italy:ACM,2013.
[21] Benson,A.R.,Gleich,D.F.,& Leskovec,J.Higher-order organization of complex networks[J].Science,2016,353(6295),163-166.
[22] Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.

基于采样的大规模图聚类分析算法

A Sampling-Based Graph Clustering Algorithm for Large-Scale Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

[1]	李来, 刘光灿, 孙玉宝, 刘青山. 各向同性的迭代量化哈希算法[J]. 电子学报, 2017, 45(7): 1707-1714.
[2]	丁琳琳, 李正道, 纪婉婷, 宋宝燕. 基于改进哈夫曼编码的大规模动态图可达查询方法[J]. 电子学报, 2017, 45(2): 359-367.