The Complexity of Finding Effectors

Laurent Bulteau (1) , Stefan Fafianie (2) , Vincent Froese (2) , Rolf Niedermeier (2) , Nimrod Talmon (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 SWT - TUB - Department of Software Engineering and Theoretical Computer Science

The NP-hard Effectors problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation processes in social networks. In the corresponding model the arcs carry probabilities and there is a probabilistic diffusion process activating nodes by neighboring activated nodes with probabilities as specified by the arcs. The point is to explain a given network activation state as well as possible by using a minimum number of " effector nodes " ; these are selected before the activation process starts. We correct, complement, and extend previous work from the data mining community by a more thorough computational complexity analysis of Effec-tors, identifying both tractable and intractable cases. To this end, we also An extended abstract appeared in 2 Laurent Bulteau et al. exploit a parameterization measuring the " degree of randomness " (the number of 'really' probabilistic arcs) which might prove useful for analyzing other probabilistic network diffusion problems as well.

Mots clés: Probabilistic Information Propagation; Network Activation; Social Networks; Influence Maximization; Exact Algorithms; Parameterized Complexity

Domaines: Algorithme et structure de données [cs.DS]; Complexité [cs.CC]

Laurent Bulteau, Stefan Fafianie, Vincent Froese, Rolf Niedermeier, Nimrod Talmon. The Complexity of Finding Effectors. Theory of Computing Systems, 2017, 60 (2), pp.253-279. ⟨10.1007/s00224-016-9670-8⟩. ⟨hal-01494357⟩