Flow Divergence: Comparing Maps of Flows with Relative Entropy
Preprint
Abstract
Networks represent how the entities of a system are connected and can be partitioned differently, prompting ways to compare partitions. Common approaches for comparing network partitions include information-theoretic measures based on mutual information and set-theoretic measures such as the Jaccard index. These measures are often based on computing the agreement in terms of overlap between different partitions of the same set. However, they ignore link patterns which are essential for the organisation of networks. We propose flow divergence, an information-theoretic divergence measure for comparing network partitions, inspired by the ideas behind the Kullback-Leibler divergence and the map equation for community detection. Similar to the Kullback-Leibler divergence, flow divergence adopts a coding perspective and compares two network partitions $\mathsf{M}_a$ and $\mathsf{M}_b$ by considering the expected extra number of bits required to describe a random walk on a network using $\mathsf{M}_b$ relative to reference partition $\mathsf{M}_a$. Because flow divergence is based on random walks, it can be used to compare partitions with arbitrary and different depths. We show that flow divergence distinguishes between partitions that traditional measures consider to be equally good when compared to a reference partition. Applied to real networks, we use flow divergence to estimate the cost of overfitting in incomplete networks and to visualise the solution landscape of network partitions.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Mapping robust multiscale communities in chromosome contact networksScientific Reports, 2023
- Mapping flows on weighted and directed networks with incomplete observationsJournal of Complex Networks, 2021
- Interaction data from the Copenhagen Networks StudyScientific Data, 2019
- Understanding information theoretic measures for comparing clusteringsBehaviormetrika, 2018
- Organization Mining Using Online Social NetworksNetworks and Spatial Economics, 2015
- Ranking and clustering of nodes in networks with smart teleportationPhysical Review E, 2012
- Community detection in graphsPhysics Reports, 2010
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences of the United States of America, 2008
- Modularity and community structure in networksProceedings of the National Academy of Sciences of the United States of America, 2006
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002