Edge orientation for optimizing controllability of complex networks

Recently, as the controllability of complex networks attracts much attention, how to design and optimize the controllability of networks has become a common and urgent problem in the field of controlling complex networks. Previous work focused on the structural perturbation and neglected the role of edge direction to optimize the network controllability. In a recent work [Phys. Rev. Lett. 103, 228702 (2009)], the authors proposed a simple method to enhance the synchronizability of networks by assignment of link direction while keeping network topology unchanged. However, the controllability is fundamentally different from synchronization. In this work, we systematically propose the definition of assigning direction to optimize controllability, which is called the edge orientation for optimal controllability problem (EOOC). To solve the EOOC problem, we construct a switching network and transfer the EOOC problem to find the maximum independent set of the switching network. We prove that the principle of our optimization method meets the sense of unambiguity and optimum simultaneously. Furthermore, the relationship between the degree-degree correlations and EOOC are investigated by experiments. The results show that the disassortativity pattern could weaken the orientation for optimal controllability, while the assortativity pattern has no correlation with EOOC. All the experimental results of this work verify that the network structure determines the network controllability and the optimization effects.

Figure 1

Illustration of the orientation of node residual degree (NRD). The original network (a) consists of eight nodes and 12 edges. The above control configuration has two driver nodes, while the under configuration has only one driver node. The yellow node is the start node in each orientation process and the red arcs are edge directions oriented by NRD. The gray dashed lines are not yet oriented. If there is more than one suitable choice, NRD randomly selects a node or edge from the network. As node 5 (black node) has two available choices to orient edge, it results in two different numbers of driver nodes, shown as blue nodes in (d). The orientation process of steps (i), (ii), and (iii) are repeated until all nodes and edges are exhausted.

Figure 2

Illustration of finding the maximum vertex independent set to solve the orientation problem of EOOC. (a) An undirected network $G=(V,E)$ with five nodes and five undirected edges. $G^{\prime }$ is the symmetric directed network. (b) The switching network $H$ with $2·\left|E\right|$ nodes. Rule I avoids orienting the network with many two-cycle patterns between the pairs of nodes. Rule II prevents generating some in edges or out edges sharing the common tail or head node. (c) The maximum independent set of $H$ corresponds to an orientation set of $G$ which produces the least number of driver nodes. Even though there are a few different sets and they result in some different control configurations, all the control configurations have the same number of driver nodes.

Figure 3

Characteristics of $n_D$ as a function of $\langle k\rangle$ for random orientation, NRD orientation and optimal orientation on (a) ER networks, (b) SF networks with $\gamma =2.5$, (c) SF networks with $\gamma =3$, and (d) SF networks with $\gamma =4$. The results are averaged over 50 independent realizations.

Figure 4

Illustration of edge orientation of optimal controllability for directed networks. (a) A directed network $G=(V,E)$ with four nodes and four directed edges. For directed networks, some edges with inappropriate direction affect the controllability of networks, such as the blue edges. If we change the direction of blue edges, it can improve its controllability. (b) $G^{\prime }$ is the symmetric directed network. Here we assume that the weight of the real edge is 1; otherwise it is 0. Thus it results that the nodes of $H$ have weight. (c) The switching network $H$. The red nodes correspond to the real edges in $G$. The node with weight 0 in the maximum-weighted independent set implies the inappropriate edge of $G$. Therefore, the maximum-weighted independent set means not only the optimal edge orientation but also the least number of edges to change direction. In addition, although there are several different maximum-weighted independent sets, the same number of driver nodes is guaranteed for the different control configurations.

Figure 5

Characteristics of $n_D$ and percent of edge modification as a function of $\langle k\rangle$ for initial networks and modified networks on (a) and (b) ER networks; (c) and (d) SF networks with $\gamma =2.5$; (e) and (f) SF networks with $\gamma =3$. The results are averaged over 50 independent realizations.

Figure 6

Characteristics of $n_D$ as a function of degree-degree correlation $r$ for optimal orientation on (a) ER networks, (b) SF networks with $\gamma =3$, and (c) SF networks with $\langle k\rangle =3$. The results are averaged over 50 independent realizations.

Figure 7

Plot of $n_D$ and percent of edge modification as a function of four different degree-degree correlations $r(\alpha ,\beta ),\alpha ,\beta \in \left\{\mathrm{in},\mathrm{out}\right\}$ for initial networks and modified networks on ER networks. The subplots show the four directed degree-degree correlations of directed networks. The fuzzy directed links represent that they do not enter into the specific correlation. The results are averaged over 50 independent realizations.