International Journal of
Information and Education Technology

Abstract—Identifying highly robust graphs (i.e. graph having high vertex connectivity value) is a well known problem in the field of social network analysis. Robustness of a social network implicitly assumes that social links are dynamic and should be allowed to be changed with and without restrictions or constrains. In social network finding robust subgraphs is hard problem i.e. NP Complete Problem. The paper focuses on identifying whether the original graph is robust or not. It takes into consideration the Maximum degree, Minimum degree and Vertex Connectivity values of given Graph (G), based on which the algorithm determines above Property.
The algorithm uses vertex connectivity and order constraints to find robust subgraphs i.e. Dominating (H) from set of all induced subgraphs. The social network G is decomposed using minimum cut decomposition algorithm over vertex connectivity parameter. The skyline approach is used to determine the solution set Dominating (H). The computational time of algorithm is improved by using preprocessing techniques like identifying and deleting cut set vertices and also by using pruning strategies like minimum degree criteria.

Index Terms—Skyline, order, vertex connectivity, robustness.

Abhay A. Bhamaikar is with the Department of Information technology, Shree Rayeshwar Institute of Engineering and Information technology, Shivshail, Karai, Shiroda – Goa, India (e-mail: abhay_bhamaikar@rediffmail.com).
Pralhad Ramchandra Rao is with the Department of Computer Science and Technology, Goa University, India.

[PDF]

Cite:Abhay A. Bhamaikar and Pralhad Ramchandra Rao, "Identifying Dominating Graphs over Vertex Connectivity and Order Constraint in a Social Network," International Journal of Information and Education Technology vol. 3, no. 5, pp. 554-559, 2013.