Controllability and observability analysis for vertex domination centrality in directed networks

Abstract

Topological centrality is a significant measure for characterising the relative importance of a node in a complex network. For directed networks that model dynamic processes, however, it is of more practical importance to quantify a vertex's ability to dominate (control or observe) the state of other vertices. In this paper, based on the determination of controllable and observable subspaces under the global minimum-cost condition, we introduce a novel direction-specific index, domination centrality, to assess the intervention capabilities of vertices in a directed network. Statistical studies demonstrate that the domination centrality is, to a great extent, encoded by the underlying network's degree distribution and that most network positions through which one can intervene in a system are vertices with high domination centrality rather than network hubs. To analyse the interaction and functional dependence between vertices when they are used to dominate a network, we define the domination similarity and detect significant functional modules in glossary and metabolic networks through clustering analysis. The experimental results provide strong evidence that our indices are effective and practical in accurately depicting the structure of directed networks.

Figure 1. A schematic diagram illustrating the physical meaning of domination capability.

By inputting a signal at the vertex i, the state variables in the downstream system S₂ can be controlled. By observing the state variables by measuring the state of vertex i, a feedback loop can be constructed to control the upstream system S₁.

Figure 2. A schematic diagram illustrating the domination centrality and the domination similarity of vertices in a directed network.

(a): A maximum matching M₁ consisting of red links, forms a stem (in shades of green)-cycle (in shades of red) disjoint cover of the network. Additional links (AL) that connect the stems and cycles are highlighted by bold dashed lines. (b): The controllable subspace of vertex 1 is highlighted by a purple dotted line, and its observable subspace is highlighted by a green dotted line. The domination centrality of vertex 1 is the harmonic mean of the size of these two subspaces. (c): Another maximum matching, M₂, is given. (d): The controllable subspace of vertex 2 is highlighted by an orange dotted line, and its observable subspace is highlighted by a blue dotted line. (e): The overlapping phenomenon of the controllable subspaces and the observable subspaces is depicted. The Jaccard similarity coefficients of the controllable subspaces and the observable subspaces are calculated, and the arithmetic-geometric mean thereof is used to determine the domination similarity.

Figure 3. The distribution of the domination centrality in double-logarithmic coordinates.

The results for scale-free synthetic directed networks with N = 5000, 〈k_in〉 = 〈k_out〉 = 〈k〉/2 = 3, and are shown.

Figure 4. A schematic diagram illustrating the domination centrality in Homo sapiens networks.

(a): The average values of domination centrality among low-, medium- and high-degree vertices. The scatter plots of the domination centrality versus the vertex in-degree, out-degree and degree are presented in panel (b), panel (c) and panel (d), respectively. The green, blue and purple plots represent the real network, rand-Degree network and rand-ER network, respectively.

Figure 5. Module-detection results in the directed glossary network.

The modules are labelled with colours.

Figure 6. Module-detection results in the Homo sapiens network.

Certain representative modules are marked with colours and the corresponding GO terms and p-values are given.

Figure 7. The influence of the number of random samples among all maximum matchings on the domination-similarity result.

The growth rates of the sum of the complete control and observation subspaces as functions of the number of random samples of maximum matchings in the GlossTG, Homo sapiens and SmaGri networks are shown.

Figure 8. A schematic diagram illustrating the process of random sampling.

(a): The original network. (b): A bipartite graph separated into the out and in sets; the red link set {l_1,2,l_2,3,l_4,5} forms a maximum matching, M₁, and the blue path is an augmenting path when the matched link l_1,2 is removed. (c): A new maximum matching M₂ constructed by alternating the blue augmenting path.

Figure 9. The distribution of the counts in each of the 164 COLs in the GlossTG network.

(a): A matched link l_j is randomly selected from an M with a probability of 1/|M|. (b) The selection probability is adjusted based on the number of alternative COLs that are enumerated by our sampling procedure.