Learning Hierarchical Models from Graph Data

One property that has received comparatively little attention in the recent renaissance of network analysis is that of hierarchy, i.e., the observation that networks often have a fractal-like structure in which vertices cluster together in groups that then join to form group of groups, and so forth, at all levels of organization in the network. Here, we give a precise and mathematically rigorous definition of hierarchy, and describe a statistically principled way to learn the set of hierarchical features that most plausibly explain a particular real-world network. We briefly describe the advantages this approach has for automating the interpretation of network data, which include annotating edges, vertices and local structures with some notation of how surprising they are, and the generation of generic null-models for further hypothesis testing.

This work is joint with Cristopher Moore (UNM) and Mark Newman (UMich).