A parametric approach to information filtering in complex networks: The Pólya filter

Abstract

The ever increasing availability of data demands for techniques to extract relevant information from complex interacting systems, which can often be represented as weighted networks. In recent years, a number of approaches have been proposed to extract network backbones by assessing the statistical significance of links against null hypotheses of random interaction. Yet, it is well known that the growth of most real-world networks is highly non-random, as past interactions between nodes typically increase the likelihood of further interaction. Here, we propose a network filtering methodology based on a family of null hypotheses that can be calibrated to assess which links are statistically significant with respect to a given network's own heterogeneity. We design such family of null hypotheses by adapting the Pólya urn, a simple one-parameter combinatorial model driven by a self-reinforcement mechanism, to a network setting. We provide a full analytical description of our filter, and show that it retains or discards links based on a non-trivial interplay between their own local importance and the importance of the nodes they belong to. We prove that the widely used disparity filter can be recovered as a large-strength approximation for a specific value of the Pólya filter's parameter, and illustrate our findings by applying the filter to two large network datasets.

arXiv comment24 pages, 14 figures, 2 tables

References in corpus (23)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community detection in graphs
• The architecture of complex weighted networks
• Hierarchical Structure in Financial Markets
• Scale-free brain functional networks
• A tool for filtering information in complex systems
• Extracting the multiscale backbone of complex weighted networks
• Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
• Weighted evolving networks: coupling topology and weights dynamics
• Statistically validated networks in bipartite complex systems
• Weighted network modules
• World Input-Output Network
• Robust classification of salient links in complex networks
• Transport in weighted networks: Partition into superhighways and roads
• The Geospatial Characteristics of a Social Movement Communication Network
• Backbone of complex networks of corporations: The flow of control
• Hierarchical information clustering by means of topologically embedded graphs
• Predicting missing links and their weights via reliable-route-based method
• Information filtering in complex weighted networks
• Unwinding the hairball graph: pruning algorithms for weighted complex networks
• Statistically validated mobile communication networks: Evolution of motifs in European and Chinese data
• Transport on weighted Networks: when correlations are independent of degree

Cited by in corpus (14)

• backbone: An R package to extract network backbones
• Interacting discovery processes on complex networks
• The structured backbone of temporal social ties
• An Evaluation Tool for Backbone Extraction Techniques in Weighted Complex Networks
• Meta-validation of bipartite network projections
• Generalised hypergeometric ensembles of random graphs: the configuration model as an urn problem
• Extracting the signed backbone of intrinsically dense weighted networks
• Identifying sinks and sources of human flows: A new approach to characterizing urban structures
• The influence of coordinated behavior on toxicity
• Correspondence between temporal correlations in time series, inverse problems, and the Spherical Model
• Time-Dependent Urn Models reproduce the full spectrum of novelties discovery
• Generating Preferential Attachment Graphs via a Pólya Urn with Expanding Colors
• Sector Neutral Portfolios: Long memory motifs persistence in market structure dynamics
• An egonet-based approach to effective weighted network comparison