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 - divided by
 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 over-represented in G it is usually called a motif.

    The uniqueness of the i-th pattern in G, Pin, 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 Pi,nj is denoted as the j-th instance of pattern Pin and there is no other subgraph in G that is made of the same set of vertices and edges than Pi,nj . Importantly, an edge e of the pattern instance Pi,nj is incident only to vertices of this instance and denoted as an intrinsic edge of Pi,nj .


    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 ( Pi,nj )  =  1 - divided by
     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 ( Pin )  =     PDI ( Pi,nj )
     J   j=1 


    Figure 4. Topological impact of a feed-forward 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.

 
 

...::: Department of Bioinformatics, Center of Informatics,Statistics and Epidemiology UMG, University of Göttingen :::...