From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles

Abstract

The inference of network topologies from relational data is an important problem in data analysis. Exemplary applications include the reconstruction of social ties from data on human interactions, the inference of gene co-expression networks from DNA microarray data, or the learning of semantic relationships based on co-occurrences of words in documents. Solving these problems requires techniques to infer significant links in noisy relational data. In this short paper, we propose a new statistical modeling framework to address this challenge. It builds on generalized hypergeometric ensembles, a class of generative stochastic models that give rise to analytically tractable probability spaces of directed, multi-edge graphs. We show how this framework can be used to assess the significance of links in noisy relational data. We illustrate our method in two data sets capturing spatio-temporal proximity relations between actors in a social system. The results show that our analytical framework provides a new approach to infer significant links from relational data, with interesting perspectives for the mining of data on social systems.

arXiv comment10 pages, 8 figures, accepted at SocInfo2017

References in corpus (19)

• Modularity and community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Multilayer Networks
• Stochastic blockmodels and community structure in networks
• Multirelational Organization of Large-scale Social Networks in an Online World
• Modern temporal network theory: A colloquium
• Memory in network flows and its effects on spreading dynamics and community detection
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Learning Latent Block Structure in Weighted Networks
• Systemic risk analysis in reconstructed economic and financial networks
• When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
• Generalized communities in networks
• Higher-Order Aggregate Networks in the Analysis of Temporal Networks: Path structures and centralities
• Value of peripheral nodes in controlling multilayer networks
• A testing based extraction algorithm for identifying significant communities in networks
• Irreducible network backbones: unbiased graph filtering via maximum entropy
• The essential role of time in network-based recommendation
• Multiplex Network Regression: How do relations drive interactions?

Cited by in corpus (8)

• The structured backbone of temporal social ties
• Modeling social resilience: Questions, answers, open problems
• Building surrogate temporal network data from observed backbones
• HYPA: Efficient Detection of Path Anomalies in Time Series Data on Networks
• Multiplex Network Regression: How do relations drive interactions?
• The likelihood-ratio test for multi-edge network models
• Transforming Collaboration Data into Network Layers for Enhanced Analytics
• Probabilistic Multilayer Networks