一种加权稠密子图社区发现算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61673249,61572005);山西省回国留学人员科研基金(2016-004,2017-014)


Community Detection Algorithm Based on Weighted Dense Subgraphs
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61673249, 61572005); Shanxi Scholarship Council of China (201 6-004, 2017-014)

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

    目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法(overlap community detection on weighted networks,简称OCDW).首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.

    Abstract:

    Most community detection algorithms in complex networks find communities based on topological structure of the network. Some important information is included in real network data, which represents data reliability or link closeness. Combined these prior information to detect communities might obtain better clustering results. An overlapping community detection on weighted networks (OCDW) is proposed in this study. Edge weight is defined by combining network topological structure and real information. Then, vertex weight is induced by edge weight. To obtain cluster, OCDW selects seed nodes according to vertex weight. After finding a cluster, edges in this cluster reduce their weights to avoid being selected as a seed node with high probability. Compared with some classical algorithms on 9 real networks including 5 unweighted networks and 4 weighted networks, OCDW shows a considerable or better performance on F-measure, accuracy, separation, NMI, ARI, modularity and time efficiency.

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

杨贵,郑文萍,王文剑,张浩杰.一种加权稠密子图社区发现算法.软件学报,2017,28(11):3103-3114

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-05-14
  • 最后修改日期:2017-06-16
  • 录用日期:
  • 在线发布日期: 2017-11-03
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号