The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Complex networks and decentralized search algorithms
Abstract
The study of complex networks has emerged over the past several years as a theme spanning many disciplines, ranging from mathematics and computer science to the social and biological sciences. A significant amount of recent work in this area has focused on the development of random graph models that capture some of the qualitative properties observed in large-scale network data; such models have the potential to help us reason, at a general level, about the ways in which real-world networks are organized. We survey one particular line of network research, concerned with small-world phenomena and decentralized search algorithms, that illustrates this style of analysis. We begin by describing a well-known experiment that provided the first empirical basis for the “six degrees of separation” phenomenon in social networks; we then discuss some probabilistic network models motivated by this work, illustrating how these models lead to novel algorithmic and graph-theoretic questions, and how they are supported by recent empirical studies of large social networks.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Strogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,302
Bollobás, B. (1985) · Cited by 6,196
The small-world problem: (400002009-005)
Milgram, S. (1967) · PsycEXTRA Dataset · doi:10.1037/e400002009-005 · Cited by 4,790
Linked: The New Science of Networks
Barabási, A.-L., & Aldana-Gonzalez, M. (2003) · Physics Today · doi:10.1063/1.1570778 · Cited by 2,724
Freenet: A Distributed Anonymous Information Storage and Retrieval System
Clarke, I., Sandberg, O., Wiley, B., & Hong, T. W. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44702-4_4 · Cited by 2,109
The small-world phenomenon: an algorithmic perspective
Kleinberg, J. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335325 · Cited by 1,882
Self-citationAn Experimental Study of the Small World Problem
Travers, J., & Milgram, S. (1969) · Sociometry · doi:10.2307/2786545 · Cited by 1,863
Kleinberg, J. M. (2000) · Nature · doi:10.1038/35022643 · Cited by 1,737
Self-citationSix Degrees: The Science of a Connected Age
Watts, D. J. (2003) · Cited by 1,724
Epidemic algorithms for replicated database maintenance
Demers, A., Greene, D., Hauser, C., Irish, W., & Larson, J. (1987) · Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87 · doi:10.1145/41840.41841 · Cited by 1,673
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
A survey and comparison of peer-to-peer overlay network schemes
Lua, E. K., Crowcroft, J., Pias, M., Sharma, R., & Lim, S. (2005) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2005.1610546 · Cited by 1,496
Adamic, L. A., Lukose, R. M., Puniyani, A. R., & Huberman, B. A. (2001) · Physical Review E · doi:10.1103/physreve.64.046135 · Cited by 1,203
Identity and Search in Social Networks
Watts, D. J., Dodds, P. S., & Newman, M. E. J. (2002) · Science · doi:10.1126/science.1070120 · Cited by 1,052
An Experimental Study of Search in Global Social Networks
Dodds, P. S., Muhamad, R., & Watts, D. J. (2003) · Science · doi:10.1126/science.1081058 · Cited by 875
Geographic routing in social networks
Liben-Nowell, D., Novak, J., Kumar, R., Raghavan, P., & Tomkins, A. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0503018102 · Cited by 838
Durrett, R. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546594 · Cited by 780
Van Renesse, R., Birman, K. P., & Vogels, W. (2003) · ACM Transactions on Computer Systems · doi:10.1145/762483.762485 · Cited by 645
How to search a social network
Adamic, L., & Adar, E. (2005) · Social Networks · doi:10.1016/j.socnet.2005.01.007 · Cited by 606
Mathematical results on scale‐free random graphs
Bollobás, B., & Riordan, O. M. (2002) · Handbook of Graphs and Networks · doi:10.1002/3527602755.ch1 · Cited by 463
Bounded geometries, fractals, and low-distortion embeddings
Gupta, A., Krauthgamer, R., & Lee, J. R. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238226 · Cited by 405
Small-World Phenomena and the Dynamics of Information
Kleinberg, J. (2002) · Advances in Neural Information Processing Systems 14 · doi:10.7551/mitpress/1120.003.0060 · Cited by 382
Self-citationA Survey of Models of Network Formation: Stability and Efficiency
Jackson, M. O. (2003) · CaltechAUTHORS (California Institute of Technology) · doi:10.7907/c4y9t-bg336 · Cited by 374
Kleinberg, J., & Lawrence, S. (2001) · Science · doi:10.1126/science.1067014 · Cited by 320
Self-citationEpidemic algorithms for replicated database maintenance
Demers, A., Greene, D., Houser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., & Terry, D. (1988) · ACM SIGOPS Operating Systems Review · doi:10.1145/43921.43922 · Cited by 312
Six Degrees of Separation: A Play
Guare, J. (1990) · Cited by 248
Spatial gossip and resource location protocols
Kempe, D., Kleinberg, J., & Demers, A. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380796 · Cited by 224
Self-citationThe reversal small-world experiment
Killworth, P. D., & Bernard, H. R. (1978) · Social Networks · doi:10.1016/0378-8733(78)90018-7 · Cited by 215
Manku, G. S., Naor, M., & Wieder, U. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007368 · Cited by 205
The Diameter of a Cycle Plus a Random Matching
Bollobás, B., & Chung, F. R. K. (1988) · SIAM Journal on Discrete Mathematics · doi:10.1137/0401033 · Cited by 176
Discontinuity of the percolation density in one dimensional 1/|x?y|2 percolation models
Aizenman, M., & Newman, C. M. (1986) · Communications in Mathematical Physics · doi:10.1007/bf01205489 · Cited by 167
Analyzing Kleinberg's (and other) small-world Models
Martel, C., & Nguyễn, V. Đ. (2004) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1011767.1011794 · Cited by 134
On the scaling of the chemical distance in long-range percolation models
Biskup, M. (2004) · The Annals of Probability · doi:10.1214/009117904000000577 · Cited by 123
One dimensional 1/|j ? i| S percolation models: The existence of a transition forS?2
Newman, C. M., & Schulman, L. S. (1986) · Communications in Mathematical Physics · doi:10.1007/bf01211064 · Cited by 120
Kleinberg, J. M., & Raghavan, P. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.63 · Cited by 117
Self-citationGrowing and navigating the small world Web by local content
Menczer, F. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.212348399 · Cited by 110
The diameter of long‐range percolation clusters on finite cycles
Benjamini, I., & Berger, N. (2001) · Random Structures and Algorithms · doi:10.1002/rsa.1022 · Cited by 106
The diameter of a long‐range percolation graph
Coppersmith, D., Gamarnik, D., & Sviridenko, M. I. (2002) · Random Structures and Algorithms · doi:10.1002/rsa.10042 · Cited by 96
Long-range percolation in one dimension
Zhang, Z., Pu, F., & Li, B. Z. (1983) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/16/3/002 · Cited by 89
Distributed Routing in Small-World Networks
Sandberg, O. J. (2006) · doi:10.1137/1.9781611972863.14 · Cited by 65
An Experimental Study of 'Search'
Kingsley, H. L. (1932) · The American Journal of Psychology · doi:10.2307/1414831 · Cited by 46
Eclecticism shrinks even small worlds
Fraigniaud, P., Gavoille, C., & Paul, C. (2006) · Distributed Computing · doi:10.1007/s00446-005-0137-4 · Cited by 45
Greedy pathlengths and small world graphs
Higham, D. J. (2006) · Linear Algebra and its Applications · doi:10.1016/j.laa.2006.01.001 · Cited by 8
Cited by
Critical phenomena in complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1275 · Cited by 2,220
Structure and evolution of online social networks
Kumar, R., Novak, J., & Tomkins, A. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150476 · Cited by 1,084
Random walks and diffusion on networks
Masuda, N., Porter, M. A., & Lambiotte, R. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.07.007 · Cited by 657
Navigability of complex networks
Boguñá, M., Krioukov, D., & Claffy, K. C. (2009) · Nature Physics · doi:10.1038/nphys1130 · Cited by 486
Structure and Evolution of Online Social Networks
Kumar, R., Novak, J., & Tomkins, A. (2010) · Link Mining: Models, Algorithms, and Applications · doi:10.1007/978-1-4419-6515-8_13 · Cited by 431
Metadata
- Authors
- Kleinberg, J.
- Venue
- Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006
- Publisher
- EMS Press
- Published
- 2007-05-15
- Pages
- 1019-1044
- OpenAlex
- W2243945130
- Cited by
- 272
- References
- 46
- FWCI
- 77.15
- Type
- book chapter
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.