Search in power-law networks
Open accessThe DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
Abstract
Many communication and social networks have power-law link distributions, containing a few nodes that have a very high degree and many with low degree. The high connectivity nodes play the important role of hubs in communication and networking, a fact that can be exploited when designing efficient search algorithms. We introduce a number of local search strategies that utilize high degree nodes in power-law graphs and that have costs scaling sublinearly with the size of the graph. We also demonstrate the utility of these strategies on the GNUTELLA peer-to-peer network.
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
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
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (2000) · RePEc: Research Papers in Economics · Cited by 6,469
The Large-Scale Organization of Metabolic Networks
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35036627 · Cited by 4,972
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316229 · Cited by 4,196
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2001) · Physical Review E · doi:10.1103/physreve.64.026118 · Cited by 3,648
The Tipping Point: How Little Things Can Make a Big Difference
Meadows-Klue, D. (2004) · Interactive Marketing · doi:10.1057/palgrave.im.4340262 · Cited by 3,032
Kleinberg, J. M. (2000) · Nature · doi:10.1038/35022643 · Cited by 1,737
The Evolution of Random Graphs
Bollobas, B. (1984) · Transactions of the American Mathematical Society · doi:10.2307/1999405 · Cited by 1,023
A random graph model for massive graphs
Aiello, W., Chung, F., & Lu, L. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335326 · Cited by 917
Cited by
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
Spread of epidemic disease on networks
Newman, M. E. J. (2002) · Physical Review E · doi:10.1103/physreve.66.016128 · Cited by 3,218
Dorogovtsev, S. N., & Mendes, J. F. F. (2002) · Advances in Physics · doi:10.1080/00018730110112519 · Cited by 3,171
Newman, M. E. J. (2003) · Physical Review E · doi:10.1103/physreve.67.026126 · Cited by 3,087
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
Barthélemy, M. (2011) · Physics Reports · doi:10.1016/j.physrep.2010.11.002 · Cited by 2,469
Computational systems biology.
Kitano, H. (2002) · Nature · doi:10.1038/nature01254 · Cited by 2,209
BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks
Hui, P., Crowcroft, J., & Yoneki, E. (2011) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2010.246 · Cited by 1,515
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
Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence
Humphries, M. D., & Gurney, K. (2008) · PLoS ONE · doi:10.1371/journal.pone.0002051 · Cited by 1,442
Random Walks on Complex Networks
Noh, J. D., & Rieger, H. (2004) · Physical Review Letters · doi:10.1103/physrevlett.92.118701 · Cited by 1,148
Synchronization in scale-free dynamical networks: robustness and fragility
Wang, X. F., & Chen, G. (2002) · IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications · doi:10.1109/81.974874 · Cited by 1,127
Making gnutella-like P2P systems scalable
Chawathe, Y., Ratnasamy, S., Breslau, L., Lanham, N., & Shenker, S. (2003) · Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/863955.864000 · Cited by 1,082
Hyperbolic geometry of complex networks
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., & Boguñá, M. (2010) · Physical Review E · doi:10.1103/physreve.82.036106 · Cited by 1,059
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
Statistical physics of vaccination
Wang, Z., Bauch, C. T., Bhattacharyya, S., d'Onofrio, A., Manfredi, P., Perc, M., Perra, N., Salathé, M., & Zhao, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.10.006 · Cited by 872
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
Scale-Free Networks Are Ultrasmall
Cohen, R., & Havlin, S. (2003) · Physical Review Letters · doi:10.1103/physrevlett.90.058701 · Cited by 815
Bubble rap: social-based forwarding in delay tolerant networks
Hui, P., Crowcroft, J., & Yoneki, E. (2008) · Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing · doi:10.1145/1374618.1374652 · Cited by 814
Cascade Control and Defense in Complex Networks
Motter, A. E. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.098701 · Cited by 776
Matei, R., Iamnitchi, A., & Foster, P. (2002) · IEEE Internet Computing · doi:10.1109/4236.978369 · Cited by 766
Peer-to-peer architecture case study: Gnutella network
Ripeanu, M. (2002) · Proceedings First International Conference on Peer-to-Peer Computing · doi:10.1109/p2p.2001.990433 · Cited by 737
Large-scale topological and dynamical properties of the Internet
Vázquez, A., Pastor-Satorras, R., & Vespignani, A. (2002) · Physical Review E · doi:10.1103/physreve.65.066130 · Cited by 712
Find me if you can: improving geographical prediction with social and spatial proximity
Backstrom, L., Sun, E., & Marlow, C. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772698 · Cited by 705
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
Modelling dynamical processes in complex socio-technical systems
Vespignani, A. (2012) · Nature Physics · doi:10.1038/nphys2160 · Cited by 652
Graph mining: Laws, generators, and algorithms
Chakrabarti, D., & Faloutsos, C. (2006) · ACM Computing Surveys · doi:10.1145/1132952.1132954 · Cited by 609
How to search a social network
Adamic, L., & Adar, E. (2005) · Social Networks · doi:10.1016/j.socnet.2005.01.007 · Cited by 606
Self-citationOptimal Network Topologies for Local Search with Congestion
Guimerà, R., Díaz-Guilera, A., Vega-Redondo, F., Cabrales, A., & Arenas, A. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.248701 · Cited by 605
On distinguishing between Internet power law topology generators
Bu, T., & Towsley, D. (2003) · Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies · doi:10.1109/infcom.2002.1019309 · Cited by 516
Lévy flights and superdiffusion in the context of biological encounters and random searches
Viswanathan, G. M., Raposo, E. P., & da Luz, M. G. E. (2008) · Physics of Life Reviews · doi:10.1016/j.plrev.2008.03.002 · Cited by 451
Kurant, M., & Thiran, P. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.138701 · Cited by 421
Protecting free expression online with Freenet
Clarke, I., Miller, S. G., Hong, T. W., Sandberg, O., & Wiley, B. (2002) · IEEE Internet Computing · doi:10.1109/4236.978368 · Cited by 401
Survey of research towards robust peer-to-peer networks: Search methods
Risson, J., & Moors, T. (2006) · Computer Networks · doi:10.1016/j.comnet.2006.02.001 · Cited by 386
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
Traffic dynamics based on local routing protocol on a scale-free network
Wang, W.-X., Wang, B.-H., Yin, C.-Y., Xie, Y.-B., & Zhou, T. (2006) · Physical Review E · doi:10.1103/physreve.73.026111 · Cited by 382
Who Is the Best Connected Scientist?A Study of Scientific Coauthorship Networks
Newman, M. E. J. (2004) · Lecture Notes in Physics · doi:10.1007/978-3-540-44485-5_16 · Cited by 379
A local search mechanism for peer-to-peer networks
Kalogeraki, V., Gunopulos, D., & Zeinalipour-Yazti, D. (2002) · Proceedings of the eleventh international conference on Information and knowledge management · doi:10.1145/584792.584842 · Cited by 369
Average path length in random networks
Fronczak, A., Fronczak, P., & Hołyst, J. A. (2004) · Physical Review E · doi:10.1103/physreve.70.056110 · Cited by 326
AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing
Geng, T., Li, A., Shi, R., Wu, C., Wang, T., Li, Y., Haghi, P., Tumeo, A., Che, S., Reinhardt, S., et al. (2020) · 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro50266.2020.00079 · Cited by 301
Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity
Zhou, T., Liu, J.-G., Bai, W.-J., Chen, G., & Wang, B.-H. (2006) · Physical Review E · doi:10.1103/physreve.74.056109 · Cited by 286
Börner, K., Sanyal, S., & Vespignani, A. (2007) · Annual Review of Information Science and Technology · doi:10.1002/aris.2007.1440410119 · Cited by 279
Random walks on temporal networks
Starnini, M., Baronchelli, A., Barrat, A., & Pastor-Satorras, R. (2012) · Physical Review E · doi:10.1103/physreve.85.056115 · Cited by 275
Complex networks and decentralized search algorithms
Kleinberg, J. (2007) · Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006 · doi:10.4171/022-3/50 · Cited by 272
Resilience to damage of graphs with degree correlations
Vázquez, A., & Moreno, Y. (2003) · Physical Review E · doi:10.1103/physreve.67.015101 · Cited by 265
A survey on content-centric technologies for the current Internet: CDN and P2P solutions
Passarella, A. (2012) · Computer Communications · doi:10.1016/j.comcom.2011.10.005 · Cited by 226
A spectrum of routing strategies for brain networks
Avena-Koenigsberger, A., Yan, X., Kolchinsky, A., van den Heuvel, M. P., Hagmann, P., & Sporns, O. (2019) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1006833 · Cited by 115
Power Law Distributions in Information Retrieval
Petersen, C., Simonsen, J. G., & Lioma, C. (2016) · ACM Transactions on Information Systems · doi:10.1145/2816815 · Cited by 46
(2002)
Metadata
- Authors
- Adamic, L. A., Lukose, R. M., Puniyani, A. R., & Huberman, B. A.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2001-09-26
- Volume
- 64
- Issue
- 4
- Pages
- 046135-046135
- ISSN
- 1063-651X (ISSN-L)
- 1095-3787
- OpenAlex
- W1527463082
- Cited by
- 1,203
- References
- 15
- FWCI
- 37.61
- Type
- journal article
- Language
- en
- Open access
- green
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.