Vertex cover-based binary tree algorithm to detect all maximum common induced subgraphs in large communication networks

摘要

Maximum common induced subgraph (MCIS) of a communication network graph database determine the common substructures which are always active and retain the links between any pair of nodes exactly as in all graphs of the database. Many benchmark graph algorithms to predict MCIS of a graph database deal only with two graphs at a time and seek isomorphism, for which a high computational cost is to be paid. This gradually reduces the performance of the existing algorithms when the database has huge graph data. The proposed binary caterpillar MCIS algorithm to predict all MCIS of the database works for communication network graph database each of whose vertices has a unique label (IP address). In this, a new data structure which is a caterpillar-based binary tree is defined to reduce the search space of the problem using the concept of vertex cover and it takes into account all graphs of the database simultaneously to predict all MCIS of the database. This has substantially reduced unwanted comparisons among the datasets, when compared to the existing algorithms, as well as the difficulty of seeking isomorphism is avoided due to unique vertex labels. The experimental results further ensure the efficiency of the proposed algorithm with respect to existing works.