•  
  •  
 
Tsinghua Science and Technology

Authors

Shu Zhao, the Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Center of Information Support & Assurance Technology, School of Computer Science and Technology, Anhui University, Hefei 230601, China.
Wang Ke, the Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Center of Information Support & Assurance Technology, School of Computer Science and Technology, Anhui University, Hefei 230601, China.
Jie Chen, the Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Center of Information Support & Assurance Technology, School of Computer Science and Technology, Anhui University, Hefei 230601, China.
Feng Liu, the Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Center of Information Support & Assurance Technology, School of Computer Science and Technology, Anhui University, Hefei 230601, China.
Menghan Huang, the Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Center of Information Support & Assurance Technology, School of Computer Science and Technology, Anhui University, Hefei 230601, China.
Yanping Zhang, the Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Center of Information Support & Assurance Technology, School of Computer Science and Technology, Anhui University, Hefei 230601, China.
Jie Tang, the School of Computer Science and Technology, Tsinghua University, Beijing 100084, China.

Keywords

tolerance relation, community, tolerance granulation, Normalized Mutual Information (NMI) accuracy

Abstract

Community structure is one of the most important features in real networks and reveals the internal organization of the vertices. Uncovering accurate community structure is effective for understanding and exploiting networks. Tolerance Granulation based Community Detection Algorithm (TGCDA) is proposed in this paper, which uses tolerance relation (namely tolerance granulation) to granulate a network hierarchically. Firstly, TGCDA relies on the tolerance relation among vertices to form an initial granule set. Then granules in this set which satisfied granulation coefficient are hierarchically merged by tolerance granulation operation. The process is finished till the granule set includes one granule. Finally, select a granule set with maximum granulation criterion to handle overlapping vertices among some granules. The overlapping vertices are merged into corresponding granules based on their degrees of affiliation to realize the community partition of complex networks. The final granules are regarded as communities so that the granulation for a network is actually the community partition of the network. Experiments on several datasets show our algorithm is effective and it can identify the community structure more accurately. On real world networks, TGCDA achieves Normalized Mutual Information (NMI) accuracy 17.55% higher than NFA averagely and on synthetic random networks, the NMI accuracy is also improved. For some networks which have a clear community structure, TGCDA is more effective and can detect more accurate community structure than other algorithms.

Publisher

Tsinghua University Press

Share

COinS