Santo Fortunato (Aalto University, Finland)
Topic: Graph clustering
This is an introduction to a basic problem in network science: the identification of clusters, or communities, in real networks. Clusters are subsets of nodes where the density of internal links is comparatively higher than the density of external links. I will go through the basic elements of the problem: the definition of community; the definition of partition, with its suitable adaptation in the presence of hierarchy and/or overlapping communities. I will present some popular algorithms, like the Girvan-Newman algorithm and methods based on the optimization of a benefit function, both global (like the famous modularity by Newman and Girvan or the map length of Rosvall and Bergstrom), and local. The lecture will end with a brief characterization of communities in real systems, especially social and information networks.