@inproceedings{bb201716399042c9a34e494614ec7821,
title = "Efficient Algorithms for Social Network Coverage and Reach",
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 = "Approximation Algorithm, Complexity, Network Coverage, Network Reach, Social Networks",
author = "Deepak Puthal and Surya Nepal and Cecile Paris and Rajiv Ranjan and Jinjun Chen",
note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 4th IEEE International Congress on Big Data, BigData Congress 2015 ; Conference date: 27-06-2015 Through 02-07-2015",
year = "2015",
month = aug,
day = "17",
doi = "10.1109/BigDataCongress.2015.75",
language = "English",
series = "Proceedings - 2015 IEEE International Congress on Big Data, BigData Congress 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "467--474",
editor = "Latifur Khan and Carminati Barbara",
booktitle = "Proceedings - 2015 IEEE International Congress on Big Data, BigData Congress 2015",
address = "United States",
}