Journal of Software:2017.28(11):3103-3114

(山西大学 计算机与信息技术学院, 山西 太原 030006;山西大学 计算机与信息技术学院, 山西 太原 030006;计算智能与中文信息处理教育部重点实验室(山西大学), 山西 太原 030006)
Community Detection Algorithm Based on Weighted Dense Subgraphs
YANG Gui,ZHENG Wen-Ping,WANG Wen-Jian,ZHANG Hao-Jie
(School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China;School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China;Key Laboratory of Computation Intelligence and Chinese Information Processing(Shanxi University), Ministry of Education, Taiyuan 030006, China)
Chart / table
Similar Articles
Article :Browse 949   Download 961
Received:May 14, 2017    Revised:June 16, 2017
> 中文摘要: 目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法(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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61673249,61572005);山西省回国留学人员科研基金(2016-004,2017-014) 国家自然科学基金(61673249,61572005);山西省回国留学人员科研基金(2016-004,2017-014)
Foundation items:National Natural Science Foundation of China (61673249, 61572005); Shanxi Scholarship Council of China (201 6-004, 2017-014)
Reference text:


YANG Gui,ZHENG Wen-Ping,WANG Wen-Jian,ZHANG Hao-Jie.Community Detection Algorithm Based on Weighted Dense Subgraphs.Journal of Software,2017,28(11):3103-3114