Efficient Algorithms for Social Network Coverage and Reach
- 1 June 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23797703,p. 467-474
Abstract
Social networks, though started as a software tool enabling people to connect with each other, have emerged in recent times as platforms for businesses, individuals and government agencies to conduct a number of activities ranging from marketing to emergency situation management. As a result, a large number of social network analytics tools have been developed for a variety of applications. A snapshot of social networks at any particular time, called a social graph, represents the connectivity of nodes and potentially the flow of information amongst the nodes (or vertices) in the graph. Understanding the flow of information in a social graph plays an important role in social network applications. Two specific problems related to information flow have implications in many social network applications: (a) finding a minimum set of nodes one has to know to recover the whole graph (also known as the vertex cover problem) and (b) determining the minimum set of nodes one required to reach all nodes in the graph within a specific number of hops (we refer this as the vertex reach problem). Finding an optimal solution to these problems is NP-Hard. In this paper, we propose approximation based approaches and show that our approaches outperform existing approaches using both a theoretical analysis and experimental results.Keywords
This publication has 26 references indexed in Scilit:
- Vertex cover in graphs with locally few colorsInformation and Computation, 2013
- Energy Efficient Protocols for Wireless Sensor Networks: A Survey and ApproachInternational Journal of Computer Applications, 2012
- A better approximation ratio for the vertex cover problemACM Transactions on Algorithms, 2009
- Expander flows, geometric embeddings and graph partitioningJournal of the ACM, 2009
- Structural analysis of behavioral networks from the InternetJournal of Physics A: Mathematical and Theoretical, 2008
- Vertex cover might be hard to approximate to withinJournal of Computer and System Sciences, 2008
- The Coverage Problem in a Wireless Sensor NetworkMobile Networks and Applications, 2005
- A Better Approximation Ratio for the Vertex Cover Problem2005
- Ramsey numbers and an approximation algorithm for the vertex cover problemActa Informatica, 1985
- A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem1985