Efficient Algorithms for Social Network Coverage and Reach

Deepak Puthal, Surya Nepal, Cecile Paris, Rajiv Ranjan, Jinjun Chen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Scopus citations

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.

Original languageBritish English
Title of host publicationProceedings - 2015 IEEE International Congress on Big Data, BigData Congress 2015
EditorsLatifur Khan, Carminati Barbara
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages467-474
Number of pages8
ISBN (Electronic)9781467372787
DOIs
StatePublished - 17 Aug 2015
Event4th IEEE International Congress on Big Data, BigData Congress 2015 - New York City, United States
Duration: 27 Jun 20152 Jul 2015

Publication series

NameProceedings - 2015 IEEE International Congress on Big Data, BigData Congress 2015

Conference

Conference4th IEEE International Congress on Big Data, BigData Congress 2015
Country/TerritoryUnited States
CityNew York City
Period27/06/152/07/15

Keywords

  • Approximation Algorithm
  • Complexity
  • Network Coverage
  • Network Reach
  • Social Networks

Fingerprint

Dive into the research topics of 'Efficient Algorithms for Social Network Coverage and Reach'. Together they form a unique fingerprint.

Cite this