Publication

Abstract : Measuring similarity of graphs is an important task in graph mining for matching, comparing, and evaluating patterns in huge graph databases. In managing huge-enterprise communication networks, the ability to measure similarity is an important performance monitoring function. It is possible to draw certain significant conclusions regarding effective utilization of networks by characterizing a computer network as a time series of graphs with IP addresses as nodes and communication between nodes as edges. The maximum common subnets of k network time series graphs give a measure of the utilization of network nodes at different intervals of time. The problem of finding the nodes in the communication network which are always active can be formulated as a Maximum Common Subgraph (MCS) detection problem which would be useful for various decision making tasks such as devising better routing algorithms. This paper presents a novel MCS detection algorithm that introduces a new heap-based data structure to find all MCS of k graphs in a graph database efficiently. The series of experiments performed and the comparison of empirical results with the existing algorithms further ensure the efficiency of the proposed algorithm.