Disparity filter algorithm of weighted network

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Disparity filter[1] is a network reduction algorithm to extract the backbone structure of undirected weighted network. Many real world networks such as citation networks, food web, airport networks display heavy tailed statistical distribution of nodes' weight and strength. Disparity filter can sufficiently reduce the network without destroying the multi-scale nature of the network. The algorithm is developed by M. Angeles Serrano, Marian Boguna and Alessandro Vespignani.

Overview of other network reduction algorithms and their limitations[edit]

k-core decomposition[edit]

k-core decomposition is an algorithm that reduces a graph into a maximal connected subgraph of vertices with at least degree k. This algorithm can only be applied to unweighted graphs.

Minimum spanning tree[edit]

A minimum spanning tree is a tree-like subgraph of a given graph G, in which it keeps all the nodes of graph G but minimize the total weight of the subgraph. A minimum spanning tree is the least expensive way to maintain the size of connected component. The significant limitation of this algorithm is it overly simplify the structure of the network(graph). Minimum spanning tree destroys local cycles, clustering coefficient which usually present in real networks and are considered as important network measurement.

Global weight threshold[edit]

A weighted graph can be easily reduced to a subgraph in which any of the edges' weight is larger than a given threshold wc. This technic has been applied to study the resistance of food web[2] and functional networks that connect correlated human brain sites.[3] The short come of this method is that it overpass the nodes with small strength. However, in real network, both strength and weight distribution in general follows heavy tailed distribution which spans several degree of order. Applying a simple cutoff on weight will removes all the information below the cut-off.

Disparity filter algorithm[edit]

The null model of normalized weight distribution[edit]

In network science, the strength notated as si of a node i is defined as si = ∑jwij, where wij is the weight of link between i and j.

In order to apply the disparity filter algorithm without overlooking nodes with low strength, a normalized weight pij is defined as pij = wij/si. In the null model, the normalized weights of a certain node with degree k is generated like this: k − 1 pins are randomly assigned between the interval 0 and 1. The interval is divide into k subintervals. The length of the subinterval represents the normalized weight of each link in the null model.

Consecutively, and based on the null model, we can derive that the normalized weight distribution of a node with degree k follows .[1]

Disparity filter[edit]

The disparity filter algorithm is based on p-value[4] statistical significance test[5] of the null model: For a given normalized weight pij, the p-value αij of pij based on the null model is given by which reduces to . The meaning of αij is the probability of having normalized weight larger or equal to pij in the framework of the given null model. By setting a significance level α (between 0 and 1), for any link of normalized weight pij, if αij is larger than α, it will be filtered out. Changing α we can progressively remove irrelevant links thus effectively extracting the backbone structure of the weighted network.[1]

Generalizations[edit]

Pólya Filter[edit]

The disparity filter algorithm has been shown to be a particular case of the Pólya Filter[6] (built around the famous combinatorial scheme known as the Pólya Urn). The Pólya Filter is able to adapt the filtering procedure to the network's own heterogeneity by using a Maximum Likelihood procedure to set its free parameter , which represent the strength of the self reinforcing mechanism ruling the underlying urn scheme. Given a significance level , the Pólya Filter has been shown to produce backbones much more sparse than the disparity filter and yet able to retain the most salient[7] links of the system.

See also[edit]

External links[edit]

References[edit]

  1. ^ a b c Serrano, M.Angeles; Boguna, Marian; Vespignani, Alessandro (2009), "Extracting the multiscale backbone of complex weighted networks", Proceedings of the National Academy of Sciences, 106 (16): 6483–6488, arXiv:0904.2389, Bibcode:2009PNAS..106.6483S, doi:10.1073/pnas.0808904106, PMC 2672499, PMID 19357301.
  2. ^ Eguiluz, Victor M; Chialvo, Dante R; Cecchi, Guillermo A; Baliki, Marwan; Apkarian, A Vania (2005), "Scale-free brain functional networks", Physical Review Letters, 94 (1): 018102, arXiv:cond-mat/0309092, Bibcode:2005PhRvL..94a8102E, doi:10.1103/PhysRevLett.94.018102, PMID 15698136.
  3. ^ Allesina, Stefano; Bodini, Antonio; Bondavalli, Cristina (2006), "Secondary extinctions in ecological networks: bottlenecks unveiled", Ecological Modelling, 194 (1): 150–161, doi:10.1016/j.ecolmodel.2005.10.016.
  4. ^ Goodman, SN (1999). "Toward Evidence-Based Medical Statistics. 1: The P Value Fallacy". Annals of Internal Medicine. 130 (12): 995–1004. doi:10.7326/0003-4819-130-12-199906150-00008. PMID 10383371.
  5. ^ R. A. Fisher (1925).Statistical Methods for Research Workers, Edinburgh: Oliver and Boyd, 1925, p. 43.
  6. ^ Marcaccioli, Riccardo; Livan, Giacomo (2019-02-14). "A Pólya urn approach to information filtering in complex networks". Nature Communications. 10 (1): 1–10. doi:10.1038/s41467-019-08667-3. ISSN 2041-1723. PMID 30765706.
  7. ^ Grady, Daniel; Thiemann, Christian; Brockmann, Dirk (2012-05-29). "Robust classification of salient links in complex networks". Nature Communications. 3 (1): 1–10. doi:10.1038/ncomms1847. ISSN 2041-1723.