Data Mining and Knowledge Engineering

Abhay Avinash Bhamaikar ¹, Pralhad Ramchandra Rao ²

Affiliations
1 Department of Information Technology, Shree Rayeshwar Institute of Engineering and Information Technology, Shivshail, Karai, Shiroda, Goa, IN
2 Department of Computer Science and Technology, Goa University, Taleigao Plateau, Goa, IN

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.

Keywords

Graph Mining, Skyline Processing, Degree, Vertex Connectivity.

Full Text