Blocking simple and complex social contagions using dominating set heuristics

Abstract

There are myriad real-life examples of contagion processes on human social networks, e.g., spread of viruses and mis/dis/information, joining groups, and social unrest. Also, there are many methods to control or block undesirable contagion spread on networks. In this work, we introduce a novel method of blocking contagions that uses nodes from dominating sets (DSs). This is the first work to use DS nodes to block contagions. Finding minimum dominating sets of graphs is an NP-Complete problem, so we generalize a well-known heuristic, enabling us to customize its execution. Our method produces a prioritized list of dominating nodes, which is, in turn, a prioritized list of blocking nodes. Given a network, we compute this list of blocking nodes and we use it to block contagions for all blocking node budgets, contagion seed sets, and parameter values of the contagion model. We provide examples to illustrate the issues associated with DS-based contagion blocking. We report on computational experiments of the blocking efficacy of our approach using seven mined networks. Among the results is that the heuristic generalization is important for improved blocking performance. We also demonstrate the effectiveness of our approach by comparing blocking results with those from the high degree heuristic, which is a common standard in blocking studies. We discuss how our general DS-based method recovers the high degree heuristic as a special case.