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

Debayan Das, Ayan Chatterjee, Nabamita Pal, Amitava Mukherjee, Mrinal Kanti Naskar


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.

Full Text:


DOI: https://doi.org/10.5296/npa.v6i1.4756

To make sure that you can receive messages from us, please add the 'macrothink.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.

Copyright © Macrothink Institute ISSN 1943-3581