面向图表示社区检测的新型聚类覆盖算法

doi:10.3969/j.issn.0372-2112.2020.09.003

电子学报 ›› 2020, Vol. 48 ›› Issue (9): 1680-1687.DOI: 10.3969/j.issn.0372-2112.2020.09.003

面向图表示社区检测的新型聚类覆盖算法

陈洁^1,2, 李锐^1,2, 赵姝^1,2, 张燕平^1,2

1. 计算智能与信号处理教育部重点实验室, 安徽合肥 230601;
2. 安徽大学计算机科学与技术学院, 安徽合肥 230601

收稿日期:2019-09-25 修回日期:2020-04-06 出版日期:2020-09-25
- 作者简介:
- 陈洁女,1982年10月出生,安徽巢湖人.安徽大学副教授,硕士生导师.主要研究方向为机器学习,粒计算和三支决策.E-mail:chenjie200398@163.com
  李锐男,1996年9月出生,安徽定远人,安徽大学计算机科学与技术学院硕士生,主要研究方向为机器学习,社团发现.E-mail:lirui1101998040@163.com
  赵姝女,1979年10月出生,安徽巢湖人.安徽大学教授,博士生导师.主要研究方向机器学习,社交网络和粒计算.E-mail:zhaoshuzs2002@hotmail.com
  张燕平 女,1962年2月出生,安徽巢湖人.安徽大学教授,博士研究生导师.主要研究方向为机器学习和粒计算.E-mail:zhangyp2@163.com
- 基金资助:
- 国家自然科学基金项目 (No.61602003，No.61876001，No.61673020），国家社科基金重大项目 (No.18ZDA032）

A New Clustering Cover Algorithm Based on Graph Representation for Community Detection

CHEN Jie^1,2, LI Rui^1,2, ZHAO Shu^1,2, ZHANG Yan-ping^1,2

1. Key Laboratory of Intelligent Computing and Signal Processing, Ministry of Education, Anhui University, Hefei, Anhui 230601, China;
2. School of Computer Science and Technology, Anhui University, Hefei, Anhui 230601, China

Received:2019-09-25 Revised:2020-04-06 Online:2020-09-25 Published:2020-09-25
- Supported by:
- National Natural Science Foundation of China (No.61602003, No.61876001, No.61673020); Major Program of National Social Science Fund of China (No.18ZDA032)

摘要/Abstract

摘要： 图表示社区检测使用图表示方法学习网络节点的向量表示，然后对节点向量进行聚类获得社团结构.然而经典的聚类算法在聚类节点向量时，得到的结果往往不能够体现社区的特性.提出一种新型的聚类覆盖算法，将聚类所得覆盖视为社区划分结果.首先在节点向量空间中计算得到每个簇的覆盖中心；然后根据覆盖中心到同类样本的平均距离作为覆盖半径，在向量空间中形成覆盖；最后对未覆盖的点做二次划分得到社区结构.在多个有真实和无真实标签网络的实验表明，所提出的算法可以得到更合理的社区结果.

关键词: 社区发现, 图表示, 聚类, 覆盖算法

Abstract: Community detection based on graph representation learn nodes' vector representation, and then communities are obtained by clustering algorithm. However, when classical clustering algorithms often fail to reflect the characteristics of communities. Cluster cover algorithm (CCL) is proposed. CCL clusters nodes' vector into covers. A cover is viewed as a community. Firstly, the cover center of each cluster is calculated in the node vector space. Then, according to the average distance among the cover center and the same class samples as the cover radius, a cover is formed in the vector space. Finally, the nodes outside the covers are grouped into suitable cover to obtain community structure. Experiments with real and non-real tag networks show that the algorithm can get more reasonable community results.

Key words: community detection, graph represents, clustering, cover algorithm

中图分类号:

TP391

陈洁, 李锐, 赵姝, 等. 面向图表示社区检测的新型聚类覆盖算法[J]. 电子学报, 2020, 48(9): 1680-1687.

CHEN Jie, LI Rui, ZHAO Shu, et al. A New Clustering Cover Algorithm Based on Graph Representation for Community Detection[J]. Acta Electronica Sinica, 2020, 48(9): 1680-1687.

参考文献

[1] Newman M E J.Detecting community structure in networks[J].The European Physical Journal B,2004,38(2):321-330.
[2] Hartigan J A,Wong M A.Algorithm AS136:A k-means clustering algorithm[J].Journal of the Royal Statistical Society.Series C (Applied Statistics),1979,28(1):100-108.
[3] 张铃,张钹.多层前向网络的交叉覆盖设计算法[J].软件学报,1999,10(7):737-742. Zhang L,Zhang B.An alternative covering design algorithm of multi-layer neural networks[J].Journal of Software,1999.10(7):737-742.(in Chinese).
[4] Fortunato S,Hric D.Community detection in networks:A user guide[J].Physics Reports,2016,659:1-44.
[5] 张桂杰,张健沛,杨静,等.基于链接相似性聚类的重叠社区识别[J].电子学报,2015,43(7):1329-1335. Zhang GJ,Zhang JP,Yang J,et al.Overlapping community detection based on link similarity clustering[J].Acta Electronica Sinica,2015,43(7):1329-1335.(in Chinese).
[6] Li H J,Bu Z,Li A,et al.Fast and accurate mining the community structure:integrating center locating and membership optimization[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(9):2349-2362.
[7] DeMeo P,Ferrara E,Fiumara G,et al.Generalized Louvain method for community detection in large networks[A].Intelligent Systems Design and Applications[C].Cordoba,Spain:IEEE,2011.88-93.
[8] 於志勇,陈基杰,郭昆,等.基于影响力与种子扩展的重叠社区发现[J].电子学报,2019,47(01):155-162. Yu ZY,Chen JJ,Guo K,et al.Overlapping community detection based on influence and seeds extension[J].Acta Electronica Sinica,2019,47(01):155-162.(in Chinese).
[9] 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):036106-036118.
[10] Cui P,Wang X,Pei J,et al.A survey on network embedding[J].IEEE Transactions on Knowledge and Data Engineering,2018,31(5):833-852.
[11] Perozzi B,Al-Rfou R,Skiena S.Deepwalk:Online learning of social representations[A].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York:ACM,2014.701-710.
[12] Grover A,Leskovec J.node2vec:Scalable feature learning for networks[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Francisco:ACM,2016.855-864.
[13] 陶冶,张书奎,张力,等.移动感知器网络中基于随机游走和协作关系的任务分发算法[J].电子学报,2019,47(8):1601-1611. Tao Y,Zhang SK,Zhang L,et al.Task distribution algorithm based on random walk and cooperative relationship in mobile sensor networks[J].Acta Electronica Sinica,2019,47(8):1601-1611.(in Chinese).
[14] Wang D,Cui P,Zhu W.Structural deep network embedding[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Francisco:ACM,2016.1225-1234.
[15] 张铃,张钹.M-P神经元模型的几何意义及其应用[J].软件学报,1998,9(5):334-338. Zhang L,Zhang B.A geometrical representation of M-P neural model and its applications[J].Journal of Software,1998,9(5):334-338.(in Chinese).
[16] Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[17] Tian B,Li W.Community detection method based on mixed-norm sparse subspace clustering[J].Neurocomputing,2018,275:2150-2161.

面向图表示社区检测的新型聚类覆盖算法

A New Clustering Cover Algorithm Based on Graph Representation for Community Detection

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张少波, 原刘杰, 毛新军, 朱更明. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报, 2022, 50(9): 2181-2188.
[2]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[3]	王波, 王悦, 王伟, 侯嘉尧. 开放环境下自适应聚类优化包络的相机来源取证[J]. 电子学报, 2022, 50(8): 1840-1850.
[4]	钟沛龙, 黎明, 何超, 陈昊. 基于SOM聚类和自适应算子选择的高维多目标进化算法[J]. 电子学报, 2022, 50(8): 1959-1974.
[5]	李凯, 张可心. 结构α-熵的加权高斯混合模型的子空间聚类[J]. 电子学报, 2022, 50(3): 718-725.
[6]	汪禹宏, 张屹. 基于适应度指导交配限制策略的重组算子与多目标优化研究[J]. 电子学报, 2022, 50(3): 710-717.
[7]	路皓翔, 刘振丙, 张静, 王子民. 结合多尺度循环卷积和多聚类空间的红外图像增强[J]. 电子学报, 2022, 50(2): 415-425.
[8]	赵嘉, 王刚, 吕莉, 樊棠怀. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[J]. 电子学报, 2022, 50(11): 2730-2737.
[9]	高雷阜, 张梦瑶, 赵世杰. 融合簇边界移动与自适应合成的混合采样算法[J]. 电子学报, 2022, 50(10): 2517-2529.
[10]	江巨浪, 刘国明, 朱柱, 黄忠, 郑江云. 基于快速模糊聚类的动态多直方图均衡化算法[J]. 电子学报, 2022, 50(1): 167-176.
[11]	孟海宁, 冯锴, 朱磊, 张贝贝, 童新宇, 黑新宏. 基于Laplacian图谱的短文本聚类算法[J]. 电子学报, 2021, 49(9): 1716-1723.
[12]	张屹, 陆逸舟, 王帅, 陆曈曈. 基于多源交配选择策略的重组算子与多目标优化研究[J]. 电子学报, 2021, 49(9): 1754-1760.
[13]	李鹏, 闵慧, 罗爱静. 基于动态图的PPI网络构建和复合物挖掘算法研究[J]. 电子学报, 2021, 49(8): 1489-1497.
[14]	姜春茂, 赵书宝. 基于阴影集的多粒度三支聚类集成[J]. 电子学报, 2021, 49(8): 1524-1532.
[15]	廖彬, 黄静莱, 王鑫, 孙瑞娜, 葛晓燕, 国冰磊. SCEA:一种适应高维海量数据的并行聚类集成算法[J]. 电子学报, 2021, 49(6): 1077-1087.