Back close

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

Publication Type : Journal Article

Publisher : International Journal of Network Protocols and Algorithms

Source : International Journal of Network Protocols and Algorithms, Aug 2014

Url : https://www.researchgate.net/publication/266796004_A_Degree-first_Greedy_Search_Algorithm_for_the_Evaluation_of_Structural_Controllability_of_Real_World_Directed_Complex_Networks

Campus : Amritapuri

School : School of Computing

Verified : Yes

Year : 2014

Abstract : 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.

Cite this Research Publication : A. Chatterjee, D. Das, N. Bhowmick, A. Mukherjee, M. K. Naskar, "A Degree-first Greedy Search Algorithm for the Evaluation of Structural Controllability of Real World Directed Complex Networks", International Journal of Network Protocols and Algorithms, Aug 2014

Admissions Apply Now