作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2019, Vol. 45 ›› Issue (6): 140-145. doi: 10.19678/j.issn.1000-3428.0050734

• 移动互联与通信技术 • 上一篇    下一篇

边异质网络中的社区结构发现算法

王思檬,曹佳   

  1. 北京林业大学 信息学院,北京 100083
  • 收稿日期:2018-03-12 出版日期:2019-06-15 发布日期:2019-06-15
  • 作者简介:王思檬(1993—),女,硕士研究生,主研方向为复杂网络、数据处理;曹佳,副教授。
  • 基金资助:

    国家自然科学基金(61602042);中央高校基本科研业务费专项资金(YX2013-29)。

Community structure detection algorithm for heterogeneous edge network

WANG Simeng,CAO Jia   

  1. School of Information Science and Technology,Beijing Forestry University,Beijing 100083,China
  • Received:2018-03-12 Online:2019-06-15 Published:2019-06-15

摘要:

为解决社区结构发现算法功能社区与拓扑社区不一致的问题,提出一种基于边类型相似性聚类(TESC)的社区结构发现算法。该算法以局部拓扑特征与异质信息为目标进行节点聚类,基于节点邻接边类型构造网络节点之间的相似矩阵,从而获取边异质信息。在该相似矩阵的基础上,通过传统层次聚类的思想将相似度大的节点进行合并,进而利用轮廓系数优化社区数量,得到最终社区划分结果。选取社区结构已知的4个真实网络和6个人工合成基准LFR网络,通过与同质网络的GN、Louvain算法以及异质网络的Hete-SPAEM、Hetero-Attractor算法对比,结果表明TESC算法获得的社区结构更接近于网络实际社区结构。

关键词: 复杂网络, 异质网络, 社区发现, 聚类, 边异质

Abstract:

In order to solve the problem that topological communities gotten by community structure detection algorithms are not same with the functional communities,a community structure detection algorithm based on Typed-Edge Similarity Clustering(TESC) is proposed.The algorithm clusters nodes with local topological features and heterogeneous information,and constructs similarity matrices between network nodes based on node neighboring edge types to obtain heterogeneous edge information.On the basis of the similarity matrix,the nodes with large similarity are continuously merged by the idea of traditional hierarchical clustering,and then the number of communities is optimized by using the contour coefficients to obtain the final community division result.Selecting 4 real networks with known community structure and 6 artificial synthetic LFR benchmark networks,comparing with GN,Louvain algorithm of homogeneous network and Hete-SPAEM and Hetero-Attractor algorithms of heterogeneous network,the results show that the community structure obtained by the TESC algorithm are more consistent with the actual community of the network.

Key words: complex network, heterogeneous network, community detection, clustering, heterogeneous edge

中图分类号: