Mining important sub-graphs using skyline approach over vertex connectivity constraint

Abstract

Mining of Sub-Graphs having highest value over vertex connectivity and Degree constraint plays a major role in Applications such as Social Network Analysis, Bioinformatics, Mobile Communications and Transportation Problems. This paper focuses on mining important sub-graphs over Degree and vertex connectivity constraint. The sub-graphs are obtained by decomposing the given graph using Min Cut Decomposition (MCD) algorithm over vertex connectivity constraint. To avoid MCD, preprocessing is done by detecting cut vertex, The detected node as cut vertex is deleted so as to obtain sub-graphs. Further more to avoid MCD, Pruning strategies like Minimum degree criteria, wherein the node satisfying minimum degree criteria is deleted so as to obtain sub-graphs, and lastly the pruning is done by checking if Sub-Graphs obtained belongs to Clique, Cycle or Tree. If obtained sub-graph satisfies any one of the above types, the sub-graphs are added to solution set. The obtained sub-graphs are compared over vertex connectivity and degree values. The sub-graph having highest number of vertices and vertex connectivity value forms the solution. To determine Important Sub-Graphs Skyline approach is used.