Title: An efficient algorithm for finding all possible input nodes for controlling complex networks,
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.