Accessibility navigation

Weighted alpha-rate dominating sets in social networks

Vukadinovic Greetham, D., Poghosyan, A. and Charlton, N. (2015) Weighted alpha-rate dominating sets in social networks. In: Third International Workshop on Complex Networks and their Applications, 23-27 Nov 2014, Marrakech, Morocco.

[img] Text - Accepted Version
· Restricted to Repository staff only
· The Copyright of this document has not been checked yet. This may affect its availability.


It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

Official URL:


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.

Item Type:Conference or Workshop Item (Paper)
Divisions:Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics > Centre for the Mathematics of Human Behaviour (CMOHB)
ID Code:38038

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation