Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results

详细信息    查看全文

• 作者：Chris J. Kuhlman (1)
  V. S. Anil Kumar (1)
  Madhav V. Marathe (1)
  S. S. Ravi (2)
  Daniel J. Rosenkrantz (2)
  
  1. Virginia Bioinformatics Institute ; Virginia Tech ; Blacksburg ; VA聽 ; 24061 ; USA
  2. Department of Computer Science ; University at Albany鈥揝UNY ; 1400 Washington Avenue ; Albany ; NY聽 ; 12222 ; USA
  
• 关键词：Complex contagions ; Blocking ; Social networks
• 刊名：Data Mining and Knowledge Discovery
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：29
• 期：2
• 页码：423-465
• 全文大小：1,578 KB
• 参考文献：1. Acemoglu D, Ozdaglar A (2011) Opinion dynamics and learning in social networks. Dyn Games Appl 1:3鈥?9 CrossRef
  2. Albert R, Jeong H, Barabasi A (2000) Error and attack tolerance of complex networks. Nature 406:378鈥?81 CrossRef
  3. Anderson A, Huttenlocher D, Kleinberg J, Leskovec J (2012) Effects of user similarity in social media. In: Proceedings of the 5th ACM symposium on web search and data mining (WSDM 2012).
  4. Anshelevich E, Chakrabarty D, Hate A, Swamy C (2009) Approximation algorithms for the firefighter problem: cuts over time and aubmodularity. In: Proceedings of the conference of the international society for augmentative and alternative communication (ISAAC 2009), pp 974鈥?83
  5. Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM (2009) Detecting critical nodes in sparse graphs. Comput Oper Res 36(7):2193鈥?200 CrossRef
  6. Barabasi A, Albert R (1999) Emergence of scaling in random networks. Nature 286:509鈥?12
  7. Barash V (2011) The dynamics of social contagion. PhD thesis, Cornell University.
  8. Barash V, Cameron C, Macy M (2012) Critical phenomena in complex contagions. Soc Netw 34:451鈥?61 CrossRef
  9. Barrett C, Bisset K, Eubank S, Feng X, Marathe M (2008) EpiSimdemics: an efficient algorithm for simulating the spread of infectious disease over large realistic social networks. In: Proceedings of the 2008 ACM/IEEE conference on supercomputing.
  10. Barrett CL, Hunt HB, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE (2006) Complexity of reachability problems for finite discrete dynamical systems. J Comput Syst Sci 72(8):1317鈥?345 CrossRef
  11. Barrett CL, Hunt HB, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE, Thakur M (2007) Predecessor existence problems for finite discrete dynamical systems. Theor Comput Sci 386(1鈥?):3鈥?7 CrossRef
  12. Bonacich P (1972) Factoring and weighting approaches to status scores and clique identification. J Math Soc 2:113鈥?20 CrossRef
  13. Borgatti SP (2006) Identifying sets of key players in a social network. Comput Math Organiz Theor 12:21鈥?4 CrossRef
  14. Briesemeister L, Lincoln P, Porras P (2003) Epidemic profiles and defense of scale-free networks. In: Proceedings of the 2003 ACM CCS Workshop on Rapid Malcode (WORM 03), pp 67鈥?5
  15. Centola D (2009) Failure in complex social networks. J Math Soc 33:64鈥?8 CrossRef
  16. Centola D (2010) The spread of behavior in an online social network experiment. Science 329:1194鈥?197 CrossRef
  17. Centola D, Macy M (2007) Complex contagions and the weakness of long ties. Am J Sociol 113(3):702鈥?34 CrossRef
  18. Centola D, Eguiluz V, Macy M (2006) Cascade dynamics of complex propagation. Phys A 374:449鈥?56 CrossRef
  19. Centola D, Gonzlez-Avella JC, Eguluz VM, Miguel MS (2007) Homophily, cultural drift, and the co-evolution of cultural groups. J Conflict Resolut 51:905鈥?29 CrossRef
  20. Cha M, Mislove A, Adams B, Gummadi K (2008) Characterizing social cascades in Flickr. In: Proc. of the first workshop on online social networks (WOSN 08), pp 13鈥?8
  21. Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. ACM Trans Inf Syst Secur 10(4):1鈥?6 CrossRef
  22. Cohen R, Havlin S, Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys Rev Lett 91:247
  23. Cormen T, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press, Cambridge
  24. Crucitti P, Latora V, Marchiori M, Rapisarda A (2004) Error and attack tolerance of complex networks. Phys A 340:388鈥?94 CrossRef
  25. Dezso Z, Barabasi A (2002) Halting viruses in scale-free networks. Phys Rev E 65:055 CrossRef
  26. Dodds PS, Watts DJ (2005) A generalized model of social and biological contagion. J Theor Biol 232(4):587鈥?04 CrossRef
  27. Domingos P, Richardson M (2001) Mining the network value of customers. In: Proc. ACM intl. conf. on data mining and knowledge discovery (KDD 2001), pp 57鈥?1
  28. Dreyer P, Roberts F (2009) Irreversible \(k\) -Threshold Processes: Graph-Theoretical Threshold Models of the Spread of Disease and Opinion. Discrete Applied Mathematics 157:1615鈥?627 CrossRef
  29. Eubank S, Kumar VSA, Marathe MV, Srinivasan A, Wang N (2006) Structure of social contact networks and their impact on epidemics. In: Abello J, Cormode G (eds) Discrete methods in epidemiology. DIMACS series in discrete mathematics and theoretical computer science. American Mathematical Society, Providence, pp 179鈥?00
  30. Freeman LC (1976) A set of measures of centrality based on betweenness. Sociometry 40:35鈥?1 CrossRef
  31. Ganesh A, Massoulie L, Towsley D (2005) The effect of network topology on the spread of epidemics. In: Proceedings of the 24th annual joint conference of the IEEE computer and communications societies (INFOCOM 2005), vol 2, pp 1455鈥?466
  32. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Co., San Francisco
  33. Gonzalez-Bailon S, Borge-Holthoefer J, Rivero A, Moreno Y (2011) The dynamics of protest recruitment through an online network. Nature Scientific Reports pp 1鈥?. doi:10.1038/srep00197
  34. Granovetter M (1973) The strength of weak ties. Am J Sociol 78(6):1360鈥?380 CrossRef
  35. Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420鈥?443 CrossRef
  36. Gruhl D, Guha R, Liben-Nowell D, Tomkins A (2004) Information diffusion through blogspace. In: Proc. of the 13th international world wide web conference (WWW 2004), pp 491鈥?01
  37. Guha R, Kumar R, Raghavan P, Tomkins A (2004) Propagation of trust and distrust. In: Proc. of the 13th international world wide web conference (WWW 2004), pp 403鈥?12
  38. Habiba, Yu Y, Berger-Wolf TY, Saia J (2008) Finding spread blockers in dynamic networks. In: The 2nd SNA-KDD Workshop 鈥?8 (SNA-KDD 2008)
  39. Harris KM (2008) The National Longitudinal Study of Adolescent Health (Add Health), Waves I and II, 1994鈥?996; Wave III, 2001鈥?002 [machine-readable data file and documentation]. Chapel Hill, NC: Carolina Population Center, University of North Carolina at Chapel Hill 2008
  40. Holme P (2004) Efficient local strategies for vaccination and network attack. Europhys Lett 68:908鈥?14 CrossRef
  41. Jin C, Liu J, Deng Q (2009) Network virus propagation model based on effects of removing time and user vigilance. Int J Netw Secur 9:156鈥?63
  42. Kawachi K (2008) Deterministic models for rumor transmission. Nonlinear Anal 9:1989鈥?028 CrossRef
  43. Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proc. ACM Intl. Conf. on data mining and knowledge discovery (KDD 2003), pp 137鈥?46
  44. Kempe D, Kleinberg J, Tardos E (2005) Influential nodes in a diffusion model for social networks. In: Proc. Intl. Conf. on automata, languages and programming (ICALP 2005), pp 1127鈥?138
  45. Kleinberg J (2007) Cascading behavior in networks: algorithmic and economic Issues. In: Nissan N, Roughgarden T, Tardos E, Vazirani V (eds) Algorithmic game theory. Cambridge University Press, New York, pp 613鈥?32 CrossRef
  46. Kleinberg JM (1999) Authoritative sources in a hyperlinked environment. J ACM 46:604鈥?32 CrossRef
  47. Kossinets G, Kleinberg J, Watts D (2008) The structure of information pathways in a social communication network. In: Proc. ACM Intl. Conf. on data mining and knowledge siscovery (KDD 2008)
  48. Kuhlman C, Kumar V, Marathe M, Ravi S, Rosenkrantz D, Swarup S, Tuli G (2011) A bithreshold model of complex contagion and its application to the spread of smoking behavior. In: Proceedings of the workshop on social network mining and analysis (SNA-KDD 2011)
  49. Kuhlman CJ, Kumar VA, Marathe MV, Ravi SS, Rosenkrantz DJ (2010a) Exploiting network structure in enhancing diffusion of complex contagions. In: Proc. workshop on analysis of complex networks (ACNE 2010)
  50. Kuhlman CJ, Kumar VA, Marathe MV, Ravi SS, Rosenkrantz DJ (2010b) Finding critical nodes for inhibiting diffusion of complex contagions in social networks. In: Proceedings of the European conference on machine learning and principles and practice of knowledge discovery in databases (ECML PKDD 2010), pp 111鈥?27
  51. Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Trans Web 1(1):251鈥?62 CrossRef
  52. Leskovec J, Lang K, Dasgupta A, Mahoney M (2008) Statistical properties of community structure in large social and information networks. In: Proceedings of the 17th international world wide web conference (WWW 2008)
  53. Leskovec J, Huttenlocher D, Kleinberg J (2010) Predicting positive and negative links in online social networks. In: Proceedings of the 19th international world wide web conference (WWW 2010)
  54. Liu YY, Slotine JJ, Barabsi AL (2011) Controllability of complex networks. Nature 473:167鈥?73 CrossRef
  55. Longini IM, Nizam A, Xu S, Ungchusak K, Hanshaoworakul W, Cummings DAT, Halloran ME (2005) Containing pandemic influenza at the source. Science 309:1083鈥?087 CrossRef
  56. Macy M (1991) Chains of cooperation: threshold effects in collective action. Am Sociol Rev 56(6):730鈥?47 CrossRef
  57. Madar N, Kalisky T, Cohen R, Ben-Avraham D, Havlin S (2004) Immunization and epidemic dynamics in complex networks. Eur Phys J B 38:269鈥?76 CrossRef
  58. Martin G, Marinescu MC, Singh DE, Carretero J (2011) Leveraging social networks for understanding the evolution of epidemics. BMC Syst Biol 5:1鈥?6 CrossRef
  59. Melnik S, Ward JA, Gleeson JP, Porter MA (2013) Multi-stage complex contagion. Chaos 23:013 CrossRef
  60. Mobilia M (2003) Does a single zealot affect an infinite group of voters? Phys Rev Lett 91(2):028701 CrossRef
  61. Mobilia M, Petersen A, Redner S (2007) On the role of zealotry in the voter model. J Stat Mech P08029:1鈥?7
  62. Newman M (2003) The structure and function of complex networks. SIAM Rev 45:167鈥?56 CrossRef
  63. Newman MEJ, Park J (2003) Why social networks are different from other types of networks. Phys Rev E 68:036122 CrossRef
  64. Page L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: Bringing order to the web. Technical Report 1999鈥?6, Stanford InfoLab.
  65. Pastor-Satorras R, Vespignani A (2001) Epidemic spreading in scale-free networks. Phys Rev Lett 86:3200鈥?203 CrossRef
  66. Perumalla K, Seal S (2010) Reversible parallel discrete-event execution of large-scale epidemic outbreak models. In: Proceedings of the 24th ACM/IEEE/SCS workshop on principles of advanced and distributed simulation (PADS 2010)
  67. Porras P, Briesemeister L, Skinner K, Levitt K, Rowe J, Ting YCA (2004) A hybrid quarantine defense. In: Proceedings of the 2004 ACM CCS Workshop on Rapid Malcode (WORM 04), pp 73鈥?2
  68. Prakash B, Tong H, Valler N, Faloutsos M, Faloutsos C (2010) Virus propagation on time-varying networks: theory and immunization algorithms. In: Proceedings of the 2010 European conference on machine learning and knowledge discovery in databases (ECML PKDD 2010), pp 99鈥?14
  69. Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and a sub-constant error-probability characterization of NP. In: Proc. ACM symp. on theory of computing (STOC 1997), pp 475鈥?84
  70. Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proc. ACM Intl. Conf. on data mining and knowledge discovery (KDD 2002), pp 61鈥?0
  71. Richardson M, Agrawal R, Domingos P (2003) Trust Management for the Semantic Web. In: Proc. of the Second International Semantic Web Conference (ISWC 2003), pp 351鈥?68
  72. Romero D, Meeder B, Kleinberg J (2011) Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In: Proceedings of the 20th international world wide web conference (WWW 2011)
  73. Salathe M, Jones J (2010) Dynamics and control of diseases in networks with community structure. PLoS Comput Biol 6:e1000,736-1鈥揺1000,736-11 CrossRef
  74. Schank T, Wagner D (2005) Approximating clustering coefficients and transitivity. J Algorithms Appl 9(2):265鈥?75 CrossRef
  75. Schelling T (1978) Micromotives and macrobehavior. W. W. Norton and Company, New York
  76. Seidman SB (1983) Network structure and minimum degree. Soc Netw 5:269鈥?87 CrossRef
  77. Shi X, Zhu J, Cai R, Zhang L (2009) User grouping behavior in online forums. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining (KDD 09), pp 777鈥?86
  78. Siegel D (2009) Social networks and collective action. Am J Polit Sci 53:122鈥?38 CrossRef
  79. Siegel D (2010) When does repression work? collective action in social networks. J Polit 73:993鈥?010 CrossRef
  80. Tantipathananandh C, Berger-Wolf TY, Kempe D (2007) A framework for community identification in dynamic social networks. In: Proc. ACM Intl. Conf. on data mining and knowledge discovery (KDD 2007), pp 717鈥?26
  81. Tong H, Prakash B, Tsourakakis C, Eliassi-Rad T, Faloutsos C, Chau D (2010) On the vulnerability of large graphs. In: Proceedings of the 10th IEEE conference on data mining (ICDM 2010), pp 1091鈥?096
  82. Ugander J, Backstrom L, Marlow C (2012) Structural diversity in social contagion. Proc Natl Acad Sci 109(9):5962鈥?966 CrossRef
  83. Vazirani VV (2001) Approximation algorithms. Springer, New York
  84. Vespignani A (2012) Modelling dynamical processes in complex socio-technical systems. Nat Phys 8:32鈥?9 CrossRef
  85. Wang Y, Chakrabarti D, Wang C, Faloutsos C (2003) On the vulnerability of large graphs. In: Proceedings of the 22nd international symposium on reliable distributed systems (RDS 2003), pp 25鈥?4
  86. Watts D (2002) A simple model of global cascades on random networks. Proc Natl Acad Sci 99(9):5766鈥?771 CrossRef
  87. Yildiz E, Acemoglu D, Ozdaglar A, Saberi A, Scaglione A (2011) Discrete opinion dynamics with stubborn agents. OPRE-2011-01-026.
  88. Zhang HF, Li KZ, Fu XC, Wang BH (2009) An efficient control strategy of epidemic spreading on scale-free networks. Phys Rev Lett 26:068,901-1鈥?68,901-4
  
• 刊物类别：Computer Science
• 刊物主题：Data Mining and Knowledge Discovery
  Computing Methodologies
  Artificial Intelligence and Robotics
  Statistics
  Statistics for Engineering, Physics, Computer Science, Chemistry and Geosciences
  Information Storage and Retrieval
  
• 出版者：Springer Netherlands
• ISSN：1573-756X

文摘

We consider the problem of inhibiting undesirable contagions (e.g. rumors, spread of mob behavior) in social networks. Much of the work in this context has been carried out under the 1-threshold model, where diffusion occurs when a node has just one neighbor with the contagion. We study the problem of inhibiting more complex contagions in social networks where nodes may have thresholds larger than 1. The goal is to minimize the propagation of the contagion by removing a small number of nodes (called critical nodes) from the network. We study several versions of this problem and prove that, in general, they cannot even be efficiently approximated to within any factor \(\rho \ge 1\) , unless P = NP. We develop efficient and practical heuristics for these problems and carry out an experimental study of their performance on three well known social networks, namely epinions, wikipedia and slashdot. Our results show that these heuristics perform significantly better than five other known methods. We also establish an efficiently computable upper bound on the number of nodes to which a contagion can spread and evaluate this bound on many real and synthetic networks.