电子学报 ›› 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. 1. 计算智能与信号处理教育部重点实验室, 安徽合肥 230601;
    2. 安徽大学计算机科学与技术学院, 安徽合肥 230601
  • 收稿日期:2019-09-25 修回日期:2020-04-06 出版日期:2020-09-25 发布日期: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 Jie1,2, LI Rui1,2, ZHAO Shu1,2, ZHANG Yan-ping1,2   

  1. 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

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

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

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

中图分类号: