基于KL-Ball的社区挖掘方法

Community Mining Based on KL-Ball

针对邻接矩阵的稀疏特性,采用KL散度来计算网络节点间的距离,提出了一种基于KL-Ball的社区挖掘方法。该方法中,一个KL-Ball代表一个社区,它从质心、半径、互信息及密度4个方面来描述社区,其中质心决定了社区在网络中的位置,半径刻画了社区所能覆盖的范围,互信息度量了社区中包含节点的一致性,密度反映了社区包含节点的数量。给定一个半径,期望从复杂网络中寻找具有低信息、高密度的社区,低信息使得社区包含的节点具有较强的一致性,高密度使得一个社区具有较强的凝聚性。为此,定义了一个基于KL-Ball的社区挖掘目标函数,给出它的优化算法,并从理论上证明了该算法的收敛性。依据社区半径的大小及质心的位置,该算法可应用于非重叠社区挖掘以及重叠社区挖掘。实验结果表明,基于KL-Ball的社区挖掘方法可有效地挖掘网络中蕴含的社区结构,包括非重叠的社区及重叠的社区。

This paper presents a new community mining method where each community is viewed as a KL-Ball,and the KL divergence is adopted to measure the distance between nodes in the sparse adjacency matrix.This paper defines the KL-Ball consisting of four aspects:center,radius,mutual information and density.The center determines the location of KL-Ball in the complex network,and the radius determines the region of KL-Ball.The mutual information is used to measure the consistency of objects in a community,and the density is adopted to measure the coherence of a community.Given a radius,we aim to find communities with lower-information and higher-density in the complex network.For this purpose,we define the community mining objective function based on KL-Ball.Then we propose an optimization algorithm to minimize the objective function and theoretically prove the convergence of it.The proposed algorithm adopts a flexible community mining framework,and can be applied to several kinds of community mining tasks based on different locations and regions of the KL-Balls,such as the traditional community mining,high precision community mining and overlapping community detection.The experiment results show that the proposed KL-Ball based method can effectively find the community structure in complex network,including non-overlapping and overlapping communities.