nach oben

Journal of Combinatorial Optimization

Erschienen in:

17.08.2016

Centralized and decentralized rumor blocking problems

verfasst von: Xin Chen, Qingqin Nong, Yan Feng, Yongchang Cao, Suning Gong, Qizhi Fang, Ker-I Ko

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper consists of two parts. In the first part, we study a centralized rumor blocking problem with a novel social objective function different from those in the literature. We will show that this objective function is non-decreasing and submodular and hence corresponding rumor blocking problem has a greedy approximation with objective function value at least \(1-1/e\) of the optimal. In the second part, we study a decentralized rumor blocking problem with two selfish protectors, which falls into a 2-player non-cooperate game model. We will show that this game is a basic valid utility system and hence the social utility of any Nash equilibrium in the game is at least a half of the optimal social utility.

Vorheriger Artikel Local ratio method on partial set multi-cover

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Budak C, Agrawal C, El Abbadi A (2011) Limiting the spread of misinformation in social networks. In: Proceedings of the 20th international conference on World wide web. ACM, pp. 665–674

Chen W, Lu W, Zhang N (2012) Time-critical influence maximization in social networks with time-delayed diffusion process. arXiv:1204.3074

Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 1029–1038

Fan L, Lu Z, Wu W, Thuraisingham B, Ma H, Bi Y (2013) Least cost rumor blocking in social networks. In: Proceedings IEEE 33rd international conference on distributed computing systems (ICDCS), pp 540–549

Fan L, Wu W, Xing K et al (2016) Precautionary rumor containment via trustworthy people in social networks. Discret Math Algorithm Appl 8(01):1650004MathSciNetCrossRefMATH

Fan L, Wu W, Zhai X et al (2014) Maximizing rumor containment in social networks with constrained time. Soc Netw Anal Min 4(1):1–10CrossRef

He X, Song G, Chen W et al (2012) Influence blocking maximization in social networks under the competitive linear threshold model. In: SDM, pp 463–474

Kempe D, Kleinberg J, Tardos É (2005) Influential nodes in a diffusion model for social networks. International colloquium on automata, languages, and programming. Springer, BerlinMATH

Kempe D, Kleinberg J (2003) É Tardos. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 137–146

Kotnis B, Kuri J (2014) Cost effective rumor containment in social networks. arXiv:1403.6315

Li S, Zhu Y, Li D, Kim D, Huang H (2013) Rumor restriction in online social networks. In: Proceedings 2013 IEEE 32nd international performance computing and communications conference (IPCCC). pp 1–10

Nemhauser LG, Wolsey AL, Fisher LM (1978) An analysis of approximations for maximizing submodular set functional. Math Program 14(1):265–294CrossRefMATH

Vetta A (2002) Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: Proceedings 43rd annual IEEE symposium on foundations of computer science. pp 416–425

Titel: Centralized and decentralized rumor blocking problems
verfasst von: Xin Chen
Qingqin Nong
Yan Feng
Yongchang Cao
Suning Gong
Qizhi Fang
Ker-I Ko
Publikationsdatum: 17.08.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-0067-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2017

An exact semidefinite programming approach for the max-mean dispersion problem

Newly deterministic construction of compressed sensing matrices via singular linear spaces over finite fields

Maximizing target-temporal coverage of mission-driven camera sensor networks

On minimally 2-connected graphs with generalized connectivity

On zero-sum -magic graphs

The minimum value of geometric-arithmetic index of graphs with minimum degree 2