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: firstname.lastname@example.org).
Pralhad Ramchandra Rao is with the Department of Computer Science and Technology, Goa University, India.
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.