一种基于广度优先搜索的社区发现方法

A Community Discovery Method Based on Breadth-First-Search

由于当前的算法不能很好地将网络的联通性和单个节点的属性综合考虑,分析了凝聚和分裂层次聚类经典算法的局限性,从而给出边的载荷、边的权重、连接度门限、图形分割等定义.综合考虑网络的拓扑结构和边的权重关系,提出了基于广度优先搜索的社会网络社区发现算法SoNetCD.算法通过删除社区之间的边而得到社区结构,它对社区之间的边判断准确,对社区内部的边误删率低.运用经典数据集进行实验的结果表明,该算法具有比经典GN算法更好的结果.

In view of the existing algorithm that is unable to take better account of the network connectivity and the attributes of individual nodes comprehensively,the limitation of the typical algorithms of agglomerative and divisive clustering was analyzed,thus defining conceptually the edge loading,edge weight,connectivity threshold and graph segmentation.Then,a new algorithm SoNetCD based on BFS（breadth-first-search）is presented for discovering the communities in social networks,which takes both network topology and edge weight into consideration.Inter-community edges are cancelled to reveal the community structure in the algorithm,thus judging exactly the inter-community and lowering the failure rate of cancelling inner-community edges.Experimental results of a real-world social network dataset showed that the SoNetCD outperforms the typical GN algorithm in identifying community structure.