[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The unified model of social influence and its application in influence maximization

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

Abstract

The study of information dissemination on a social network has gained significant importance with the rise of social media. Since the true dynamics are hidden, various diffusion models have been exposed to explain the cascading behavior. Such models require extensive simulation for estimating the dissemination over time. In an earlier work, we proposed a unified model which provides an approximate analytical solution to the problem of predicting probability of infection of every node in the network over time. Our model generalizes a large class of diffusion process. We demonstrate through extensive empirical evaluation that the error of approximation is small. We build upon our unified model to develop an efficient method for influence maximization. Unlike most approaches, we assume that diffusion spreads not only via the edges of the underlying network, but also through temporal functions of external out-of-network processes. We empirically evaluate our approach and compare it against state-of-the-art approaches on real-world large-scale networks. The evaluation demonstrates that our method has significant performance gains over widely used seed-set selection algorithms.

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
£29.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 includes VAT (United Kingdom)

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. Note that this is different from the linear threshold model in Kempe et al. (2003) in that the threshold may change at every time step.

  2. http://digg.com/.

  3. The dataset can be found online at http://www-scf.usc.edu/~ajiteshs/datasets/digg_ASONAM2014.txt (last accessed on Oct 19, 2015).

  4. Density refers to the ratio of the number of links present in the graph to the total number of possible links.

References

  • Abrahamson E, Rosenkopf L (1997) Social network effects on the extent of innovation diffusion: a computer simulation. Organ Sci 8(3):289–309

    Article  Google Scholar 

  • Anagnostopoulos A, Kumar R, Mahdian M (2008) Influence and correlation in social networks. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 7–15

  • Bakshy E, Rosenn I, Marlow C, Adamic L (2012) The role of social networks in information diffusion. In: Proceedings of the 21st international conference on World Wide Web. ACM, New York, pp 519–528

  • Bass FM (2004) A new product growth for model consumer durables. Manage Sci 50(12 Supplement):1825–1832

    Article  Google Scholar 

  • Bóta A, Krész M, Pluhár A (2013) Approximations of the generalized cascade model. Acta Cybernetica 21(1):37–51

    MATH  MathSciNet  Google Scholar 

  • Budak C, Agrawal D, El Abbadi A (2012) Diffusion of information in social networks: is it all local? In: 2012 IEEE 12th international conference on data mining (ICDM), pp 121–130. doi:10.1109/ICDM.2012.74

  • Chelmis C, Prasanna VK (2013) The role of organization hierarchy in technology adoption at the workplace. In: Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining. ASONAM ’13. ACM, New York, pp 8–15

  • Chelmis C, Srivastava A, Prasanna VK (2014) Computational models of technology adoption at the workplace. Soc Netw Anal Min 4(1):1–18

    Article  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. ACM, New York, pp 199–208

  • Chen W, Wang C, Wang Y (2010a) 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, New York, pp 1029–1038

  • Chen W, Yuan Y, Zhang L (2010b) Scalable influence maximization in social networks under the linear threshold model. In: 2010 IEEE 10th international conference on data mining (ICDM). IEEE, pp 88–97

  • Choi H, Kim SH, Lee J (2010) Role of network structure and network effects in diffusion of innovations. Ind Mark Manag 39(1):170–177

    Article  Google Scholar 

  • de Caen D (1998) An upper bound on the sum of squares of degrees in a graph. Discret Math 185(1):245–248

    Article  MATH  Google Scholar 

  • Du N, Song L, Gomez-Rodriguez M, Zha H (2013) Scalable influence estimation in continuous-time diffusion networks. In: Advances in neural information processing systems, pp 3147–3155

  • Erdős P, Rényi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5:17–61

    Google Scholar 

  • Fan L, Wu W, Zhai X, Xing K, Lee W, Du DZ (2014) Maximizing rumor containment in social networks with constrained time. Soc Netw Anal Min 4(1):1–10

    Article  Google Scholar 

  • Gionis A, Terzi E, Tsaparas P (2013) Opinion maximization in social networks. In: SDM, SIAM, pp 387–395

  • Gomez Rodriguez M, Leskovec J, Krause A (2010) Inferring networks of diffusion and influence. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’10. ACM, New York, pp 1019–1028. doi:10.1145/1835804.1835933

  • Goyal A, Bonchi F, Lakshmanan LV (2010) Learning influence probabilities in social networks. In: Proceedings of the third ACM international conference on Web search and data mining. WSDM ’10. ACM, New York, pp 241–250. doi:10.1145/1718487.1718518

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

  • Goyal A, Lu W, Lakshmanan LV (2011b) Simpath: an efficient algorithm for influence maximization under the linear threshold model. In: 2011 IEEE 11th international conference on data mining (ICDM). IEEE, pp 211–220

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

    Article  Google Scholar 

  • Hajibagheri A, Hamzeh A, Sukthankar G (2013) Modeling information diffusion and community membership using stochastic optimization. In: Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining. ASONAM ’13. ACM, New York, pp 175–182. doi:10.1145/2492517.2492545

  • Hethcote HW (2000) The mathematics of infectious diseases. SIAM Rev 42(4):599–653

    Article  MATH  MathSciNet  Google Scholar 

  • Jacquez JA, Simon CP (1993) The stochastic SI model with recruitment and deaths I. Comparison with the closed SIS model. Math Biosci 117(1–2):77–125

    Article  MATH  MathSciNet  Google Scholar 

  • Kamp C (2010) Untangling the interplay between epidemic spread and transmission network dynamics. PLoS Comput Biol 6(11):e1000984

  • Kelman HC (1961) Processes of opinion change. Public Opin Q 25(1):57–78

    Article  Google Scholar 

  • Kempe D, Kleinberg J, Tardos E (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, New York, pp 137–146

  • Kleinberg J (2007) Cascading behavior in networks: algorithmic and economic issues. In: Roughgarden T, Tardos E, Vazirani VV, Nisan N (eds) Algorithmic Game Theory. Cambridge University Press, Cambridge

  • Lahiri M, Cebrian M (2010) The genetic algorithm as a general diffusion model for social networks. In: AAAI

  • Leskovec J, Adamic LA, Huberman BA (2006) The dynamics of viral marketing. In: Proceedings of the 7th ACM conference on electronic commerce. ACM, New York, pp 228–237

  • Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) 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

  • Lin YR, Sun J, Castro P, Konuru R, Sundaram H, Kelliher A (2009) Metafac: community discovery via relational hypergraph factorization. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’09. ACM, New York, pp 527–536. doi:10.1145/1557019.1557080

  • Lu Z, Zhang W, Wu W, Kim J, Fu B (2012) The complexity of influence maximization problem in the deterministic linear threshold model. J Comb Optim 24(3):374–378

    Article  MATH  MathSciNet  Google Scholar 

  • Myers SA, Zhu C, Leskovec J (2012) Information diffusion and external influence in networks. In: Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’12. ACM, New York, pp 33–41. doi:10.1145/2339530.2339540

  • Newman ME (2002) Spread of epidemic disease on networks. Phys Rev E 66(1):016128

  • 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 

  • Srivastava A, Chelmis C, Prasanna VK (2014) Influence in social networks: a unified model? In: Proceedings of the 2014 IEEE/ACM international conference on advances in social networks analysis and mining. ASONAM ’14. IEEE, pp 451–454

  • Srivastava A, Chelmis C, Prasanna VK (2016) Computational models for cascades in massive graphs: how to spread a rumor in parallel. In: Bader DA (ed) Parallel graph algorithms. Chapman and Hall/CRC Computational Science (to appear)

  • Subbian K, Sharma D, Wen Z, Srivastava J (2013) Finding influencers in networks using social capital. In: Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining. ASONAM ’13. ACM, New York, pp 592–599. doi:10.1145/2492517.2492552

  • Tang J, Sun J, Wang C, Yang Z (2009) Social influence analysis in large-scale networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’09. ACM, New York, pp 807–816. doi:10.1145/1557019.1557108

  • Tong H, Papadimitriou S, Faloutsos C, Philip SY, Eliassi-Rad T (2010) Basset: scalable gateway finder in large graphs. In: Advances in knowledge discovery and data mining. Springer, Berlin, pp 449–463

  • Valente TW (1996) Social network thresholds in the diffusion of innovations. Soc Netw 18(1):69–89

    Article  MathSciNet  Google Scholar 

  • Xu W, Lu Z, Wu W, Chen Z (2014) A novel approach to online social influence maximization. Soc Netw Anal Min 4(1):1–13

    Article  Google Scholar 

  • Yang J, Leskovec J (2010) Modeling information diffusion in implicit networks. In: Proceedings of the 2010 IEEE international conference on data mining. IEEE Computer Society, Washington, pp 599–608

Download references

Acknowledgments

This work is supported by Chevron USA Inc. under the joint project, Center for Interactive Smart Oilfield Technologies (CiSoft), at the University of Southern California.

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Southern California, Los Angeles, USA

    Ajitesh Srivastava

  2. Ming Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles, USA

    Charalampos Chelmis & Viktor K. Prasanna

Authors
  1. Ajitesh Srivastava
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Charalampos Chelmis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Viktor K. Prasanna
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ajitesh Srivastava.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Srivastava, A., Chelmis, C. & Prasanna, V.K. The unified model of social influence and its application in influence maximization. Soc. Netw. Anal. Min. 5, 66 (2015). https://doi.org/10.1007/s13278-015-0305-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13278-015-0305-x

Keywords

Search

Navigation