Abstract
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 tf within Δt=tf−t0 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 Nc 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 Ns > Nc . 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.
Keywords
temporal networks; complex networks; driver nodes; controllability; heuristic
Date of this Version
3-8-2019
Comments
This is the post-print version of the article. The version of record was published in IMA Journal of Complex Networks. DOI: 10.1093/comnet/cnz004