Network Structure Inference, A Survey: Motivations, Methods, and Applications

Abstract

Networks represent relationships between entities in many complex systems, spanning from online social interactions to biological cell development and brain connectivity. In many cases, relationships between entities are unambiguously known: are two users 'friends' in a social network? Do two researchers collaborate on a published paper? Do two road segments in a transportation system intersect? These are directly observable in the system in question. In most cases, relationship between nodes are not directly observable and must be inferred: does one gene regulate the expression of another? Do two animals who physically co-locate have a social bond? Who infected whom in a disease outbreak in a population? Existing approaches for inferring networks from data are found across many application domains and use specialized knowledge to infer and measure the quality of inferred network for a specific task or hypothesis. However, current research lacks a rigorous methodology which employs standard statistical validation on inferred models. In this survey, we examine (1) how network representations are constructed from underlying data, (2) the variety of questions and tasks on these representations over several domains, and (3) validation strategies for measuring the inferred network's capability of answering questions on the system of interest.

37 pages, ACM Computing Surveys (in press)

References in corpus (11)

• Graph Embedding Techniques, Applications, and Performance: A Survey
• Dynamics of person-to-person interactions from distributed RFID sensor networks
• Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
• Complex networks in climate dynamics - Comparing linear and nonlinear network construction methods
• The backbone of the climate network
• Causal Inference and Causal Explanation with Background Knowledge
• A Bayesian Approach to Network Modularity
• Inferring Networks of Substitutable and Complementary Products
• Correlation networks from flows. The case of forced and time-dependent advection-diffusion dynamics
• On the Efficiency of the Information Networks in Social Media
• Evaluating Social Networks Using Task-Focused Network Inference

Cited by in corpus (10)

• Bayesian inference of network structure from unreliable data
• Network Inference from Consensus Dynamics
• Predicting synchronized gene coexpression patterns from fibration symmetries in gene regulatory networks in bacteria
• Snowboot: Bootstrap Methods for Network Inference
• Machine learning technique for morphological classification of galaxies from SDSS. II. The image-based morphological catalogs of galaxies at 0.02<z<0.1
• Spectral partitioning of time-varying networks with unobserved edges
• System Size Identification from Sinusoidal Probing in Diffusive Complex Networks
• Evaluating Social Networks Using Task-Focused Network Inference
• Tensor product algorithms for inference of contact network from epidemiological data
• Inferring the time-varying functional connectivity of large-scale computer networks from emitted events