IRMA-International.org: Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks

Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks
View Sample PDF
Author(s): 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)
Copyright: 2018
Volume: 9
Issue: 2
Pages: 32
Source title: International Journal of Service Science, Management, Engineering, and Technology (IJSSMET)
Editor(s)-in-Chief: Ahmad Taher Azar (Prince Sultan University, Riyadh, Kingdom of Saudi Arabi and Benha University, Egypt) and Ghazy Assassa (Benha University, Egypt)
DOI: 10.4018/IJSSMET.2018040101

Purchase

View Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks on the publisher's website for pricing and purchasing information.

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.

Related Content

Brian J. Galli. © 2020. 13 pages.
Lajmi Fatma, Jalel Ghabi, Hedi Dhouibi. © 2020. 17 pages.
Oluseun A Ishola, Modinat O Olusoji. © 2020. 15 pages.
Taimoor Basharat. © 2020. 9 pages.
Libin Thomas, J Sandeep, Bhargavi Goswami, Joy Paulose. © 2020. 18 pages.
Brian J. Galli. © 2020. 26 pages.
Radia Belkeziz, Zahi Jarir. © 2020. 17 pages.
Body Bottom