Weighted alpha-rate dominating sets in social networks

Danica Vukadinovic Greetham, Anush Poghosyan, Nathaniel Charlton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

We are looking into variants of a domination set problem in social networks. While randomised algorithms for solving the minimum weighted domination set problem and the minimum alpha and alpha-rate domination problem on simple graphs are already present in the literature, we propose here a randomised algorithm for the minimum weighted alpha-rate domination set problem which is, to the best of our knowledge, the first such algorithm. A theoretical approximation bound based on a simple randomised rounding technique is given. The algorithm is implemented in Python and applied to a UK Twitter mentions networks using a measure of individuals' influence (klout) as weights. We argue that the weights of vertices could be interpreted as the costs of getting those individuals on board for a campaign or a behaviour change intervention. The minimum weighted alpha-rate dominating set problem can therefore be seen as finding a set that minimises the total cost and each individual in a network has at least alpha percentage of its neighbours in the chosen set. We also test our algorithm on generated graphs with several thousand vertices and edges. Our results on this real-life Twitter networks and generated graphs show that the implementation is reasonably efficient and thus can be used for real-life applications when creating social network based interventions, designing social media campaigns and potentially improving users' social media experience.

Original languageEnglish
Title of host publicationProceedings - 10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014
PublisherIEEE
Pages369-375
Number of pages7
ISBN (Electronic)9781479979783
DOIs
Publication statusPublished - 7 Apr 2015
Event10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014 - Marrakech, Morocco
Duration: 23 Nov 201427 Nov 2014

Conference

Conference10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014
CountryMorocco
CityMarrakech
Period23/11/1427/11/14

Keywords

  • alpha-rate dominating sets
  • randomised algorithms
  • social networks
  • weighted domination

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Signal Processing
  • Computer Networks and Communications

Cite this

Greetham, D. V., Poghosyan, A., & Charlton, N. (2015). Weighted alpha-rate dominating sets in social networks. In Proceedings - 10th International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014 (pp. 369-375). [7081572] IEEE. https://doi.org/10.1109/SITIS.2014.51