direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

The Complexity of Finding Effectors

Vincent Froese (TU Berlin)

The NP-hard Effectors problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of (random) information-propagation processes. 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 best possible using a minimum number of “effector nodes”; these are selected before the activation process starts. We 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.

Date
Speaker
Location
Language
07.05.2015
16:15
Vincent Froese
TEL 512
english

Back to the research colloquium site.

Zusatzinformationen / Extras