Identifying and using driver nodes in temporal networks

• Published in: Journal of complex networks 2019-10, Vol.7 (5), p.720-748
• Main Authors: Ravandi, Babak, Mili, Fatma, Springer, John A
• Format: Article
• Language: English
• ISSN: 2051-1329; 2051-1329
• DOI: 10.1093/comnet/cnz004

In many approaches developed for defining complex networks, the main assumption is that the network is in a relatively stable state that can be approximated with a fixed topology. However, in several applications, this approximation is not adequate because (a) the system modelled is dynamic by nature, and (b) the changes are an essential characteristic that cannot be approximated. Temporal networks capture changes in the topology of networks by including the temporal information associated with their structural connections, that is, links or edges. Here, we focus on controllability of temporal networks, that is, the study of steering the state of a network to any desired state at deadline $t_f$ within $\Delta t=t_f - t_0$ steps through stimulating key nodes called driver nodes. Recent studies provided analytical approaches to find a maximum controllable subspace for an arbitrary set of driver nodes. However, finding the minimum number of driver nodes $N_c$ required to reach full control is computationally prohibitive. In this article, we propose a heuristic algorithm that quickly finds a suboptimal set of driver nodes with size $N_s \geq N_c$. We conduct experiments on synthetic and real-world temporal networks induced from ant colonies and e-mail communications of a manufacturing company. The empirical results in both cases show the heuristic algorithm efficiently identifies a small set of driver nodes that can fully control the networks. Also, as shown in the case of ants’ interactions networks, the driver nodes tend to have a large degree in temporal networks. Furthermore, we analyze the behavior of driver nodes within the context of their datasets, through which, we observe that queen ants tend to avoid becoming a driver node.