Journal of Frontiers of Computer Science and Technology ›› 2012, Vol. 6 ›› Issue (5): 456-464.DOI: 10.3778/j.issn.1673-9418.2012.05.007

Previous Articles     Next Articles

Online Social Network Community Structure Detection Algorithm Based on Number of Shared Friends

FANG Ping1,2,3, GUO Zhengbiao1,2, LI Zhitang1,2,4+, TU Hao2,4, YANG Yanming3   

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


方 平1,2,3,郭正彪1,2,李芝棠1,2,4+,涂 浩2,4,杨彦明3   

  1. 1. 华中科技大学 计算机科学与技术学院,武汉 430074
    2. 华中科技大学 下一代互联网接入系统国家工程实验室,武汉 430074
    3. 海军航空工程学院 青岛分院,山东 青岛 266041
    4. 华中科技大学 网络与计算中心,武汉 430074

Abstract: To partition online social networks into groups fast and correctly, this paper proposes an algorithm for detecting community structures in online social networks based on shared friends and node neighbors information. By looking for the maximum number of shared friends based on the maximum degree node, the initial community included two nodes is found, and Q value of the node is used to decide whether the node of initial community neighbor is added into the community. The final community structure is decided by the initial community information of node neighbors. Two classical social networks and synthetic datasets are used to test the performance of the algorithm. Experimental results show that the proposed algorithm is viable and effective.

Key words: online social network, community detecting, shared friends, local structure

摘要: 为了快速准确地找到在线社会网络的社区结构,提出了一种基于共同好友数和节点邻居信息的社区结构发现算法。该算法以共同好友数最多的两个节点为初始社区,不断寻找与社区连接性最强的节点,并以节点Q值为衡量标准,判断是否将该节点加入到初始社区中,最后根据节点邻居所在初始社区信息确定最终的社区划分。针对两个经典社会网络和人工生成网络数据的实验划分结果表明,该算法是可行和有效的。

关键词: 在线社会网络, 社区发现, 共同好友, 局部结构