The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Optimal Network Topologies for Local Search with Congestion
Open accessAbstract
The problem of searchability in decentralized complex networks is of great importance in computer science, economy, and sociology. We present a formalism that is able to cope simultaneously with the problem of search and the congestion effects that arise when parallel searches are performed, and we obtain expressions for the average search cost both in the presence and the absence of congestion. This formalism is used to obtain optimal network structures for a system using a local search algorithm. It is found that only two classes of networks can be optimal: starlike configurations, when the number of parallel searches is small, and homogeneous-isotropic configurations, when it is large.
Overview
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.
Integrity signals
Registry
Cites
Statistics
Verification
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.
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
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
A Set of Measures of Centrality Based on Betweenness
Freeman, L. C. (1977) · Sociometry · doi:10.2307/3033543 · Cited by 10,295
Diameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-L. (1999) · Nature · doi:10.1038/43601 · Cited by 4,260
Classes of small-world networks
Amaral, L. A. N., Scala, A., Barthélémy, M., & Stanley, H. E. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.200327197 · Cited by 3,051
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.016132 · Cited by 2,613
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,613
An 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
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
Hierarchies and the Organization of Knowledge in Production
Garicano, L. (2000) · Journal of Political Economy · doi:10.1086/317671 · Cited by 1,194
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
Growth dynamics of the World-Wide Web
Huberman, B. A., & Adamic, L. A. (1999) · Nature · doi:10.1038/43604 · Cited by 863
The Firm as a Communication Network
Bolton, P., & Dewatripont, M. (1994) · The Quarterly Journal of Economics · doi:10.2307/2118349 · Cited by 761
The Organization of Decentralized Information Processing
Radner, R. (1993) · Econometrica · doi:10.2307/2951495 · Cited by 699
Probability, Statistics, and Queueing Theory with Computer Science Applications
Baxter, L. A., & Allen, A. O. (1992) · Technometrics · doi:10.2307/1269262 · Cited by 633
Communication in Networks with Hierarchical Branching
Arenas, A., Díaz-Guilera, A., & Guimerà, R. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3196 · Cited by 449
Self-citationPhase transition in a computer network traffic model
Ohira, T., & Sawatari, R. (1998) · Physical Review E · doi:10.1103/physreve.58.193 · Cited by 254
Information transfer and phase transitions in a model of internet traffic
Solé, R. V., & Valverde, S. (2001) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(00)00536-7 · Cited by 190
Dynamical properties of model communication networks
Guimerà, R., Arenas, A., Díaz-Guilera, A., & Giralt, F. (2002) · Physical Review E · doi:10.1103/physreve.66.026704 · Cited by 190
Self-citationTraveling salesman problem and Tsallis statistics
Penna, T. J. P. (1995) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.51.r1 · Cited by 150
Adaptive random walks on the class of Web graphs
Tadić, B. (2001) · The European Physical Journal B · doi:10.1007/s100510170071 · Cited by 47
Cited by
Complex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
The structure and dynamics of multilayer networks
Boccaletti, S., Bianconi, G., Criado, R., del Genio, C. I., Gómez-Gardeñes, J., Romance, M., Sendiña-Nadal, I., Wang, Z., & Zanin, M. (2014) · Physics Reports · doi:10.1016/j.physrep.2014.07.001 · Cited by 3,125
Link prediction in complex networks: A survey
Lü, L., & Zhou, T. (2011) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.11.027 · Cited by 2,819
Characterization of complex networks: A survey of measurements
Costa, L. D. F., Rodrigues, F. A., Travieso, G., & Villas Boas, P. R. (2007) · Advances in Physics · doi:10.1080/00018730601170527 · Cited by 2,475
Barthélemy, M. (2011) · Physics Reports · doi:10.1016/j.physrep.2010.11.002 · Cited by 2,469
Metadata
- Authors
- Guimerà, R., Díaz-Guilera, A., Vega-Redondo, F., Cabrales, A., & Arenas, A.
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2002-11-21
- Volume
- 89
- Issue
- 24
- Pages
- 248701-248701
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2107047240
- Cited by
- 605
- References
- 22
- FWCI
- 8.99
- Type
- journal article
- Language
- en
- Open access
- bronze
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.