Cover Image


View/Hide Left Panel
Click for next page ( 188

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement

Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page 187
Social Networks: Mom Sexual Networks to Threatened Networks H. Eugene Stanley and Shlomo Havlin2 Center for Polymer Studies and Department of Physics Boston University, Boston, VIA 02215, USA 2 Minerva Center and Department of Physics Bar-Ilan University, Reman Gan, Israel Abstract. Our scientific goal is to uncover common principles governing the behavior of a range of social networks. Our practical goal is to use this understanding to den velop specific strategies to destroy threat networks and, in parallel, to develop specific strategies to defend threatened social networks against attack. There are recent hints that progress toward achieving both goals can be achieved applying new approaches Tom modern statisticad physics to social network structure and dynamics. ~ Introduction Populations, which can be viewed as networks of social acquaintances, are vul- nerable to disease epidemics such as AIDS. Any random immunization of people against such disease attacks is problematic because it must encompass almost the entire population ~ order to successfully stop the spreading epidemic [1- 54. Other types of social networks are organizations, e.g., security agencies, in which working relations are represented by links. To be effective, these organi- zations must be stable and allow rapid data flow in the network. We have begun addressing these problems using concepts and tools of both social sciences and statistical and nonlinear physics by designing more stable social network structures, enabling them to resist both random and intentional attacks. For this purpose, we need to better understand the topological structures of existing social networks, and to improve our understanding of transport In such systems. Our methods in statistical physics are based on relatively new concepts, such as correlated site-bond percolation theory t~10~. The applications of percola- tion theory range from predicting the amount of oil that can be extracted from an underground reservoir, to understanding the network formation mechanism involved in the hardening of a boiled egg. The use of percolation theory has already proven valuable in the study of social networks. The Bar-Ilan group has generalized percolation theory in order to analyze the structure and stability of general networks under random failures t11] and intentional attacks t12~. Based on this generalization, we ace following up on a novel approach for designing new social networks that are more resilient to attack. We are also developing methods based on the percolation approach :13] that will enable us to immunize populations more effectively against different types of epidemics. DYNAMIC SOCIAL fJ~TWO~ MODELING ~D TRYSTS 187

OCR for page 187
2 H. Eugene Stanley and Shlomo Havlin 2 Recent Advances on Scal - free Social Networks Very recent analysis of social networks, as well as many other networks (such as trust networks and sexual networks), reveals that some of these networks display the important property of being scal~free [6,2,14], i.e., there is a very wide distribution of the number of links per vertex. Most vertices have a small number of connections. However, there are a small number of vertices that have a very large number of connections, and there are vertices in the full range between these extremes. Further, it seems that there is a possible explanation for this scale-free behavior t2,15], and that the results for sexual networks extend to other social networks [16~. Our groups are studying the structure of a wide range of social network types t17], and are building mathematical models and tools for large social networks t13~. :~ studies conducted about the stability of scale-free social networks, it was proven that these networks are optimally resilient to the random failure of individuals t113. Even if almost all elements of a network malfunction, a large fraction of the individuals will be left connected, allowing continuing interac- tions between a large fraction of the population. This situation is unlike that of homogeneous networks, in which such a failure will break the entire network into small, unconnected islands. On the other hand, a deliberate, successful attack on the most-connected elements in the network will lead to failure of the entire network after only a small fraction of nodes have been targeted [12~. Further, studies show that search can be conducted In such heterogeneous networks in a much more efficient way than in homogeneous networks [18~. A connection exists between (a) the stability of a network and (b) the prom agation of disease. Heterogeneous networks are prone to the rapid spread of epidemics. If the individuals to be immunized are chosen randomly, spreading is unavoidable, even if almost all individuals in the network are immunized. How- ever, if the individuals to be irmnunized are chosen using "smart" strategies, it becomes possible to reduce the number of infected individuals to almost zero. Using models, it is possible to forecast the consequences of epidemic outbursts and to try to control them. It is established that random immunization of a large fraction of the population fails to prevent epidemics of diseases that spread upon contact between infected individuals; for example, Malaria requires 99% of the population to be immunized in order to stop epidemic spreading [4,54. On the other hand, targeted immunization of the most-connected individuals requires global knowledge of the topology of the social network in question, rendering 99% immunization impractical. We recently proposed an effective strategy, based on the immunization of a small fraction of acquaintances of randomly-selected indi- viduals, that prevents epidemics without requiring global knowledge of the social network [194. 3 Recent Advances on Marc Flow in Networks We are adapting recent results on traffic flow to social network analysis. In 1994, Leland et al. t20] found that Ethernet LAN tragic is selsimilar; "bursts" occur 188 DYNAMIC SOCIAL N~TWORKMODE~WG ED ISIS

OCR for page 187
From Sexual Networks to Threatened Networks 3 on every time scale. These findings show that long-range correlations in the interval times of arriving packets and extreme variability (or infinite limit of the variance). Paxson and Floyd t21] have found evidence for self-similarity of Wide Area Network (WAN) Traffic, and showed the failure of Poisson modeling in this case. New empirical Endings challenge the validity of the traditional queuing models, and new models have since been proposed. In contrast to the above measurements, Takayasu et al. t22-24] have measured a 1/f power spectrum only at the critical point of a phase transition, and it is still not clear whether the flow is always self-similar in such networks. They found finite correlation times in the fluctuations of network traffic, and identified phase transitions between "sparse" and "Jason" phases of the network. The empirical phenomena mentioned above can influence the design of con- trol schemes for traffic. However, the empirical description of the traffic is not yet complete. As the Bar-Ilan group has demonstrated recently in the case of ve- hicular traffic [25], a careful nonlinear statistical analysis of measured data may lead to the finding of several congested phases. One of our goals is to clarify this issue, and one method that we will use in the analysis of measured time series is Detrended Fluctuation Analysis (DFA). DFA was developed by the Boston group [26] and has been successfully applied by us and others to many systems, e.g., to UNA sequences [27,28], the analysis of climate changes [29,30], heart rate variability [31-34], economics [35], and even prime numbers [36~. One of the advantages of this method is its ability to detect long-rage correlations in the records in the presence of trends and other nonstationarities. 4 Characteristic Properies of Real Networks 4.1 Classification of Real Networks We have developed a method that classifies complex real-world networks accord- ing to their statistical topological properties [17~. By studying a wide range of different types of networks, we find evidence for the occurrence of three classes of small-world networks: (a) scale-free networks, (b) broad-scale networks, characterized by a connectivity distribution that has a power-law regime followed by a sharp cut-off; (c) single-scale networks, characterized by a connectivity distribution with a fast-decaying tail. 4.2 Percolation A percolation approach for general networks has been developed, with surpris- ing results for scale-free networks [11-13~. The network is fully resilient to the random failure of sites and is extremely vulnerable to intentional attack. This analytical approach is being developed to study realistic social networkse.g., where known correlations between individuals are included where the measured DYNAMIC SOCKS NETWO~MODEL~G kD TRYSTS 189

OCR for page 187
4 H. Eugene Stanley and Shlomo Havlin ) clustering property and real geographical distance, measured experimentally, are being taken into account. Preliminary findings show that the geographical eject has a strong influence on the stability and transport of the network [37-393. 4.3 Structural Id Transport Properties of Networks We are studying several topological properties of networkse.g., clustering and correlations. Some preliminary results already exist, such as the work on clus- tering in trust networks [40~. The clustering coefficient [41,42], which quantifies the extent to which nodes adjacent to a given node are linked, seems not to be affected when the network collapses. This may be relevant to terrorist organi- zations that are comprised of small, strongly-connected cells that are connected to each other by a few, highly-connected individuals [43~. The clustering was foiled to be important also ire electric power networks, e.g., the power grid in the Western States in which the clustering coefficient is significantly larger than that of random networks. A useful method to quantify correlations (by measur- ing assortative tendencies, i.e., the tendency of high-degree vertices to associate preferentially with other high-degree vertices) was suggested recently by New- man [443. We have preliminary results extending these studies to other real social net- works. We are also studying the degree distribution for sites at a given distance from the most-connected site [45~. We are also studying the effect of geograph- ical distance in real networks. This information is important for evaluating the stability and the immunization threshold. We are also analyzing the transport properties of data flow in social networks. We are applying DFA analysis And multiLractal analysis [46] to better understand trim sport in complex social net- works. We also are developing structural and transport modeling that will enable a better understanding of the structure and transport in such networks. 4.4 Optimizing the Stability of Threatened Networks We are using the analytical approach we developed to calculate the percolation threshold for a given network t11,12], in order to design topologies that improve the stability of scale-free networks under both random failures and intentional attacks. This is being done by calculating the percolation threshold while keeping the average number of links for an individual in the network constant (for safety and security reasons) and then varying parameters such as the form of the degree distribution, the type of correlations, and the clustering coefficients. We are also testing the effect of geographical distances on the stability of scale free networks. This will enable us to propose ways to design more stable networks and to improve the stability of existing networks. 4.5 Immunization of Networks Random immunization fails to prevent epidemics of diseases that spread in pow ulations upon contact between infected individuals t4,5], the same is true for . . 190 DYNAMIC SOCL4L NT:TWORKMODEL~G kD ^^YSIS

OCR for page 187
From Sexual Networks to Threatened Networks 5 immunization of computers against nruses [474. Unless almost the entire system is immunized, the virus continues to spread through the population or computer network. To deal with this problem, the Bar-Ilan group has developed an analyt- ical method that can accurately determine, for various scenarios, the threshold needed to stop spreading epidemics t133. Among these possible scenarios are (i) immunizing people who are acquaintances of an infected individual and (ii) immunizing only those people who ace acquaintances of at least two infected individuals. Our recent results on social networks are complemented by analogous strate- gies for protecting other threatened networks, such as communication networks. For example, the Bar-IlaD group has already demonstrated that, in scale-free uncorrelated networks, if we immunize the neighbors of randomly-chosen sites, the critical threshold can be reduced by a factor of five t194. This result has dramatic practical implications. Our analytical approach is enabling us to study efficient immunization strate- gies in more realistic networks where, e.g., correlations, clustering effects, and geographical topology are taken into account. The immU:iization approach is also helping to develop methods to disintegrate targeted organizations, since by removing the nodes that are most relevant for immunity, the targeted network will collapse. 5 Possible Contributions of Social Network Research (a) We are improving the tentative explanation [15] of scale-free social networks, and develop a better understanding of the range of social networks that are scale-free 16. (b) We are developing a better understanding of the topological structures and the tomography of threatened social networks. (c) We are developing new algorithms to improve the stability and safety of threatened networks. We are designing networks for optimal resistance to epidemics, malfunctions and attacks, and we are designing efficient and se- cure algorithms for organizational data flow. (d) We are designing efficient methods for effective "immunization" that will greatly reduce spreading in threatened networksthe same mathematics describes spread of infectious agents in social networks, or '~ruses" in com- munication networks. These methods will also help to identity weaknesses and thereby protect threatened networks. 6 Discussion We are seeking to test whether concepts and methods of statistical physics such as scaling and percolation theory can be usefully applied to social networks, with special emphasis on social networks such as sexual networks and threatened networks. Many of the primary methods being used in our network research have been developed by our research group. These include the analytical percolation DYNAMIC SOCIAL NETWORK AJODE~WG ED TRYSTS 191

OCR for page 187
6 H. Eugene Stanley and Shlomo Havlin approach to general networks t11-13], the efficient immunization theory [19,13], and the DFA method [263. We also were among the first to identify seal - free networks in certain social systems Id sexual networks [14-16], and we developed an approach for classifying network topologies t173. Acknowledgments We thank Y. berg, L. A. N. Amoral, C. Edling, K. Fukuda, and F. Liljeros for collaborations on which a part of this paper is based, and ONR N00014 02 1 1033 for support. References 1. R. Albert, H. Jeong Id A.-L Barabasi, "Attack and Error Tolerance of Complex Networks," Nature 406, 378~382 (2000~. 2. R. Albert and A.-L. Barabasi, UStatistical Mechanics of Complex Networks," Rev. Mod. Phys. 74, 47-97 (2002). 3. S. N. Dorogovtsev and J. F. F. Mendes, "Evolution of Networks," Adv. in Phys. 51, 10701187 (2002). 4. R. M. Anderson, and R. M. May, Infections Diseases of Humans (Oxford University Press, Oxford, 1991~. 5. A. L. Lloyd and R. M. May, Chow Viruses Spread among Computers and People, Science 292, 131~1317 (2001). 6. H. E. Stanley, Escaping, Universality, and Renormalization: Three Pillars of Modern Critical Phenomena," Reviews of Modern Physics 71, S358-S366 (1999~. 7. A.-L. Bazabasi, Linked: The New Science of Networks (Perseus Publishing, C~m- bridge, 2002). 8. H. E. Stanley, J. S. Andrade, S. Havlin et al., Percolation Phenomena: A Broad- Brush Introduction with Some Recent Applications to Porous Media, Liquid Water, and City Growth," Physica A 266, 5-16 (1999~. 9. A. Bunde and S. Havlin, eds., Factors and Disordered Systems (Springer, New York, 19963. 10. D. ben-Avrah~m and S. Havlin, Diffusion and Reactions in Factors arid Disordered Systems (Cambridge University Press, Cambridge, 20003. 11. R. Cohen, K. Erez, D. ben-Avraham, and S. Hairline Resilience of the Internet to Random Breakdown," Phys. Rev. Lett. 85, 4626 (2000). 12. R. Cohen, K. Erez, D. ben-A~rraham, and S. Harelip, Breakdown oftheInternet under Intentional Attack," Phys. Rear. Lett. 86, 3682 (2001). 13. R. Cohen, S. Havlin, and D. ben-Ayrah~m, "Structural Properties of Scale-Fiee Networks" in Handbook of Graphs and Networks: From the Genome to the Internet, edited by S. Bornholdt and H. G. Schuster (Wiley-VCH, Berlin, in press, 20023. 14. F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, and Y. ~berg, "The Web of Human Sexual Contacts," Nature 411, 907-908 (2001) cond-mat/0106507. 15. L. A. N. Amaral, C. R. Edlillg, F. Liljeros, and H. E. Stanley, ~Mechanisrns for the Formation of a Web of Sexual Contacts" (preprint). 16. F. Liljeros, L. A. N. Amaral7 and H. E. Stanley, "Scal+In~rariance in the Growth of Voluntary Organizations," Europhys. Lett. (submitted). 192 DYNAMIC SOCIAL N~TWORKAdODE:LING AND ANALYSIS

OCR for page 187
From Sexual Networks to Threatened Networks 7 17. L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley, Classes of Behavior of Small-World Networks," Proc. National Academy of Sciences 97, 11149-11152 (2000~. 18. L. A. Anemic, R. M. Lukose, A. R. Punyani, and B. A. Huberman, "Search in Power Law Networks," Phys. Rev. E 64, 046135 (2001~. 19. R. Cohen, D. ben-Avraham, and S. Havlin, prescient Immunization of Populations and Computers," cond-mat/0207387 (2002~. 20. W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson, ton the Self-Similar Nature of Ethernet Marc (Extended Version)," IEEE/ACM liens. Netw. 2, 1 (1994~. 21 or ~ ~ fat ~~ ~ {ACT?- ~ ~ ~ # 22. 23. v. raxson and 5. Floyd, "Wide Area triadic: The failure of Poisson Modeling," IEEE/ACM liars. Netw. 3, 226 (1995~. K. Fukuda, H. Tal~yasu, and M. Takayasu, "Spatial and Temporal Behavior of Congestion in Internet Traffic," Ffactals 7, 23 (1999~. M. Takayasu, H. Takayasu, and K. Fukoda, "Dynamic Phase Transition Observed in Internet Traffic Flow," Physica A 277, 248 (2000~. 24. M. Takayasu, H. I~kayasu, and K. Fukuda, "Application of Statistical Physics to Internet Traffic," Physica A 274, 140 (1999~. 25. E. Tomer, L. Safonov, and S. Havlin, Presence of Many Stable Nonhomogeneous States in an Inertial Car-Following Models Phys. Rear. Lett. 84, 382 (2000~. 26. C. K. Peng, S. Havlm, H. E. Stanley, and A. L. Goldberger, Quantification of Scaling Exponents and Crossover Phenomena in Nonstationary Heartbeat Time Series" [P~oc. NATO Dynamacai Disease Conference], edited by L. Glass, Chaos 5, 82-87 (1995). 27. C.-K. Peng, S. V. Buldyrev, S. Havlin, M. Simons, H. E. Stanley, and A. L. Gold- berger, Con the Mosaic Organization of DNA Sequences, Phys. Rev. E 49 (1994) 1691-1695. 28. S. V. Buldyrev, A. L. Goldberger, S. Havlin, R. N. Mantegna, M. E. Matsa, C.- K. Peng, M. Simons, and H. E. Stanley, Long-Range Correlation Properties of Coding and Noncoding DNA Sequences: GenBank Analysis" Phys. Rev. E 51, 5084-5091 (1995). 29. A. Bunde, H. J. Schellnhuber, and J. Kropp, eds., The Science of Disasters: Climate Disruptions, Heart Attacks, and Market Crashes (Springer-Verlag, Berlin, 2002~. 30. R. B. Govindan, D. Vyushin, A. Bunde, S. Brenner, S. Havlin, and H. J. SchellaLu- ber, "Global Climate Models Violate Scaling of the Observed Atmospheric Vari- ability,n Phys. Rev. Lett. 89, 028501 (2002). 31. A. Bunde, S. HaYlin, J. W. Kantelhardt, T. Penzel, J. H. Peter, and K. Voigt, Collated and Unco~elated Regions in Heart-R^t.~ Flllrt~l~i~nc allying Amp Phys. Rev. Lett. 857 3736-3739 (2000). 32. J. W. Kantelhardt, E. Koscielny-Bunde, H.H.A. Rego, S. Havlin, and A. Budder Physica A 294, 441 (2001~. 33. K. Hu, Z. Chen, P. Ch. I~ov, P. Carpena, and H. E. Stanley, Deflect of Mends on Detrended Fluctuation Analysis" Phys. Rear. E 64, 01111~1 - 01111~19 (2001) physics/0103018. 34. Z. Chen, P. Ch. Ivanov, K. Hu, and H. E. Stanley, deflect of Nonstationarities on Detrended Fluctuation Analysis" Phys. Rev. E 65, 041107-1 to 041107-15 (2002~. physics/011 1 103. 35. Y. Liu, P. Gopikrishnan, P. Cizeau, M. Meyer, C.-K. Peng, and H. E. Stanley, The statistical properties of the volatility of price fluctuations Phys. Rev. 60, 139~1400 (1999~. ~ t, ~_ it, DYNAMIC SOCIAL NETWOR~MODEL~G ED ISIS 193

OCR for page 187
8 H. Eugene Stanley and Shlomo Havl~n 36. P. Human, P. Ch. I~ov, and H. E. Stanley, Statistical Physics and Prime Num- bers" (preprint). 37. A. F. Rozenfeld, R. Cohen, D. ben-A`rrah~m, and S. Havlm, Scale-Fee Networks on Lattices," Phys. Rev. Lett. xx, x- (2003) cond-mat/0205613. 38. R. Cohen and S. Havlin, "Ultra Small World in Scale-Fiee Networks, Phys. Rev. Lett. xx, xxx-xxx (2003) cond-mat/0205476 (2002~. 39. D. ben-Avrah~m, A. F. Rozenfeld, R. Cohen, and S. Havlin, Geographical Em- bedding of Scal - Ffee Networks," cond-mat/0301504 (2003~. 40. X. Guardiola et al., "Macros and Microstructure of Trust networks," cond- mat/020640 (2002~. 41. D. J. Watts and S. H. Strogatz, Collective Dynamics of 'Small-World' Networks," Nature 393, 440 442 (19983. 42. D. J. Watts, Small WorYds: Size Dynamics of ]\Jet?vorks between Order and Ran- domness (Princeton University Press, Princeton, 1999~. 43. V. E. Krebs, "Mapping Networlcs of Terrorist Cells,n Connections 24, 43-52 (2002~. 44. M. E. J. Newman, "Assortative Mixing ~ Networks," cond-mat/0205405 (2002~. 45. R. Cohen, D. Doler, S. Havlin, T. Kalisky, O. Mohryn, and Y. Shavitt, "On the Tomography of Networks and Multicart liees," Tech. Report TR 2002-49, Hebrew University, Israel. 46. P. Ch. I~ov, L. A. Nunes Amaral, A. L. Goldberger, S. Havlin, M. G. Rosenblum, Z. Struzik, and H. E. Stanley, "Multifractality in Human Heartbeat Dynamics," Nature 399, 461 (1999~. 47. R. Pastor-Sattoras and A. Vespign~-ni, Epidemic Dyan~mics and Endemic States in Compex Networks," Phys. Rev. E 63, 066117 (2001~. 194 DYNAMIC SOCIAL NETWORK MODELING ED ^^YSIS