Information-Theoretic Approach to Community Detection Problem
Keywords:
Community detection, Stochastic block model, Network theory, Clustering, Information theoryAbstract
Real world complex networks possess hidden information called communities or clusters, which are composed of nodes that are tightly connected within communities and weakly connected between communities. Investigation of communities proved to have countless applications in different sciences such as computer science and machine learning, biology, economics, and social networks. Parallel to the development of various detection algorithms, probabilistic network models also gained more attention, particularly stochastic block model which is a generative model for random graphs generating networks with community structure. This paper explores the state of the art on the connections of stochastic block model with information theory
References
M. Newman, “Networks: an introduction”, Oxford University Press, Oxford, 2010.
M. Girvan and M. Newman, "Finding and evaluating community structure in networks", Physical Review E, vol. 69, 026113, 2004.
S. Fortunato, "Community detection in graphs", Physics Reports 486, pp. 75-174, 2010.
P. Holland, K. Laskey and S. Leinhardt, "Stochastic block models: First steps ", Social Networks, vol. 5, no. 2, pp. 109-137, 1983.
E. Abbe and C. Sandon, "Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms", IEEE 56th Annual Symp. on Foundations of Computer science, USA, pp. 670 – 688, 2015.
E. Abbe, "Community detection and the stochastic block model", IEEE Information Theory Society Newsletter, vol. 66, no. 1, pp. 3- 12, 2016.
E. Abbe and C. Sandon, "Recovering communities in the general stochastic block model without knowing the parameters”, Advances in Neural Information Processing Systems, vol. 28, pp. 676 – 684, 2015.
A. Decelle, F. Krzakala, C. Moore and L. Zdeborova, "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications", Physical Review E, vol. 84, 066106, 2011.
V. Kanade, E. Mossel and T. Schramm, “Global and local information in clustering labeled block models”, IEEE Transactions on Information Theory, vol. 62, no. 10, pp. 5906– 5917, 2016.
E. Abbe and M. Wainwright, “Information theory meets machine learning”, tutorial, Intern. Symp. on Information Theory, 2015.
E. Abbe, A. Bandeira and G. Hall, "Exact recovery in the stochastic block model", IEEE Transactions on Information Theory, vol. 62, no. 1, pp. 471 – 487, 2016.
M. Rosvall and C. T. Bergstrom, “An information-theoretic framework for resolving community structure in complex networks”, Proc. Natl. Acad. Sci. USA, vol. 104, no. 18, pp. 7327 – 7331, 2007.
M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure”, Proc. Natl. Acad. Sci. USA, vol. 105, no. 4, pp. 1118 - 1123, 2008.
E. Ziv, M. Middendorf and C. H. Wiggins, “Information theoretic approach to network modularity”, Physical Review E, vol. 71, no. 4, 046117, 2005.
D. J. C. Mackay, “Information theory, inference and learning algorithms”, Cambridge University Press, fourth printing, 2005.
L. Danon, A. Diaz-Guilera, J. Duch and A. Arenas, “Comparing community stucture identification”, Journal of Statistical Mechanics: Theory and Experiment, P09008, 2005.
M. Meila, “Comparing clusterings – an information based distance”, Journal of Multivar. Anal., vol. 98, no. 5, pp. 873 – 895, 2007.
B. Karrer, E. Levina and M. Newman, “Robustness of community structure in networks”, Physical Review E, vol. 77, 046119, 2008.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
