Cited by 2,639Limits and Structures in Graph TheoryComplex Network Analysis TechniquesStochastic processes and statistical mechanics

The DOI matches its Crossref record.

Random Graphs

Bollobás, Béla·2001·Cambridge University Press eBooks

DOI 10.1017/cbo9780511814068

Open this paper in CoChat — free account

Abstract

In this second edition of the now classic text, the already extensive treatment given in the first edition has been heavily revised by the author. The addition of two new sections, numerous new results and 150 references means that this represents a comprehensive account of random graph theory. The theory (founded by Erdös and Rényi in the late fifties) aims to estimate the number of graphs of a given degree that exhibit certain properties. It not only has numerous combinatorial applications, but also serves as a model for the probabilistic treatment of more complicated random structures. This book, written by an acknowledged expert in the field, can be used by mathematicians, computer scientists and electrical engineers, as well as people working in biomathematics. It is self-contained, and with numerous exercises in each chapter, is ideal for advanced courses or self study.

Integrity signals

Registry

Crossref · 10.1017/cbo9780511814068

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

Sorted by citations

Items 601–700 of 998

Global convergence of COVID-19 basic reproduction number and estimation from early-time SIR dynamicsPreprint
Katul, G. G., Mrad, A., Bonetti, S., et al. (2020) · medRxiv · doi:10.1101/2020.04.10.20060954 · Cited by 29
Diversity-Multiplexing Tradeoff in OFDMA Systems: An H-Matching Approach
Bai, B. B., Chen, W., Letaief, K. B., & Cao, Z. (2011) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2011.092011.101114 · Cited by 28
A lower-bound on the number of rankings required in recommender systems using collaborativ filtering
Marbach, P. (2008) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2008.4558538 · Cited by 28
Network inference from consensus dynamics
Segarra, S., Schaub, M. T., & Jadbabaie, A. (2017) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8264130 · Cited by 27
Model in SM of DEE Based on Service-Oriented Interactions at Dynamic Software Product Lines
Mkrttchian, V. S., Bershadsky, A. M., Bozhday, A., et al. (2015) · Advances in mobile and distance learning book series · doi:10.4018/978-1-4666-8119-4.ch014 · Cited by 28
Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdos-Rényi Graphs
Dai, O. E., Cullina, D., Kiyavash, N., et al. (2019) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3341617.3326151 · Cited by 28
“Note that d = o ( 1 ) for p 01 + p 10 ≤ o (cid:0) n − 2 (cid:1) , that problem, given in Theorem 3.17 in [26], is p = ω (cid:0) n − 1 / 5 log n (cid:1) , which corresponds to the region”
BackgroundInfluential
Adaptive-network models of collective dynamics
Zschaler, G. (2012) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2012-01648-5 · Cited by 28
“In order to understand the origin and the structure of networks, many simple models of network formation have been proposed. ey are typically formulated as constructive algorithms, which sample from an ensemble of networks satisfying certain constraints (Bollobás, 2001).”
Background
SWITCHER-RANDOM-WALKS: A COGNITIVE-INSPIRED MECHANISM FOR NETWORK EXPLORATION
Goñi, J., MARTINCORENA, I., Corominas‐Murtra, B., Arrondo, G., Ardanza-Trevijano, S., & Villoslada, P. (2010) · International Journal of Bifurcation and Chaos · doi:10.1142/s0218127410026204 · Cited by 36
“Full connectedness is hard to ensure in a pure random graph.”
Background
The Effect of Eavesdroppers on Network Connectivity: A Secrecy Graph Approach
Goel, S., Aggarwal, V., Yener, A., et al. (2011) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2011.2148714 · Cited by 28
“Similar results exist on connectivity in random graphs [22]; an area initiated by the work of Erdős and Réyni [23].”
Result
On the random graph induced by a random key predistribution scheme under full visibility
Yağan, O., & Makowski, A. M. (2008) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2008.4595045 · Cited by 28
Generative Data Models for Validation and Evaluation of Visualization Techniques
Schulz, C., Nocaj, A., El‐Assady, M., Frey, S., Hlawatsch, M., Hund, M., Karch, G. K., Netzel, R., Schätzle, C., Butt, M., et al. (2016) · Workshop on Beyond Time and Errors: Novel Evaluation Methods for Visualization · doi:10.1145/2993901.2993907 · Cited by 28
Analysis of an Iterated Local Search Algorithm for Vertex Coloring
Sudholt, D., & Zarges, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17517-6_31 · Cited by 28
Line-of-Sight Networks
FRIEZE, A. M., Kleinberg, J. M., Ravi, R., et al. (2008) · Combinatorics Probability Computing · doi:10.1017/s0963548308009334 · Cited by 28
Stability criteria for the contextual emergence of macrostates in neural networks
Graben, P. B., Barrett, A. B., & Harald Atmanspacher, A. (2009) · Network Computation in Neural Systems · doi:10.1080/09548980903161241 · Cited by 29
The phase transition in the uniformly grown random graph has infinite order
Bollobás, B., Janson, S., & Riordan, O. M. (2004) · Random Structures and Algorithms · doi:10.1002/rsa.20041 · Cited by 28
Self-citation
Synchronization landscapes in small-world-connected computer networks
Güçlü, H., Korniss, G., Novotny, M. A., Toroczkai, Z., & Ràcz, Z. (2006) · Physical Review E · doi:10.1103/physreve.73.066115 · Cited by 28
A Practical Minimal Perfect Hashing Method
Botelho, F. C., Kohayakawa, Y., & Ziviani, N. (2005) · Lecture notes in computer science · doi:10.1007/11427186_42 · Cited by 28
Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes
Chandran, L. S., Francis, M. C., & Sivadasan, N. (2008) · Algorithmica · doi:10.1007/s00453-008-9163-5 · Cited by 28
“As shown in [6], we can then carry over the result to the G(n, m) model since p = m/ (”
Background
On connectivity properties of large-scale sensor networks
Pishro-Nik, H., Chan, K., & Fekri, F. (2004) · doi:10.1109/sahcn.2004.1381952 · Cited by 28
“Related problems to graph theoretic results in this paper have been studied in the context of random graph theory [5], continuum percolation and geometric probability [6], [7], [8], [9], [10] and the study of wireless network graphs [11], [12], [13], [14], [15], [16], [17].”
Background
On connectivity thresholds in superposition of random key graphs on random geometric graphs
Krishnan, B. S., Ganesh, A. J., & Manjunath, D. (2013) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2013.6620654 · Cited by 27
Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
Bogolyubskii, L. I., Гусев, А. С., Pyaderkin, M. M., et al. (2014) · Doklady Mathematics · doi:10.1134/s1064562414050147 · Cited by 27
Chromatic numbers of real and rational spaces with real or rational forbidden distances
Raigorodskii, A. M., & Шитова, И. М. (2008) · Sbornik Mathematics · doi:10.1070/sm2008v199n04abeh003934 · Cited by 27
Information diffusion in overlaying social-physical networks
Yağan, O., Qian, D., Zhang, J., et al. (2012) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2012.6310749 · Cited by 27
A Unified Matching Framework for Multi-Flow Decode-and-Forward Cooperative Networks
Bai, B. B., Chen, W., Letaief, K. B., et al. (2012) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2012.120219 · Cited by 27
On Resource Reuse for Cellular Networks with Femto- and Macrocell Coexistence
Shi, Y., MacKenzie, A. B., DaSilva, L. A., et al. (2010) · IEEE Global Telecommunications Conference (GLOBECOM) · doi:10.1109/glocom.2010.5683443 · Cited by 27
Modularity affects the robustness of scale-free model and real-world social networks under betweenness and degree-based node attack
Nguyen, Q., Vu, T. V., Dinh, H.-D., Cassi, D., Scotognella, F., Alfieri, R., & Bellingeri, M. (2021) · Applied Network Science · doi:10.1007/s41109-021-00426-y · Cited by 28
Emotional Contagion in Physical–Cyber Integrated Networks: The Phase Transition Perspective
Zhang, G., Lu, D., & Jia, X. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3052766 · Cited by 26
Social nucleation: Group formation as a phase transition
Schweitzer, F., & Andres, G. (2022) · Physical review. E · doi:10.1103/physreve.105.044301 · Cited by 26
Testing community structure for hypergraphs
Yuan, M., Liu, R., Feng, Y., & Shang, Z. (2022) · The Annals of Statistics · doi:10.1214/21-aos2099 · Cited by 37
Extremal Results in Random Graphs
Rödl, V., & Schacht, M. (2013) · Bolyai Society mathematical studies · doi:10.1007/978-3-642-39286-3_20 · Cited by 27
Counting connected graphs and hypergraphs via the probabilistic method
Coja‐Oghlan, A., Moore, C., & Sanwalani, V. (2007) · Random Structures and Algorithms · doi:10.1002/rsa.20160 · Cited by 27
Stochastic processes in random graphs
Puhalskii, A. A. (2005) · The Annals of Probability · doi:10.1214/009117904000000784 · Cited by 27
Consensus and synchronization problems on small-world networks
Gu, L., Zhang, X., & Zhou, Q. (2010) · Journal of Mathematical Physics · doi:10.1063/1.3456080 · Cited by 27
The effect of multi-radio nodes on network connectivity -- a graph theoretic analysis
Faragó, A., & Basagni, S. (2008) · IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) · doi:10.1109/pimrc.2008.5173153 · Cited by 27
Sharding social networks
Duong, Q., Goel, S., Hofman, J. M., et al. (2013) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/2433396.2433424 · Cited by 27
“Bollobás [3] that Erdos-Renyi graphs do not contain large, isolated sets of nodes (Theorem 3).”
Background
An evolutionary model of social networks
Ludwig, M., & Abell, P. (2007) · The European Physical Journal B · doi:10.1140/epjb/e2007-00200-x · Cited by 27
Modeling ad hoc sensor networks using random graph theory
Kawahigashi, Y. T. H. (2005) · doi:10.1109/ccnc.2005.1405152 · Cited by 27
Spectrum of Markov Generators on Sparse Random Graphs
Bordenave, C., Caputo, P., & Chafaï, D. (2013) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21496 · Cited by 27
Choosing from a large tournament
Fey, M. (2007) · Social Choice and Welfare · doi:10.1007/s00355-007-0279-3 · Cited by 27
Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
Galvin, D., & Tetali, P. (2005) · Random Structures and Algorithms · doi:10.1002/rsa.20094 · Cited by 27
LDPC Codes Achieve List Decoding Capacity
Mosheiff, J., Resch, N., Ron‐Zewi, N., et al. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00050 · Cited by 27
A phase transition for avoiding a giant component
Bohman, T., & Kim, J. H. (2005) · Random Structures and Algorithms · doi:10.1002/rsa.20085 · Cited by 27
Numerical evaluation of the upper critical dimension of percolation in scale-free networks
Wu, Z., Lagorio, C., Braunstein, L. A., et al. (2007) · Physical Review E · doi:10.1103/physreve.75.066110 · Cited by 27
Leveraging multi-AP diversity for transmission resilience in wireless networks: architecture and performance analysis
Zhu, Y., Zhang, Q., Niu, Z., et al. (2009) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2009.060157 · Cited by 27
Gradient networks
Toroczkai, Z., Kozma, B., Bassler, K. E., Hengartner, N., & Korniss, G. (2008) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/41/15/155103 · Cited by 27
The Small World Network Structure of Boards of DirectorsPreprint
Conyon, M. J., & Muldoon, M. R. (2004) · SSRN Electronic Journal · doi:10.2139/ssrn.546963 · Cited by 27
𝓁_p-Spread and Restricted Isometry Properties of Sparse Random MatricesPreprint
Guruswami, V., Manohar, P., & Mosheiff, J. (2022) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2022.7 · Cited by 27
Cost and profit driven cloud-P2P interaction
Chakareski, J. (2013) · Peer-to-Peer Networking and Applications · doi:10.1007/s12083-013-0235-1 · Cited by 26
Случайные графы: модели и предельные характеристики
Zhukovskii, M. E., & Raigorodskii, A. M. (2015) · Успехи математических наук · doi:10.4213/rm9626 · Cited by 26
Distribution of shortest path lengths in subcritical Erdős-Rényi networks
Katzav, E., Biham, O., & Hartmann, A. K. (2018) · Physical review. E · doi:10.1103/physreve.98.012301 · Cited by 27
Vulnerability studies in the fields of transportation and complex networks: a citation network analysis
Sugishita, K., & Asakura, Y. (2020) · Public Transport · doi:10.1007/s12469-020-00247-9 · Cited by 28
SSE and SSD: Page-Efficient Searchable Symmetric Encryption
Bossuat, A., Bost, R., Fouque, P.-A., et al. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-84252-9_6 · Cited by 26
Quantum Approximate Optimization Algorithm Pseudo-Boltzmann States
Díez-Valle, P., Porras, D., & García‐Ripoll, J. J. (2023) · Physical Review Letters · doi:10.1103/physrevlett.130.050601 · Cited by 32
A proof of the Kahn–Kalai conjecture
Park, J., & Pham, H. T. (2023) · Journal of the American Mathematical Society · doi:10.1090/jams/1028 · Cited by 26
Equilibrium Statistical Mechanicsof Network Structures
Farkas, I. J., Derényi, I., Palla, G., & Vicsek, T. (2004) · Lecture notes in physics · doi:10.1007/978-3-540-44485-5_8 · Cited by 26
Thickness, relative hyperbolicity, and randomness in Coxeter groups
Behrstock, J., Hagen, M., & Sisto, A. (2017) · Algebraic & Geometric Topology · doi:10.2140/agt.2017.17.705 · Cited by 30
GENERATING AN ASSORTATIVE NETWORK WITH A GIVEN DEGREE DISTRIBUTION
Zhou, J., Xu, X.-K., Zhang, J., et al. (2008) · International Journal of Bifurcation and Chaos · doi:10.1142/s0218127408022536 · Cited by 26
A random graph model of kidney exchanges
Toulis, P., & Parkes, D. C. (2011) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1993574.1993626 · Cited by 25
Distributed computation of node and edge betweenness on tree graphs
Wang, W., & Tang, C. Y. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6759856 · Cited by 24
Toward $k$ -Connectivity of the Random Graph Induced by a Pairwise Key Predistribution Scheme With Unreliable Links
Yavuz, F., Zhao, J., Yağan, O., et al. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2471295 · Cited by 26
“, n} [2].”
BackgroundMethod
Streaming Graph Partitioning in the Planted Partition Model
Tsourakakis, C. E. (2015) · doi:10.1145/2817946.2817950 · Cited by 26
Loops and Self-Reference in the Construction of Dictionaries
Levary, D., Eckmann, J., Moses, E., et al. (2012) · Physical Review X · doi:10.1103/physrevx.2.031018 · Cited by 26
“The strongly connected nature of the core suggests that definitional loops play an important role in shaping the underlying topology of the dictionary graph.”
Background
Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
Bogolubsky, L. I., Гусев, А. С., Pyaderkin, M. M., et al. (2015) · Sbornik Mathematics · doi:10.1070/sm2015v206n10abeh004498 · Cited by 26
Distribution of shortest path lengths in a class of node duplication network models
Steinbock, C., Biham, O., & Katzav, E. (2017) · Physical review. E · doi:10.1103/physreve.96.032301 · Cited by 25
“Central measures of the DSPL such as the mean distance and extremal measures such as the diameter were studied [15, 24–27].”
MethodResultInfluential
Distribution of shortest cycle lengths in random networks
Bonneau, H., Hassid, A., Biham, O., et al. (2017) · Physical review. E · doi:10.1103/physreve.96.062307 · Cited by 26
Avoiding small subgraphs in Achlioptas processes
Krivelevich, M., Loh, P., & Sudakov, B. (2008) · Random Structures and Algorithms · doi:10.1002/rsa.20254 · Cited by 26
The order of the giant component of random hypergraphs
Behrisch, M., Coja‐Oghlan, A., & Kang, M. (2009) · Random Structures and Algorithms · doi:10.1002/rsa.20282 · Cited by 26
The degree sequences and spectra of scale‐free random graphs
Jordan, J. (2005) · Random Structures and Algorithms · doi:10.1002/rsa.20101 · Cited by 26
The t-Improper Chromatic Number of Random Graphs
Kang, R. J., & McDiarmid, C. (2009) · Combinatorics Probability Computing · doi:10.1017/s0963548309990216 · Cited by 26
“For further background into the colouring of random graphs, consult [3,9].”
Using Gossips to Spread Information: Theory and Evidence from Two Randomized Controlled TrialsPreprint
Banerjee, A. V., Chandrasekhar, A. G., Duflo, E., et al. (2014) · SSRN Electronic Journal · doi:10.2139/ssrn.2425379 · Cited by 26
Dynamic energy-aware network re-configuration for cellular urban infrastructures
Samdanis, K., Kutscher, D., & Brunner, M. (2010) · IEEE Globecom Workshops (GC Wkshps) · doi:10.1109/glocomw.2010.5700178 · Cited by 25
“The Erdós - Rényi model [11], G(V,p) is used to create a random instance for the simulation topology with V = 40 number of cells and probability of adjacency between two cells p = 0.”
Method
Consensus Over Random Graph Processes: Network Borel–Cantelli Lemmas for Almost Sure Convergence
Shi, G., Anderson, B. D. O., & Johansson, K. H. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2468584 · Cited by 25
Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов
Bogolubsky, L. I., Гусев, А. С., Pyaderkin, M. M., et al. (2015) · Математический сборник · doi:10.4213/sm8344 · Cited by 25
A pliable index coding approach to data shuffling
Song, L., Fragouli, C., & Zhao, T. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006991 · Cited by 25
The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
Pontiveros, G. F., Griffiths, S., & Morris, R. (2020) · Memoirs of the American Mathematical Society · doi:10.1090/memo/1274 · Cited by 25
Embedded Test Decompressor to Reduce the Required Channels and Vector Memory of Tester for Complex Processor Circuit
Han, Y., Hu, Y. H., Li, X., et al. (2007) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/tvlsi.2007.893652 · Cited by 25
On Optimizing Overlay Topologies for Search in Unstructured Peer-to-Peer Networks
Hsiao, H., & Su, H.-W. (2011) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2011.241 · Cited by 25
Bounds on the Generalised Acyclic Chromatic Numbers of Bounded Degree Graphs
Greenhill, C., & Pikhurko, O. (2005) · Graphs and Combinatorics · doi:10.1007/s00373-005-0635-y · Cited by 25
Online HodgeRank on Random Graphs for Crowdsourceable QoE Evaluation
Xu, Q., Xiong, J., Huang, Q., & Yao, Y. (2014) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2013.2292568 · Cited by 24
“Random graph is a graph generated by some random process [16], [41].”
Background
Interference Alignment in Dense Wireless Networks
Niesen, U. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2119690 · Cited by 25
Sampling for Conditional Inference on Network Data
Zhang, J., & Chen, Y. (2013) · Journal of the American Statistical Association · doi:10.1080/01621459.2012.758587 · Cited by 25
How complex are random graphs in first order logic?
Kim, J. H., Pikhurko, O., Spencer, J., et al. (2004) · Random Structures and Algorithms · doi:10.1002/rsa.20049 · Cited by 25
Localization and Universality of Eigenvectors in Directed Random Graphs
Metz, F. L., & Neri, I. (2021) · Physical Review Letters · doi:10.1103/physrevlett.126.040604 · Cited by 29
Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
Zhang, P., Zeng, Y., & Zhou, H. (2009) · Physical Review E · doi:10.1103/physreve.80.021122 · Cited by 25
Multi-level analysis of an interaction network between individuals in a mailing-list
Dorat, R., Matthieu Latapy, B., Conein, B., & Auray, N. (2007) · Annals of Telecommunications · doi:10.1007/bf03253264 · Cited by 24
Edge percolation on a random regular graph of low degreePreprint
Pittel, B. G., Jimmy, D. T., & Lyons, K. (2008) · Cited by 25
Supporting Highly Mobile Users in Cost-Effective Decentralized Mobile Operator Networks
Taleb, T., Samdanis, K., & Ksentini, A. (2014) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2014.2299633 · Cited by 24
The Energy of Random Graphs
Li, X., Shi, Y., & Gutman, İ. (2012) · Springer eBooks · doi:10.1007/978-1-4614-4220-2_6 · Cited by 24
Exploring the Characteristics of Innovation Adoption in Social Networks: Structure, Homophily, and Strategy
Li, Y., Wu, C., Luo, P., & Zhang, W. (2013) · Entropy · doi:10.3390/e15072662 · Cited by 26
Wireless Sensor Networks Under the Random Pairwise Key Predistribution Scheme: Can Resiliency Be Achieved With Small Key Rings?
Yağan, O., & Makowski, A. M. (2016) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2016.2527742 · Cited by 24
Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction
Ding, C., & Qi, H. (2016) · Mathematical Programming · doi:10.1007/s10107-016-1090-7 · Cited by 24
“Other properties such as the degree distribution, the connectivity, the diameters of the Bernoulli random graph, can be found in (e.g., Bollob´as, 2001; Janson et al., 2011).”
Background
Linear stability analysis of large dynamical systems on random directed graphs
Neri, I., & Metz, F. L. (2020) · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · Cited by 24
Network structure from a characterization of interactions in complex systems
Rings, T., Bröhl, T., & Lehnertz, K. (2022) · Scientific Reports · doi:10.1038/s41598-022-14397-2 · Cited by 26
Basic Types of Coarse-Graining
Gorban, A. N. (2006) · Springer eBooks · doi:10.1007/3-540-35888-9_7 · Cited by 26
On large‐girth regular graphs and random processes on trees
Backhausz, Á., & Szegedy, B. (2018) · Random Structures and Algorithms · doi:10.1002/rsa.20769 · Cited by 24
Local Limit Theorems for the Giant Component of Random Hypergraphs
Behrisch, M., Coja‐Oghlan, A., & Kang, M. (2014) · Combinatorics Probability Computing · doi:10.1017/s0963548314000017 · Cited by 24
Sampling networks from their posterior predictive distribution
Goyal, R., Blitzstein, J. K., & Gruttola, V. D. (2014) · Network Science · doi:10.1017/nws.2014.2 · Cited by 22
Distributed data storage in sensor networks using decentralized erasure codes
Dimakis, A. G., Prabhakaran, V. M., & Ramchandran, K. (2005) · 2018 52nd Asilomar Conference on Signals, Systems, and Computers · doi:10.1109/acssc.2004.1399381 · Cited by 24
Structural symmetry in evolutionary games
McAvoy, A., & Hauert, C. (2015) · Journal of The Royal Society Interface · doi:10.1098/rsif.2015.0420 · Cited by 23
“Lieberman et al. (2005) show that this fixation probability is independent of the location of the mutant if everyone has the same number of neighbors, i.e. the graph is regular (Bollobás, 2001).”
BackgroundMethod
Explicit Near-Ramanujan Graphs of Every Degree
Mohanty, S., O’Donnell, R., & Paredes, P. (2020) · SIAM Journal on Computing · doi:10.1137/20m1342112 · Cited by 24

Authors: Bollobás, B.
Affiliations: University of Memphis (US)
Corresponding author: Bollobás, Béla
ORCID: Bollobás, Béla
Venue: Cambridge University Press eBooks
Publisher: Cambridge University Press
Published: 2001-08-30
DOI: 10.1017/cbo9780511814068
OpenAlex: W390146837
Cited by: 2,639
References: 0
Citations by year: 2026: 37 · 2025: 68 · 2024: 79 · 2023: 82 · 2022: 126 · 2021: 136 · 2020: 137 · 2019: 111 · 2018: 108 · 2017: 138 · 2016: 138 · 2015: 129 · 2014: 136 · 2013: 135 · 2012: 151
FWCI: 6.29
Type: book
Language: en
Open access: closed
Licence: www.cambridge.org/core/terms (unspecified, 3498 d)
Locations: Cambridge University Press eBooks (publishedVersion)
Topics: Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Limits and Structures in Graph Theory
Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
Physical Sciences › Mathematics › Mathematical Physics › Stochastic processes and statistical mechanics
Keywords: random graphs, Erdős-Rényi random graphs, degree sequences, probabilistic combinatorics, random structures, graph enumeration

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

Random Graphs

Abstract

Overview

Integrity signals

Verification

Claims the paper makes

Claims other papers make about this one

Citations

Cited by

Related

Metadata

Record

About these checks