An efficient algorithm for finding all possible input nodes for controlling complex networks
arXiv:1703.00876 · doi:10.1038/s41598-017-10744-w
Abstract
Understanding structural controllability of a complex network requires to identify a Minimum Input nodes Set (MIS) of the network. It has been suggested that finding an MIS is equivalent to computing a maximum matching of the network, where the unmatched nodes constitute an MIS. However, maximum matching of a network is often not unique, and finding all MISs may provide deep insights to the controllability of the network. Finding all possible input nodes, which form the union of all MISs, is computationally challenging for large networks. Here we present an efficient enumerative algorithm for the problem. The main idea is to modify a maximum matching algorithm to make it efficient for finding all possible input nodes by computing only one MIS. We rigorously proved the correctness of the new algorithm and evaluated its performance on synthetic and large real networks. The experimental results showed that the new algorithm ran several orders of magnitude faster than the existing method on large real networks.
References in corpus (10)
- Specificity and stability in topology of protein networks
- The Dynamics of Viral Marketing
- Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design
- The Anatomy of a Scientific Rumor
- Controllability analysis of the directed human protein interaction network identifies disease genes and drug targets
- Emergence of bimodality in controlling complex networks
- Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
- The number of matchings in random graphs
- Structure controllability of complex network based on preferential matching
- Input graph: the hidden geometry in controlling complex networks