A Degree-first Greedy Search Algorithm for the Evaluation of Structural Controllability of Real World Directed Complex Networks

[摘要] Ubiquitous data flow through a directed complex network requires the complete structural controllability of the network. For evaluating the structural controllability of any network, determination of maximum matching in the network is a cardinal task and has always been a problem of immense concern. Its solution is mandatory in structural control theory for controlling real world complex networks. The existing classical approach through the Hopcroft-Karp algorithm and other proposed algorithms require the determination of the bipartite equivalent graph (i.e., network), which belongs to the NP-complete class of problems. In this article, we propose a degree-first greedy search algorithm to determine maximum matching in unipartite graphs without determining its bipartite equivalent. Thus this classical problem of the NP-Complete class can be solved using the heuristic, with reduced complexity. This algorithm can be efficiently used to find maximum matching in most of the real world complex networks that follow Erdős-Rényi model. Simulation results obtained using our heuristic reveal that dense and homogenous networks can be controlled with fewer controller nodes popularly termed as driver nodes, compared to the sparse inhomogeneous networks.

[学科分类] 计算机应用

[关键词] Augmenting path;complex networks;driver nodes;Erdős-Rényi model;maximum matching;structural controllability;unipartite and bipartite graph.