基于贡献函数的重叠社区划分算法

发布时间：2018-11-15 10:43

【摘要】：现实世界中的网络结构呈现出重叠社区的特征。在研究经典的标签算法的基础上,该文提出基于贡献函数的重叠社区发现算法。算法将每个节点用三元组(阈值、标签、从属系数)集合来表示。节点的阈值是每次迭代过程中标签淘汰的依据,该值由多元线性方程自动计算而来。从属系数用于衡量当前节点与标签所标识社区的相关度,从属系数的值越大说明该节点与标签所标识社区的关联性越强。在每一次迭代的过程中,算法依据贡献函数计算每个节点的从属系数,并生成新的三元组集合。然后依据标签决策规则淘汰标签,进行从属系数规范化。通过对真实的复杂网络和LFR(Lancichinetti Fortunato Radicchi)自动生成的网络进行测试可知,该算法的社区划分准确率高,而且划分结果稳定。
[Abstract]:The network structure in the real world is characterized by overlapping communities. Based on the study of classical label algorithms, this paper proposes an overlapping community discovery algorithm based on contribution function. Each node is represented by a set of triples (threshold, label, subordinate coefficient). The threshold of nodes is the basis of label elimination in each iteration process, which is automatically calculated by multivariate linear equations. The dependency coefficient is used to measure the correlation between the current node and the community identified by the label, and the greater the value of the subordinate coefficient is, the stronger the correlation between the node and the community identified by the label is. In each iteration, the algorithm calculates the subordinate coefficients of each node according to the contribution function, and generates a new set of triples. Then the label is eliminated according to the label decision rule, and the subordinate coefficient is standardized. By testing the real complex network and the network generated automatically by LFR (Lancichinetti Fortunato Radicchi), it can be seen that the algorithm has high accuracy of community partition, and the result of partition is stable.
【作者单位】：上海交通大学电子信息与电气工程学院;
【基金】：国家973关键技术研究项目(2013CB329603) 国家自然科学基金(61472248)~~
【分类号】：O157.5;TP301.6

【相似文献】