Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Log in
Learn more about individual access
Request company access
13th International Engine Congress 2026 | 24 + 25 February 2026

Meeting Place for the Powertrain and Sustainable Fuels Community

Take part as a speaker in the 13th International Engine Congress 2026, the Meeting Place for the Powertrain, and Sustainable Fuels Community for the exchange of experience. Submit a subject proposal online about our main subject areas: Passenger car engine technology, Commercial vehicle engine technology and Sustainable Fuels & Energy!
EXTENDED SEARCH
Log in
Top
Social Network Analysis and Mining
Published in:

01-12-2016 | Original Article

On finding small sets that influence large networks

Authors: Gennaro Cordasco, Luisa Gargano, Adele A. Rescigno

Published in: Social Network Analysis and Mining | Issue 1/2016

Log in

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

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.
previous article Influence learning for cascade diffusion models: focus on partial orders of infections
next article Focal structures analysis: identifying influential sets of individuals in a social network

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
Footnotes
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.
 
Literature
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
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
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
Metadata
Title
On finding small sets that influence large networks
Authors
Gennaro Cordasco
Luisa Gargano
Adele A. Rescigno
Publication date
01-12-2016
Publisher
Springer Vienna
Published in
Social Network Analysis and Mining / Issue 1/2016
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-016-0408-z

Other articles of this Issue 1/2016

A significant core structure inside the social network evolutionary process

  • Original Article

Stepping back from the trees to see the forest: a network approach to valuing intelligence

  • Original Article

Centrality in the global network of corporate control

  • Open Access
  • Original Article

Tracking local communities in streaming graphs with a dynamic algorithm

  • Original Article

Spectral embedding of directed networks

  • Original Article

Parallel collective factorization for modeling large heterogeneous networks

  • Original Article

Premium Partner

    Image Credits