计算机工程 ›› 2011, Vol. 37 ›› Issue (18): 41-43.doi: 10.3969/j.issn.1000-3428.2011.18.014

• 软件技术与数据库 • 上一篇    下一篇

基于完全子图的社区发现算法

骆 挺,钟才明,陈 辉   

  1. (宁波大学科学技术学院,浙江 宁波 315000)
  • 收稿日期:2011-04-21 出版日期:2011-09-20 发布日期:2011-09-20
  • 作者简介:骆 挺(1980-),男,讲师、硕士,主研方向:数据挖掘,复杂网络,多媒体技术;钟才明,副教授、博士;陈 辉,本科生
  • 基金项目:
    浙江省自然科学基金资助项目(Y1090851);浙江省教育厅科研基金资助项目(Y201016652);宁波大学校科研基金资助项目(XYL11001)

Community Detection Algorithm Based on Complete Subgraph

LUO Ting, ZHONG Cai-ming, CHEN Hui   

  1. (College of Science and Technology, Ningbo University, Ningbo 315000, China)
  • Received:2011-04-21 Online:2011-09-20 Published:2011-09-20

摘要: 根据复杂网络中同一社区内节点连接比较紧密,社区之间节点连接比较稀疏的特点,提出一种基于完全子图的社区发现算法,通过判别2个节点是否能在网络中与任意一个节点构成3个节点的完全子图来确认该2点是否属于同一社区。对于有些节点并不满足完全子图,或在不同社区同时满足完全子图的情况,采用节点社区归属度解决该节点的归属问题。该算法不需要任何参数设置,在计算机生成网络和真实网络上进行测试,结果验证了该算法的可行性和准确性。

关键词: 复杂网络, 社区发现, 聚类, 完全子图, 邻接矩阵

Abstract: Nodes in the same community are connected densely, and nodes from different communities are connected sparsely. According to this character, if two nodes and any other one node can constitute three-node complete subgraph, the two nodes are considered in the same community. Some nodes are not satisfied with complete subgraph, or are satisfied with complete subgraph for different communities at same time. A node rate of community ownership is proposed for solving those problems. The algorithm is not requested to set any parameters, and it is tested on the computer-generated and real network. Experimental results show the effectiveness and correctness of the algorithm.

Key words: complex network, community detection, clustering, complete subgraph, adjacent matrix

中图分类号: