Journal Home > Volume 24 , Issue 6

Local community detection aims to find a cluster of nodes by exploring a small region of the network. Local community detection methods are faster than traditional global community detection methods because their runtime does not depend on the size of the entire network. However, most existing methods do not take the higher-order connectivity patterns crucial to the network into consideration. In this paper, we develop a new Local Community Detection method based on network Motif (LCD-Motif) which incorporates the higher-order network information. LCD-Motif adopts the local expansion of a seed set to identify the local community with minimal motif conductance, representing a generalization of the conductance metric for network motifs. In contrast to PageRank-like diffusion methods, LCD-Motif finds the community by seeking a sparse vector in the span of the local spectra, such that the seeds are in its support vector. We evaluate our approach using real-world datasets across various domains and synthetic networks. The experimental results show that LCD-Motif can achieve a higher performance than state-of-the-art methods.


menu
Abstract
Full text
Outline
About this article

Local Community Detection Based on Network Motifs

Show Author's information Yunlei ZhangBin Wu*( )Yu LiuJinna Lv
Beijing Key Laboratory of Intelligence Telecommunications Software and Multimedia, School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China.

Abstract

Local community detection aims to find a cluster of nodes by exploring a small region of the network. Local community detection methods are faster than traditional global community detection methods because their runtime does not depend on the size of the entire network. However, most existing methods do not take the higher-order connectivity patterns crucial to the network into consideration. In this paper, we develop a new Local Community Detection method based on network Motif (LCD-Motif) which incorporates the higher-order network information. LCD-Motif adopts the local expansion of a seed set to identify the local community with minimal motif conductance, representing a generalization of the conductance metric for network motifs. In contrast to PageRank-like diffusion methods, LCD-Motif finds the community by seeking a sparse vector in the span of the local spectra, such that the seeds are in its support vector. We evaluate our approach using real-world datasets across various domains and synthetic networks. The experimental results show that LCD-Motif can achieve a higher performance than state-of-the-art methods.

Keywords: community detection, network motifs, local spectral clustering, seed set expansion, random walk

References(21)

[1]
Fortunato S., Community detection in graphs, Phys. Rep., vol. 486, nos. 3–5, pp. 75-174, 2010.
[2]
Li Y. X., He K., Bindel D., and Hopcroft J. E., Uncovering the small community structure in large networks: A local spectral approach, in Proc. 24th Int. Conf. World Wide Web, Florence, Italy, 2015, pp. 658-668.
[3]
Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., and Alon U., Network motifs: Simple building blocks of complex networks, Science, vol. 298, no. 5594, pp. 824-827, 2002.
[4]
Mangan S. and Alon U., Structure and function of the feed-forward loop network motif, Proc. Nat. Acad. Sci. USA, vol. 100, no. 21, pp. 11 980-11 985, 2003.
[5]
Holland P. W. and Leinhardt S., A method for detecting structure in sociometric data, Am. J. Sociol., vol. 76, no. 3, pp. 492-513, 1970.
[6]
Honey C. J., Kötter R., Breakspear M., and Sporns O., Network structure of cerebral cortex shapes functional connectivity on multiple time scales, Proc. Nat. Acad. Sci. USA, vol. 104, no. 24, pp. 10 240-10 245, 2007.
[7]
Rosvall M., Esquivel A. V., Lancichinetti A., West J. D., and Lambiotte R., Memory in network flows and its effects on spreading dynamics and community detection, Nat. Commun., vol. 5, p. 4630, 2014.
[8]
Benson A. R., Gleich D. F., and Leskovec J., Higher-order organization of complex networks, Science, vol. 353, no. 6295, pp. 163-166, 2016.
[9]
Fortunato S. and Hric D., Community detection in networks: A user guide, Phys. Rep., vol. 659, pp. 1-44, 2016.
[10]
Lim S. and Lee J. G., Motif-based embedding for graph clustering, J. Stat. Mech., vol. 2016, no. 12, p. 123 401, 2016.
[11]
Yin H., Benson A. R., Leskovec J., and Gleich D. F., Local higher-order graph clustering, in Proc. 23rd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Halifax, Canada, 2017, pp. 555-564.
DOI
[12]
Chen L., Zhang J., Cai L. J., and Deng Z. Y., Fast community detection based on distance dynamics, Tsinghua Sci. Technol., vol. 22, no. 6, pp. 564-585, 2017.
[13]
Wu B., Xiao Y., and Zhang Y. L., Parallel incremental dynamic community detection algorithm based on Spark, (in Chinese), J. Tsinghua Univ. (Sci. Technol.), vol. 57, no. 10, pp. 1030-1037, 2017.
[14]
Tsourakakis C. E., Pachocki J., and Mitzenmacher M., Scalable motif-aware graph clustering, in Proc. 26th Int. Conf. on World Wide Web, Perth, Australia, 2017, pp. 1451-1460.
DOI
[15]
Andersen R. and Lang K. J., Communities from seed sets, in Proc. 15th Int. Conf. on World Wide Web, Edinburgh, Scotland, 2006, pp. 223-232.
DOI
[16]
Whang J. J., Gleich D. F., and Dhillon I. S., Overlapping community detection using neighborhood-inflated seed expansion, IEEE Trans. Knowl. Data Eng., vol. 28, no. 5, pp. 1272-1284, 2016.
[17]
Kloumann I. M. and Kleinberg J. M., Community membership identification from small seed sets, in Proc. 20th ACM Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 1366-1375.
DOI
[18]
Kloster K. and Gleich D. F., Heat kernel based community detection, in Proc. 20th ACM Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 1386-1395.
DOI
[19]
Latapy M., Main-memory triangle computations for very large (sparse (power-law)) graphs, Theor. Comput. Sci., vol. 407, nos. 1–3, pp. 458-473, 2008.
[20]
Megiddo N., Linear programming in linear time when the dimension is fixed, J. ACM, vol. 31, no. 1, pp. 114-127, 1984.
[21]
Andrea L., Santo F., and Filippo R., Benchmark graphs for testing community detection algorithms, Phy. Rev. E Stat. Nonlinear Soft Matter Phys., vol. 78, no. 4, p. 046110, 2008.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 19 March 2018
Revised: 07 June 2018
Accepted: 24 June 2018
Published: 05 December 2019
Issue date: December 2019

Copyright

© The author(s) 2019

Acknowledgements

This work was supported by the National Social Science Foundation of China (No. 16ZDA055).

Rights and permissions

Return