Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks

Traian Marius Truta, Alina Campan and Matthew Beckerich
Additional contact information
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
Matthew Beckerich: Computer Science Department, College of Informatics, Northern Kentucky University, Highland Heights, USA

International Journal of Service Science, Management, Engineering, and Technology (IJSSMET), 2018, vol. 9, issue 2, 1-32

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

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
https://services.igi-global.com/resolvedoi/resolve ... 8/IJSSMET.2018040101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jssmet:v:9:y:2018:i:2:p:1-32

Access Statistics for this article

International Journal of Service Science, Management, Engineering, and Technology (IJSSMET) is currently edited by Ahmad Taher Azar

More articles in International Journal of Service Science, Management, Engineering, and Technology (IJSSMET) from IGI Global
Bibliographic data for series maintained by Journal Editor ().