The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Ultrafast consensus in small-world networks
Abstract
In this paper, we demonstrate a phase transition phenomenon in algebraic connectivity of small-world networks. Algebraic connectivity of a graph is the second smallest eigenvalue of its Laplacian matrix and a measure of speed of solving consensus problems in networks. We demonstrate that it is possible to dramatically increase the algebraic connectivity of a regular complex network by 1000 times or more without adding new links or nodes to the network. This implies that a consensus problem can be solved incredibly fast on certain small-world networks giving rise to a network design algorithm for ultra fast information networks. Our study relies on a procedure called "random rewiring" due to Watts & Strogatz (Nature, 1998). Extensive numerical results are provided to support our claims and conjectures. We prove that the mean of the bulk Laplacian spectrum of a complex network remains invariant under random rewiring. The same property only asymptotically holds for scale-free networks. A relationship between increasing the algebraic connectivity of complex networks and robustness to link and node failures is also shown. This is an alternative approach to the use of percolation theory for analysis of network robustness. We also show some connections between our conjectures and certain open problems in the theory of random matrices.
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
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
Olfati-Saber, R., & Murray, R. M. (2004) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.834113 · Cited by 12,788
Self-citationCoordination of groups of mobile autonomous agents using nearest neighbor rules
Jadbabaie, A., Lin, J., & Morse, A. S. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.812781 · Cited by 8,339
Strogatz, S. H. (2001) · Nature · doi:10.1038/35065725 · Cited by 8,302
Godsil, C., & Royle, G. (2001) · Graduate Texts in Mathematics · doi:10.1007/978-1-4613-0163-9 · Cited by 8,154
Chemical Oscillations, Waves, and Turbulence
Kuramoto, Y. (1984) · Springer Series in Synergetics · doi:10.1007/978-3-642-69689-3 · Cited by 7,142
The Evolution of Random Graphs
(1986) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/062/06 · Cited by 5,543
Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory
Olfati-Saber, R. (2006) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.864190 · Cited by 5,037
Self-citationMetabolic stability and epigenesis in randomly constructed genetic nets
Kauffman, S. A. (1969) · Journal of Theoretical Biology · doi:10.1016/0022-5193(69)90015-0 · Cited by 4,819
The small-world problem: (400002009-005)
Milgram, S. (1967) · PsycEXTRA Dataset · doi:10.1037/e400002009-005 · Cited by 4,790
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 3,977
Bollobás, B. (1998) · Graduate Texts in Mathematics · doi:10.1007/978-1-4612-0619-4 · Cited by 3,772
Strogatz, S. H. (2000) · Physica D: Nonlinear Phenomena · doi:10.1016/s0167-2789(00)00094-4 · Cited by 3,051
Coverage Control for Mobile Sensing Networks
Cortes, J., Martinez, S., Karatas, T., & Bullo, F. (2004) · IEEE Transactions on Robotics and Automation · doi:10.1109/tra.2004.824698 · Cited by 2,710
Next century challenges: scalable coordination in sensor networks
Estrin, D., Govindan, R., Heidemann, J., & Kumar, S. (1999) · Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/313451.313556 · Cited by 2,703
Network Robustness and Fragility: Percolation on Random Graphs
Callaway, D. S., Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.5468 · Cited by 2,480
Mean-field theory for scale-free random networks
Barabási, A.-L., Albert, R., & Jeong, H. (1999) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(99)00291-5 · Cited by 2,255
Scientific collaboration networks. I. Network construction and fundamental results
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.016131 · Cited by 2,076
Synchronization of Pulse-Coupled Biological Oscillators
Mirollo, R. E., & Strogatz, S. H. (1990) · SIAM Journal on Applied Mathematics · doi:10.1137/0150098 · Cited by 2,074
Biological rhythms and the behavior of populations of coupled oscillators
Winfree, A. T. (1967) · Journal of Theoretical Biology · doi:10.1016/0022-5193(67)90051-3 · Cited by 2,012
On the Distribution of the Roots of Certain Symmetric Matrices
Wigner, E. P. (1958) · The Annals of Mathematics · doi:10.2307/1970008 · Cited by 1,463
Scale-free characteristics of random networks: the topology of the world-wide web
Barabási, A.-L., Albert, R., & Jeong, H. (2000) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(00)00018-2 · Cited by 1,408
Eigenvalues and Condition Numbers of Random Matrices
Edelman, A. (1988) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0609045 · Cited by 1,284
Ogren, P., Fiorelli, E., & Leonard, N. E. (2004) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.832203 · Cited by 1,234
Consensus protocols for networks of dynamic agents
Saber, R. O., & Murray, R. M. (2004) · Proceedings of the 2003 American Control Conference, 2003. · doi:10.1109/acc.2003.1239709 · Cited by 901
Mogilner, A., & Edelstein-Keshet, L. (1999) · Journal of Mathematical Biology · doi:10.1007/s002850050158 · Cited by 580
Agreement over random networks
Hatano, Y., & Mesbahi, M. (2004) · 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601) · doi:10.1109/cdc.2004.1430343 · Cited by 550
Mean-Field Solution of the Small-World Network Model
Newman, M. E. J., Moore, C., & Watts, D. J. (2000) · Physical Review Letters · doi:10.1103/physrevlett.84.3201 · Cited by 407
Symmetry and phaselocking in chains of weakly coupled oscillators
Kopell, N., & Ermentrout, G. B. (1986) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.3160390504 · Cited by 315
Flocking with obstacle avoidance: cooperation with limited communication in mobile networks
Saber, R. O., & Murray, R. M. (2004) · 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475) · doi:10.1109/cdc.2003.1272912 · Cited by 310
Collision avoidance for multiple agent systems
Chang, D. E., Shadden, S. C., Marsden, J. E., & Olfati-Saber, R. (2004) · 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475) · doi:10.1109/cdc.2003.1272619 · Cited by 227
Self-citationSoshnikov, A. (2002) · Journal of Statistical Physics · doi:10.1023/a:1019739414239 · Cited by 227
Consensus of information under dynamically changing interaction topologies
Ren, W., & Beard, R. W. (2004) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2004.1384632 · Cited by 152
Leaderless coordination via bidirectional and unidirectional time-dependent communication
Moreau, L. (2004) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2003.1273094 · Cited by 79
Networks in life: Scaling properties and eigenvalue spectra
Farkas, I., Derenyi, I., Jeong, H., Neda, Z., Oltvai, Z. N., Ravasz, E., Schubert, A., Barabási, A.-Ĺ., & Vicsek, T. (2002) · Cited by 73
Mesbahi, M. (2004) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2003.1273092 · Cited by 52
Cited by
Consensus and Cooperation in Networked Multi-Agent Systems
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887293 · Cited by 10,522
Self-citationFlocking for Multi-Agent Dynamic Systems: Algorithms and Theory
Olfati-Saber, R. (2006) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.864190 · Cited by 5,037
Self-citationSynchronization in complex networks
Arenas, A., Díaz-Guilera, A., Kurths, J., Moreno, Y., & Zhou, C. (2008) · Physics Reports · doi:10.1016/j.physrep.2008.09.002 · Cited by 3,713
Finite-Time Consensus Problems for Networks of Dynamic Agents
Wang, L., & Xiao, F. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2041610 · Cited by 1,170
Distributed Kalman Filter with Embedded Consensus Filters
Olfati-Saber, R. (2006) · Proceedings of the 44th IEEE Conference on Decision and Control · doi:10.1109/cdc.2005.1583486 · Cited by 1,024
Self-citation
Metadata
- Authors
- Olfati-Saber, R.
- Venue
- Proceedings of the 2005, American Control Conference, 2005.
- Publisher
- IEEE
- Published
- 2005-08-10
- Pages
- 2371-2378
- ISSN
- 0743-1619 (ISSN-L)
- OpenAlex
- W2124620758
- Cited by
- 384
- References
- 38
- FWCI
- 33.81
- Type
- conference paper
- 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.