一种加权稠密子图社区发现算法

发布时间：2018-02-14 06:41

本文关键词： 复杂网络社区发现图聚类重叠聚类稠密子图　出处：《软件学报》2017年11期 　论文类型：期刊论文

【摘要】：目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法(overlap community detection on weighted networks,简称OCDW).首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.
[Abstract]:At present, community discovery algorithms for complex networks are mostly based on the topology of the network to determine the community. However, the edges of complex networks may be weighted to indicate the degree of connection tightness or the significance of credibility. This priori information is very important to the accuracy of community discovery. In order to solve this problem, an overlap community detection on weighted networks algorithm based on weighted dense subgraph is proposed. Considering the influence of network topology and the influence of edge weight in real network, a method of defining edge weight in network is given, and the selection method of seed node and the strategy of weight updating are given. Finally, we get the clustering result. OCDW algorithm is applicable in both weighted and unweighted networks. By comparing with some classical community discovery algorithms on nine real network data sets, the results show that the algorithm OCDW is in F metric, accuracy, separation degree. Standard mutual information, adjustment of Rand coefficient, modularity and running time all show good performance.
【作者单位】：山西大学计算机与信息技术学院;山西大学计算智能与中文信息处理教育部重点实验室;
【分类号】：O157.5;TP301.6

【相似文献】