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

Network Protocols and Algorithms

Ayan Chatterjee²  Amitava Mukherjee¹  Mrinal Kanti Naskar²  Nabamita Pal³  Debayan Das² 

[1] IBM India Private Ltd., Salt lake;Jadavpur University, Kolkata;Techno India, Salt lake

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

DOI  :  10.5296/npa.v6i1.4756

学科分类：计算机应用

来源: Macrothink Institute, Inc.

【 摘 要 】

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.

【 授权许可】

Unknown