|
Items in cart [0] |
Questions? Call 888-624-8373 |
| Copyright © 2009. 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 188
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 sel£similar; "bursts" occur
188
DYNAMIC SOCIAL N~TWORKMODE~WG ED ISIS
OCR for page 189
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 networks—e.g.,
where known correlations between individuals are included where the measured
DYNAMIC SOCKS NETWO~MODEL~G kD TRYSTS
189
OCR for page 190
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 networks—e.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 191
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 networks—the 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 192
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 193
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 194
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
Representative terms from entire chapter:
threatened networks
