Top

Theory of Computing Systems

Published in:

17-03-2016

The Complexity of Finding Effectors

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

Published in: Theory of Computing Systems | Issue 2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Path-Disruption Games: Bribery and a Probabilistic Model

next article Sophistication vs Logical Depth

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

We conjecture that both models coincide if we are allowed to choose an unlimited number of effectors, that is, if the number of chosen effectors does not matter. On the contrary, they do not coincide if the number of effectors is bounded, see Section 2.

Notably, in our model it actually remains active. The point is that before the whole computation starts (and after it ends) nodes may (have) become inactive again. Still, “temporary activeness” may make a node an effector that helps explaining the currently observed network activation state.

Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall (1993)

Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)

Askalidis, G., Berry, R.A., Subramanian, V.G.: Explaining snapshots of network diffusions Structural and hardness results. In: proceedings of the 20th International Conference on Computing and Combinatorics, volume 8591 of LNCS, pp 616–625. Springer (2014)

Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized inapproximability of target set selection and generalizations. Computability 3(2), 135–145 (2014)MathSciNetMATH

Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized approximability of maximizing the spread of influence in networks. J. Discret. Algorithm. 27, 54–65 (2014)MathSciNetCrossRefMATH

Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discret. Optim. 8(1), 87–96 (2011)MathSciNetCrossRefMATH

Bharathi, S., Kempe, D., Salek, M.: Competitive influence maximization in social networks. In: proceedings of the Third International Workshop on Internet and Network Economics, volume 4858 of LNCS, pp 306–311. Springer (2007)

Chopin, M., Nichterlein, A., Niedermeier, R., Weller, M.: Constant thresholds can make target set selection tractable. Theory Comput. Syst. 55(1), 61–83 (2014)MathSciNetCrossRefMATH

Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. springer (2015)

10.

Domingos, P., Richardson, M.: Mining the network value of customers. In: proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 57–66. ACM (2001)

11.

Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. springer (2013)

12.

Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53–61 (2009)MathSciNetCrossRefMATH

13.

Flum, J., Grohe, M.: Parameterized complexity theory, springer (2006)

14.

Kempe, D., Kleinberg, J.M., Tardos, É.: Maximizing the spread of influence through a social network. Theory Comput. 11, 105–147 (2015)MathSciNetCrossRefMATH

15.

Lappas, T., Terzi, E., Gunopulos, D., Mannila, H.: Finding effectors in social networks. In: proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 1059–1068. ACM (2010)

16.

Nichterlein, A., Niedermeier, R., Uhlmann, J., Weller, M.: On tractable cases of target set selection. Soc. Netw. Anal. Min. 3(2), 233–256 (2013)CrossRefMATH

17.

Niedermeier, R.: Invitation to Fixed-Parameter algorithms. oxford university press (2006)

18.

Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)MathSciNetCrossRefMATH

19.

Wang, C., Chen, W., Wang, Y.: Scalable influence maximization for independent cascade model in large-scale social networks. Data Min. Knowl. Discov. 25(3), 545–576 (2012)MathSciNetCrossRefMATH

Title: The Complexity of Finding Effectors
Authors: Laurent Bulteau
Stefan Fafianie
Vincent Froese
Rolf Niedermeier
Nimrod Talmon
Publication date: 17-03-2016
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 2/2017
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-016-9670-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2017

Small-Bias is Not Enough to Hit Read-Once CNF

A Difference in Complexity Between Recursion and Tail Recursion

The Behavior of Clique-Width under Graph Operations and Graph Transformations

Composition Closure of Linear Extended Top-down Tree Transducers

Distance Vector-based Advance Reservation with Delay Performance Guarantees

Path-Disruption Games: Bribery and a Probabilistic Model

Premium Partner