一种有效的社会网络社区发现模型和算法

An Effective Model and Algorithm for Community Detection in Social Networks

社会网络的社区发现存在划分效果较好的算法时间复杂度过高、现有快速划分算法划分质量不佳、缺乏表达和充分利用个体和链接属性信息的模型和机制等问题.针对这些问题,提出了一种边稳定系数模型和一种能表达个体间关系紧密度的完全信息图模型,在此基础上设计和实现了一种有效的社区发现算法.提出的完全信息图模型具有较高通用性,适用于需要融合个体和链接属性的社区发现算法.通过系列实验表明,所提出的以边稳定系数模型和完全信息图为基础的算法,对社会网络中的社区发现问题是有效的.算法不仅具有较快的速度,也能适用于带权与不带权的网络,得到的社区划分结果也具有较高的划分质量.

In the research area of community detection in social network, there exist problems such as some algorithms with comparatively satisfactory detection result having high time complexity, current fast algorithms for large scale network resulting in low quality partition results, and lacking of model and mechanism to express and utilize actor and link attributes. To solve these problems, this paper proposes a model of edge stability coefficient and a model of complete information graph that can express the tightness of relation among actors, based on which an effective community detection algorithm is designed and implemented. The proposed model of complete information graph has high generality which makes it applicable to different community detection algorithms that need the input of fused information from actor and link attributes. Experiments show that the algorithm based on models of edge stability coefficient and complete information graph is effective to the problem of community detection in social networks with relatively less time cost. The algorithm is applicable to both weighted and unweighted networks with a comparatively fast speed and high quality partition result as well.