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

A new tool derived from information theory quantitatively identifies trees, hierarchies and community structures within complex networks.

Physical Review E 92, 62825 (2015)

J. Perotti, C. Tessone, G. Caldarelli

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

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 hierarchical mutual information, which is a generalization of the traditional mutual information and makes it possible to compare hierarchical partitions and hierarchical community structures. The 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.

More in Hidden communities

  • Proceedings of the National Academy of Sciences of the USA

    True scale-free networks

    Naturally occurring networks have an underlying scale-free structure that is often clouded by finite-size effects in the sample data.


    Hierarchies in directed networks

    An iterative version of a method to identify hierarchies and rankings of nodes in directed networks can partly overcome its resolution limit.

  • Journal of Statistical Mechanics

    Disentangling links in networks

    Inference from single snapshots of temporal networks can misleadingly group communities if the links between snapshots are correlated.

  • Physical Review E

    Spectral partitioning

    The spectral density of graph ensembles provides an exact solution to the graph partitioning problem and helps detect community structure.