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

For full version of this article please email me.

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)

Distributed and Centralized Control Regimes in Temporal Networks

We analyzed the intersections of nodes between the Suboptimal Minimum Driver node Sets (SMDSs) identified by our heuristic approach. Also, we were able to find the optimal solutions, Minimum Driver node Sets (MDSs), by brute force for the ants' interaction networks. Our heuristic approach shows the ant networks operate under a distributed control regime. But, the email communication network operates under a centralized control regime. The below figure illustrates the results.

Distributed and centralized control regimes in temporal networks

An execution of the proposed heuristic on a simple temporal network

The goal is finding a minimum number of driver nodes (sources in the below-left picture, e.g., s_1 and s_2) that can originate N number of node-disjoint paths that cover all nodes in the deadline (last) layer, where N is the number of nodes in a temporal networks.

An example of such node-disjoint paths are provide in the below-left figure (distinguished with color).

Identifying the Maximum Controllable Space (MCS) of a set of drivers using a maximum flow

Execution of the heuristic approach on simple temporal network

An execution of the proposed heuristic on a simple temporal network using the maximum controllable space of each node.

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