User:Augustulus2/sandbox

This is the user sandbox of Augustulus2. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

The Pairwise Disconnectivity Index (PDI) of a network’s element $e$ is a measure of topological significance of $e$ in the network, i.e. how essential for all connections in the network this element $e$ is^[1]. Such an element $e$ can be a vertex, an edge or any combination thereof. $PDI(e)$ equals to the fraction of directed paths that critically depend on the presence of $e$ in the network. This index can be viewed as a measure of redundancy of paths in a network.

PDI considers paths of any length ( $l=1,2,3...$ ) and, like betweenness centrality (BC), is a global metric. It differs from BC in several aspects. While BC emphasizes only shortest paths in a network, PDI considers all existing paths. Then, while BC addresses only to those vertices that are between other ones, PDI also applies to peripheral vertices, i.e. vertices having either zero incoming or outgoing degree.

Definition

In a directed graph $G(V,E)$ , an ordered pair of vertices $\{i,j\}|i\neq j\land i,j\in V$ , is connected if there is at least one path of any length from node i to node j in $G$ . After the removal of a given element $e$ from $G$ , we obtain a new graph $G'(V',E')|V'\in V,E'\in E$ . The more ordered pairs become disconnected upon the removal of $e$ , the higher is the topological significance of this element. Note that the ordered pair {i, j} differs from {j, i} in a directed network. Formally, the PDI of $e$ is defined as

PDI(e)=1-N'/N,

where $N$ is the number of connected ordered pairs of nodes in the original graph $G$ and $N'$ is the corresponding number in the resulting graph $G'$ after the removal of $e$ from $G$ ^[1]. The value of $PDI(e)$ ranges between 0 and 1. The maximum value 1 means that no ordered pair of nodes is linked anymore after deletion of a given $e$ and the minimum value 0 indicates that all connected ordered pairs in $G$ are still linked. Importantly, such a pairwise disconnection of nodes does not necessarily lead to a network’s disintegration - it may happen in a still connected network as well.

Practical applications

The topological significance of nodes and edges

$PDI(e)$ is estimated in a similar way as the role of a gene is investigated by knock-out experiments. The approach was applied to biological regulatory networks from different species^[1]. The genes or proteins with high PDI values were found to be of particular functional importance. The PDI of a vertex and its degree or betweenness centrality do not exhibit a simple relationship^[1]^[2].

The topological significance of network patterns and motifs

The concept of PDI can be adopted for analyzing the network patterns (e.g. network motifs) and their individual instances^[2]. To quantify the significance of a pattern instance, one has to eliminate all intrinsic (i.e. internal) edges of a pattern instance and measure how this affects the number of connected ordered pairs of vertices in the network. That is, the elimination is targeted on the intrinsic edges of a given subgraph, but not necessarily on its nodes. In the transcriptional networks of bacteria (E. coli), a unicellular eukaryote (S. cerevisiae) and higher eukaryotes (human, mouse, rat), the topological significance of a network instance does not easily correlate with the abundance of the respective pattern in a network^[2]^[3]. Although motifs, i.e. statistically significant sub-graphs or patterns, may play an essential role in their respective local contexts,^[4] they do not seem to be generally more important than other non-motif patterns for the global architecture of a network. ^[2]

Link to service for measuring the PDI

DiVa Online is a service to evaluate the topological role of a network entity in a network by calculating the pairwise disconnectivity index. It enables to do either a general analysis for all vertices/edges in given networks, to perform a targeted survey for selected ones, or to estimate the global impact of network patterns and motifs.

References

^ ^a ^b ^c ^d Potapov, A.P.; Goemann, B.; Wingender, E. (2008). "The pairwise disconnectivity index as a new metric for the topological analysis of regulatory networks". BMC Bioinformatics. 9: 227. PMID 18454847.
^ ^a ^b ^c ^d Goemann, B.; Wingender, E.; Potapov, A.P. (2009). "An approach to evaluate the topological significance of motifs and other patterns in regulatory networks". BMC Syst. Biol. 3: 53. PMID 19454001.
^ Goemann, B.; Potapov, A.P.; Ante, M.; Wingender, E. (2009). "Comparative analysis of topological patterns in different mammalian networks". Genome Inform. 23: 32–45. PMID 20180260.
^ Milo, R.; Shen-Orr, S.; Itzkovitz, S.; Kashtan, N.; Chklovskii, D.; Alon, U. (2002). "Network motifs: Simple building blocks of complex networks". Science. 298: 824–827. PMID 12399590.

External links

[1], DiVa Online, a server for calculating PDI values for a user-defined network

[potapov2008-1] Potapov, A.P.; Goemann, B.; Wingender, E. (2008). "The pairwise disconnectivity index as a new metric for the topological analysis of regulatory networks". BMC Bioinformatics. 9: 227. PMID 18454847.

[goemann2009-2] Goemann, B.; Wingender, E.; Potapov, A.P. (2009). "An approach to evaluate the topological significance of motifs and other patterns in regulatory networks". BMC Syst. Biol. 3: 53. PMID 19454001.

[goemann2009b-3] Goemann, B.; Potapov, A.P.; Ante, M.; Wingender, E. (2009). "Comparative analysis of topological patterns in different mammalian networks". Genome Inform. 23: 32–45. PMID 20180260.

[milo2002-4] Milo, R.; Shen-Orr, S.; Itzkovitz, S.; Kashtan, N.; Chklovskii, D.; Alon, U. (2002). "Network motifs: Simple building blocks of complex networks". Science. 298: 824–827. PMID 12399590.

[1]

[2]

[3]

[4]