iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s13278-016-0408-z
On finding small sets that influence large networks | Social Network Analysis and Mining Skip to main content
Springer Nature Link
Log in

On finding small sets that influence large networks

  • Original Article
  • Published:
Social Network Analysis and Mining Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  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.

References

  • Ackerman E, Ben-Zwi O, Wolfovitz G (2010) Combinatorial model and bounds for target set selection. Theor Comput Sci 411(44–46):4017–4022

    Article  MathSciNet  MATH  Google Scholar 

  • Bazgan C, Chopin M, Nichterlein A, Sikora F (2014) Parameterized approximability of maximizing the spread of influence in networks. J Discret Algorithms 27:54–65

    Article  MathSciNet  MATH  Google Scholar 

  • Ben-Zwi O, Hermelin D, Lokshtanov D, Newman I (2011) Treewidth governs the complexity of target set selection. Discret Optim 8(1):87–96

    Article  MathSciNet  MATH  Google Scholar 

  • 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–298

    Article  Google Scholar 

  • Centeno CC, Dourado MC, Penso LD, Rautenbach D, Szwarcfiter JL (2011) Irreversible conversion of graphs. Theor Comput Sci 412(29):3693–3700

    Article  MathSciNet  MATH  Google Scholar 

  • Chen N (2009) On the approximability of influence in social networks. SIAM J Discret Math 23(3):1400–1415

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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–715

    Article  MathSciNet  MATH  Google Scholar 

  • Chiang C-Y, Huang L-H, Yeh H-G (2013b) Target set selection problem for honeycomb networks. SIAM J Discret Math 27(1):310–328

    Article  MathSciNet  MATH  Google Scholar 

  • Chopin M, Nichterlein A, Niedermeier R, Weller M (2014) Constant thresholds can make target set selection tractable. Theory Comput Syst 55(1):61–83

    Article  MathSciNet  MATH  Google Scholar 

  • 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–15

    Article  MathSciNet  MATH  Google Scholar 

  • 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–58

    Article  MathSciNet  MATH  Google Scholar 

  • 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–2011

    Article  Google Scholar 

  • 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–150

    Article  MathSciNet  MATH  Google Scholar 

  • 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–66

    Article  MathSciNet  MATH  Google Scholar 

  • Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420–1443

    Article  Google Scholar 

  • 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–147

    Article  MathSciNet  MATH  Google Scholar 

  • Kundu S, Pal SK (2015) Deprecation based greedy strategy for target set selection in large scale social networks. Inf Sci 316:107–122

    Article  Google Scholar 

  • 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–37

    Article  Google Scholar 

  • Leskovec J, Krevl A (2015) SNAP datasets: stanford large network dataset collection. http://snap.stanford.edu/data

  • Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Trans Web 1(1):5

    Article  Google Scholar 

  • Newman M (2015) Network data. http://www-personal.umich.edu/~mejn/netdata/

  • Nichterlein A, Niedermeier R, Uhlmann J, Weller M (2013) On tractable cases of target set selection. Soc Netw Anal Min 3(2):233–256

    Article  MATH  Google Scholar 

  • Thirumala Reddy TV, Pandu Rangan C (2011) Variants of spreading messages. J Graph Algorithms Appl 15(5):683–699

    Article  MathSciNet  MATH  Google Scholar 

  • 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–1248

    Article  Google Scholar 

  • 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, Cambridge

    Book  MATH  Google Scholar 

  • Zafarani R, Liu H (2009) Social computing data repository at ASU. http://socialcomputing.asu.edu

  • Zaker M (2012) On dynamic monopolies of graphs with general thresholds. Discret Math 312(6):1136–1143

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Psychology, Second University of Naples, Caserta, Italy

    Gennaro Cordasco

  2. Department of Computer Science, University of Salerno, Fisciano, Italy

    Luisa Gargano & Adele A. Rescigno

Authors
  1. Gennaro Cordasco
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luisa Gargano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Adele A. Rescigno
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gennaro Cordasco.

Additional information

A preliminary version of this paper was presented at the 1st International Workshop on Dynamics in Networks (DyNo 2015) in conjunction with the 2016 IEEE/ACM International Conference ASONAM, Paris, France, August 25–28, 2015. Cordasco et al. (2015c).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cordasco, G., Gargano, L. & Rescigno, A.A. On finding small sets that influence large networks. Soc. Netw. Anal. Min. 6, 94 (2016). https://doi.org/10.1007/s13278-016-0408-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13278-016-0408-z

Keywords

Search

Navigation