Publication

Abstract : With the rapid escalation of real-world networks, the control of the entire network is a matter of immense concern.Any minor attack or failure of a small part in the network can potentially trigger cascading breakdown in the entire network. Therefore, the structural control of any real-world directed complex network is very critical to address causes and to prevent any vulnerabilities into the network, thereby making it more resilient against cascading breakdown. The prevalent algorithms like the Hopcroft-Karp (O (N2.5) algorithm) required the determination of the bipartite equivalent, which in itself is an NP-complete problem. We propose a maximal path greedy search algorithm, to compute the minimum set of driver nodes required to control the entire complex network, without the determination of its bipartite equivalent, while ensuring the maximum augmenting path corresponding to each driver node. Results indicate that in most real-world networks, the obtained number of driver nodes is much lesser compared to the existing algorithm [1]. In case of dense networks, we notice that the worst case time complexity of our proposed algorithm is of the order O(N2), while for sparse and semi-dense networks, it goes down to O(N*log N), where N is the total number of nodes in the complex network.