Disparity filter algorithm of weighted network

Theory

Network types

Features
Clique Component Cut Cycle Data structure Edge Loop Neighborhood Path Vertex Adjacency list / matrix Incidence list / matrix
Types
Bipartite Complete Directed Hyper Multi Random Weighted

Models

Topology
Random graph Erdős–Rényi Barabási–Albert Watts–Strogatz Exponential random (ERGM) Hyperbolic (HGN) Hierarchical Stochastic block model
Dynamics
Boolean network agent based Epidemic/SIR

Lists
Categories

Category:Network theory
Category:Graph theory

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

k-core decomposition

k-core decomposition is an algorithm that reduce 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

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

A weighted graph can be easily reduced to a subgraph in which any of the edges' weight is larger than a given threshold w_c. 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

The null model of normalized weight distribution

In network science, the strength s_i of a node i is defined as s_i = ∑_jw_ij, where w_ij is the weight of link between i and j. In order to apply disparity filter algorithm without overlooking nodes with low strength, a normalized weight p_ij is defined as p_ij = w_ij/s_i. 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. Based on this model, we can derive that the normalized weight distribution of a node with degree k follows $\rho (x)\,dx=(k-1)(1-x)^{{k-2}}\,dx$ .^[1]

Disparity filter

The disparity filter algorithm is based on p-value^[4] statistical significance test^[5] of the null model: For a given normalized weight p_ij, the p-value α_ij of p_ij based on the null model is given by $\alpha _{{ij}}=1-(k-1)\int _{0}^{{p_{{ij}}}}(1-x)^{{k-2}}\,dx$ which reduces to $\alpha _{ij}=(1-p_{ij})^{k-1}$ . The meaning of α_ij is the probability of having normalized weight larger or equal to p_ij in the framework of the given null model. By setting a significance level α (between 0 and 1), for any link of normalized weight p_ij, 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]

External links

References

1 2 3 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 .
↑ 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 .
↑ 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 .
↑ Goodman, SN (1999). "Toward Evidence-Based Medical Statistics. 1: The P Value Fallacy.". Annals of Internal Medicine. 130: 995–1004. doi:10.7326/0003-4819-130-12-199906150-00008. PMID 10383371.
↑ R. A. Fisher (1925).Statistical Methods for Research Workers, Edinburgh: Oliver and Boyd, 1925, p. 43.

This article is issued from Wikipedia - version of the 7/19/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.