AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (27.8 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Fast Community Detection Based on Distance Dynamics

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.
Show Author Information

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.

Keywords

community detectioninteraction modelcomplex networkgraph clusteringgraph mining

References

[1]
Fortunato S., Community detection in graphs, Physics Reports, vol. 486, no. 3, pp. 75-174, 2010.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 22 Issue 6,
December 2017
Pages 564-585
DOI: 10.23919/TST.2017.8195341
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

613

Views

20

Downloads

11

Crossref

N/A

Web of Science

13

Scopus

1

CSCD

Altmetrics
Received: 30 December 2016
Revised: 29 March 2017
Accepted: 21 April 2017
Published: 14 December 2017
© The author(s) 2017
Return