Hierarchical mutual information for the comparison of hierarchical community structures in complex networks

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.

14 pages and 12 figures

References in corpus (16)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Comparing community structure identification
• The Product Space Conditions the Development of Nations
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Extracting the hierarchical organization of complex systems
• 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
• Community detection in networks: Structural communities versus ground truth
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Benchmark model to assess community structure in evolving networks
• Topologically biased random walk with application for community finding in networks
• Detecting modules in dense weighted networks with the Potts method

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