The complexity of finding effectors

DOI10.1007/978-3-319-17142-5_20zbMath1362.68102DBLPconf/tamc/BulteauFFNT15arXiv1411.7838OpenAlexW1632976971WikidataQ62039059 ScholiaQ62039059MaRDI QIDQ519899

Vincent Froese, Rolf Niedermeier, Stefan Fafianie, Laurent Bulteau, Nimrod Talmon

Publication date: 31 March 2017

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

Abstract: 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 EFFECTORS, identifying both tractable and intractable cases. To this end, we also 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.

Full work available at URL: https://arxiv.org/abs/1411.7838

zbMATH Keywords

social networksparameterized complexityexact algorithmsinfluence maximizationnetwork activationprobabilistic information propagation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Fundamentals of parameterized complexity
• Treewidth governs the complexity of target set selection
• On the parameterized complexity of multiple-interval graph problems
• Scalable influence maximization for independent cascade model in large-scale social networks
• Parameterized approximability of maximizing the spread of influence in networks
• Constant thresholds can make target set selection tractable
• Parametrized complexity theory.
• Explaining Snapshots of Network Diffusions: Structural and Hardness Results
• On Tractable Cases of Target Set Selection
• The Complexity of Enumeration and Reliability Problems
• Parameterized Inapproximability of Target Set Selection and Generalizations
• Computational Complexity
• Parameterized Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of finding effectors