中国物理B ›› 2018, Vol. 27 ›› Issue (10): 100504-100504.doi: 10.1088/1674-1056/27/10/100504

• SPECIAL TOPIC—Recent advances in thermoelectric materials and devices • 上一篇    下一篇

Detecting overlapping communities based on vital nodes in complex networks

Xingyuan Wang(王兴元), Yu Wang(王宇), Xiaomeng Qin(秦小蒙), Rui Li(李睿), Justine Eustace   

  1. 1 School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China;
    2 Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China;
    3 School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
  • 收稿日期:2018-03-21 修回日期:2018-08-09 出版日期:2018-10-05 发布日期:2018-10-05
  • 通讯作者: Xingyuan Wang E-mail:wangxy@dlut.edu.cn
  • 基金资助:

    Project supported by the National Natural Science Foundation of China (Grant Nos. 61672124, 61370145, 61173183, and 61503375) and the Password Theory Project of the 13th Five-Year Plan National Cryptography Development Fund, China (Grant No. MMJJ20170203).

Detecting overlapping communities based on vital nodes in complex networks

Xingyuan Wang(王兴元)1,2, Yu Wang(王宇)2, Xiaomeng Qin(秦小蒙)2, Rui Li(李睿)3, Justine Eustace2   

  1. 1 School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China;
    2 Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China;
    3 School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
  • Received:2018-03-21 Revised:2018-08-09 Online:2018-10-05 Published:2018-10-05
  • Contact: Xingyuan Wang E-mail:wangxy@dlut.edu.cn
  • Supported by:

    Project supported by the National Natural Science Foundation of China (Grant Nos. 61672124, 61370145, 61173183, and 61503375) and the Password Theory Project of the 13th Five-Year Plan National Cryptography Development Fund, China (Grant No. MMJJ20170203).

摘要:

Detection of community structures in the complex networks is significant to understand the network structures and analyze the network properties. However, it is still a problem on how to select initial seeds as well as to determine the number of communities. In this paper, we proposed the detecting overlapping communities based on vital nodes algorithm (DOCBVA), an algorithm based on vital nodes and initial seeds to detect overlapping communities. First, through some screening method, we find the vital nodes and then the seed communities through the pretreatment of vital nodes. This process differs from most existing methods, and the speed is faster. Then the seeds will be extended. We also adopt a new parameter of attribution degree to extend the seeds and find the overlapping communities. Finally, the remaining nodes that have not been processed in the first two steps will be reprocessed. The number of communities is likely to change until the end of algorithm. The experimental results using some real-world network data and artificial network data are satisfactory and can prove the superiority of the DOCBVA algorithm.

关键词: complex networks, overlapping communities, vital nodes, seed communities

Abstract:

Detection of community structures in the complex networks is significant to understand the network structures and analyze the network properties. However, it is still a problem on how to select initial seeds as well as to determine the number of communities. In this paper, we proposed the detecting overlapping communities based on vital nodes algorithm (DOCBVA), an algorithm based on vital nodes and initial seeds to detect overlapping communities. First, through some screening method, we find the vital nodes and then the seed communities through the pretreatment of vital nodes. This process differs from most existing methods, and the speed is faster. Then the seeds will be extended. We also adopt a new parameter of attribution degree to extend the seeds and find the overlapping communities. Finally, the remaining nodes that have not been processed in the first two steps will be reprocessed. The number of communities is likely to change until the end of algorithm. The experimental results using some real-world network data and artificial network data are satisfactory and can prove the superiority of the DOCBVA algorithm.

Key words: complex networks, overlapping communities, vital nodes, seed communities

中图分类号:  (Computational methods in statistical physics and nonlinear dynamics)

  • 05.10.-a
02.10.Ox (Combinatorics; graph theory)