东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2010, Vol. 31 ›› Issue (3): 346-349.DOI: -

• 论著 • 上一篇    下一篇

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

陈东明;徐晓伟;   

  1. 东北大学软件学院;阿肯色大学(小石城)信息科学系;
  • 收稿日期:2013-06-20 修回日期:2013-06-20 发布日期:2013-06-20
  • 通讯作者: -
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(60872040);;

A community discovery method based on breadth-first-search

Chen, Dong-Ming (1); Xu, Xiao-Wei (2)   

  1. (1) School of Software, Northeastern University, Shenyang 110004, China; (2) Department of Information Science, University of Arkansas at Little Rock, Little Rock 72204, United States
  • Received:2013-06-20 Revised:2013-06-20 Published:2013-06-20
  • Contact: Chen, D.-M.
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

734

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

关键词: 社会网络, 社区发现, 广度优先搜索, 聚类, 模块化

Abstract: 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.

中图分类号: