Abstract
Overlapping community detection is an important research topic in analyzing real-world networks. Among existing algorithms for detecting overlapping communities, generative models have shown their superiorities. However, previous generative models do not consider the intrinsic geometry of probability distribution manifold. To tackle this problem, we propose a Manifold Regularized Symmetric Joint Link Model (MSJL), which utilizes the local geometrical structure of manifold to improve the performance of overlapping community detection. MSJL assumes that the community probability distribution lives on a submanifold, and adopts the manifold assumption which specifically requires two close nodes in an intrinsic geometry to have similar community distribution. The structure of the intrinsic manifold is modeled by a nearest neighbor graph, and MSJL incorporates the graph Laplacian as a manifold regularization into the maximum likelihood function of the standard SJL model. Experiments on synthetic benchmarks and real-world networks demonstrate that MSJL can significantly improve the performance compared with the state-of-the-art methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Mixing parameter \(\mu \) is the fraction of links of a node that connect to other nodes outside its community.
- 2.
Networks data are download from http://www-personal.umich.edu/~mejn/netdata/.
References
Ahn, Y.Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. Nature 466(7307), 761–764 (2010)
Ball, B., Karrer, B., Newman, M.: Efficient and principled method for detecting communities in networks. Phys. Rev. E 84(3), 036103 (2011)
Belkin, M., Niyogi, P.: Laplacian eigenmaps and spectral techniques for embedding and clustering. NIPS 14, 585–591 (2001)
Belkin, M., Niyogi, P., Sindhwani, V.: Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res. 7, 2399–2434 (2006)
Cai, D., He, X., Han, J., Huang, T.S.: Graph regularized nonnegative matrix factorization for data representation. IEEE Trans. Pattern Anal. Mach. Intell. 33(8), 1548–1560 (2011)
Cai, D., Mei, Q., Han, J., Zhai, C.: Modeling hidden topics on document manifold. In: CIKM, pp. 911–920. ACM (2008)
Dernyi, I., Palla, G., Vicsek, T.: Clique percolation in random networks. Phys. Rev. Lett. 94(16), 160202 (2005)
Gregory, S.: Finding overlapping communities in networks by label propagation. New J. Phys. 12(10), 103018 (2010)
He, X., Cai, D., Shao, Y., Bao, H., Han, J.: Laplacian regularized gaussian mixture model for data clustering. IEEE Trans. Knowl. Data Eng. 23(9), 1406–1418 (2011)
Lancichinetti, A., Fortunato, S.: Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E 80(1), 016118 (2009)
Lancichinetti, A., Fortunato, S., Kertsz, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11(3), 033015 (2009)
Lancichinetti, A., Radicchi, F., Ramasco, J.J., Fortunato, S.: Finding statistically significant communities in networks. PloS One 6(4), e18961 (2011)
Lee, J.: Introduction to Smooth Manifolds, vol. 218. Springer, New York (2012)
Neal, R.M., Hinton, G.E.: A view of the EM algorithm that justifies incremental, sparse, and other variants. In: Jordan, M.I. (ed.) Learning in Graphical Models, pp. 355–368. Springer, Netherlands (1998)
Newman, M.E., Leicht, E.A.: Mixture models and exploratory analysis in networks. Proceedings of the National Academy of Sciences 104(23), 9564–9569 (2007)
Nicosia, V., Mangioni, G., Carchiolo, V., Malgeri, M.: Extending the definition of modularity to directed graphs with overlapping communities. J. Stat. Mech. Theor. Exp. 2009(03), P03024 (2009)
Ren, W., Yan, G., Liao, X., Xiao, L.: Simple probabilistic algorithm for detecting community structure. Phys. Rev. E 79(3), 036111 (2009)
Roweis, S.T., Saul, L.K.: Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500), 2323–2326 (2000)
Tenenbaum, J.B., De Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science 290(5500), 2319–2323 (2000)
Wang, Z., Hu, Y., Xiao, W., Ge, B.: Overlapping community detection using a generative model for networks. Physica A: Stat. Mech. Appl. 392(20), 5218–5230 (2013)
Xie, J., Kelley, S., Szymanski, B.K.: Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput. Surv. (CSUR) 45(4), 43 (2013)
Acknowledgments
This work was supported by National Science Foundation of China (No. 61272374 and No. 61300190), Specialized Research Fund for the Doctoral Program of Higher Education (No. 20120041110046) and Key Project of Chinese Ministry of Education (No. 313011).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Chen, H., Zhang, X., Liang, W., Ding, F. (2015). Manifold Regularized Symmetric Joint Link Model for Overlapping Community Detection. In: Li, XL., Cao, T., Lim, EP., Zhou, ZH., Ho, TB., Cheung, D. (eds) Trends and Applications in Knowledge Discovery and Data Mining. Lecture Notes in Computer Science(), vol 9441. Springer, Cham. https://doi.org/10.1007/978-3-319-25660-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-25660-3_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25659-7
Online ISBN: 978-3-319-25660-3
eBook Packages: Computer ScienceComputer Science (R0)