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

Community Detection Algorithm Based on Weighted Dense Subgraphs

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

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.