TY - JOUR
T1 - An efficient algorithm for finding all possible input nodes for controlling complex networks
AU - Zhang, Xizhe
AU - Han, Jianfei
AU - Zhang, Weixiong
N1 - Funding Information:
This research was supported by the Fundamental Research Funds for the Central Universities of China under grand number N140404011, and the Natural Science Foundation of China under grant number 91546110, and China Scholarship Council under grant number 201606085011, and the Special Program for Applied Research on Super Computation of the NSFC-Guangdong Joint Fund (the second phase).
Publisher Copyright:
© 2017 The Author(s).
PY - 2017/12/1
Y1 - 2017/12/1
N2 - Understanding structural controllability of a complex network requires to identify a Minimum Input nodes Set (MIS) of the network. Finding an MIS is known to be equivalent to computing a maximum matching of the network, where the unmatched nodes constitute an MIS. However, maximum matching is often not unique for a network, and finding all possible input nodes, the union of all MISs, may provide deep insights to the controllability of the network. 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. The algorithm can also output a set of substituting nodes for each input node in the MIS, so that any node in the set can replace the latter. 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 an existing method on large real networks.
AB - Understanding structural controllability of a complex network requires to identify a Minimum Input nodes Set (MIS) of the network. Finding an MIS is known to be equivalent to computing a maximum matching of the network, where the unmatched nodes constitute an MIS. However, maximum matching is often not unique for a network, and finding all possible input nodes, the union of all MISs, may provide deep insights to the controllability of the network. 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. The algorithm can also output a set of substituting nodes for each input node in the MIS, so that any node in the set can replace the latter. 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 an existing method on large real networks.
UR - https://www.scopus.com/pages/publications/85028977029
U2 - 10.1038/s41598-017-10744-w
DO - 10.1038/s41598-017-10744-w
M3 - Article
C2 - 28878394
AN - SCOPUS:85028977029
SN - 2045-2322
VL - 7
JO - Scientific reports
JF - Scientific reports
IS - 1
M1 - 10677
ER -