针对有向图的局部扩展的重叠社区发现算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

基金项目:


Overlapping Community Detection From Local Extension in Directed Graphs
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引 用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community, LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWS-OCD算法能够有效地发现带权无向图中的重叠社区。

    Abstract:

    Most of the previous research on community detection are mainly based on the undirected graph structures. However, in actual complex networks, the links relation usually shows the asymmetric characteristic or directionality, such as citation network of scientific papers, the one-way follow relationship on Twitter, and hyperlinks between web pages. Therefore, based on the propagation of informat ion and the direction of information transmission, a k-Path conception and calculation method for measuring the similarity of co-community neighboring is presented to weigh possibility of nodes in the same community. Furthermore, the method of transferring directed graphs into undirected graphs with similarity of weight is presented. Then the local extension algorithm of detecting overlapping community based on weighted undirected graphs is proposed. Several experiments on the real data sets are conducted and analyzed. Experimental results demonstrate that the k-Path conception can achieve the reasonable conversion for directed graph and improve the effectiveness of the community gathering nodes. Finally, the results show that the algorithm can detect the overlapping community effectively.

    参考文献
    相似文献
    引证文献
引用本文

张海燕,梁循,周小平.针对有向图的局部扩展的重叠社区发现算法[J].数据采集与处理,2015,30(3):683-693

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2015-07-31