摘要： 根据复杂网络中同一社区内节点连接比较紧密，社区之间节点连接比较稀疏的特点，提出一种基于完全子图的社区发现算法，通过判别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
中图分类号:
骆挺, 钟才明, 陈辉. 基于完全子图的社区发现算法[J]. 计算机工程, 2011, 37(18): 41-43.
JIA Ting, ZHONG Cai-Meng, CHEN Hui. Community Detection Algorithm Based on Complete Subgraph[J]. Computer Engineering, 2011, 37(18): 41-43.