Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
arXiv:1508.04388 · doi:10.1103/PhysRevE.92.062825
Abstract
The quest for a quantitative characterization of community and modular structure of complex networks produced a variety of methods and algorithms to classify different networks. However, it is not clear if such methods provide consistent, robust and meaningful results when considering hierarchies as a whole. Part of the problem is the lack of a similarity measure for the comparison of hierarchical community structures. In this work we give a contribution by introducing the {\it hierarchical mutual information}, which is a generalization of the traditional mutual information, and allows to compare hierarchical partitions and hierarchical community structures. The {\it normalized} version of the hierarchical mutual information should behave analogously to the traditional normalized mutual information. Here, the correct behavior of the hierarchical mutual information is corroborated on an extensive battery of numerical experiments. The experiments are performed on artificial hierarchies, and on the hierarchical community structure of artificial and empirical networks. Furthermore, the experiments illustrate some of the practical applications of the hierarchical mutual information. Namely, the comparison of different community detection methods, and the study of the consistency, robustness and temporal evolution of the hierarchical modular structure of networks.
arXiv comment14 pages and 12 figures
References in corpus (39)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in networks using the eigenvectors of matrices
- Multilayer Networks
- Specificity and stability in topology of protein networks
- Comparing community structure identification
- The Product Space Conditions the Development of Nations
- Temporal Networks
- Spatial Networks
- Community detection algorithms: a comparative analysis
- Hierarchical structure and the prediction of missing links in networks
- Hierarchical Structure in Financial Markets
- Detecting the overlapping and hierarchical community structure of complex networks
- Finding statistically significant communities in networks
- Extracting the hierarchical organization of complex systems
- Topology of correlation based minimal spanning trees in real and model markets
- Analysis of the structure of complex networks at different resolution levels
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Networks of equities in financial markets
- Correlation, hierarchies, and networks in financial markets
- Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
- Multinetwork of international trade: A commodity-specific analysis
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Community detection in networks: Structural communities versus ground truth
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- A network analysis of countries' export flows: firm grounds for the building blocks of the economy
- Small world-Fractal Transition in Complex Networks: Renormalization Group Approach
- Community detection for correlation matrices
- Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks
- Benchmark model to assess community structure in evolving networks
- Estimating the resolution limit of the map equation in community detection
- Hierarchical multiresolution method to overcome the resolution limit in complex networks
- Topologically biased random walk with application for community finding in networks
- Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
- Detecting modules in dense weighted networks with the Potts method
- Geometric origin of scaling in large traffic networks
- Unsupervised clustering analysis: a multiscale complex networks approach
Cited by in corpus (11)
- Community detection in networks: A user guide
- Element-centric clustering comparison unifies overlaps and hierarchy
- Efficient community detection of network flows for varying Markov times and bipartite networks
- Exploring the solution landscape enables more reliable network community detection
- Hierarchical community structure in networks
- Hierarchical benchmark graphs for testing community detection algorithms
- Comparing the hierarchy of keywords in on-line news portals
- Towards a generalization of information theory for hierarchical partitions
- Thermodynamics of the Minimum Description Length on Community Detection
- Partial order similarity based on mutual information
- On the Possibility of Rewarding Structure Learning Agents: Mutual Information on Linguistic Random Sets