一种基于结构相似性的图聚类算法

doi:10.3969/j.issn.1006-2475.2016.03.005

计算机与现代化

一种基于结构相似性的图聚类算法

(山东理工大学计算机系，山东淄博 255049)

收稿日期:2015-12-22 出版日期:2016-03-17 发布日期:2016-03-17
作者简介:金超（1991-），男，山东泰安人，山东理工大学计算机系硕士研究生，研究方向：数据挖掘算法; 通信作者：张龙波（1968-），男，教授，博士，研究方向：数据库理论与应用，数据挖掘; 王海鹏（1980-），男，讲师，博士，研究方向：数据挖掘，生物信息学; 安建瑞（1990-），男，硕士研究生，研究方向：数据挖掘算法; 怀浩（1988-），男，硕士研究生，研究方向：数据挖掘算法; 王晓丹（1991-），女，硕士研究生，研究方向：数据挖掘算法。
基金资助:
山东省自然科学基金资助项目(ZR2014FQ024)

A Graph Clustering Algorithm Based on Structural Similarity

(Department of Computer Science, Shandong University of Technology, Zibo 255049, China)

Received:2015-12-22 Online:2016-03-17 Published:2016-03-17

摘要/Abstract

摘要： 图聚类是发现网络中潜在结构的一项重要任务。提出一种基于结构相似性的图聚类算法GNSCAN，给出该算法的相关定义以及算法的执行过程。采用真实数据集对该算法进行测试，从理论分析及结果2方面证明GNSCAN算法在效率上比GN算法得到明显的提高。在GNSCAN算法的基础上，提出一种改进的GNSCAN算法IGNSCAN，算法时间复杂度得到进一步降低。

关键词: 社区发现, 社会网络, GNSCAN算法, 结构相似性

Abstract: Network clustering (or graph partitioning) is an important task for the discovery of underlying structures in networks. In this paper, a fast algorithm named GNSCAN based on structure similarity is proposed, and the related definition and algorithm implementation process are given. In order to test the performance of the algorithm, a group of real datasets are used to test the algorithm. The theoretical analysis and experimental results show that the proposed GNSCAN algorithm is improved in efficiency. On the basis of the above GNSCAN algorithm, IGNSCAN is proposed. And the computation complexity of the algorithm IGNSCAN is more efficiency.

Key words: community discovery, social network, GNSCAN algorithm, structural similarity

中图分类号:

TP391

金超，张龙波，王海鹏，安建瑞，怀浩，王晓丹. 一种基于结构相似性的图聚类算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2016.03.005.

JIN Chao, ZHANG Long-bo, WANG Hai-peng, AN Jian-rui, HUAI Hao, WANG Xiao-dan. A Graph Clustering Algorithm Based on Structural Similarity[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.03.005.

参考文献

[1] Flake G W, Tarjan R E, Tsioutsiouliklis K. Graph clustering and minimum cut trees[J]. Internet Mathematics, 2003,1(4):385-408.

[2] Beineke L W, Wilson R J. Topics in Algebraic Graph Theory[M]. Cambridge University Press, 2004:276.

[3] Yang Bo, Cheung W K, Liu Jiming. Community mining from signed social networks[J]. IEEE Transactions on Knowledge & Data Engineering, 2007,19(10):1333-1348.

[4] 沈华伟,程学旗,陈海强,等. 基于信息瓶颈的社区发现[J]. 计算机学报, 2008,31(4):677-686.

[5] 黄发良,张师超,朱晓峰. 基于多目标优化的网络社区发现方法[J]. 软件学报, 2013,24(9):2062-2077.

[6] 段炼,朱欣焰. 基于社区时空主题模型的微博社区发现方法[J]. 电子科技大学学报, 2014,43(3):464-469.

[7] McDaid A F, Murphy T B, Friel N, et al. Model-based clustering in networks with stochastic community finding[C]// COMPSTAT 2012 Proceedings. 2012.

[8] Chen Dongming, Dong Yanlin, Huang Xinyu, et al. A community finding method for weighted dynamic online social network based on user behavior[J]. International Journal of Distributed Sensor Networks, 2015,2015: Article No. 97.

[9] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002,99(12):7821-7826.

[10] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004,69(6):279-307.

[11] Xu Xiaowei, Yuruk N, Feng Zhidan, et al. SCAN: A structural clustering algorithm for networks[C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2007:824-833.

[12] Zhao Weizhong, Martha V, Xu Xiaowei. PSCAN: A parallel structural clustering algorithm for big networks in MapReduce[C]// Proceedings of the 27th IEEE International Conference on Advanced Information Networking and Applications (AINA). 2013:862-869.

[13] Zhang Huijuan, Sun Shixuan. A graph clustering algorithm based on shared neighbors and connectivity[C]// Proceedings of the 8th IEEE International Conference on Computer Science & Education (ICCSE). 2013:761-764.

[14] 吴烨,钟志农,熊伟,等. 一种高效的属性图聚类方法[J]. 计算机学报, 2013,36(8):1704-1713.

[15] 冷泳林,鲁富宇. 基于MapReduce的SimRank算法在图聚类中的应用[J]. 电子设计工程, 2015,23(6):9-11.

[16] Tabrizi S A, Shakery A, Asadpour M, et al. Personalized pageRank clustering: A graph clustering algorithm based on random walks[J]. Physica A: Statistical Mechanics & Its Applications, 2013,392(22):5772-5785.

[17] Newman M E J. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2012,8(1):25-31.

一种基于结构相似性的图聚类算法

A Graph Clustering Algorithm Based on Structural Similarity

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

[1]	舒鹏, 杜庆伟. 一种融合多维信息的移动社区发现方法[J]. 计算机与现代化, 2021, 0(05): 88-92.
[2]	许小媛, 李海波, 于本成, 刘芳. 具有对偶约束的半监督重叠社区发现方法[J]. 计算机与现代化, 2020, 0(08): 63-68.
[3]	熊永芳,林友芳,武志昊. 带层次网络结构的业务系统层次组织结构发现[J]. 计算机与现代化, 2019, 0(07): 88-.
[4]	张勤1,2，贾渊1，王耀彬1. 基于稀疏特征点的零件图像拼接方法[J]. 计算机与现代化, 2019, 0(02): 19-.
[5]	杨梓舒. 基于模体的社会网络特征分析[J]. 计算机与现代化, 2017, 0(8): 36-.
[6]	陈立虎，林友芳，武志昊，景丽萍. 一种基于层次约简的多层网络社区发现算法[J]. 计算机与现代化, 2017, 0(6): 84-90.
[7]	梁智学;齐立磊. 基于iPhone平台的航班LBS系统[J]. 计算机与现代化, 2013, 1(9): 121-125.
[8]	黄国伟;陈志. 基于社会网络的两阶段垃圾邮件过滤方法[J]. 计算机与现代化, 2013, 1(7): 43-046,.
[9]	杨静;王靖. 基于聚类分析检索团伙多起犯罪的迭代算法 [J]. 计算机与现代化, 2013, 1(1): 1-4.
[10]	张韦全;陈京民. 基于社会网络挖掘的微博参政群体实证研究[J]. 计算机与现代化, 2012, 1(201): 67-70.
[11]	孙祯桢;渠文博;倪奕. 科学家、组织与技术及其关系的社会网络分析[J]. 计算机与现代化, 2012, 1(11): 158-161.