Mạng lưới phức tạp

The European Physical Journal B - Tập 38 - Trang 147-162 - 2004
L. A. N. Amaral1, J. M. Ottino1
1Department of Chemical and Biological Engineering, Northwestern University, Evanston, USA

Tóm tắt

Chúng tôi mô tả ngắn gọn bộ công cụ được sử dụng để nghiên cứu các hệ thống phức tạp: động lực học phi tuyến, vật lý thống kê và lý thuyết mạng. Chúng tôi đặc biệt nhấn mạnh lý thuyết mạng - chủ đề của số đặc biệt này - và tầm quan trọng của nó trong việc tăng cường khung lý thuyết cho nghiên cứu định lượng các hệ thống phức tạp. Để minh họa các vấn đề chính, chúng tôi điểm qua một số lĩnh vực mà lý thuyết mạng đã dẫn đến những phát triển đáng kể trong sự hiểu biết của chúng ta về các hệ thống phức tạp. Cụ thể, chúng tôi thảo luận về những thay đổi, xuất phát từ lý thuyết mạng, trong sự hiểu biết của chúng ta về (i) Internet và các mạng lưới truyền thông khác, (ii) cấu trúc của các hệ sinh thái tự nhiên, (iii) sự lây lan của bệnh tật và thông tin, (iv) cấu trúc của các mạng lưới tín hiệu tế bào, và (v) độ bền vững của cơ sở hạ tầng. Cuối cùng, chúng tôi thảo luận về cách mà tính phức tạp yêu cầu cả công cụ mới và sự mở rộng của khung khái niệm - bao gồm một định nghĩa mở rộng về những gì được hiểu là một “dự đoán định lượng.”

Từ khóa

#lý thuyết mạng #hệ thống phức tạp #động lực học #vật lý thống kê #mạng lưới truyền thông #hệ sinh thái tự nhiên #bệnh tật và thông tin #tín hiệu tế bào #độ bền vững cơ sở hạ tầng

Tài liệu tham khảo

J.M. Ottino, AIChE J. 49, 292 (2003)

G.L. Baker, J.P. Gollub, Chaotic Dynamics: An Introduction (Cambridge University Press, Cambridge, UK, 1990)

L. Glass, M.C. MacKey, From Clocks to Chaos: The Rhythms of Life (Princeton University Press, Princeton, NJ, 1988)

J.M. Ottino, The Kinematics of Mixing: Stretching, Chaos, and Transport (Cambridge University Press, Cambridge, UK, 1989)

S. Wolfram, A New Kind of Science (Champaign, IL, Wolfram Media, 2002)

J.M. Epstein, R.L. Axtell, Growing Artificial Societies: Social Science from the Bottom Up (Cambridge, MA, MIT Press, 1996)

H.E. Stanley, Introduction to Phase Transitions and Critical Phenomena (Oxford University Press, Oxford, 1971)

H.E. Stanley, Rev. Mod. Phys. 71, S358-S364 (1999) [Special Issue for the Centennial of the American Physical Society]

C.-K. Peng, S. Havlin, H.E. Stanley, A.L. Goldberger, Chaos 5, 82 (1995)

P.Ch. Ivanov, L.A.N. Amaral, A.L. Goldberger et al. , Nature 399, 461 (1999)

L.A.N. Amaral, P.Ch. Ivanov, N. Aoyagi et al. , Phys. Rev. Lett. 86, 6026 (2001)

A.L. Goldberger, L.A.N. Amaral, J.M. Hausdorff et al. , Proc. Nat. Acad. Sci. USA 99 Supp. 1, 2466 (2002)

U.A. Muller, M.M. Dacorogna, R.B. Olsen et al. , J. Banking Fin. 14, 1189 (1990)

A. Pagan, J. Empirical Finance 3, 15 (1996)

P. Gopikrishnan, V. Plerou, L.A.N. Amaral et al. , Phys. Rev. E 60, 5305 (1999)

V. Plerou, P. Gopikrishnan, L.A.N. Amaral et al. , Phys. Rev. E 60, 6519 (1999)

M.H.R. Stanley, L.A.N. Amaral, S.V. Buldyrev et al. , Nature 379, 804 (1996)

L.A.N. Amaral, S.V. Buldyrev, S. Havlin et al. , J. Phys. I France 7, 621 (1997)

Y. Lee, L.A.N. Amaral, D. Canning et al. , Phys. Rev. Lett. 81, 3275 (1998)

L.A.N. Amaral, S.V. Buldyrev, S. Havlin et al. , Phys. Rev. Lett. 80, 1385 (1998)

V. Plerou, L.A.N. Amaral, P. Gopikrishnan et al. , Nature 400, 433 (1999)

L.A.N. Amaral, P. Gopikrishnan, K. Matia et al. , Scientometrics 51, 9 (2001)

H.E. Stanley, L.A.N. Amaral, S.V. Buldyrev et al. , Proc. Nat. Acad. Sci. USA 99 Supp. 1, 2561 (2002)

R. Jackiw, Phys. Today 25, 23 (1972)

P.J.E. Peebles, The Large-Scale Structure of the Universe (Princeton University Press, Princeton, NJ, 1980)

F. Liljeros, C.R. Edling, L.A.N. Amaral, Microbes Infect. 5, 189 (2003)

J.J. Binney, N.J. Dowrick, A.J. Fisher, M.E.J. Newman, The Theory of Critical Phenomena: An Introduction to the Renormalization Group (Oxford University Press, Oxford, 1992)

S. Ulam, in Proc. Int. Congress Math. 2, 264 (1950)

M. Gardner, Scientific American 223, 120 (1970)

D.J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness (Princeton University Press, Princeton, NJ, 1999)

M.E.J. Newman, J. Stat. Phys. 101, 819 (2000)

S.H. Strogatz, Nature 410, 268 (2001)

R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002)

S.N. Dorogovtsev, J.F.F. Mendes, Adv. Phys. 51, 1079 (2002)

S. Wasserman, K. Faust, Social Network Analysis (Cambridge University Press, Cambridge, UK, 1994)

A.F.J. van Raan, Nature 347, 626 (1990)

M.E.J. Newman, P. Natl. Acad. Sci. USA 98, 404 (2001)

F. Liljeros, C.R. Edling, L.A.N. Amaral et al. , Nature 411, 907 (2001)

E.M. Jin, M. Girvan, M.E.J. Newman, Phys. Rev. E 64, 046132 (2001)

M. Girvan, M.E.J. Newman, P. Natl. Acad. Sci. USA 99, 7821 (2002)

D.J. Watts, P.S. Dodds, M.E.J. Newman, Science 296, 1302 (2002)

H. Ebel, L.-I. Mielsch, S. Bornholdt, Phys. Rev. E 66, 035103(R) (2002)

R. Guimera, L. Danon, A. Diaz-Guilera, F. Giralt, A. Arenas, Self-similar community structure in organisations, arXiv:cond-mat/0211498

M. Faloutsos, P. Faloutsos, C. Faloutsos, ACM SIGCOMM ‘99, Comput. Commun. Rev. 29, 251 (1999)

R. Albert, H. Jeong, A.-L. Barabási, Nature 401, 130 (1999)

B.A. Huberman, L.A. Adamic, Nature 401, 131 (1999)

S.L. Pimm, J.H. Lawton, J.E. Cohen, Nature 350, 669 (1991)

R.T. Paine, Nature 355, 73 (1992)

J. Camacho, R. Guimerá, L.A.N. Amaral, Phys. Rev. E 65, 030901(R) (2002)

J. Camacho, R. Guimerá, L.A.N. Amaral, Phys. Rev. Lett. 88, 228102 (2002)

J.A. Dunne, R.J. Williams, N.D. Martinez, P. Natl. Acad. Sci. USA 99, 12917 (2002)

C. Koch, G. Laurent, Science 284, 96 (1999)

L.F. Lago-Fernandez, R. Huerta, F. Corbacho, J.A. Siguenza, Phys. Rev. Lett. 84, 2758 (2000)

U. Alon, M.G. Surette, N. Barkai, S. Leibler, Nature 397, 168 (1999)

R. Milo, S. Shen-Orr, S. Itzkovitz et al. , Science 298, 824 (2002)

Z.N. Oltvai, A.-L. Barabási, Science 298, 763 (2002)

H. Jeong, S.P. Mason, A.-L. Barabási, Z.N. Oltvai, Nature 411, 41 (2001)

A.C. Gavin et al. , Nature 415, 141 (2002)

Y. Ho et al. , Nature 415, 180 (2002)

H. Jeong, B. Tombor, R. Albert et al. , Nature 407, 651 (2000)

A. Wagner, D.A. Fell, P. Roy. Soc. London B-Biol. Sci. 268, 1803 (2001)

E. Ravasz, A.L. Somera, D.A. Mongru et al. , Science 297, 1551 (2002)

The Small World, edited by M. Kochen (Norwood, NJ, Ablex, 1989)

S. Milgram, Psychol. Today 1, 61 (1967)

J. Travers, S. Milgram, Sociometry 32, 425 (1969)

B. Bollobás, Random Graphs (London, Academic Press, 1985)

D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998)

M. Barthélemy, L.A.N. Amaral, Phys. Rev. Lett. 82, 3180 (1999)

A. Barrat, M. Weigt, Eur. Phys. J. B 13, 547 (2000)

A.-L. Barabási, R. Albert, Science 286, 509 (1999)

P.O. Seglen, J. Am. Soc. Inf. Sci. 43, 628 (1992)

S. Redner, Eur. Phys. J. B 4, 131 (1998)

R. Cohen, S. Havlin, Phys. Rev. Lett. 90, 058701 (2003)

L.A.N. Amaral, A. Scala, M. Barthélemy, H.E. Stanley, Proc. Nat. Acad. Sci. USA 97, 11149 (2000)

S. Mossa, M. Barthélemy, H.E. Stanley, L.A.N. Amaral, Phys. Rev. Lett. 88, 138701 (2002)

M.E.J. Newman, SIAM Rev. 45, 167 (2003)

S.N. Dorogovtsev, J.F.F. Mendes, Evolution of Networks: From Biological nets to the Internet and WWW (Oxford University Press, Oxford, 2003)

A. Tanenbaum, Computer Networks, 3rd edn. (Prentice Hall, Englewood Cliffs, 1996)

D. Comer, Internetworking with TCP/IP, Vol. 1, 4th edn. (Prentice Hall, Englewood Cliffs, 2000)

A. Bunde, J. Kropp, H.J. Schellnhuber, The Science of Disasters: Climate Disruptions, Heart Attacks, and Market Crashes (Springer-Verlag, Berlin, 2002)

Unsolved Problem on Noise 1999, edited by D. Abbott, L.B. Kish, AIP Conf. Proc. 511 (American Institute of Physics, Melville NY, 2000)

W.E. Leland, M.S. Taqqu, W. Willinger, D.V. Wilson, IEEE/ACM Trans. Network 2, 1 (1994)

V. Paxson, S. Floyd IEEE/ACM Trans. Network 3, 226 (1995)

M. Crovella, A. Bestavros, IEEE/ACM Trans. Network 5, 835 (1997)

I. Csabai, J. Phys. A 27, 417 (1994)

M. Takayasu, H. Takayasu, T. Sato, Physica A 233, 924 (1996)

M. Takayasu et al. , Physica A 277, 248 (2000)

K. Fukuda et al. , Physica A 287, 289 (2000)

K. Fukuda et al. , in Traffic and Granular Flow 2001, edited by Y. Sugiyama et al. (Springer, Heidelberg, 2002)

P. Bernaola-Glaván, P.Ch. Ivanov, L.A.N. Amaral, H.E. Stanley, Phys. Rev. Lett. 87, 168105 (2001)

K. Fukuda, L.A.N. Amaral, H.E. Stanley, Europhys. Lett. 62, 189 (2003)

K.A. Eriksen, I. Simonsen, S. Maslov, K. Sneppen, Phys. Rev. Lett. 90, 148701 (2003)

M. Barthélémy, B. Gondran, E. Guichard, Physica A 319, 633 (2003)

J.-J. Pansiot, D. Grad, ACM Comp. Comm. Rev. 28, 41 (1998)

R. Govindan, A. Reddy, in Proceedings of IEEE INFOCOM’97 (1997), p. 850

H. Chou, A note on power-laws on Internet topology, arXiv:cs.NI/0012019 (2000)

G. Caldarelli, R. Marchetti, L. Pietronero, Europhys. Lett. 52, 386 (2000)

S.-H. Yook, H. Jeong, A.-L. Barabási, Proc. Nat. Ac. Sci. USA 99, 13382 (2002)

The National Laboratory for Applied Network Research (NLANR), sponsored by the National Science Foundation, provides Internet routing related information based on border gateway protocol data (see http://moat.nlanr.net/)

R. Pastor-Satorras, A. Vázquez, A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001)

A. Vázquez, R. Pastor-Satorras, A. Vespignani Phys. Rev. E 65, 066130 (2002)

D. Garlaschelli, G. Caldarelli, L. Pietronero, Nature 423, 165 (2003)

R.M. Anderson, R.M. May, Infectious Diseases in Humans (Oxford University Press, Oxford, 1992)

R. Pastor-Satorras, A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001)

R. Pastor-Satorras, A, Vespignani, Phys. Rev. E 65, 036104 (2002)

D.J. Watts, Proc. Nat. Ac. Sci. USA 99, 5766 (2002)

R. Cohen, S. Havlin, D. ben-Avraham, Efficient Immunization Strategies for Computer Networks and Populations, arXiv:cond-mat/0207387

Z. Dezso, A.-L. Barabási, Phys. Rev. E 65, 055103 (2002)

V.M. Egu\’iluz, K. Klemm, Phys. Rev. Lett. 89, 108701 (2002)

A. Vazquez et al. , Phys. Rev. E 67, 046111 (2003)

L.S. Liebovitch, I.B. Schwartz, Phys. Rev. E 68, 017101 (2003)

M.E.J. Newman, S. Forrest, J. Balthrop, Phys. Rev. E 66, 035101 (2002)

B. Vogelstein, D. Lane, A.J. Levine, Nature 408, 307 (2000)

R. Albert, H. Jeong, A.-L. Barábasi, Nature 406, 378 (2000)

A. Broder et al. , Computer Networks 33, 309 (2000)

R. Cohen, K. Erez, D. Ben-Avrham, S. Havlin, Phys. Rev. Lett. 85, 4626 (2000)

D.S. Callaway, M.E.J. Newman, S.H. Strogatz, D.J. Watts, Phys. Rev. Lett. 85, 5468 (2000)

R. Cohen, K. Erez, D. Ben-Avrham, S. Havlin, Phys. Rev. Lett. 86, 3682 (2001)

P. Holme, B.J. Kim, Phys. Rev. E 65, 066109 (2002)

P. Holme, Phys. Rev. E 66, 036119 (2002)

T. McMahon, Science 179, 1201 (1973)

G.B. West, J.H. Brown, B.J. Enquist, Science 276, 122 (1997)

J.R. Banavar, A. Maritan, A. Rinaldo, Nature 399, 130 (1999)

L.P. Kadanoff, Physics Today 54, 34 (2001)

J.M. Ottino, Nature 427, 399 (2004)