Structural Inference of Hierarchies in Networks

Abstract

One property of networks that has received comparatively little attention is hierarchy, i.e., the property of having vertices that cluster together in groups, which then join to form groups of groups, and so forth, up through all levels of organization in the network. Here, we give a precise definition of hierarchical structure, give a generic model for generating arbitrary hierarchical structure in a random graph, and describe a statistically principled way to learn the set of hierarchical features that most plausibly explain a particular real-world network. By applying this approach to two example networks, we demonstrate its advantages for the interpretation of network data, the annotation of graphs with edge, vertex and community properties, and the generation of generic null models for further hypothesis testing.

8 pages, 8 figures

References in corpus (12)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding community structure in very large networks
• Assortative mixing in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical organization of modularity in metabolic networks
• Defining and identifying communities in networks
• A General Formalism for Inhomogeneous Random Graphs
• Community Detection as an Inference Problem
• Structural Inference of Hierarchies in Networks

Cited by in corpus (18)

• Community detection in graphs
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Mixture models and exploratory analysis in networks
• Extracting the hierarchical organization of complex systems
• Robustness of community structure in networks
• A sequential algorithm for fast clique percolation
• Structural Inference of Hierarchies in Networks
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Markers of criticality in phase synchronisation
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Hubs and Clusters in the Evolving U. S. Internal Migration Network
• Discernment of Hubs and Clusters in Socioeconomic Networks
• Private Graph Data Release: A Survey
• Organizational Chart Inference
• Clustering on the Edge: Learning Structure in Graphs
• Graph Embedding with Hierarchical Attentive Membership