Information-theoretic clustering of large-scale networks

SNIC 2017/10-6


Swestore Medium

Principal Investigator:

Martin Rosvall


Umeå universitet

Start Date:


End Date:


Primary Classification:

10105: Computational Mathematics

Secondary Classification:

10299: Other Computer and Information Science

Tertiary Classification:

10399: Other Physics Topics



To comprehend the hierarchical organization of large integrated systems, we have developed an information-theoretic approach called the map equation. The map equation exploits the duality between compression and pattern detection; by compressing a description of a random walker as a proxy for real flow on a network, we find regularities in the network that induce this system-wide flow. Finding the shortest multilevel description of the random walker, therefore, gives us the best hierarchical clustering of the network — the optimal number of levels and modular partition at each level — concerning the dynamics on the network. With a novel search algorithm, we extract and illustrate the rich multilevel organization of several large social and biological networks. Over the last years, we have used our access to Abisko in more than ten different projects. A project on networks with memory uses multi-step real pathways of dynamics in social and biological networks, and we use novel algorithms to comprehend the structure of such higher-order dynamics. The project for the next year aims to further analyze more real systems concerning memory effects and the consequences for structural organization and impacts on, for example, information, biogeographical, and disease spreading.