nach oben

Soft Computing

Erschienen in:

12.02.2016 | Foundations

Efficient influence maximization under TSCM: a suitable diffusion model in online social networks

verfasst von: Yadong Qin, Jun Ma, Shuai Gao

Erschienen in: Soft Computing | Ausgabe 4/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The study on influence modeling is to understand the information diffusion and word-of-mouth marketing. Independent Cascade Model (ICM) is the most widely studied theoretical diffusion model. However, until now it is unknown whether ICM matches the real information diffusion in online social networks. In this paper, we demonstrate that ICM cannot model accurately for the structure of information diffusion over real networks through our experiments. Meanwhile, we propose a more suitable diffusion model named Three Steps Cascade Model (TSCM) to simulate information diffusion process in online social networks. We focus on the influence maximization problem under TSCM. First, we show that this optimization problem is NP hard. Then we prove that the greedy algorithm can guarantee an influence spread within 63 % of the optimal value. Finally we devise an efficient algorithm which is scalable for large social networks. The experiment results on large-scale real networks show the robustness and utility of our approach.

Nächster Artikel Rough approximations based on soft binary relations and knowledge bases

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

http://weibo.com.

http://en.wikipedia.org/wiki/Monte_Carlo_method.

http://en.wikipedia.org/wiki/Breadth-first_search.

http://deim.urv.cat/~aarenas/data/welcome.htm.

http://snap.stanford.edu/data/ca-HepPh.html.

http://snap.stanford.edu/data/email-EuAll.html.

http://snap.stanford.edu/data/soc-pokec.html.

Cao J-X, Wu J-L, Shi W, Liu B, Zheng X, Luo J-Z (2014) Sina microblog information diffusion analysis and prediction. Chin J Comput 37(4):779–790

Cha M, Mislove A, Gummadi KP (2009) A measurement-driven analysis of information propagation in the flickr social network. In: Proceedings of the 18th international conference on World wide web, ACM, pp 721–730

Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 199–208

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

Christakis NA, Fowler JH (2009) Connected: The surprising power of our social networks and how they shape our lives. Hachette Digital Inc

Cohen E, Delling D, Pajor T, Werneck RF (2014) Sketch-based influence maximization and computation: Scaling up with guarantees. In: Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, ACM, pp 629–638

Demaine ED, Hajiaghayi M, Mahini H, Malec DL, Raghavan S, Sawant A, Zadimoghadam M (2014) How to influence people with partial incentives. In: Proceedings of the 23rd international conference on World wide web, ACM, pp 937–948

Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 57–66

Goel S, Watts DJ, Goldstein DG (2012) The structure of online diffusion networks. In: Proceedings of the 13th ACM conference on electronic commerce, ACM, pp 623–638

Goyal A, Lu W, Lakshmanan LV (2011) Celf++: optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on World wide web, ACM, pp 47–48

Guo J, Zhang P, Zhou C, Cao Y, Guo L (2013) Personalized influence maximization on social networks. In: Proceedings of the 22nd ACM international conference on Conference on information & knowledge management, ACM, pp 199–208

Heidari M, Asadpour M, Faili H (2015) Smg: Fast scalable greedy algorithm for influence maximization in social networks. Phys A Stat Mech Appl 420:124–133CrossRef

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

Kwak H, Lee C, Park H, Moon S (2010) What is twitter, a social network or a news media? In: Proceedings of the 19th international conference on World wide web, ACM, pp 591–600

Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007a) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 420–429

Leskovec J, McGlohon M, Faloutsos C, Glance NS, Hurst M (2007b) Patterns of cascading behavior in large blog graphs. SDM SIAM 7:551–556

Li G, Chen S, Feng J, Tan Kl, Li Ws (2014) Efficient location-aware influence maximization. In: Proceedings of the 2014 ACM SIGMOD international conference on Management of data, ACM, pp 87–98

Li H, Bhowmick SS, Sun A, Cui J (2015) Conformity-aware influence maximization in online social networks. VLDB J Int J Very Large Data Bases 24(1):117–141CrossRef

Misner IR (1994) The world’s best-known marketing secret: building your business with word-of-mouth marketing. Bard & Stephen, Austin

Nail J (2004) The consumer advertising backlash. Forrester research and intelliseek market research report

Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functionsi. Math Program 14(1):265–294

Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 61–70

Tang Y, Xiao X, Shi Y (2014) Influence maximization: Near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD international conference on Management of data, ACM, pp 75–86

Wang D, Wen Z, Tong H, Lin CY, Song C, Barabási AL (2011) Information spreading in context. In: Proceedings of the 20th international conference on World wide web, ACM, pp 735–744

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

Wang Q, Jin Y, Lin Z, Cheng S, Yang T (2016) Influence maximization in social networks under an independent cascade-based model. Phys A Stat Mech Appl 444:20–34

Zhang H, Nguyen DT, Zhang H, Thai MT (2015) Least cost influence maximization across multiple social networks, pp 1–11

Zhu T, Wang B, Wu B, Zhu C (2014) Maximizing the spread of influence ranking in social networks. Inf Sci 278:535–544MathSciNetCrossRef

Titel: Efficient influence maximization under TSCM: a suitable diffusion model in online social networks
verfasst von: Yadong Qin
Jun Ma
Shuai Gao
Publikationsdatum: 12.02.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 4/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-016-2068-3

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 4/2017

A dynamic multi-objective evolutionary algorithm using a change severity-based adaptive population management strategy

Evaluation of the hotels e-services quality under the user’s experience

Uncertainty measures of rough sets based on discernibility capability in information systems

Cut approach to invariance groups of lattice-valued functions

Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm

An uncertain furniture production planning problem with cumulative service levels