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.
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.