Inference for graphs and networks: Extending classical tools to modern data

Abstract

Graphs and networks provide a canonical representation of relational data, with massive network data sets becoming increasingly prevalent across a variety of scientific fields. Although tools from mathematics and computer science have been eagerly adopted by practitioners in the service of network inference, they do not yet comprise a unified and coherent framework for the statistical analysis of large-scale network data. This paper serves as both an introduction to the topic and a first step toward formal inference procedures. We develop and illustrate our arguments using the example of hypothesis testing for network structure. We invoke a generalized likelihood ratio framework and use it to highlight the growing number of topics in this area that require strong contributions from statistical science. We frame our discussion in the context of previous work from across a variety of disciplines, and conclude by outlining fundamental statistical challenges whose solutions will in turn serve to advance the science of network inference.

16 pages, 6 figures; submitted for publication

References in corpus (20)

• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Hierarchical structure and the prediction of missing links in networks
• An information-theoretic framework for resolving community structure in complex networks
• Mixed membership stochastic blockmodels
• Detecting fuzzy community structures in complex networks with a Potts model
• A survey of random processes with reinforcement
• Mixture models and exploratory analysis in networks
• Consistency of spectral clustering
• Robustness of community structure in networks
• Modeling social networks from sampled data
• A Bayesian Approach to Network Modularity
• Comparison and validation of community structures in complex networks
• Community Structure in Graphs
• Thermodynamics of Community Structure

Cited by in corpus (3)

• Bootstrapping Exchangeable Random Graphs
• Consistency of Maximum Likelihood for Continuous-Space Network Models I
• Bayesian Models Applied to Cyber Security Anomaly Detection Problems