# Network Backboning with Noisy Data

@article{Coscia2017NetworkBW, title={Network Backboning with Noisy Data}, author={Michele Coscia and Frank M. H. Neffke}, journal={2017 IEEE 33rd International Conference on Data Engineering (ICDE)}, year={2017}, pages={425-436} }

Networks are powerful instruments to study complex phenomena, but they become hard to analyze in data that contain noise. [...] Key Method Our approach uses a more realistic null model for the edge weight creation process than prior work. In particular, it simultaneously considers the propensity of nodes to send and receive connections, whereas previous approaches only considered nodes as emitters of edges. We test our model with real world networks of different types (flows, stocks, cooccurrences, directedâ€¦ Expand

#### Figures, Tables, and Topics from this paper

#### 47 Citations

A PĂłlya urn approach to information filtering in complex networks

- Computer Science, Biology
- Nature Communications
- 2019

A filtering methodology inspired by the PĂłlya urn is proposed, a combinatorial model driven by a self-reinforcement mechanism, which relies 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. Expand

Sparsistent filtering of comovement networks from high-dimensional data

- Computer Science, Mathematics
- ArXiv
- 2021

Applying asymptotic theory for high dimensional data for the filter, it is shown that it can be tuned to interpolate between zero filtering to maximal filtering that induces sparsity and consistency while having the least spectral distance from a linear shrinkage estimator. Expand

Irreducible network backbones: unbiased graph filtering via maximum entropy

- Mathematics, Physics
- ArXiv
- 2017

This work introduces a rigorous method that outputs the network backbone that is irreducible to the local properties of nodes, i.e. their degrees and strengths and employs an exact maximum-entropy formulation guaranteeing that the filtered network encodes only the links that cannot be inferred from local information. Expand

Noise Corrected Sampling of Online Social Networks

- Computer Science
- ACM Trans. Knowl. Discov. Data
- 2021

Overall, the noise-corrected network sampling performs well: it has the best rank average among the tested methods across a wide range of applications. Expand

Pearson Correlations on Complex Networks

- 2021

Complex networks are useful tools to understand propagation events like epidemics, word-of-mouth, adoption of habits, and innovations. Estimating the correlation between two processes happening onâ€¦ Expand

Using arborescences to estimate hierarchicalness in directed complex networks

- Computer Science, Medicine
- PloS one
- 2018

This paper proposes a structural argument: a network has a strong top-down organization if the authors need to delete only few edges to reduce it to a perfect hierarchyâ€”an arborescence. Expand

Extracting the signed backbone of intrinsically dense weighted networks

- Computer Science, Physics
- J. Complex Networks
- 2021

The first methods for extracting signed network backbones from intrinsically dense unsigned weighted networks are provided using a null model based on statistical techniques and the proposed significance filter and vigor filter allow inferring edge signs. Expand

Detecting informative higher-order interactions in statistically validated hypergraphs

- Physics, Computer Science
- Communications Physics
- 2021

This work proposes an analytic approach to filter hypergraphs by identifying those hyperlinks that are over-expressed with respect to a random null hypothesis, and represent the most relevant higher-order connections. Expand

SeiĂ°r: Efficient Calculation of Robust Ensemble Gene Networks

- Biology
- 2021

Seidr (stylized SeiĂ°r), a software toolkit designed to assist scientists in gene regulatory and gene co-expression network inference, which creates community networks to reduce algorithmic bias and utilizes noise corrected network backboning to prune noisy edges in the networks. Expand

Benchmarking API Costs of Network Sampling Strategies

- Computer Science
- 2018 IEEE International Conference on Big Data (Big Data)
- 2018

This paper creates a benchmark that tests the performance of a method in a multifaceted way, and shows that some methods which are considered to perform poorly actually can perform well with tighter budgets, or with different API policies. Expand

#### References

SHOWING 1-10 OF 48 REFERENCES

Nonparametric Sparsification of Complex Multiscale Networks

- Physics, Medicine
- PloS one
- 2011

This paper introduces a new method for backbone extraction that does not rely on any particular null model, but instead uses the empirical distribution of similarity weight to determine and then retain statistically significant edges. Expand

Missing and spurious interactions and the reconstruction of complex networks

- Computer Science, Medicine
- Proceedings of the National Academy of Sciences
- 2009

This work is able to reliably identify both missing and spurious interactions in noisy network observations and enables network reconstructions that yield estimates of the true network properties that are more accurate than those provided by the observations themselves. Expand

Robust classification of salient links in complex networks.

- Computer Science, Physics
- Nature communications
- 2012

It is shown that link salience is a robust approach to classifying network elements based on a consensus estimate of all nodes, and points towards a better understanding of universal features in empirical networks that are masked by their complexity. Expand

Extracting the multiscale backbone of complex weighted networks

- Medicine, Computer Science
- Proceedings of the National Academy of Sciences
- 2009

A filtering method is defined that offers a practical procedure to extract the relevant connection backbone in complex multiscale networks, preserving the edges that represent statistically significant deviations with respect to a null model for the local assignment of weights to edges. Expand

Sparsification of influence networks

- Mathematics, Computer Science
- KDD
- 2011

It is claimed that sparsification is a fundamental data-reduction operation with many applications, ranging from visualization to exploratory and descriptive data analysis, and an optimal, dynamic-programming algorithm is presented, whose search space is typically much smaller than that of the brute force, exhaustive-search approach. Expand

Network Sampling: From Static to Streaming Graphs

- Computer Science, Physics
- TKDD
- 2013

A family of sampling methods based on the concept of graph induction that generalize across the full spectrum of computational models (from static to streaming) while efficiently preserving many of the topological properties of the input graphs. Expand

Structure-preserving sparsification methods for social networks

- Mathematics, Computer Science
- Social Network Analysis and Mining
- 2016

The first systematic conceptual and experimental comparison of edge sparsification methods on a diverse set of network properties is contributed and it is shown that they can be understood as methods for rating edges by importance and then filtering globally or locally by these scores. Expand

Maps of random walks on complex networks reveal community structure

- Computer Science, Physics
- Proceedings of the National Academy of Sciences
- 2008

An information theoretic approach is introduced that reveals community structure in weighted and directed networks of large-scale biological and social systems and reveals a directional pattern of citation from the applied fields to the basic sciences. Expand

The architecture of complex weighted networks.

- Mathematics, Physics
- Proceedings of the National Academy of Sciences of the United States of America
- 2004

This work studies the scientific collaboration network and the world-wide air-transportation network, which are representative examples of social and large infrastructure systems, respectively, and defines appropriate metrics combining weighted and topological observables that enable it to characterize the complex statistical properties and heterogeneity of the actual strength of edges and vertices. Expand

Sampling from large graphs

- Mathematics, Computer Science
- KDD '06
- 2006

The best performing methods are the ones based on random-walks and "forest fire"; they match very accurately both static as well as evolutionary graph patterns, with sample sizes down to about 15% of the original graph. Expand