Abstract
Abstract. Social interactions are conduits for various processes spreading through a population, from rumors and opinions to behaviors and diseases. In the context of the spread of a disease or undesirable behavior, it is important to identify blockers: individuals that are most effective in stopping or slowing down the spread of a process through the population. This problem has so far resisted systematic algorithmic solutions. In an effort to formulate practical solutions, in this paper we ask: Are there structural network measures that are indicative of the best blockers in dynamic social networks? Our contribution is two-fold. First, we extend standard structural network measures to dynamic networks. Second, we compare the blocking ability of individuals in the order of ranking by the new dynamic measures. We found that overall, simple ranking according to a node’s static degree, or the dynamic version of a node’s degree, performed consistently well. Surprisingly the dynamic clustering coefficient seems to be a good indicator, while its static version performs worse than the random ranking. This provides simple practical and locally computable algorithms for identifying key blockers in a network.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adibi, J.: Enron email dataset, http://www.isi.edu/~adibi/Enron/Enron.htm
Anderson, R.M., May, R.M.: Infectious Diseases of Humans: Dynamics and Control. Oxford University Press, Oxford (1992)
Anthonisse, J.: The rush in a graph. Mathematische Centrum, Amsterdam (1971)
Aspnes, J., Chang, K., Yampolskiy, A.: Inoculation strategies for victims of viruses and the sum-of-squares partition problem. J. Comput. Syst. Sci. 72(6), 1077–1093 (2006)
Asur, S., Parthasarathy, S., Ucar, D.: An event-based framework of characterizing the evolutionary behavior of interaction graphs. In: Proceedings of the Thirteenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2007)
Barabasi, A.L., Jeong, H., Neda, Z., Ravasz, E., Schubert, A., Vicsek, T.: Evolution of the social network of scientific collaborations. Physica A: Statistical Mechanics and its Applications 311(3-4), 590–614 (2002)
Berger, E.: Dynamic monopolies of constant size. J. Combin. Theory Series B 83, 191–200 (2001)
Berger, N., Borgs, C., Chayes, J.T., Saberi, A.: On the spread of viruses on the internet. In: SODA 2005: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 301–310. Society for Industrial and Applied Mathematics (2005)
Berger-Wolf, T., Hart, W., Saia, J.: Discrete sensor placement problems in distribution networks. Mathematical and Computer Modelling (2005)
Berry, J., Fleischer, L., Hart, W., Phillips, C., Watson, J.: Sensor placement in municipal water networks. Journal of Water Resources Planning and Management 131(3) (2005a)
Berry, J., Hart, W., Phillips, C., Uber, J.G., Watson, J.: Sensor placement in municipal water networks with temporal integer programming models. Journal of Water Resources Planning and Management 132(4), 218–224 (2006)
Börner, K., Dall’Asta, L., Ke, W., Vespignani, A.: Studying the emerging global brain: Analyzing and visualizing the impact of co-authorship teams. Complexity, Special issue on Understanding Complex Systems 10(4), 57–67 (2005)
Börner, K., Maru, J., Goldstone, R.: The simultaneous evolution of author and paper networks. PNAS 101(suppl. 1), 5266–5273 (2004)
Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. In: WWW7: Proceedings of the 7th International Conference on World Wide Web 7, pp. 107–117. Elsevier Science Publishers B. V., Amsterdam (1998)
Broido, A., Claffy, K.: Internet topology: connectivity of IP graphs. In: Proceedings of SPIE ITCom (2001)
Carley, K.: Communicating new ideas: The potential impact of information and telecommunication technology. Technology in Society 18(2), 219–230 (1996)
Carreras, I., Miorandi, D., Canright, G., Engøo-Monsen, K.: Eigenvector centrality in highly partitioned mobile networks: Principles and applications. Studies in Computational Intelligence (SCI) 69, 123–145 (2007)
Chen, L., Carley, K.: The impact of social networks in the propagation of computer viruses and countermeasures. IEEE Trasactions on Systems, Man and Cybernetics (forthcoming)
Chen, N.: On the approximability of influence in social networks. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1029–1037 (2008)
Clauset, A., Eagle, N.: Persistence and periodicity in a dynamic proximity network (unpublished manuscript)
Cohen, R., Havlin, S., ben Avraham, D.: Efficient immunization strategies for computer networks and populations. Physical Review Letters (2003)
Dezsö, Z., Barabási, A.-L.: Halting viruses in scale-free networks. Physical Review E 65(055103(R)) (2002)
Domingos, P.: Mining social networks for viral marketing. IEEE Intelligent Systems 20, 80–82 (2005)
Domingos, P., Richardson, M.: Mining the network value of customers. In: Seventh International Conference on Knowledge Discovery and Data Mining (2001)
Eagle, N., Pentland, A.: Reality mining: Sensing complex social systems. Journal of Personal and Ubiquitous Computing (2006)
Eubank, S., Guclu, H., Kumar, V., Marathe, M., Srinivasan, A., Toroczkai, Z., Wang, N.: Modelling disease outbreaks in realistic urban social networks. Nature 429, 180–184 (2004) (supplement material)
Fagin, R., Kumar, R., Sivakumar, D.: Comparing top k lists. In: SODA 2003: Proc., 14th ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 28–36. Society for Industrial and Applied Mathematics (2003)
Feige, U., Mirrokni, V., Vondrák.: Maximizing non-monotone submodular functions. In: Foundations of Computer Science, FOCS (2007)
Fischhoff, I.R., Sundaresan, S.R., Cordingley, J., Larkin, H.M., Sellier, M.-J., Rubenstein, D.I.: Social relationships and reproductive state influence leadership roles in movements of plains zebra (Equus burchellii). Animal Behaviour 73(5), 825–831 (2007)
Fischhoff, I.R., Sundaresan, S.R., Cordingley, J., Rubenstein, D.I.: Habitat use and movements of plains zebra (Equus burchelli) in response to predation danger from lions. Behavioral Ecology 18(4), 725–729 (2007)
Freeman, L.: A set of measures of centrality based on betweenness. Sociometry 40, 35–41 (1977)
Freeman, L.C.: Centrality in social networks: I. conceptual clarification. Social Networks 1, 215–239 (1979)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99, 8271–8276 (2002)
Goldenberg, J., Libai, B., Muller, E.: Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters 12(3), 211–223 (2001)
Goldenberg, J., Libai, B., Muller, E.: Using complex systems analysis to advance marketing theory development. Academy of Marketing Science Review (2001)
Granovetter, M.: The strength of weak ties. American J. Sociology 78(6), 1360–1380 (1973)
Granovetter, M.: Threshold models of collective behavior. American J. Sociology 83(6), 1420–1443 (1978)
Gruhl, D., Guha, R., Liben-Nowell, D., Tomkins, A.: Information diffusion through blogspace. In: WWW 2004: Proc. 13th Intl Conf on World Wide Web, pp. 491–501. ACM Press, New York (2004)
Habiba, C.T., Berger-Wolf, T.Y.: Betweenness centrality in dynamic networks. Technical Report 2007-19, DIMACS (2007)
Holme, P.: Efficient local strategies for vaccination and network attack. Europhys. Lett. 68(6), 908–914 (2004)
Hopcroft, J., Khan, O., Kulis, B., Selman, B.: Natural communities in large linked networks. In: Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, pp. 541–546 (2003)
Jordán, F., Benedek, J., Podani, Z.: Quantifying positional importance in food webs: A comparison of centrality indices. Ecological Modelling 205, 270–275 (2007)
Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820–842 (2002)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining (2003)
Klimt, B., Yang, Y.: The enron corpus: A new dataset for email classification research. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) ECML 2004. LNCS (LNAI), vol. 3201, pp. 217–226. Springer, Heidelberg (2004)
Leskovec, J., Adamic, L.A., Huberman, B.A.: The dynamics of viral marketing. In: EC 2006: Proceedings of the 7th ACM conference on Electronic commerce, pp. 228–237. ACM Press, New York (2006)
Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J.: Cost-effective outbreak detection in networks. In: Proc. 13th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining (2007)
Lewin, K.: Principles of Topological Psychology. McGraw Hill, New York (1936)
Ley, M.: Digital bibliography & library project (DBLP) (December 2005); A digital copy of the databse has been provided by the author, http://dblp.uni-trier.de/
Liljeros, F., Edling, C., Amaral, L.N.: Sexual networks: Implication for the transmission of sexually transmitted infection. Microbes and Infection (2003)
May, R.M., Lloyd, A.L.: Infection dynamics on scale-free networks. Physical Review E 64(066112) (2001)
Moody, J.: The importance of relationship timing for diffusion. Social Forces (2002)
Moreno, Y., Nekovee, M., Pacheco, A.F.: Dynamics of rumor spreading in complex networks. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics) 69(6), 066130 (2004)
Morris, M.: Epidemiology and social networks:modeling structured diffusion. Sociological Methods and Research 22(1), 99–126 (1993)
Mossel, E., Roch, S.: On the submodularity of influence in social networks. In: The Annual ACM Symposium on Theory of Computing(STOC) (2007)
Newman, M.: The structure and function of complex networks. SIAM Review 45, 167–256 (2003)
Newman, M.E.: Spread of epidemic disease on networks. Physical Review E 66(016128) (2002)
Newman, M.E.J.: Scientific collaboration networks. i. network construction and fundamental results. Physical Review E 64, 016131 (2001)
Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86(14), 3200–3203 (2001)
Rogers, E.M.: Diffusion of Innovations, 5th edn. Simon & Shuster, Inc., New York (2003)
Rubenstein, D.I., Sundaresan, S., Fischhoff, I., Saltz, D.: Social networks in wild asses: Comparing patterns and processes among populations. In: Stubbe, A., Kaczensky, P., Samjaa, R., Wesche, K., Stubbe, M. (eds.) Exploration into the Biological Resources of Mongolia, vol. 10, pp. 159–176. Martin-Luther-University, Halle-Wittenberg (2007)
Sabidussi, G.: The centrality index of a graph. Psychometrika 31, 581–603 (1966)
Sundaresan, S.R., Fischhoff, I.R., Dushoff, J., Rubenstein, D.I.: Network metrics reveal differences in social organization between two fission-fusion species, Grevy’s zebra and onager. Oecologia 151, 140–149 (2007)
Vredeveld, T., Lenstra, J.: On local search for the generalized graph coloring problem. Operations Research Letters 31, 28–34 (2003)
Watts, D.: A simple model of global cascades on random networks. PNAS 99, 5766–5771 (2002)
Watts, D., Strogatz, S.: Collective dynamics of small-world networks. Nature 393, 440–442 (1998)
Young, H.P.: Innovation diffusion and population heterogeneity, Working paper (2006)
Zanette, D.H.: Dynamics of rumor propagation on small-world networks. Phys. Rev. E 65(4), 041908 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Habiba, Yu, Y., Berger-Wolf, T.Y., Saia, J. (2010). Finding Spread Blockers in Dynamic Networks. In: Giles, L., Smith, M., Yen, J., Zhang, H. (eds) Advances in Social Network Mining and Analysis. SNAKDD 2008. Lecture Notes in Computer Science, vol 5498. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14929-0_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-14929-0_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14928-3
Online ISBN: 978-3-642-14929-0
eBook Packages: Computer ScienceComputer Science (R0)