2019 · 10 citations · 9 references
Social SciencesSociologyCollective BehaviorKnowledge NetworksSocial InfluenceGraph AlgorithmsGreedy AlgorithmsNetwork CentralityNetwork OptimizationSocial Network AnalysisSocial NetworksDominating SetsGreedy ApproximationGreedy HeuristicsNode Influence
As a variant of the dominating set problem, the positive influence dominating set problem tries to find a set such that at least half neighbors of every node in the graph are included by it. Because this problem has wide applications in social networks, it has received more and more attention. This paper presents a fast greedy algorithm to solve the problem. Sufficient experiments on typical real networks show that compared with the existing algorithms, the quality of the solutions obtained by the algorithm is close to or even better, while the running time is greatly reduced. Especially, when the network becomes larger, the running time can be reduced by several orders of magnitude.
9
{SNAP Datasets}: {Stanford} Large Network Dataset Collection
Jure Leskovec, Andrej Krevl · 2014 · 2.8K citations
On positive influence dominating sets in social networks
Feng Wang, Hongwei Du, E. Camacho et al. · Theoretical Computer Science · 2009 · 94 citations