计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (17): 38-42.

• 理论研究、研发设计 • 上一篇    下一篇

复杂网络局部社区挖掘的节点接近度算法

方  平1,3,4,李芝棠2,3,4,涂  浩2,4,郭正彪3,4   

  1. 1.海军航空工程学院 青岛校区,山东 青岛 266041
    2.华中科技大学 网络与计算中心,武汉 430074
    3.华中科技大学 计算机科学与技术学院,武汉 430074
    4.华中科技大学 下一代互联网接入系统国家工程实验室,武汉 430074
  • 出版日期:2013-09-01 发布日期:2013-09-13

Closeness degree of node algorithm for mining local community from complex networks

FANG Ping1,3,4, LI Zhitang2,3,4, TU Hao2,4, GUO Zhengbiao3,4   

  1. 1.Qingdao Branch, Naval Aeronautical and Astronautical University, Qingdao, Shandong 266041, China
    2.Network Center, Huazhong University of Science and Technology, Wuhan 430074, China
    3.College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
    4.National Engineering Laboratory for Next Generation Internet Access System, Huazhong University of Science and Technology, Wuhan 430074, China
  • Online:2013-09-01 Published:2013-09-13

摘要: 为了准确、快速地发现大规模复杂网络中的局部社区,提出了一种基于节点接近度的局部社区发现算法。该算法以最大度节点作为起始节点,利用节点接近度和局部社区Q值不断搜索其邻居节点,将接近度最大的节点加入初始社区形成新的初始社区;同时,该算法也可以应用于复杂网络全局社区结构的划分。对2个典型复杂网络进行了局部社区挖掘分析,实验结果表明,该算法能够有效识别隐藏在实验网络中的局部社区。针对稀疏网络,该算法的时间复杂度为O(nlog(n)),n为网络节点数。

关键词: 复杂网络, 局部社区发现, 节点接近度

Abstract: To make the local community detection faster and more accurate, this paper proposes an algorithm for detecting local community structures in complex networks based on closeness degree of node. The proposed method, which uses the maximal closeness degree of node and the local community’s Q value, starts from the maximum degree node of the network and detects the community it belongs to by searching the neighbor nodes. It is also applicable for global community structure detecting. The experiments on two typical complex networks show that the algorithm can effectively mine the intrinsic local community structure in networks. The time complexity of the algorithm is O(nlog(n)) on a sparse graph, where n is the number of nodes.

Key words: complex network, local community detection, closeness degree of node