Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks

Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks

Traian Marius Truta (Computer Science Department, College of Informatics, Northern Kentucky University, Highland Heights, USA), Alina Campan (Computer Science Department, College of Informatics, Northern Kentucky University, Highland Heights, USA) and Matthew Beckerich (Computer Science Department, College of Informatics, Northern Kentucky University, Highland Heights, USA)
DOI: 10.4018/IJSSMET.2018040101


Social networks are increasingly becoming an outlet that is more and more powerful in spreading news and influence individuals. Compared with other traditional media outlets such as newspaper, radio, and television, social networks empower users to spread their ideological message and/or to deliver target advertising very efficiently in terms of both cost and time. In this article, the authors focus on efficiently finding dominating sets in social networks for the classical dominating set problem as well as for two related problems: partial dominating sets and d-hop dominating sets. They will present algorithms for determining efficiently a good approximation for the social network minimum dominating sets for each of the three variants. The authors ran an extensive suite of experiments to test the presented algorithms on several datasets that include real networks made available by the Stanford Network Analysis Project and synthetic networks that follow the power-law and random models that they generated for this work. The performed experiments show that the selection of the algorithm that performs best to determine efficiently the dominating set is dependent of network characteristics and the order of importance between the size of the dominating set and the time required to determine such a set.
Article Preview

1. Introduction

Do you know an adult that never used an online social network? While some may have old relatives that may not have used such networks, this is becoming increasingly rare. It is not a surprise that their influence competes with well-established media outlets such as newspapers, television, and radio. For instance, social networks were used extensively for political campaigns such as 2016 United States presidential elections (Pew Research Center, 2016) and 2016 republican and democratic primaries (Whitten, 2015). As early as 2008, the United States presidential elections were shaped by the intensive use of social networks (Dutta & Fraser, 2008). Even in non-democratic regimes, social networks are used to increase the political awareness of users in such countries (Reuter & Szakonyi, 2013).

Social networks are nowadays a hot research topic in computer science community due to the large-scale usage of online social networks. According to the Statistic Portal (Statista Facebook, 2016), Facebook had 1.79 billion active users in the third quarter of 2016 out of which 1.57 billion accessed their Facebook account on a mobile device. Facebook had surpassed the 1 billion mark in the third quarter of 2012, and as recent as 2008, this social network had only 100 million users. Other social networks are increasingly popular. For instance, LinkedIn has 467 million members as of September 2016 after passing the 100 million mark in early 2011 (Statista LinkedIn, 2016) and Twitter has 317 million members in the third quarter of 2016 after having 100 million users in the Summer of 2011 (Statista Twitter, 2016). Considering this usage trend, many academics from a wide array of areas such as sociology, mathematics, physics, communications, and computer science work on different problems that are related to social networks. This research flurry does not come without a strong base; a lot of research has been done already for general graphs and networks and these results are in many cases applicable to social networks (Babers & Hassanien, 2017; Cardoso et al., 2013; Chowdhuri et al., 2014a; Chowdhuri et al., 2014b; Gupta et al., 2016; Wahi et al., 2014). That being said, today there is an increase attention given to the social aspects of the networks as well to the increase size of such networks.

Social networks always existed in the human history, to survive and then to better their life, people always relied on the friends/relative network around them. However, documenting such small social networks was not done on a regular basis thought history. Still, the evolution of social networks from 1200 AD – 1450 AD from pre-Hispanic Southwest in the current United States is reflected in thousands of ceramic and obsidian artifacts (Mills, et al., 2013). From an academic perspective, social networks research started in the first half of 20th century in the sociology community and it was expanded to other areas such as computer science and physics in the 1990s (Freeman, 2011). Once online social networks became a reality with MySpace and Friendster and more recently with Facebook, LinkedIn, Twitter and many others, social networks have grown tremendously in size and a new path of research that focus on developing fast and accurate solutions for very large social networks has increased in importance.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing