Heuristic for maximum matching in directed complex networks

Determining maximum matching in any network has always been a problem of immense concern. Its solution is a necessary requirement in structural control theory for controlling real world complex networks. The prevalent 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 develop 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 which follow Erdos-Rényi model. Simulation results obtained using our heuristic show that dense and homogenous networks can be controlled with fewer controller nodes popularly termed as driver nodes, compared to the sparse inhomogeneous networks.