Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Social Network Analysis and Mining
Erschienen in: Social Network Analysis and Mining 1/2016

01.12.2016 | Original Article

On finding small sets that influence large networks

verfasst von: Gennaro Cordasco, Luisa Gargano, Adele A. Rescigno

Erschienen in: Social Network Analysis and Mining | Ausgabe 1/2016

Einloggen

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

search-config
loading …

Abstract

We consider the problem of selecting a minimum size subset of nodes in a network that allows to activate all the nodes of the network. We present a fast and simple algorithm that, in real-life networks, produces solutions that outperform the ones obtained by using the best algorithms in the literature. We also investigate the theoretical performances of our algorithm and give proofs of optimality for some classes of graphs. From an experimental perspective, experiments also show that the performance of the algorithms correlates with the modularity of the analyzed network. Moreover, the more the influence among communities is hard to propagate, the less the performances of the algorithms differ. On the other hand, when the network allows some propagation of influence between different communities, the gap between the solutions returned by the proposed algorithm and by the previous algorithms in the literature increases.
Vorheriger Artikel Influence learning for cascade diffusion models: focus on partial orders of infections
Nächster Artikel Focal structures analysis: identifying influential sets of individuals in a social network

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
Fußnoten
1
In the rest of the paper we will omit the subscript G whenever the graph G is clear from the context.
 
2
Notice that in each of Cases 1, 2 and 3 ties are broken at random.
 
Literatur
Ackerman E, Ben-Zwi O, Wolfovitz G (2010) Combinatorial model and bounds for target set selection. Theor Comput Sci 411(44–46):4017–4022MathSciNetCrossRefMATH
Bazgan C, Chopin M, Nichterlein A, Sikora F (2014) Parameterized approximability of maximizing the spread of influence in networks. J Discret Algorithms 27:54–65MathSciNetCrossRefMATH
Ben-Zwi O, Hermelin D, Lokshtanov D, Newman I (2011) Treewidth governs the complexity of target set selection. Discret Optim 8(1):87–96MathSciNetCrossRefMATH
Bond RM, Fariss CJ, Jones JJ, Kramer ADI, Marlow C, Settle JE, Fowler JH (2012) A 61-million-person experiment in social influence and political mobilization. Nature 489:295–298CrossRef
Centeno CC, Dourado MC, Penso LD, Rautenbach D, Szwarcfiter JL (2011) Irreversible conversion of graphs. Theor Comput Sci 412(29):3693–3700MathSciNetCrossRefMATH
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, KDD ’09, pp 199–208, New York, NY
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, pp 1029–1038
Chen W, Castillo C, Lakshmanan L (2013) Information and influence propagation in social networks. Morgan & Claypool, San Rafael
Chiang C-Y, Huang L-H, Li B-J, Jiaojiao W, Yeh H-G (2013a) Some results on the target set selection problem. J Comb Optim 25(4):702–715MathSciNetCrossRefMATH
Chiang C-Y, Huang L-H, Yeh H-G (2013b) Target set selection problem for honeycomb networks. SIAM J Discret Math 27(1):310–328MathSciNetCrossRefMATH
Chopin M, Nichterlein A, Niedermeier R, Weller M (2014) Constant thresholds can make target set selection tractable. Theory Comput Syst 55(1):61–83MathSciNetCrossRefMATH
Christakis NA, Fowler JH (2011) Connected: the surprising power of our social networks and how they shape our lives—how your friends’ friends’ friends affect everything you feel,think, and do. back bay books, reprint edn, January 2011
Cicalese F, Cordasco G, Gargano L, Milanič M, Vaccaro U (2014) Latency-bounded target set selection in social networks. Theor Comput Sci 535:1–15MathSciNetCrossRefMATH
Cicalese F, Cordasco G, Gargano L, Milanič M, Peters J, Vaccaro U (2015) Spread of influence in weighted networks under time and budget constraints. Theor Comput Sci 586:40–58MathSciNetCrossRefMATH
Coja-Oghlan A, Feige U, Krivelevich M, Reichman D (2015) Contagious sets in expanders. In: Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, pp 1953–1987
Cordasco G, Gargano L, Mecchia M, Rescigno AA, Vaccaro U (2015a) A fast and effective heuristic for discovering small target sets in social networks. In: Proceedings of COCOA 2015, vol 9486, pp 193–208
Cordasco G, Gargano L, Rescigno AA, Vaccaro U (2015b) Optimizing spread of influence in social networks via partial incentives. In: Structural information and communication complexity: 22nd international colloquium, SIROCCO 2015, pp 119–134. Springer International Publishing
Cordasco G, Gargano L, Rescigno AA (2015c) Influence propagation over large scale social networks. In: Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining, ASONAM 2015, Paris, France, pp 1531–1538
Cordasco G, Gargano L, Rescigno AA, Vaccaro U (2016b) Evangelism in social networks. In: Combinatorial algorithms—27th international workshop, IWOCA 2016, Helsinki, Finland, 17–19 Aug 2016, proceedings, pp 96–108
Cordasco G, Gargano L, Rescigno AA, Vaccaro U (2016b) Evangelism in social networks. In: Combinatorial algorithms—27th international workshop, IWOCA 2016, Helsinki, Finland, 17–19 Aug 2016, proceedings, pp 96–108
Dinh TN, Zhang H, Nguyen DT, Thai MT (2014) Cost-effective viral marketing for time-critical campaigns in large-scale social networks. IEEE/ACM Trans Netw 22(6):2001–2011CrossRef
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, KDD ’01, pp 57–66, New York, NY, USA
Flocchini P, Královic R, Ruzicka P, Roncato A, Santoro N (2003) On time versus size for monotone dynamic monopolies in regular topologies. J Discret Algorithms 1(2):129–150MathSciNetCrossRefMATH
Freund D, Poloczek M, Reichman D (2015) Contagious sets in dense graphs. In: Proceedings of 26th int’l workshop on combinatorial algorithms (IWOCA2015)
Gargano L, Hell P, Peters JG, Vaccaro U (2015) Influence diffusion in social networks under time window constraints. Theor Comput Sci 584(C):53–66MathSciNetCrossRefMATH
Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420–1443CrossRef
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, KDD ’03, pp 137–146, New York, NY, USA
Kempe D, Kleinberg J, Tardos É (2005) Influential nodes in a diffusion model for social networks. In: Proceedings of the 32Nd international conference on automata, languages and programming, ICALP’05, pp 1127–1138, Berlin
Kempe D, Kleinberg J, Tardos É (2015) Maximizing the spread of influence through a social network. Theory Comput 11(4):105–147MathSciNetCrossRefMATH
Kundu S, Pal SK (2015) Deprecation based greedy strategy for target set selection in large scale social networks. Inf Sci 316:107–122CrossRef
Leppaniemi M, Karjaluoto H, Lehto H, Goman A (2010) Targeting young voters in a political campaign: empirical insights into an interactive digital marketing campaign in the 2007 finnish general election. J Nonprofit Publ Sect Mark 22(1):14–37CrossRef
Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Trans Web 1(1):5CrossRef
Nichterlein A, Niedermeier R, Uhlmann J, Weller M (2013) On tractable cases of target set selection. Soc Netw Anal Min 3(2):233–256CrossRefMATH
Rival J-B, Walach J (2007) The use of viral marketing in politics: a case study of the 2007 french presidential election. Master thesis, Jönköping University, Jönköping International Business School
Shakarian P, Eyre S, Paulo D (2013) A scalable heuristic for viral marketing under the tipping model. Soc Netw Anal Min 3(4):1225–1248CrossRef
Tumulty K (2007) Obama’s viral marketing campaign. TIME Magazine, July 2007
Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, CambridgeCrossRefMATH
Metadaten
Titel
On finding small sets that influence large networks
verfasst von
Gennaro Cordasco
Luisa Gargano
Adele A. Rescigno
Publikationsdatum
01.12.2016
Verlag
Springer Vienna
Erschienen in
Social Network Analysis and Mining / Ausgabe 1/2016
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-016-0408-z

Weitere Artikel der Ausgabe 1/2016

Social Network Analysis and Mining 1/2016 Zur Ausgabe

Original Article

Social ties and checkin sites: connections and latent structures in location-based social networks

Original Article

Computing competing cascades on signed networks

Original Article

Fast rumor source identification via random walks

Original Article

Empirical analysis of the Portuguese governments social network

Original Article

CADIVa: cooperative and adaptive decentralized identity validation model for social networks

Original Article

Sampling algorithms for weighted networks