摘要：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.
