Research Article: Structural Controllability of Temporal Networks with a Single Switching Controller

Date Published: January 20, 2017

Publisher: Public Library of Science

Author(s): Peng Yao, Bao-Yu Hou, Yu-Jian Pan, Xiang Li, Wen-Bo Du.


Temporal network, whose topology evolves with time, is an important class of complex networks. Temporal trees of a temporal network describe the necessary edges sustaining the network as well as their active time points. By a switching controller which properly selects its location with time, temporal trees are used to improve the controllability of the network. Therefore, more nodes are controlled within the limited time. Several switching strategies to efficiently select the location of the controller are designed, which are verified with synthetic and empirical temporal networks to achieve better control performance.

Partial Text

Since the seminal work of the Watts-Strogatz (WS) and Barabási-Albert (BA) models [1][2], we have a better understanding of our real world from the perspective of complex network science. With the development of portable electronic devices nowadays, people find that many real-world networks, generated from e-mail contacts [3], instant messages [4], online forums [5] and WiFi records [6–9], contain a plenty of temporal information which yields temporal networks [10]. Compared to static networks, temporal networks have their own characteristics such as bursts and the power-law distributions of contact intervals [11, 12].

In a temporal network, every node and edge might be valid (or activated) only at some specific time points. A temporal network is associated with a Linear Time-Variant (LTV) system as [38] X(k+1)-X(k)tk+1-tk=Ak+1TX(k)+Bk+1U(k)(1)
where k ∈ {0, 1, ⋯, T − 1}, tk+1 > tk. X(k)=[x1(k),x2(k),⋯,xN(k)]T∈RN is the vector of nodes, N denotes the number of nodes in the network. U(k)=[u1(k),u2(k),⋯,uM(k)]T∈RM is the vector of input signals from controllers outside the network. Ak+1∈RN×N denotes the adjacency matrix of the network at time point k + 1, and Ak+1T denotes its transpose matrix. Besides, the node set of the network is denoted as V = {v1, v2, ⋯, vN}. ∀ak+1,ij ∈ Ak+1, if there is a directed edge from node i to node j at time point k + 1, ak+1,ij ≠ 0. Otherwise, ak+1,ij = 0. Bk+1∈RN×M denotes the input matrix at time point k + 1. M is the number of external controllers (usually, M ≤ N). ∀bk+1,ij ∈ Bk+1, if controller j connects node i at time point k + 1, bk+1,ij > 0. Otherwise, bk+1,ij = 0. Pair (Ak+1, Bk+1) describes a network with its external controllers at time point k + 1 as well as its associated system. The discretized temporal network is then described by a sequence of pair (A1, B1), (A2, B2), ⋯, (AT, BT).

In summary, we have transformed a temporal network with a switching controller into the time-ordered graph (TOG) as well as its temporal trees. The location of the controller leads to heterogeneous trees so more nodes in the network could be controlled. As a result, the single switching controller almost makes all the network controlled with sufficient time. While a fixed controller could only control parts of the networks. Four controller switching strategies have been proposed to select the location of the controller. The “Global” strategy requires the knowledge of adjacency matrices over the whole time period. The “Descend” and “Ascend” strategies need the information of the aggregated degrees. The “Greedy” strategy only has to know the adjacency matrices of the past time points. These strategies are verified with both synthetic networks and empirical networks. In general, controller switching strategies that use more temporal topology information gain the higher efficiency. With the “Global” strategy, more nodes are controlled in limited time points. However, since the “Global” strategy (and the “Greedy” strategy as well) selects columns from matrices Gk, k = 1, 2, ⋯, T, to enlarge the rank of Wc, this leads to more computational cost and time to find the controller’s proper location, which would be difficult to satisfy when the network size increases. Therefore, we have to make a tradeoff between the demand of computational resource and the strategy performance.