Community Structure in Complex Networks

Santo Fortunato, Professor of Complex Systems, Department of Biomedical Engineering and Computational Science, Aalto University

Abstract
Complex systems typically display a modular structure, as modules are easier to assemble than the individual units of the system, and more resilient to failures. In the network representation of complex systems, modules, or communities, appear as subgraphs whose nodes have an appreciably larger probability to get connected to each other than to other nodes of the network. In this talk I will address three fundamental questions: How is community structure generated? How to detect it? How to test the performance of community detection algorithms? I will show that communities emerge naturally in growing network models favoring triadic closure, a mechanism necessary to implement for the generation of large classes of systems, like e.g., social networks. I will discuss the limits of the most popular class of clustering algorithms, those based on the optimization of a global quality function, like modularity maximization. Testing algorithms is probably the single most important issue of network community detection, as it implicitly involves the concept of community, which is still controversial. I will discuss the importance of using realistic benchmark graphs with built-in community structure.

Bio
Santo Fortunato is Professor of Complex Systems at the Department of Computer Science of Aalto University, Finland. Previously he was director of the Sociophysics Laboratory at the Institute for Scientific Interchange in Turin, Italy. Prof. Fortunato got his PhD in Theoretical Particle Physics at the University of Bielefeld In Germany. He then moved to the field of complex systems, via a postdoctoral appointment at the School of Informatics and Computing of Indiana University. His current focus areas are network science, especially community detection in graphs, computational social science and science of science. His research has been published in leading journals, including Nature, PNAS, Physical Review Letters, Reviews of Modern Physics, Physics Reports and has collected about 15,000 citations (Google Scholar). His review article Community detection in graphs (Physics Reports 486, 75-174, 2010) is the most cited paper on networks of the last years. He received the Young Scientist Award for Socio- and Econophysics 2011, a prize given by the German Physical Society, for his outstanding contributions to the physics of social systems.

Related Info