Open Access Open Access  Restricted Access Subscription or Fee Access

Mining Important Sub-Graphs Using Skyline Approach over Vertex Connectivity Constraint

Abhay Avinash Bhamaikar, Pralhad Ramchandra Rao


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.


Graph Mining, Skyline Processing, Degree, Vertex Connectivity.

Full Text:



A N.Papadopoulos, A. Lyritsis, and Y Manalopoulos, “SkyGraph: an algorithm for important subgraph discovery in relational graphs”, DMKD (2008), Springer, 23 Jun 2008, pp. 57-76.

Cook DJ, Holder L B (eds) (2007) Mining graph data. Wiley, London.

Hartuv E, Shamir R (2000), A Clustering algorithm based on Graph Connectivity. Inform Process Lett 76: 175-181.

Wu Z, Leahy R (1993) An optimal graphs theoretic approach to data clustering: theory and its application to image segmentation, IEEE Trans Pattern Anal Machine Intell 15(11): 1101-1113.

Hu H, Yan X, Huang Y, Han J, Zhou XJ (2005) Mining coherent dense subgraphs acrossmassive biological networks for functional discovery. Bioinformatics 21(1):i213–i221

Yan X, Mehan MR, Huang Y, Waterman MS, Yu PS, Zhou XJ (2007) A graph-based approach to systematically reconstruct human transcriptional regulatory modules. Bioinformatics 23(13):i577–i586

Bron,C. and Kerbosch,J. (1973) Finding All Cliques of an Undirected Graph. Communications of the ACM, 16: 575-577.

Chiba,N. and Nishizeki,T. (1985) Arboricity and Subgraph Listing Algorithms. SIAM J. Comput., 14:210-223.

T. Chakraborty, J. Chuzhoy and S. Khanna. Network Design for Vertex Connectivity. Proc. of ACM STOC, 2008.

Graph Theory. Addison-Wesley Publishing Company, Reading, Mass.Harley, E., Bonner, A.J., and Goodman, N. (2001) Uniform Integration of Genome Mapping Data Using Intersection Graphs. Bioinformatics 17: 487-494.

Johnston, H.C. (1976) Cliques of a Graph --- Variations on the Bron-Kerbosch Algorithm. International Journal of Computer and Information Sciences 5: 209-238.

Loukakis, E. (1983) A New Backtracking Algorithm for Generating the Family of Maximal Independent Sets of a Graph. Comp. and Maths. With Appls., 9: 583-589.

A. Hanneman and M. Riddle, “Introduction to social network methods,”online at hanneman/nettext/, 2005.

Moon, J.W. and Moser,L. (1965) On cliques in graphs. Israel J. Math 3: 23-28.

Pardalos, P.M. and Xue,J. (1994) The maximum clique problem. Journal of Global Optimization 4:301-328.

Pardalos, P.M., Bomze,I.M., Budinich,M. and Pelillo,M. (1999) The Maximum Clique Problem. in Handbook of Combinatorial Optimization, Supplement, Vol. A (Eds: Du,D.and Pardalos,P.M.), Kluwer Academic Publishers: 1-74.

Zhu F, Yan X, Han J, Yu PS (2007) gPrune: a constraint pushing framework for graph pattern mining. In: Proceedings of PAKDD conference, pp 388–400

YanX, Zhou XJ,Han J (2005) Mining closed relational graphs with connectivity constraints. In: Proceedings of ACM KDD conference, pp 324–333

T. Chakraborty, J. Chuzhoy and S. Khanna. Network Design for Vertex Connectivity. Proc. Of ACM STOC, 2008.

J. Chuzhoy and S. Khanna. Algorithms for Single-Source vertex-Connectivity. Proc. Of IEEE FOCS, October 2008.

S. Even, “An algorithm for determining whether the connectivity of a graph is at least k,” SIAM Journal of Computing 4 (1975), 393-396.

S. Even, Graph Algorithms, Computer Science, 1979.

S. Even and R. E. Tarjan, “Network flow and testing graph connectivity,” SIAM Journal of Computing 4 (1975), pp. 507-518.

A‐H. Esfahanian and S. L. Hakimi, “On computing the connectivities of graphs and digraphs,” NETWORKS, Vol. 14, pp. 355-366, 1984.

D. J. Kleitman, “Methods for investigating connectivity of large graphs,” IEEE Trans. Circuit Theory 16 (1969), pp. 232-233.

Y. Mansour and B. Schieber, “Finding the edge connectivity of directed graphs,” Journal of Algorithms 10 (1989), pp. 76-85.

D. W. Matula, “Determining edge connectivity in O(mn),” Proceedings of 28th Symp. on Foundations of Computer Science, (1987), pp. 249-251.

Z. Galil, “Finding the vertex connectivity of graphs,” SIAM Journal of Computing, 9 (1980), pp. 197199.

Z. Galil and G. F. Italiano, “Reducing edge connectivity to vertex connectivity,” ACM SIGACT News 22 (1991), pp. 57-61.

M. R. Henzinger, S. Rao and H. N. Gabow, “Computing vertex Connectivity : new bounds from old techniques,” Proc. 37th IEEE F. O. C.S. (1996), pp. 462-471.

C. P. Schnorr, “Bottlenecks and edge connectivity in unsymmetrical networks,” SIAM Journal of Computing 8 (1979), 265-274.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.