CoChat
Sign Up
Cited by 18,719Complex Network Analysis TechniquesComplex Systems and Time Series AnalysisGraph theory and applications

The Structure and Function of Complex Networks

Open access
Newman, M. E. J.·2003·SIAM Review
DOI 10.1137/s003614450342480
Open this paper in CoChat — free accountOpen PDF

Abstract

Abstract. Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1137/s003614450342480

Cites

17 of 17 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The distribution of degrees of vertices in a random network generally follows the Poisson distribution.

    “The distribution of degrees of vertices in a complex network and a random network generally follows the power-law distribution and Poisson distribution, respectively (Barabási and Albert, 1999; Newman, 2003, 2010).”

    From Syntactic Networks of Interlanguage Across L2 Modalities and Proficiency Levels (2021) · cites this paper as Newman, 2003

    In “Degree distributions” (p. 12), Newman says the Erdős–Rényi random graph has a binomial degree distribution that becomes Poisson in the large-graph limit. “Random graphs” (p. 20) also describes random-graph models with other degree distributions. The claim is supported for the standard large-graph model, but not for random networks generally. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • The distribution of degrees of vertices in a complex network generally follows the power-law distribution.

    “The distribution of degrees of vertices in a complex network and a random network generally follows the power-law distribution and Poisson distribution, respectively (Barabási and Albert, 1999; Newman, 2003, 2010).”

    From Syntactic Networks of Interlanguage Across L2 Modalities and Proficiency Levels (2021) · cites this paper as Newman, 2003

    The Degree distributions section (p. 13) says many networks have power-law tails, but some have exponential tails. The Scale-free networks section (pp. 13–14) also describes exponential and truncated power-law degree distributions. Thus the paper supports power laws as common in complex networks, not as their general degree-distribution form. (LLM, conf=0.87)

    Experimental — accuracy not yet measured

  • Several models based on mechanisms such as preferential attachment, fitness, or constrained random wiring were developed to reproduce degree distributions commonly observed in empirical systems.

    “Several models, based on mechanisms like preferential attachment 15 , fi tness 94 , or constrained random wiring 54 , to mention some of them, were developed to reproduce degree distributions commonly observed in empirical systems.”

    From Complex networks from classical to quantum (2019) · cites this paper as [54]

  • Other risks from rewiring include 'phase transitions', where a gradual change in individual connections or network structure triggers a sudden and dramatic shift in the behaviour of the entire network.

    “Other risks from rewiring include 'phase transitions', where a gradual change in individual connections or network structure triggers a sudden and dramatic shift in the behaviour of the entire network (Newman, 2003, see also Section 3.4).”

    From Multi-Agent Risks from Advanced AI (2025) · cites this paper as Newman, 2003

  • SNA makes it possible to understand and highlight interactions and knowledge flows between actors.

    “SNA makes it possible to understand and highlight interactions and knowledge flows between actors (Chaudhury et al. 2017;Isaac 2012;Newman 2003).”

    From Scenarios for an agroecological transition of smallholder family farmers: a case study in Guadeloupe (2022) · cites this paper as Newman 2003

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 166

  1. [2][2] Adamic, L. A., The small world web, in Lecture Notes in Computer Science , vol. 1696, pp. 443-454, Springer, New York (1999). -
  2. [3][3] Adamic, L. A. and Adar, E., Friends and neighbors on the Web, Social Networks (in press). -
  3. [5][5] Adamic, L. A., Lukose, R. M., and Huberman, B. A., Local search in unstructured networks, in S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs and Networks , Wiley VCH, Berlin (2003). -
  4. [7][7] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B., Network Flows: Theory, Algorithms, and Applications , Prentice Hall, Upper Saddle River, New Jersey (1993). -
  5. [8][8] Aiello, W., Chung, F., and Lu, L., A random graph model for massive graphs, in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing , pp. 171-180, Association of Computing Machinery, New York (2000). -
  6. [9][9] Aiello, W., Chung, F., and Lu, L., Random evolution of massive graphs, in J. Abello, P. M. Pardalos, and M. G. C. Resende (eds.), Handbook of Massive Data Sets , pp. 97-122, Kluwer, Dordrecht (2002). -
  7. [10][10] Alberich, R., Miro Julia, J., and Rossello, F., Mar vel Universe looks almost like a real social network, Preprint cond mat/0202174 (2002). -
  8. [16][16] Aldana, M., Dynamics of Boolean networks with scale free topology, Preprint cond mat/0209571 (2002). -
  9. [20][20] Amaral, L. A. N., Scala, A., Barth´ el´ emy, M., and Stan ley, H. E., Classes of small world networks, Proc. Natl. Acad. Sci. USA 97 , 11149-11152 (2000). -
  10. [23][23] Anderson, R. M. and May, R. M., Infectious Diseases of Humans , Oxford University Press, Oxford (1991). -
  11. [25][25] Arenas, A., Cabrales, A., D´ ıaz Guilera, A., Guimer` a, R., and Vega Redondo, F., Search and congestion in complex networks, in R. Pastor Satorras and J. Rubi (eds.), Proceedings of the XVIII Sitges Conference on Statistical Mechanics , Lecture Notes in Physics, Springer, Berlin (2003). -
  12. [26][26] Bailey, N. T. J., The Mathematical Theory of Infectious Diseases and Its Applications , Hafner Press, New York (1975). -
  13. [28][28] Ball, F., Mollison, D., and Scalia Tomba, G., Epidemics with two levels of mixing, Annals of Applied Probability 7 , 46-89 (1997). -
  14. [30][30] Banks, D. L. and Carley, K. M., Models for network evolution, Journal of Mathematical Sociology 21 , 173196 (1996). -
  15. [31][31] Barab´ asi, A. L., Linked: The New Science of Networks , Perseus, Cambridge, MA (2002). -
  16. [39][39] Barrat, A., Comment on 'Small world networks: Evi dence for crossover picture', Preprint cond mat/9903323 (1999). -
  17. [44][44] Bauer, M. and Bernard, D., A simple asymmetric evolving random network, Preprint cond mat/0203232 (2002). -
  18. [45][45] Bearman, P. S., Moody, J., and Stovel, K., Chains of af fection: The structure of adolescent romantic and sexual networks, Preprint, Department of Sociology, Columbia University (2002). -
  19. [47][47] Bender, E. A. and Canfield, E. R., The asymptotic num ber of labeled graphs with given degree sequences, Journal of Combinatorial Theory A 24 , 296-307 (1978). -
  20. [49][49] Berg, J., L¨ assig, M., and Wagner, A., Evolution dy namics of protein networks, Preprint cond mat/0207711 (2002). -
  21. [51][51] Bianconi, G., Mean field solution of the Ising model on a Barab´ asi-Albert network, Preprint cond mat/0204455 (2002). -
  22. [56][56] Blanchard, P., Chang, C. H., and Kr¨ uger, T., Epi demic thresholds on scale free graphs: The interplay between exponent and preferential choice, Preprint cond mat/0207319 (2002). -
  23. [58][58] Bogu˜ n´ a, M., Pastor Satorras, R., and Vespignani, A., Absence of epidemic threshold in scale free networks with connectivity correlations, Preprint cond mat/0208163 (2002). -
  24. [59][59] Bogu˜ n´ a, M., Pastor Satorras, R., and Vespignani, A., Epidemic spreading in complex networks with degree correlations, in R. Pastor Satorras and J. Rubi (eds.), Proceedings of the XVIII Sitges Conference on Statistical Mechanics , Lecture Notes in Physics, Springer, Berlin (2003). -
  25. [60][60] Bollob´ as, B., A probabilistic proof of an asymptotic for mula for the number of labelled regular graphs, European Journal on Combinatorics 1 , 311-316 (1980). -
  26. [61][61] Bollob´ as, B., The diameter of random graphs, Trans. Amer. Math. Soc. 267 , 41-52 (1981). -
  27. [62][62] Bollob´ as, B., Modern Graph Theory , Springer, New York (1998). -
  28. [64][64] Bollob´ as, B. and Riordan, O., The diameter of a scale free random graph, Preprint, Department of Mathemat ical Sciences, University of Memphis (2002). -
  29. [66][66] Bonacich, P. F., A technique for analyzing overlapping memberships, in H. Costner (ed.), Sociological Methodology , Jossey Bass, San Francisco (1972). -
  30. [68][68] Bordens, M. and G´ omez, I., Collaboration networks - in science, in H. B. Atkins and B. Cronin (eds.), The Web of Knowledge: A Festschrift in Honor of Eugene Garfield , Information Today, Medford, NJ (2000). -
  31. [70][70] Bornholdt, S. and Schuster, H. G. (eds.), Handbook of Graphs and Networks , Wiley VCH, Berlin (2003). -
  32. [73][73] Broadbent, S. R. and Hammersley, J. M., Percolation processes: I. Crystals and mazes, Proc. Cambridge Philos. Soc. 53 , 629-641 (1957). -
  33. [75][75] Broida, A. and Claffy, K. C., Internet topology: Con nectivity of IP graphs, in S. Fahmy and K. Park (eds.), Scalability and Traffic Control in IP Networks , no. 4526 in Proc. SPIE, pp. 172-187, International Society for Optical Engineering, Bellingham, WA (2001). -
  34. [79][79] Caldarelli, G., Pastor Satorras, R., and Vespignani, A., Cycles structure and local ordering in complex net works, Preprint cond mat/0212026 (2002). -
  35. [83][83] Capocci, A., Caldarelli, G., and De Los Rios, P., Quantitative description and modeling of real networks, Preprint cond mat/0206336 (2002). -
  36. [84][84] Castellano, C., Vilone, D., and Vespignani, A., Incom plete ordering of the voter model on small world net works, Preprint cond mat/0210465 (2002). -
  37. [86][86] Chen, Q., Chang, H., Govindan, R., Jamin, S., Shenker, S. J., and Willinger, W., The origin of power laws in Internet topologies revisited, in Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies , IEEE Computer Soci ety (2002). -
  38. [88][88] Chung, F. and Lu, L., The average distances in random graphs with given expected degrees, Proc. Natl. Acad. Sci. USA 99 , 15879-15882 (2002). -
  39. [89][89] Chung, F. and Lu, L., Connected components in ran dom graphs with given degree sequences, Annals of Combinatorics 6 , 125-145 (2002). -
  40. [90][90] Chung, F., Lu, L., Dewey, T. G., and Galas, D. J., Duplication models for biological networks, Journal of Computational Biology (in press). -
  41. [91][91] Cohen, J. E., Briand, F., and Newman, C. M., Community food webs: Data and theory , Springer, New York (1990). -
  42. [92][92] Cohen, R., ben Avraham, D., and Havlin, S., Efficient immunization of populations and computers, Preprint cond mat/0207387 (2002). -
  43. [100][100] Coulumb, S. and Bauer, M., Asymmetric evolving ran dom networks, Preprint cond mat/0212371 (2002). -
  44. [101][101] Crane, D., Invisible colleges: Diffusion of knowledge in scientific communities , University of Chicago Press, Chicago (1972). -
  45. [103][103] Davis, A., Gardner, B. B., and Gardner, M. R., Deep South , University of Chicago Press, Chicago (1941). -
  46. [105][105] Davis, G. F., Yoo, M., and Baker, W. E., The small world of the corporate elite, Preprint, University of Michigan Business School (2001). -
  47. [110][110] Dodds, P. S., Muhamad, R., and Watts, D. J., An exper iment study of social search and the small world prob lem, Preprint, Department of Sociology, Columbia Uni versity (2002). -
  48. [119][119] Dorogovtsev, S. N. and Mendes, J. F. F., Language as an evolving word web, Proc. R. Soc. London B 268 , 2603-2606 (2001). -
  49. [121][121] Dorogovtsev, S. N. and Mendes, J. F. F., Accelerated growth of networks, in S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs and Networks , pp. 318-341, Wiley VCH, Berlin (2003). -
  50. [127][127] Dorogovtsev, S. N., Mendes, J. F. F., and Samukhin, A. N., Metric structure of random networks, Preprint cond mat/0210085 (2002). -
  51. [128][128] Dorogovtsev, S. N., Mendes, J. F. F., and Samukhin, A. N., Principles of statistical mechanics of random net works, Preprint cond mat/0204111 (2002). -
  52. [129][129] Dorogovtsev, S. N. and Samukhin, A. N., Meso scopics and fluctuations in networks, Preprint cond mat/0211518 (2002). -
  53. [131][131] Du, D., Gu, J., and Pardalos, P. M. (eds.), Satisfiability Problem: Theory and Applications , no. 35 in DIMACS Series in Discrete Mathematics and Theoretical Com puter Science, American Mathematical Society, Provi dence, RI (1997). -
  54. [132][132] Dunne, J. A., Williams, R. J., and Martinez, N. D., Food web structure and network theory: The role of connectance and size, Proc. Natl. Acad. Sci. USA 99 , 12917-12922 (2002). -
  55. [133][133] Dunne, J. A., Williams, R. J., and Martinez, N. D., Network structure and biodiversity loss in food webs: Robustness increases with connectance, Ecology Letters 5 , 558-567 (2002). -
  56. [134][134] Durrett, R. T., Rigorous results for the CallawayHopcroft-Kleinberg-Newman-Strogatz model, Preprint, Department of Mathematics, Cornell University (2003). -
  57. [137][137] Eckmann, J. P. and Moses, E., Curvature of co links uncovers hidden thematic layers in the world wide web, Proc. Natl. Acad. Sci. USA 99 , 5825-5829 (2002). -
  58. [138][138] Egghe, L. and Rousseau, R., Introduction to Informetrics , Elsevier, Amsterdam (1990). -
  59. [140][140] Eigen, M. and Schuster, P., The Hypercycle: A Principle of Natural Self-Organization , Springer, New York (1979). -
  60. [146][146] Eriksen, K. A., Simonsen, I., Maslov, S., and Snep pen, K., Modularity and extreme edges of the Internet, Preprint cond mat/0212001 (2002). -
  61. [147][147] Everitt, B., Cluster Analysis , John Wiley, New York (1974). -
  62. [148][148] Faloutsos, M., Faloutsos, P., and Faloutsos, C., On power law relationships of the internet topology, Computer Communications Review 29 , 251-262 (1999). -
  63. [149][149] Fararo, T. J. and Sunshine, M., A Study of a Biased Friendship Network , Syracuse University Press, Syra cuse (1964). -
  64. [156][156] Ferrer i Cancho, R. and Sol´ e, R. V., Optimization in complex networks, Preprint cond mat/0111222 (2001). -
  65. [157][157] Ferrer i Cancho, R. and Sol´ e, R. V., The small world of human language, Proc. R. Soc. London B 268 , 22612265 (2001). -
  66. [158][158] Flake, G. W., Lawrence, S. R., Giles, C. L., and Coet zee, F. M., Self organization and identification of Web communities, IEEE Computer 35 , 66-71 (2002). -
  67. [163][163] French, J. R. P., A formal theory of social power, Psychological Review 63 , 181-194 (1956). -
  68. [164][164] Fronczak, A., Fronczak, P., and Holyst, J. A., Ex act solution for average path length in random graphs, Preprint cond mat/0212230 (2002). -
  69. [167][167] Galaskiewicz, J., Social Organization of an Urban Grants Economy , Academic Press, New York (1985). -
  70. [170][170] Garfinkel, I., Glei, D. A., and McLanahan, S. S., As sortative mating among unmarried parents, Journal of Population Economics 15 , 417-432 (2002). -
  71. [171][171] Girvan, M. and Newman, M. E. J., Community struc ture in social and biological networks, Proc. Natl. Acad. Sci. USA 99 , 8271-8276 (2002). -
  72. [175][175] Goh, K. I., Oh, E., Jeong, H., Kahng, B., and Kim, D., Classification of scale free networks, Proc. Natl. Acad. Sci. USA 99 , 12583-12588 (2002). -
  73. [176][176] Goldberg, D., Nichols, D., Oki, B. M., and Terry, D., Using collaborative filtering to weave an information tapestry, Comm. ACM 35 , 61-70 (1992). -
  74. [185][185] Guimer` a, R., Danon, L., D´ ıaz Guilera, A., Giralt, F., and Arenas, A., Self similar community structure in or ganisations, Preprint cond mat/0211498 (2002). -
  75. [187][187] Hammersley, J. M., Percolation processes: II. The con nective constant, Proc. Cambridge Philos. Soc. 53 , 642645 (1957). -
  76. [188][188] Harary, F., Graph Theory , Perseus, Cambridge, MA (1995). -
  77. [189][189] Hayes, B., Graph theory in practice: Part I, American Scientist 88 (1), 9-13 (2000). -
  78. [190][190] Hayes, B., Graph theory in practice: Part II, American Scientist 88 (2), 104-109 (2000). -
  79. [192][192] Hethcote, H. W., The mathematics of infectious dis eases, SIAM Review 42 , 599-653 (2000). -
  80. [196][196] Holme, P., Edling, C. R., and Liljeros, F., Struc ture and time evolution of the Internet community pus sokram.com, Preprint cond mat/0210514 (2002). -
  81. [197][197] Holme, P., Huss, M., and Jeong, H., Subnet work hierarchies of biochemical pathways, Preprint cond mat/0206292 (2002). -
  82. [203][203] Huberman, B. A., The Laws of the Web , MIT Press, Cambridge, MA (2001). -
  83. [205][205] Iamnitchi, A., Ripeanu, M., and Foster, I., Locating data in (small world?) peer to peer scientific collabora tions, in P. Druschel, F. Kaashoek, and A. Rowstron (eds.), Proceedings of the First International Workshop on Peer-to-Peer Systems , no. 2429 in Lecture Notes in Computer Science, pp. 232-241, Springer, Berlin (2002). -
  84. [206][206] Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M., and Sakaki, Y., A comprehensive two hybrid analysis to explore the yeast protein interactome, Proc. Natl. Acad. Sci. USA 98 , 4569-4574 (2001). -
  85. [207][207] Jaffe, A. and Trajtenberg, M., Patents, Citations and Innovations: A Window on the Knowledge Economy , MIT Press, Cambridge, MA (2002). -
  86. [208][208] Jain, A. K., Murty, M. N., and Flynn, P. J., Data clus tering: A review, ACM Computing Surveys 31 , 264-323 (1999). -
  87. [210][210] Jain, S. and Krishna, S., A model for the emergence of cooperation, interdependence, and structure in evolv ing networks, Proc. Natl. Acad. Sci. USA 98 , 543-547 (2001). -
  88. [211][211] Janson, S., suppress Luczak, T., and Rucinski, A., Random Graphs , John Wiley, New York (1999). -
  89. [218][218] Jones, J. H. and Handcock, M. S., An assessment of preferential attachment as a mechanism for human sex ual network formation, Preprint, University of Wash ington (2003). -
  90. [219][219] Jordano, P., Bascompte, J., and Olesen, J. M., Invariant properties in coevolutionary networks of plant animal interactions, Ecology Letters 6 , 69-81 (2003). -
  91. [221][221] Kalapala, V. K., Sanwalani, V., and Moore, C., The structure of the United States road network, Preprint, University of New Mexico (2003). -
  92. [223][223] Karo´ nski, M., A review of random graphs, Journal of Graph Theory 6 , 349-389 (1982). -
  93. [225][225] Kauffman, S. A., Gene regulation networks: A theory for their structure and global behavior, in A. Moscana and A. Monroy (eds.), Current Topics in Developmental Biology 6 , pp. 145-182, Academic Press, New York (1971). -
  94. [226][226] Kauffman, S. A., The Origins of Order , Oxford Univer sity Press, Oxford (1993). -
  95. [227][227] Kautz, H., Selman, B., and Shah, M., ReferralWeb: Combining social networks and collaborative filtering, Comm. ACM 40 , 63-65 (1997). -
  96. [229][229] Kephart, J. O. and White, S. R., Directed graph epi demiological models of computer viruses, in Proceedings of the 1991 IEEE Computer Society Symposium on Research in Security and Privacy , pp. 343-359, IEEE Computer Society, Los Alamitos, CA (1991). -
  97. [237][237] Kleinberg, J. M., Authoritative sources in a hyperlinked environment, J. ACM 46 , 604-632 (1999). -
  98. [239][239] Kleinberg, J. M., The small world phenomenon: An al gorithmic perspective, in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing , pp. 163-170, Association of Computing Machinery, New York (2000). -
  99. [240][240] Kleinberg, J. M., Small world phenomena and the dy namics of information, in T. G. Dietterich, S. Becker, and Z. Ghahramani (eds.), Proceedings of the 2001 Neural Information Processing Systems Conference , MIT Press, Cambridge, MA (2002). -
  100. [241][241] Kleinberg, J. M., Kumar, S. R., Raghavan, P., Ra jagopalan, S., and Tomkins, A., The Web as a graph: Measurements, models and methods, in Proceedings of the International Conference on Combinatorics and Computing , no. 1627 in Lecture Notes in Computer Sci ence, pp. 1-18, Springer, Berlin (1999). -
  101. [244][244] Knuth, D. E., The Stanford GraphBase: A Platform for Combinatorial Computing , Addison Wesley, Read ing, MA (1993). -
  102. [248][248] Krapivsky, P. L. and Redner, S., Rate equation ap proach for growing networks, in R. Pastor Satorras and J. Rubi (eds.), Proceedings of the XVIII Sitges Conference on Statistical Mechanics , Lecture Notes in Physics, Springer, Berlin (2003). -
  103. [252][252] Kulkarni, R. V., Almaas, E., and Stroud, D., Evolution ary dynamics in the Bak Sneppen model on small world networks, Preprint cond mat/9908216 (1999). -
  104. [254][254] Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A. S., and Upfal, E., Stochastic models for the Web graph, in Proceedings of the 42st Annual IEEE Symposium on the Foundations of Computer Science , pp. 57-65, Institute of Electrical and Electronics Engineers, New York (2000). -
  105. [261][261] Latora, V. and Marchiori, M., Economic small world behavior in weighted networks, Preprint cond mat/0204089 (2002). -
  106. [265][265] Liljeros, F., Edling, C. R., and Amaral, L. A. N., Sex ual networks: Implication for the transmission of sexu ally transmitted infection, Microbes and Infections (in press). -
  107. [268][268] suppress Luczak, T., Sparse random graphs with a given degree sequence, in A. M. Frieze and T. suppress Luczak (eds.), Proceedings of the Symposium on Random Graphs, Pozna´ n 1989 , pp. 165-182, John Wiley, New York (1992). -
  108. [269][269] Mariolis, P., Interlocking directorates and control of cor porations: The theory of bank control, Social Science Quarterly 56 , 425-439 (1975). -
  109. [271][271] Marsden, P. V., Network data and measurement, Annual Review of Sociology 16 , 435-463 (1990). -
  110. [275][275] Maslov, S., Sneppen, K., and Zaliznyak, A., Pattern detection in complex networks: Correlation profile of the Internet, Preprint cond mat/0205379 (2002). -
  111. [276][276] May, R. M. and Anderson, R. M., The transmission dy namics of human immunodeficiency virus (HIV), Philos. Trans. R. Soc. London B 321 , 565-607 (1988). -
  112. [278][278] Meester, R. and Roy, R., Continuum Percolation , Cam bridge University Press, Cambridge (1996). -
  113. [281][281] Menczer, F., Pant, G., Ruiz, M., and Srinivasan, P., Evaluating topic driven Web crawlers, in D. H. Kraft, W. B. Croft, D. J. Harper, and J. Zobel (eds.), Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pp. 241-249, Association of Computing Machinery, New York (2001). -
  114. [285][285] Mitchell, M., Introduction to Genetic Algorithms , MIT Press, Cambridge, MA (1996). -
  115. [292][292] Moody, J., The structure of a social science collabora tion network, Preprint, Department of Sociology, Ohio State University (2003). -
  116. [295][295] Moreira, A. A., Andrade, Jr., J. S., and Amaral, L. A. N., Extremum statistics in scale free network models, Preprint cond mat/0205411 (2002). -
  117. [298][298] Moreno, Y., Pastor Satorras, R., V´ azquez, A., and Vespignani, A., Critical load and congestion instabili ties in scale free networks, Preprint cond mat/0209474 (2002). -
  118. [301][301] Moreno, Y. and V´ azquez, A., Disease spreading in struc tured scale free networks, Preprint cond mat/0210362 (2002). -
  119. [302][302] Morris, M., Data driven network models for the spread of infectious disease, in D. Mollison (ed.), Epidemic Models: Their Structure and Relation to Data , pp. 302322, Cambridge University Press, Cambridge (1995). -
  120. [303][303] Morris, M., Sexual networks and HIV, AIDS 97: Year in Review 11 , 209-216 (1997). -
  121. [313][313] Newman, M. E. J., The structure of scientific collabora tion networks, Proc. Natl. Acad. Sci. USA 98 , 404-409 (2001). -
  122. [319][319] Newman, M. E. J., Random graphs as models of net works, in S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs and Networks , pp. 35-68, Wiley VCH, Berlin (2003). -
  123. [320][320] Newman, M. E. J., Barab´ asi, A. L., and Watts, D. J., The Structure and Dynamics of Networks , Princeton University Press, Princeton (2003). -
  124. [330][330] Pastor Satorras, R. and Rubi, J. (eds.), Proceedings of the XVIII Sitges Conference on Statistical Mechanics , Lecture Notes in Physics, Springer, Berlin (2003). -
  125. [336][336] Pastor Satorras, R. and Vespignani, A., Epidemics and immunization in scale free networks, in S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs and Networks , Wiley VCH, Berlin (2003). -
  126. [338][338] Pennock, D. M., Flake, G. W., Lawrence, S., Glover, E. J., and Giles, C. L., Winners don't take all: Char acterizing the competition for links on the web, Proc. Natl. Acad. Sci. USA 99 , 5207-5211 (2002). -
  127. [339][339] Pimm, S. L., Food Webs , University of Chicago Press, Chicago, 2nd ed. (2002). -
  128. [345][345] Ramezanpour, A., Karimipour, V., and Mashaghi, A., Generating correlated networks from uncorrelated ones, Preprint cond mat/0212469 (2002). -
  129. [346][346] Rapoport, A., Contribution to the theory of random and biased nets, Bulletin of Mathematical Biophysics 19 , 257-277 (1957). -
  130. [347][347] Rapoport, A., Cycle distribution in random nets, Bulletin of Mathematical Biophysics 10 , 145-157 (1968). -
  131. [352][352] Resnick, P. and Varian, H. R., Recommender systems, Comm. ACM 40 , 56-58 (1997). -
  132. [353][353] Rinaldo, A., Rodr´ ıguez Iturbe, I., and Rigon, R., Chan nel networks, Annual Review of Earth and Planetary Science 26 , 289-327 (1998). -
  133. [354][354] Ripeanu, M., Foster, I., and Iamnitchi, A., Mapping the Gnutella network: Properties of large scale peer to peer systems and implications for system design, IEEE Internet Computing 6 , 50-57 (2002). -
  134. [356][356] Rodr´ ıguez Iturbe, I. and Rinaldo, A., Fractal River Basins: Chance and Self-Organization , Cambridge Uni versity Press, Cambridge (1997). -
  135. [357][357] Roethlisberger, F. J. and Dickson, W. J., Management and the Worker , Harvard University Press, Cambridge, MA (1939). -
  136. [358][358] Rothenberg, R., Baldwin, J., Trotter, R., and Muth, S., The risk environment for HIV transmission: Results from the Atlanta and Flagstaff network studies, Journal of Urban Health 78 , 419-431 (2001). -
  137. [363][363] Scott, J., Social Network Analysis: A Handbook , Sage Publications, London, 2nd ed. (2000). -
  138. [366][366] Sen, P., Dasgupta, S., Chatterjee, A., Sreeram, P. A., Mukherjee, G., and Manna, S. S., Small world properties of the Indian railway network, Preprint cond mat/0208535 (2002). -
  139. [367][367] Shardanand, U. and Maes, P., Social information fil tering: Algorithms for automating 'word of mouth', in Proceedings of ACM Conference on Human Factors and Computing Systems , pp. 210-217, Association of Com puting Machinery, New York (1995). -
  140. [369][369] Sigman, M. and Cecchi, G. A., Global organization of the Wordnet lexicon, Proc. Natl. Acad. Sci. USA 99 , 1742-1747 (2002). -
  141. [371][371] Smith, R. D., Instant messaging as a scale free network, Preprint cond mat/0206378 (2002). -
  142. [372][372] Snijders, T. A. B., Markov chain Monte Carlo estima tion of exponential random graph models, Journal of Social Structure 2 (2) (2002). -
  143. [375][375] Sol´ e, R. V. and Montoya, J. M., Complexity and fragility in ecological networks, Proc. R. Soc. London B 268 , 2039-2045 (2001). -
  144. [376][376] Sol´ e, R. V. and Pastor Satorras, R., Complex networks in genomics and proteomics, in S. Bornholdt and H. G. Schuster (eds.), Handbook of Graphs and Networks , pp. 145-167, Wiley VCH, Berlin (2003). -
  145. [378][378] Solomonoff, R. and Rapoport, A., Connectivity of ran dom nets, Bulletin of Mathematical Biophysics 13 , 107117 (1951). -
  146. [379][379] Sporns, O., Network analysis, complexity, and brain function, Complexity 8 (1), 56-60 (2002). -
  147. [381][381] Stauffer, D., Monte Carlo simulations of Sznajd mod els, Journal of Artificial Societies and Social Simulation 5 (1) (2002). -
  148. [382][382] Stauffer, D., Aharony, A., da Fontoura Costa, L., and Adler, J., Efficient Hopfield pattern recognition on a scale free neural network, Preprint cond mat/0212601 (2002). -
  149. [384][384] Steyvers, M. and Tenenbaum, J. B., The large scale structure of semantic networks: Statistical anal yses and a model for semantic growth, Preprint cond mat/0110012 (2001). -
  150. [385][385] Strauss, D., On a general class of models for interaction, SIAM Review 28 , 513-527 (1986). -
  151. [386][386] Strogatz, S. H., Nonlinear Dynamics and Chaos , Addison Wesley, Reading, MA (1994). -
  152. [389][389] Szab´ o, G., Alava, M., and Kert´ esz, J., Structural transi tions in scale free networks, Preprint cond mat/0208551 (2002). -
  153. [396][396] V´ azquez, A., Statistics of citation networks, Preprint cond mat/0105031 (2001). -
  154. [397][397] V´ azquez, A., Growing networks with local rules: Prefer ential attachment, clustering hierarchy and degree cor relations, Preprint cond mat/0211528 (2002). -
  155. [398][398] V´ azquez, A., Bogu˜ n´ a, M., Moreno, Y., Pastor Satorras, R., and Vespignani, A., Topology and cor relations in structured scale free networks, Preprint cond mat/0209183 (2002). -
  156. [405][405] Wagner, A. and Fell, D., The small world inside large metabolic networks, Proc. R. Soc. London B 268 , 18031810 (2001). -
  157. [406][406] Walsh, T., Search in a small world, in T. Dean (ed.), Proceedings of the 16th International Joint Conference on Artificial Intelligence , Morgan Kaufmann, San Fran cisco, CA (1999). -
  158. [409][409] Wasserman, S. and Faust, K., Social Network Analysis , Cambridge University Press, Cambridge (1994). -
  159. [412][412] Watts, D. J., Small Worlds , Princeton University Press, Princeton (1999). -
  160. [413][413] Watts, D. J., A simple model of global cascades on ran dom networks, Proc. Natl. Acad. Sci. USA 99 , 57665771 (2002). -
  161. [420][420] White, H. D., Wellman, B., and Nazer, N., Does citation reflect social structure? Longitudinal evidence from the 'Globenet' interdisciplinary research group, Preprint, University of Toronto (2003). -
  162. [421][421] White, J. G., Southgate, E., Thompson, J. N., and Brenner, S., The structure of the nervous system of the nematode C. Elegans, Phil. Trans. R. Soc. London 314 , 1-340 (1986). -
  163. [422][422] Wilkinson, D. and Huberman, B. A., A method for find ing communities of related genes, Preprint, Stanford University (2002). -
  164. [423][423] Williams, R. J., Berlow, E. L., Dunne, J. A., Barab´ asi, A. L., and Martinez, N. D., Two degrees of separation in complex food webs, Proc. Natl. Acad. Sci. USA 99 , 12913-12916 (2002). -
  165. [426][426] Young, H. P., The diffusion of innovations in social net works, in L. E. Blume and S. N. Durlauf (eds.), The Economy as an Evolving Complex System , vol. 3, Ox ford University Press, Oxford (2003). -
  166. [429][429] Zhu, J. Y. and Zhu, H., Introducing small world network effect to critical dynamics, Preprint cond mat/0212542 (2002).

Cited by

Sorted by citations

Authors
Newman, M. E. J.
Affiliations
Santa Fe Institute (US)
Corresponding author
Newman, M. E. J.
ORCID
Newman, M. E. J.
Venue
SIAM Review
Publisher
Society for Industrial & Applied Mathematics (SIAM)
Published
2003-01-01
Volume
45
Issue
2
Pages
167-256
ISSN
  • 0036-1445 (ISSN-L)
  • 1095-7200
DOI
10.1137/s003614450342480
OpenAlex
W2148606196
Cited by
18,719
References
17
Citations by year
2026: 493 · 2025: 574 · 2024: 588 · 2023: 573 · 2022: 723 · 2021: 789 · 2020: 813 · 2019: 925 · 2018: 958 · 2017: 1004 · 2016: 1006 · 2015: 1053 · 2014: 1089 · 2013: 1134 · 2012: 1018
FWCI
251.48
Type
journal article
Language
en
Open access
Locations
  • SIAM Review (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • U.S. National Science Foundation (DMS-0109086, DMS-0234188)
  • James S. McDonnell Foundation and the Santa Fe Institute
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Complex Systems and Time Series Analysis
  • Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
Keywords
complex networks, small-world effect, degree distribution, clustering, network correlation, random graph models, network growth models, preferential attachment, dynamical processes on networks, social networks, biological networks, internet

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review