Skip to main content
Erschienen in: Social Network Analysis and Mining 4/2013

01.12.2013 | Original Article

A scalable heuristic for viral marketing under the tipping model

verfasst von: Paulo Shakarian, Sean Eyre, Damon Paulo

Erschienen in: Social Network Analysis and Mining | Ausgabe 4/2013

Einloggen

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

search-config
loading …

Abstract

In a “tipping” model, each node in a social network, representing an individual, adopts a property or behavior if a certain number of his incoming neighbors currently exhibit the same. In viral marketing, a key problem is to select an initial “seed” set from the network such that the entire network adopts any behavior given to the seed. Here we introduce a method for quickly finding seed sets that scales to very large networks. Our approach finds a set of nodes that guarantees spreading to the entire network under the tipping model. After experimentally evaluating 31 real-world networks, we found that our approach often finds seed sets that are several orders of magnitude smaller than the population size and outperform nodal centrality measures in most cases. In addition, our approach scales well—on a Friendster social network consisting of 5.6 million nodes and 28 million edges we found a seed set in under 3.6 h. Our experiments also indicate that our algorithm provides small seed sets even if high-degree nodes are removed. Last, we find that highly clustered local neighborhoods, together with dense network-wide community structures, suppress a trend’s ability to spread under the tipping model.

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!

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!

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!

Fußnoten
1
Note that in the symmetric networks we examined, our empirical results hold for the number of incoming adjacent edges as well as the total number of adjacent edges.
 
2
Louvain modularity was computed using the implementation available from CRANS at http://​perso.​crans.​org/​aynaud/​communities/​.
 
Literatur
Zurück zum Zitat Baxter GJ, Dorogovtsev SN, Goltsev AV, Mendes JFF (2011) Heterogeneous k-core versus bootstrap percolation on complex networks. Phys Rev E 83(5):051134 Baxter GJ, Dorogovtsev SN, Goltsev AV, Mendes JFF (2011) Heterogeneous k-core versus bootstrap percolation on complex networks. Phys Rev E 83(5):051134
Zurück zum Zitat Ben-Zwi O, Hermelin D, Lokshtanov D, Newman I (2011) Treewidth governs the complexity of target set selection. Discrete Optim 8(1):87–96MathSciNetCrossRefMATH Ben-Zwi O, Hermelin D, Lokshtanov D, Newman I (2011) Treewidth governs the complexity of target set selection. Discrete Optim 8(1):87–96MathSciNetCrossRefMATH
Zurück zum Zitat Borgs C, Brautbar M, Chayes J, Lucier B (2012) Influence maximization in social networks: towards an optimal algorithmic solution. arXiv preprint arXiv:1212.0884 Borgs C, Brautbar M, Chayes J, Lucier B (2012) Influence maximization in social networks: towards an optimal algorithmic solution. arXiv preprint arXiv:1212.0884
Zurück zum Zitat Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E (2007) From the cover: a model of Internet topology using k-shell decomposition. PNAS 104(27):11150–11154. doi:10.1073/pnas.0701175104 Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E (2007) From the cover: a model of Internet topology using k-shell decomposition. PNAS 104(27):11150–11154. doi:10.​1073/​pnas.​0701175104
Zurück zum Zitat Chen N (2009) On the approximability of influence in social networks. SIAM J Discret Math 23:1400–1415CrossRef Chen N (2009) On the approximability of influence in social networks. SIAM J Discret Math 23:1400–1415CrossRef
Zurück zum Zitat 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, KDD ’10. ACM, New York, pp 1029–1038 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, KDD ’10. ACM, New York, pp 1029–1038
Zurück zum Zitat Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press. http://mitpress.mit.edu/catalog/item/default.asp?tid=8570&ttype=2 Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press. http://​mitpress.​mit.​edu/​catalog/​item/​default.​asp?​tid=​8570&​#38;ttype=2
Zurück zum Zitat Jackson M, Yariv L (2005) Diffusion on social networks. Economie Publique 16(1):69–82 Jackson M, Yariv L (2005) Diffusion on social networks. Economie Publique 16(1):69–82
Zurück zum Zitat Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: KDD ’03: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 137–146. doi:10.1145/956750.956769 Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: KDD ’03: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 137–146. doi:10.​1145/​956750.​956769
Zurück zum Zitat Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA (2010) Identification of influential spreaders in complex networks. Nat Phys (11):888–893. doi:10.1038/nphys1746 Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA (2010) Identification of influential spreaders in complex networks. Nat Phys (11):888–893. doi:10.​1038/​nphys1746
Zurück zum Zitat Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: KDD ’07: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 420–429. doi:10.1145/1281192.1281239 Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: KDD ’07: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 420–429. doi:10.​1145/​1281192.​1281239
Zurück zum Zitat Page L, Brin S, Motwani R, Winograd T (1998) The pagerank citation ranking: bringing order to the web. In: Proceedings of the 7th international world wide web conference, pp 161–172 Page L, Brin S, Motwani R, Winograd T (1998) The pagerank citation ranking: bringing order to the web. In: Proceedings of the 7th international world wide web conference, pp 161–172
Zurück zum Zitat Schelling TC (1978) Micromotives and Macrobehavior. W.W. Norton and Co., Pennsylvania Schelling TC (1978) Micromotives and Macrobehavior. W.W. Norton and Co., Pennsylvania
Zurück zum Zitat Wasserman S, Faust K (1994) Social network analysis: methods and applications, 1 edn. No. 8 in Structural analysis in the social sciences. Cambridge University Press, Cambridge Wasserman S, Faust K (1994) Social network analysis: methods and applications, 1 edn. No. 8 in Structural analysis in the social sciences. Cambridge University Press, Cambridge
Zurück zum Zitat Zhang L, Marbach P (2011) Two is a crowd: optimal trend adoption in social networks. In: Proceedings of international conference on game theory for networks (GameNets) Zhang L, Marbach P (2011) Two is a crowd: optimal trend adoption in social networks. In: Proceedings of international conference on game theory for networks (GameNets)
Metadaten
Titel
A scalable heuristic for viral marketing under the tipping model
verfasst von
Paulo Shakarian
Sean Eyre
Damon Paulo
Publikationsdatum
01.12.2013
Verlag
Springer Vienna
Erschienen in
Social Network Analysis and Mining / Ausgabe 4/2013
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-013-0135-7

Weitere Artikel der Ausgabe 4/2013

Social Network Analysis and Mining 4/2013 Zur Ausgabe