Centrality measures-based algorithm to visualize a maximal common induced subgraph in large communication networks

摘要

Communication networks are ubiquitous, increasingly complex, and dynamic. Predicting and visualizing common patterns in such a huge graph data of communication network is an essential task to understand active patterns evolved in the network. In this work, the problem is to find an active pattern in a communication network which is modeled as detection of a maximal common induced subgraph (CIS). The state of the communication network is captured as a time series of graphs which has periodic snapshots of logical communications within the network. A new centrality measure is proposed to assess the variation in successive graphs and to identify the behavior of each node in the time series graph. It extents help in the process of selecting a suitable candidate vertex for maximality in each step of the proposed algorithm. This paper is a pioneer attempt in using centrality measures to detect a maximal CIS of the huge graph database, which gives promising effect in the resultant graph in terms of large number of vertices. The algorithm has polynomial time complexity, and the efficiency of the algorithm is demonstrated by a series of experiments with synthetic graph datasets of different orders. The performance of real-time datasets further ensured the competence of the proposed algorithm.