Identifying and Using Driver Nodes in Temporal Networks

Babak Ravandi 1, Fatma Mili 2, and John A Springer 3Journal of Complex Networks, 2019. [journal] [Research Gate]DOI: 10.1093/comnet/cnz0041 PhD Candidate in Department of Computer and Information Technology, Purdue University, West Lafayette, Indiana 47906, USA2 Dean and Professor of College of Computing and Informatics, University of North Carolina at Charlotte, Charlotte, USA 3 Professor, Department of Computer and Information Technology, Purdue University, West Lafayette, Indiana 47906, USA

To download the accepted version scroll down.

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 modeled 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, i.e., links or edges. We focus here 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 Δ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 work, we propose a heuristic algorithm that quickly finds a suboptimal set of driver nodes with size N_s >= 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.

Complete Controllability with Two Driver Nodes (red: intervention points)

Performance of the heuristic approach

Ants’ interactions networks in 6 colonies

Ant Temnothorax rugatulus (Ants' interactions dataset is available here)

Identifying and using driver nodes in temporal networks - accepted version.pdf