Annotated Hypergraphs: Models and Applications

Hypergraphs offer a natural modeling language for studying polyadic
interactions between sets of entities. Many polyadic interactions are
asymmetric, with nodes playing distinctive roles. In an academic collaboration
network, for example, the order of authors on a paper often reflects the nature
of their contributions to the completed work. To model these networks, we
introduce \emph{annotated hypergraphs} as natural polyadic generalizations of
directed graphs. Annotated hypergraphs form a highly general framework for
incorporating metadata into polyadic graph models. To facilitate data analysis
with annotated hypergraphs, we construct a role-aware configuration null model
for these structures and prove an efficient Markov Chain Monte Carlo scheme for
sampling from it. We proceed to formulate several metrics and algorithms for
the analysis of annotated hypergraphs. Several of these, such as assortativity
and modularity, naturally generalize dyadic counterparts. Other metrics, such
as local role densities, are unique to the setting of annotated hypergraphs. We
illustrate our techniques on six digital social networks, and present a
detailed case-study of the Enron email data set.