Fast Community Detection Based on Distance Dynamics

Lei Chen; Jing Zhang; Lijun Cai; Ziyun Deng

doi:10.23919/TST.2017.8195341

Tsinghua Science and Technology 2017, 22(6): 564-585 https://doi.org/10.23919/TST.2017.8195341

Open Access | Issue | Published: 14 December 2017

Fast Community Detection Based on Distance Dynamics

Show Author's Information Hide Author's Information Lei Chen, Jing Zhang, Lijun Cai(

), Ziyun Deng

School of Information and Electrical Engineering, Hunan University of Science and Technology, Xiangtan 411201, China.

College of Electrical and Information Engineering, Hunan University, Changsha 410082, China.

College of Information Science and Engineering, Hunan University, Changsha 410082, China.

Department of Economics and Trade, Changsha Commerce and Tourism College, Changsha 410082, China.

Keywords:

complex network, community detection, interaction model, graph clustering, graph mining

Cite this article:

Chen L, Zhang J, Cai L, et al. Fast Community Detection Based on Distance Dynamics. Tsinghua Science and Technology, 2017, 22(6): 564-585. https://doi.org/10.23919/TST.2017.8195341

Download citation

EndNote(RIS)

BibTeX

452

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

The distance dynamics model is excellent tool for uncovering the community structure of a complex network. However, one issue that must be addressed by this model is its very long computation time in large-scale networks. To identify the community structure of a large-scale network with high speed and high quality, in this paper, we propose a fast community detection algorithm, the F-Attractor, which is based on the distance dynamics model. The main contributions of the F-Attractor are as follows. First, we propose the use of two prejudgment rules from two different perspectives: node and edge. Based on these two rules, we develop a strategy of internal edge prejudgment for predicting the internal edges of the network. Internal edge prejudgment can reduce the number of edges and their neighbors that participate in the distance dynamics model. Second, we introduce a triangle distance to further enhance the speed of the interaction process in the distance dynamics model. This triangle distance uses two known distances to measure a third distance without any extra computation. We combine the above techniques to improve the distance dynamics model and then describe the community detection process of the F-Attractor. The results of an extensive series of experiments demonstrate that the F-Attractor offers high-speed community detection and high partition quality.

Full text

Abstract

Full text

Outline

About this article

Fast Community Detection Based on Distance Dynamics

Show Author's information Hide Author's Information Lei Chen, Jing Zhang, Lijun Cai(

), Ziyun Deng

School of Information and Electrical Engineering, Hunan University of Science and Technology, Xiangtan 411201, China.

College of Electrical and Information Engineering, Hunan University, Changsha 410082, China.

College of Information Science and Engineering, Hunan University, Changsha 410082, China.

Department of Economics and Trade, Changsha Commerce and Tourism College, Changsha 410082, China.

Abstract

Keywords: complex network, community detection, interaction model, graph clustering, graph mining

References(34)

[1]

Fortunato S., Community detection in graphs, Physics Reports, vol. 486, no. 3, pp. 75-174, 2010.

DOI Google Scholar

[2]

Papadopoulos S., Kompatsiaris Y., Vakali A., and Spyridonos P., Community detection in social media, Data Mining and Knowledge Discovery, vol. 24, no. 3, pp. 515-554, 2012.

DOI Google Scholar

[3]

Zhang X. and Cheng W., Pattern mining in linked data by edge-labeling, Tsinghua Sci. Techol., vol. 21, no. 2, pp. 168-175, 2016.

DOI Google Scholar

[4]

Barbieri N., Bonchi F., and Manco G., Cascade-based community detection, in Proc. 6th ACM International Conference on Web Search and Data Mining, Rome, Italy, 2013, pp. 33-42.

DOI

[5]

Yang Y., Guo H., Tian T., and Li H., Link prediction in brain networks based on a hierarchical random graph model, Tsinghua Sci. Technol., vol. 20, no. 3, pp. 306-315, 2015.

DOI Google Scholar

[6]

Li Y., He K., Bindel D., and Hopcroft J. E., Uncovering the small community structure in large networks: A local spectral approach, in Proc.24th International Conference on World Wide Web, Florence, Italy, 2015, pp. 658-668.

DOI

[7]

van Gennip Y., Hunter B., Ahn R., Elliott P., Luh K., Halvorson M., Reid S., Valasik M., Wo J., Tita G. E., et al., Community detection using spectral clustering on sparse geosocial data, SIAM Journal on Applied Mathematics, vol. 73, no. 1, pp. 67-83, 2013.

DOI Google Scholar

[8]

Traganitis A. P., Slavakis K., and Giannakis B. G., Spectral clustering of large-scale communities via random sketching and validation, in the 49th Annual Conference on Information Sciences and Systems (CISS), New York, NY, USA, 2015, pp. 1-6.

DOI

[9]

Newman M. E. J. and Girvan M., Finding and evaluating community structure in networks, Physical Review E, vol. 69, no. 2, pp. 26-33, 2004.

DOI Google Scholar

[10]

Marquitti F. M. D., Guimares P. R., Pires M. M., and Bittencourt L. F., MODULAR: Software for the autonomous computation of modularity in large network sets, Ecography, vol. 37, no. 3, pp. 221-224, 2014.

DOI Google Scholar

[11]

Aktunc R., Toroslu I. H., Ozer M., and Davulcu H., A dynamic modularity based community detection algorithm for large-scale networks, in IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France, 2015, pp. 1177-1183.

DOI

[12]

Schulke C. and Ricci-Tersenghi F., Multiple phases in modularity-based community detection, Physical Review E, vol. 92, no. 4, pp. 42-48, 2015.

DOI Google Scholar

[13]

Xiang J., Hu T., Zhang Y., Hu K., Li J. M., Xu X. K., Liu C. C., and Chen S., Local modularity for community detection in complex networks, Physica A: Statistical Mechanics and its Applications, vol. 443, no. 1, pp. 451-459, 2016.

DOI Google Scholar

[14]

Fortunato S. and Barthelemy M., Resolution limit in community detection, Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no. 1, pp. 36-41, 2007.

DOI Google Scholar

[15]

Raghavan U. N., Albert R., and Kumara S., Near linear time algorithm to detect community structures in large-scale networks, Physical Review E, vol. 76, no. 3, pp. 96-106, 2007.

DOI Google Scholar

[16]

Sun H., Liu J., Huang J., Wang G. T., Yang Z., Song Q. B., and Jia X. L., CenLP: A centrality-based label propagation algorithm for community detection in networks, Physica A: Statistical Mechanics and its Applications, vol. 436, no. 12, pp. 767-780, 2015.

DOI Google Scholar

[17]

Staudt C. L. and Meyerhenke H., Engineering parallel algorithms for community detection in massive networks, IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 1, pp. 171-184, 2016.

DOI Google Scholar

[18]

Arenas A. and Diaz-Guilera A., Synchronization and modularity in complex networks, The European Physical Journal Special Topics, vol. 143, no. 1, pp. 19-25, 2007.

DOI Google Scholar

[19]

Oliveira J. E. M. and Quiles M. G., Community detection in complex networks using coupled kuramoto oscillators, in the 14th International Conference on Computational Science and Its Applications (ICCSA), Washington DC, USA, 2014, pp. 85-90.

[20]

Oliveira J. E. M., Quiles M. G., Maia M. D. N., and Macau E. E. N., Community detection with lower time complexity using coupled Kuramoto oscillators, in Proc. of 30th Annual ACM Symposium on Applied Computing, Salamanca, Spain, 2015, pp. 1160-1166.

DOI

[21]

Shao J., Han Z., Yang Q., and Zhou T., Community detection based on distance dynamics, in Proc. of 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, Australia, 2015, pp. 1075-1084.

DOI

[22]

Wang J., Li M., Wang H., and Pan Y., Identification of essential proteins based on edge clustering coefficient, IEEE/ACM Transactions on Computational Biology & Bioinformatics, vol. 9, no. 4, pp. 1070-1080, 2012.

DOI Google Scholar

[23]

Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the United States of America, vol. 99, no. 12, pp. 7821-7826, 2002.

DOI Google Scholar

[24]

Rives A. W. and Galitski T., Modular organization of cellular networks, Proceedings of the National Academy of Sciences of the United States of America, vol. 100, no. 3, pp. 1128-1133, 2003.

DOI Google Scholar

[25]

Gower J. C., Measures of similarity dissimilarity and distance, Encyclopedia of Statistical Sciences, vol. 5, no. 3, pp. 397-405, 1985.

Google Scholar

[26]

Willett P., Barnard J. M., and Downs G. M., Chemical similarity searching, Journal of Chemical Information and Computer Sciences, vol. 38, no. 6, pp. 983-996, 1998.

DOI Google Scholar

[27]

Spath H., Cluster Analysis Algorithms for Data Reduction and Classification of Objects. Chichester, UK: Ellis Horwood, 1980.

[28]

Lipkus A. H., A proof of the triangle inequality for the Tanimoto distance, Journal of Mathematical Chemistry, vol. 26, no. 3, pp. 263-265, 1999.

DOI Google Scholar

[29]

Rosvall M. and Bergstrom C. T., Maps of random walks on complex networks reveal community structure, Proceedings of the National Academy of Sciences of the United States of America, vol. 105, no. 4, pp. 1118-1123, 2008.

DOI Google Scholar

[30]

Clauset A., Newman E. M., and Moore C., Finding community structure in very large networks, Physical Review E, vol. 70, no. 6, pp. 264-277, 2004.

DOI Google Scholar

[31]

Blondel D. V., Guillaume L. J., Lambiotte R., and Lefebvre E., Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory & Experiment, vol. 2008, no. 10, pp. 155-168, 2008.

DOI Google Scholar

[32]

Strehl A. and Ghosh J., Cluster ensemblesa knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, vol. 3, no. 12, pp. 583-617, 2003.

Google Scholar

[33]

Rand W. M., Objective criteria for the evaluation of clustering methods, Journal of the American Statistical Association, vol. 66, no. 336, pp. 846-850, 1971.

DOI Google Scholar

[34]

Newman M. E. J., Modularity and community structure in networks, Proceedings of the National Academy of Sciences of the United States of America, vol. 103, no. 23, pp. 8577-8582, 2006.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 30 December 2016

Revised: 29 March 2017

Accepted: 21 April 2017

Published: 14 December 2017

Issue date: December 2017

Copyright

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Nos. 61573299, 61174140, 61472127, and 61272395); the Social Science Foundation of Hunan Province (No. 16ZDA07); China Postdoctoral Science Foundation (Nos. 2013M540628 and 2014T70767); the Natural Science Foundation of Hunan Province (Nos. 14JJ3107 and 2017JJ5064); and the Excellent Youth Scholars Project of Hunan Province (No. 15B087).