Journal Home > Volume 20 , Issue 6

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.


menu
Abstract
Full text
Outline
About this article

Tolerance Granulation Based Community Detection Algorithm

Show Author's information Shu ZhaoWang KeJie Chen( )Feng LiuMenghan HuangYanping ZhangJie Tang
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.
School of Computer Science and Technology, Tsinghua University, Beijing 100084, China.

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.

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

References(18)

[1]
Girvan M., Newman M. E. J., Community structure in social and biological networks, Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, 2002.
[2]
Lancichinetti A., Fortunato S., Radicchi F., Benchmark graphs for testing community detection algorithms, Physical Review E, vol. 78, no. 4, p. 046110, 2008.
[3]
Newman M. E. J., Detecting community structure in networks, The European Physical Journal B-Condensed Matter and Complex Systems, vol. 38, no. 2, pp. 321–330, 2004.
[4]
Lancichinetti A., Fortunato S., Community detection algorithms: A comparative analysis, Physical Review E, vol. 80, no. 5, p. 056117, 2009.
[5]
Fortunato S., Community detection in graphs, Physics Reports, vol. 486, no. 3, pp. 75–174, 2010.
[6]
Liu W., Chen L., Community detection in disease-gene network based on principal component analysis, Tsinghua Science and Technology, vol. 18, no. 5, pp. 454–461, 2013.
[7]
Qian F. L., Zhang Y. P, Duan Z., Zhang Y., Community-based user domain model collaborative recommendation algorithm, Tsinghua Science and Technology, vol. 18, no. 4, pp. 353–359, 2013.
[8]
Kuncheva L. I., Using diversity in cluster ensembles, in Systems, Man and Cybernetics, 2004 IEEE International Conference, 2014, vol. 2, pp. 1214–1219.
[9]
Kleinberg J. M., Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), vol. 46, no. 5, pp. 604–632, 1999.
[10]
Newman M. E. J., Fast algorithm for detecting community structure in networks, Physical Review E, vol. 69, no. 6, p. 066133, 2004.
[11]
Zhang L., Zhang B., Fuzzy tolerance quotient spaces and fuzzy subsets, Science China Information Sciences, vol. 53, no. 4, pp. 704–714, 2010.
[12]
Zhao S., Ke W., Chen J., Zhang Y. P., Community detection algorithm based on clustering granulation, Journal of Computer Applications, vol. 34, no. 10, pp. 2812–2815, 2014.
[13]
Shen H. W., Cheng X. Q., Cai K., Hu M. B., Detect overlapping and hierarchical community structure in networks, Physica A: Statistical Mechanics and Its Applications, vol. 388, no. 8, pp. 1706–1712, 2009.
[14]
Wu T., Guo Y., Chen L. T., Liu Y. B., Fast overlapping and hierarchical community detection via local dynamic interaction, arXiv preprint arXiv, vol. 388, no. 8, pp. 1706–1712, 2009.
[15]
Du N., Wu B., Xu L., Wang B., A parallel algorithm for enumerating all maximal cliques in complex network, in Data Mining Workshops, ICDM Workshops, Hong Kong, China, 2006, pp. 320–324.
DOI
[16]
Girvan M., Newman M. E. J., Finding and evaluating community structure in networks, Physical Review E, vol. 69, no. 2, p. 026113, 2004.
[17]
Zachary W. W., An information flow model for conflict and fission in small groups, Journal of Anthropological Research, vol. 33, no. 4, pp. 452–473, 1977.
[18]
Lusseau D., The emergent properties of a dolphin social network, Proceedings of the Royal Society of London B: Biological Sciences, vol. 270, no. Suppl 2, pp. S186–S188, 2003.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 27 March 2015
Revised: 15 July 2015
Accepted: 22 July 2015
Published: 17 December 2015
Issue date: December 2015

Copyright

© The author(s) 2015

Acknowledgements

This work is partially supported by the National High-Tech Research and Development (863) Program of China (No. 2015AA124102), the National Natural Science Foundation of China (Nos. 61402006 and 61175046), the Provincial Natural Science Research Program of Higher Education Institutions of Anhui Province (No. KJ2013A016), the Provincial Natural Science Foundation of Anhui Province (No. 1508085MF113), the College Students National Innovation & Entrepreneurship Training program of Anhui University (No. 201410357041), and the Recruitment Project of Anhui University for Academic and Technology Leader.

Rights and permissions

Return