Paper Info
Title
An efficient algorithm for enumerating all possible input nodes in controlling complex networks.
Abstract
Controlling complex networks is of great importance in many application regions. Recent works found that the minimum number of input nodes (MIS) used to control a network can be obtained by the maximum matching. However, the maximum matchings of a network are not unique, and there may exist numerous MISs. Finding all possible input nodes is difficult for the large-scale networks because of high computational costs. Here we present an efficient algorithm to enumerating all possible input nodes of a network. We rigorously prove that all possible input nodes can be obtained by a simple modification of the maximum matching algorithm, which allows us to obtain all possible input nodes (the union of all MISs) by only computing one MIS. The experiment results on both synthetic and real networks show that the computational complexity of the proposed algorithm is significantly improved contrast to the previous one. Speedup of up 100000x compared with the previous algorithm was observed for large-scale synthetic networks and real networks.
Year
Venue
Field
2017
arXiv: Discrete Mathematics
Algorithm,Theoretical computer science,Matching (graph theory),Complex network,Mathematics,Computational complexity theory,Speedup
DocType
Volume
Citations 
Journal
abs/1703.00876
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Xi-zhe Zhang1388.94
Jianfei Han200.34