

Pairwise disconnectivity index
The pairwise disconnectivity index (PDI) evaluates the topological significance of a network entity (vertex, edge, groups of vertices/edges) based on its influence on the connectedness of a network. This can be quantified by estimating how the deletion of an entity affects the existing number of connected ordered pairs of vertices in a network. The more of these pairs are being disconnected upon the removal of a network entity the more important it is.
In a directed network, an ordered pair of vertices (i,j) consists of two distinct nodes i and j. Such a pair is connected if there exists at least one path of any length from vertex i to vertex j. The pair (i,j) differs from the ordered pair (j,i), which is connected if there is a path from vertex j to vertex i. In an undirected network all pairs are unordered, i.e. (i,j) = (j,i).
Let G be a (directed) graph and N the number of connected (ordered) pairs of vertices in G. The PDI of a network entity is defined as

 N' 
PDI ( entity ) = 1   
 N 

and always ranges between 0 and 1. The maximum PDI of 1 means that no ordered pair of vertices in G is linked anymore due to the deletion of the entity whereas 0 indicates that all ordered pairs in G are still linked.
Note, that the meaning of N' depends on the chosen network entity. An entity may be

a single vertex v: N' refers to the number of connected (ordered) pairs of vertices in G without v and its edges.

a group of vertices, e.g. {a,b,c}: N' is the number of connected (ordered) pairs of vertices in G without the vertices a,b,c and their edges.

Figure 1. Estimating the pairwise disconnectivity index (PDI) of a vertex in an example network.


a single edge e: N' is the number of connected (ordered) pairs of vertices in G without e.

a group of edges, e.g. {a > b,c > a}: N' is the number of connected (ordered) pairs of vertices in G without the edges a > b and c > a.

Figure 2. Estimating the pairwise disconnectivity index (PDI) of an edge in an example network.


a topological pattern or a pattern instance: in a directed graph G, a pattern is the joint feature of every n connected vertices and describes the way how n vertices are connected with each other. A pattern always comprehends all existing edges between n vertices. None of the n vertices is isolated from the others, i.e. each of the n vertices must be directly attached to at least another one. If a pattern is overrepresented in G it is usually called a motif.
The uniqueness of the ith pattern in G, P_{i}^{n}, is due to its structure and the particular set of J subgraphs of G whose n vertices are exactly connected to each other as described by the pattern.
The subgraph P_{i,}^{n}_{j} is denoted as the jth instance of pattern
P_{i}^{n} and there is no other subgraph in G that is made of the same set of vertices and edges than
P_{i,}^{n}_{j} . Importantly, an edge e of the pattern instance
P_{i,}^{n}_{j} is incident only to vertices of this instance and denoted as an intrinsic edge of
P_{i,}^{n}_{j} .
Figure 3. Topological patterns and their instances. a) Toy graph G. b) The entirety of all patterns made of 3 vertices in G. c) The two instances of the second pattern in G. 
The topological role of a pattern instance is based on the coherence between its vertices. Since deleting the instrinsic edges destroys this coherence the PDI of a pattern instance is defined as
 N' 
PDI ( P_{i,}^{n}_{j} ) = 1   
 N 
and N' refers to the number of connected ordered pairs of vertices in G without the intrinsic edges of the pattern instance. For evaluating the topological role of the corresponding pattern the PDI values of all its instances need to be considered equally. Hence, the PDI of a pattern is defined as
 1   _{J}  
PDI ( P_{i}^{n} ) =    ∑  PDI ( P_{i,}^{n}_{j} ) 
 J   ^{j=1}  
Figure 4. Topological impact of a feedforward loop (ffl) instance with the intrinsic edges X > Y, X > Z and Y > Z.
Its environment is denoted by the blue vertices and edges. The connection between an ordered pair of vertices can be
affected only then by the ffl instance if all paths linking the pair consist of at least one of the instrinsic edges (e.g. the
ordered pair (2,6)). Otherwise, the pattern instance is not crucial for the connection (e.g. the ordered pair (2,4)).

For more detailed information about the pairwise disconnectivity index, please consider the related publications.


