The DOI matches its Crossref record.
Random Graphs
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“Network analyses (Fig. 4c, see also Supplementary Notes) reveal that the mouse brain has a higher mean clustering coefficient (which gives the ratio of existing over possible connections), 0.42, than expected by a random network29,30 with identical sparseness, 0.12.”
From A mesoscale connectome of the mouse brain (2014) · cites this paper as [30]
Citations
Cited by
Sorted by citations
Items 801–900 of 998
A new dominance concept and its application to diversity-stability analysisPreprint
Ma, Z. S., & Ellison, A. M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.08835 · Cited by 18
On the Size-Ramsey Number of Cycles
Javadi, R., Khoeini, F., Omidi, G. R., et al. (2019) · Combinatorics Probability Computing · doi:10.1017/s0963548319000221 · Cited by 19
Percolation framework of the Earth's topography
Fan, J., Meng, J., & Saberi, A. A. (2019) · Physical review. E · doi:10.1103/physreve.99.022304 · Cited by 19
Coded Caching Over Multicast Routing Networks
Bayat, M., Wan, K., & Caire, G. (2021) · IEEE Transactions on Communications · doi:10.1109/tcomm.2021.3061678 · Cited by 19
Stability analysis of multiplayer games on adaptive simplicial complexes
Schlager, D., Clauß, K., & Kuehn, C. (2022) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/5.0078863 · Cited by 19
Criado, R., & Romance, M. (2011) · Springer optimization and its applications · doi:10.1007/978-1-4614-0857-4_1 · Cited by 20
Elimination of Subjectivity from Trust Recommendation
Hasan, O., Brunie, L., Pierson, J., et al. (2009) · IFIP advances in information and communication technology · doi:10.1007/978-3-642-02056-8_5 · Cited by 19
“We generate a simulated web of trust based on a random graph [30] as described in Figure 2.”
MethodThe Role of Nonlinear Relapse on Contagion Amongst Drinking Communities
Cintrón-Arias, A., Sánchez, F., Wang, X., et al. (2009) · Springer eBooks · doi:10.1007/978-90-481-2313-1_14 · Cited by 19
Zhang, H., Leung, C. H. C., & Raikundalia, G. K. (2007) · Springer eBooks · doi:10.1007/978-0-387-44641-7_3 · Cited by 19
Grimmett, G. (2008) · Progress in probability · doi:10.1007/978-3-7643-8786-0_15 · Cited by 19
Diffusion and cascading behavior in random networks
Lelarge, M. (2011) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2160803.2160852 · Cited by 19
“We define a random multigraph (allowing for self-loop and multiple links) with given degree sequence d, denoted by G(n, d) by the configuration model [1].”
MethodPhase transitions for modified Erdős–Rényi processes
Janson, S., & Spencer, J. (2011) · Arkiv för matematik · doi:10.1007/s11512-011-0157-1 · Cited by 19
Connectivity for Bridge-Addable Monotone Graph Classes
Addario‐Berry, L., McDiarmid, C., & Reed, B. A. (2012) · Combinatorics Probability Computing · doi:10.1017/s0963548312000272 · Cited by 19
On the stability of the independence number of a random subgraph
Raigorodskii, A. M. (2017) · Doklady Mathematics · doi:10.1134/s1064562417060266 · Cited by 19
Warnke, L. (2012) · Random Structures and Algorithms · doi:10.1002/rsa.20468 · Cited by 19
Extreme fluctuations in noisy task-completion landscapes on scale-free networks
Güçlü, H., Korniss, G., & Toroczkai, Z. (2007) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.2735446 · Cited by 19
Multicolored Hamilton Cycles and Perfect Matchings in Pseudorandom Graphs
Kühn, D., & Osthus, D. (2006) · SIAM Journal on Discrete Mathematics · doi:10.1137/050627010 · Cited by 19
Note on the Structure of Kruskal’s Algorithm
Broutin, N., Devroye, L., & McLeish, E. (2008) · Algorithmica · doi:10.1007/s00453-008-9164-4 · Cited by 19
“[14] or Bollobás [4]).”
BackgroundBollobás, B., & Riordan, O. M. (2009) · Random Structures and Algorithms · doi:10.1002/rsa.20270 · Cited by 19
Self-citationSimple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs
Raptopoulos, C., & Spirakis, P. G. (2005) · Lecture notes in computer science · doi:10.1007/11602613_50 · Cited by 19
Marinari, E., Semerjian, G., & Kerrebroeck, V. V. (2007) · Physical Review E · doi:10.1103/physreve.75.066708 · Cited by 19
“Random graph theory [1, 2, 3] is a fascinating branch of mathematics, at the frontier between classical graph theory and probability.”
An Integrative Semantic Framework for Image Annotation and Retrieval
Osman, T., Thakker, D., Schaefer, G., et al. (2007) · IEEE/WIC/ACM International Conference on Web Intelligence · doi:10.1109/wi.2007.69 · Cited by 19
Time evolution of continuous-time quantum walks on dynamical percolation graphs
Darázs, Z., & Kiss, T. (2013) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/46/37/375305 · Cited by 19
“tum walks [6]. Randomness in graph theory has been an ever developing field since the pioneering works by Erd˝os and R´enyi [7]. Today, there is a refined mathematical theory for treating random graphs [8] and, at the same time, statistical methods borrowed from physics continue to be a motor for research in random netw…”
BackgroundTowards supporting highly mobile nodes in decentralized mobile operator networks
Taleb, T., Samdanis, K., & Filali, F. (2012) · International Conference on Communications · doi:10.1109/icc.2012.6364192 · Cited by 18
“The Erdos-Renyi model [17], G(V,p) is used to create a random instance for the simulation topology with V = 60 number of eNBs and p = 0.”
MethodFacebook as a Small World: a topological hypothesis
Caci, B., Cardaci, M., & Tabacchi, M. E. (2011) · Social Network Analysis and Mining · doi:10.1007/s13278-011-0042-8 · Cited by 17
Zero-one laws for first-order formulas with a bounded quantifier depth
Zhukovskii, M. E. (2011) · Doklady Mathematics · doi:10.1134/s1064562411010054 · Cited by 18
Synchronization Probability in Large Complex Networks
Manaffam, S., & Seyedi, A. (2013) · IEEE Transactions on Circuits & Systems II Express Briefs · doi:10.1109/tcsii.2013.2277957 · Cited by 18
Topological data analysis of human brain networks through order statistics
Das, S., Anand, D. V., & Chung, M. K. (2023) · PLoS ONE · doi:10.1371/journal.pone.0276419 · Cited by 25
Quantum-like states on complex synchronized networks
Scholes, G. D. (2024) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2024.0209 · Cited by 24
Largest Components in Random Hypergraphs
Cooley, O., Kang, M., & Person, Y. (2018) · Combinatorics Probability Computing · doi:10.1017/s096354831800010x · Cited by 18
“[8, 12]) how the structure of the components changes as p (resp.”
BackgroundSmall-world graphs: characterization and alternative constructions
Rama Cont, A., & Tanimura, E. (2008) · Advances in Applied Probability · doi:10.1239/aap/1231340159 · Cited by 18
Spectral perturbation and reconstructability of complex networks
Liu, D., Wang, H., & Mieghem, P. V. (2010) · Physical Review E · doi:10.1103/physreve.81.016101 · Cited by 18
All normalized anti-monotonic overlap graph measures are bounded
Calders, T., Ramon, J., & Dyck, D. V. (2011) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-011-0217-y · Cited by 18
Randomized Graph Coloring Algorithm for Physical Cell ID Assignment in LTE-A Femtocellular Networks
Pratap, A., Misra, R., & Gupta, U. (2016) · Wireless Personal Communications · doi:10.1007/s11277-016-3522-3 · Cited by 18
Optimal Filter Design for Signal Processing on Random Graphs: Accelerated Consensus
Kruzick, S., & Moura, J. M. F. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2784359 · Cited by 18
“The simplest of these, the Erdős-Rényi model, consists of a network with N nodes in which links between each pair of nodes are included according to independent trials with some probability θ [32].”
MethodDigitally Annealed Solution for the Vertex Cover Problem with Application in Cyber Security
Javad-Kalbasi, M., Dabiri, K., Valaee, S., et al. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8683696 · Cited by 18
“We also studied the performance of Digital Annealer on Erdős Rényi random graphs [27] with | ν |= 64k (k = 1, 2, .”
MethodGraph Learning Under Partial Observability
Matta, V., Santos, A., & Sayed, A. H. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3013432 · Cited by 18
Hybrid evolutionary algorithms on minimum vertex cover for random graphs
Pelikán, M., Kalapala, R., & Hartmann, A. K. (2007) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1276958.1277073 · Cited by 18
On the Ramsey numbers for complete distance graphs with vertices in $ \{0,1\}^n$
Mikhailov, K. A., & Raigorodskii, A. M. (2009) · Sbornik Mathematics · doi:10.1070/sm2009v200n12abeh004059 · Cited by 18
Critical random graphs and the structure of a minimum spanning tree
Addario‐Berry, L., Broutin, N., & Reed, B. A. (2008) · Random Structures and Algorithms · doi:10.1002/rsa.20241 · Cited by 18
“These three phases correspond to p ∼ c/n for c lower than, equal to, or larger than one, respectively [3, 10, 20].”
BackgroundDiscrepancy in Graphs and Hypergraphs
Bollobás, B., & Scott, A. (2006) · Bolyai Society mathematical studies · doi:10.1007/978-3-540-32439-3_3 · Cited by 18
“Then by standard bounds on the tail of the binomial distribution (see [2], Theorem 1.”
BackgroundSelf-citationContinuum percolation with steps in an annulus
Balister, P., Bollobás, B., & Walters, M. (2004) · The Annals of Applied Probability · doi:10.1214/105051604000000891 · Cited by 18
Self-citationNetworks preserving evolutionary equilibria and the power of randomization
Kearns, M. J., & Suri, S. (2006) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1134707.1134729 · Cited by 18
“15 of [5] gives us that C ≥ (1− )n − 24 log n τ2 .”
BackgroundMethodInfluentialRobustness in large-scale random networks
Kim, M., & Médard, M. (2005) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2004.1354658 · Cited by 18
Large‐deviations/thermodynamic approach to percolation on the complete graph
Biskup, M., Chayes, L., & Smith, S. A. (2007) · Random Structures and Algorithms · doi:10.1002/rsa.20169 · Cited by 18
PLANTING COLOURINGS SILENTLYPreprint
Bapst, V., Coja‐Oghlan, A., & Efthymiou, C. (2016) · Cited by 18
Tree-structure expectation propagation for LDPC decoding over the BECPreprint
Olmos, P. M., & Murillo-Fuentes, J. J. (2013) · Cited by 18
On the Asymptotics of Constrained Exponential Random GraphsPreprint
Kenyon, R., & Yin, M. (2014) · Cited by 18
Return probabilities and hitting times of random walks on sparse Erdös-Rényi graphs
Martin, O., & Šulc, P. (2010) · Physical Review E · doi:10.1103/physreve.81.031111 · Cited by 17
Topology Enhancements in Wireless Multihop Networks: A Top-Down Approach
Stai, E., Karyotis, V. A., & Papavassiliou, S. (2011) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2011.250 · Cited by 16
“assumption is valid for Random Graphs (RGs) [21] and”
BackgroundEletreby, R., & Yağan, O. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2018.2808141 · Cited by 17
Bipartite graph structures for efficient balancing of heterogeneous loads
Leconte, M., Lelarge, M., & Massoulié, L. (2012) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2318857.2254764 · Cited by 17
Null Models and Community Detection in Multi-Layer Networks
Paul, S., & Chen, Y. (2021) · Sankhya A · doi:10.1007/s13171-021-00257-0 · Cited by 37
Anomalous biased diffusion in networks
Skarpalezos, L., Kittas, A., Argyrakis, P., et al. (2013) · Physical Review E · doi:10.1103/physreve.88.012817 · Cited by 17
Graph compression—save information by exploiting redundancy
Sun, J., Bollt, E. M., & ben‐Avraham, D. (2008) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2008/06/p06001 · Cited by 17
Designing Securely Connected Wireless Sensor Networks in the Presence of Unreliable Links
Yağan, O., & Makowski, A. M. (2011) · International Conference on Communications · doi:10.1109/icc.2011.5962806 · Cited by 17
On the Non-Planarity of a Random Subgraph
FRIEZE, A. M., & Krivelevich, M. (2013) · Combinatorics Probability Computing · doi:10.1017/s0963548313000308 · Cited by 17
“[1], that whp |V (G1)| ∼ xn and |E(G1)| ∼ cn(2x− x(2))/2 where x is the unique solution in (0, 1) to x = 1 − e.”
Nonconsensus opinion model on directed networks
Qu, B., Li, Q., Havlin, S., Stanley, E., & Wang, H. (2014) · Physical Review E · doi:10.1103/physreve.90.052811 · Cited by 17
“In order to examine how the directionality ξ influences the NCO model, we apply DIR to undirected network models to generate directed binomial networks, SF networks, and random regular (RR) networks6 [42] with directionality ranging over [0,1]. The NCO model is further simulated on each directed network instance. All s…”
MethodDo greedy assortativity optimization algorithms produce good results?
Winterbach, W., de Ridder, D., Wang, H., et al. (2012) · The European Physical Journal B · doi:10.1140/epjb/e2012-20899-2 · Cited by 17
“Erdős-Rényi networks [2] are a 2-parameter family of random networks denoted Gp(N).”
BackgroundSocial Network Analysis, Large-Scale
Batagelj, V. (2011) · Springer eBooks · doi:10.1007/978-1-4614-1800-9_177 · Cited by 18
Complex networks and activity spreading
Kuznetsov, O. P. (2015) · Automation and Remote Control · doi:10.1134/s0005117915120012 · Cited by 17
“More detailed information on the theory of random graphs can be found in the books [5, 13, 14].”
BackgroundDynamic Measure of Network Robustness
Singer, Y. (2006) · IEEE Convention of Electrical and Electronics Engineers in Israel · doi:10.1109/eeei.2006.321105 · Cited by 18
On the Clique and the Chromatic Numbers of High-Dimensional Distance Graphs
Raigorodskii, A. M., & Rubanov, O. I. (2009) · Hindustan Book Agency · doi:10.1007/978-93-86279-46-0_11 · Cited by 17
Projective networks : topologies for large parallel computer systems
Camarero, C., Martínez, C., Vallejo, E., et al. (2017) · UCrea (University of Cantabria) · doi:10.1109/tpds.2016.2635640 · Cited by 17
Sainudiin, R., Yogeeswaran, K., Nash, K. A., & Sahioun, R. (2019) · Social Network Analysis and Mining · doi:10.1007/s13278-019-0567-9 · Cited by 17
The Share Size of Secret-Sharing Schemes for Almost All Access Structures and Graphs
Beimel, A., & Farràs, O. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-64381-2_18 · Cited by 17
Near-Optimal Robust Virtual Controller Placement in 5G Software Defined Networks
Tohidi, E., Parsaeefard, S., Maddah-Ali, M. A., Khalaj, B. H., & Leon‐Garcia, A. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3068975 · Cited by 17
Tarzia, M. (2022) · Physical review. B./Physical review. B · doi:10.1103/physrevb.105.174201 · Cited by 17
Algorithms for channel assignment in mobile wireless networks using temporal coloring
Feng, Y., Bar-Noy, A., Basu, P., et al. (2013) · doi:10.1145/2507924.2507965 · Cited by 17
Beyond centrality—classifying topological significance using backup efficiency and alternative paths
Shavitt, Y., & Singer, Y. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/8/266 · Cited by 17
The evolution of subcritical Achlioptas processes
Riordan, O. M., & Warnke, L. (2014) · Random Structures and Algorithms · doi:10.1002/rsa.20530 · Cited by 17
Edge percolation on a random regular graph of low degree
Pittel, B. (2008) · The Annals of Probability · doi:10.1214/07-aop361 · Cited by 17
Nicaud, C. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44522-8_2 · Cited by 16
“Proving formally the experimental results such as those presented in [44], where non-deterministic automata are drawn under the Erdős-Rényi model for random graphs [11], would be an important first step in the analysis of the typical properties of random non-deterministic automata.”
BackgroundRainbow spanning trees in complete graphs colored by one‐factorizations
Horn, P. (2017) · Journal of Graph Theory · doi:10.1002/jgt.22160 · Cited by 17
On the length of a random minimum spanning tree
Cooper, C., FRIEZE, A. M., Ince, N., et al. (2018) · doi:10.1184/r1/6478898.v1 · Cited by 17
On the effect of very large nodes in Internet graphs
Reittu, H., & Norros, I. (2003) · IEEE Global Telecommunications Conference (GLOBECOM) · doi:10.1109/glocom.2002.1189105 · Cited by 17
An Alliance Based Peering Scheme for P2P Live Media Streaming
Purandare, D., & Guha, R. K. (2007) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2007.907453 · Cited by 17
THE CONTINUUM LIMIT OF DISCRETE GEOMETRIES
Requardt, M. (2006) · International Journal of Geometric Methods in Modern Physics · doi:10.1142/s0219887806001156 · Cited by 17
Wiuf, C., & Stumpf, M. P. H. (2006) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2005.1622 · Cited by 17
Diffusion of Innovations on Random Networks: Understanding the Chasm
Lelarge, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92185-1_25 · Cited by 17
Adding Structure to Unstructured Peer-to-Peer Networks: The Role of Overlay Topology
Merugu, S., Srinivasan, S., & Zegura, E. F. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-39405-1_8 · Cited by 17
Statistical mechanics of error exponents for error-correcting codes
Mora, T., & Rivoire, O. (2006) · Physical Review E · doi:10.1103/physreve.74.056110 · Cited by 17
Coloring Random Graphs — an Algorithmic Perspective
Krivelevich, M. (2002) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8211-8_11 · Cited by 17
The Dynamics of Organizational LearningPreprint
Huberman, B. A. (1997) · SSRN Electronic Journal · doi:10.2139/ssrn.49440 · Cited by 17
HOW LIKELY IS AN I.I.D. DEGREE SEQUENCE TO BE GRAPHICAL?Preprint
No., B., Arratia, R., & Liggett, T. M. (2005) · Cited by 17
Hierarchy in directed random networks
Mones, E. (2013) · Physical Review E · doi:10.1103/physreve.87.022817 · Cited by 16
The largest critical point in the zero-one k -law
Zhukovskii, M. E. (2015) · Sbornik Mathematics · doi:10.1070/sm2015v206n04abeh004467 · Cited by 16
Ranking a Set of Objects: A Graph Based Least-Square Approach
Christoforou, E., Nordio, A., Tarable, A., & Leonardi, E. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3053423 · Cited by 16
“The LS, WLS , and ML algorithms have been applied to randomly generated regular graphs [23] whose nodes have degree ρ = 6 (lines with square marker) and ρ = 12 (lines without markers).”
MethodNetwork Structure of the Master Clock Is Important for Its Primary Function
Gu, C., Li, J., Zhou, J., Yang, H., & Rohling, J. H. T. (2021) · Frontiers in Physiology · doi:10.3389/fphys.2021.678391 · Cited by 16
Exploring the topic evolution of Dunhuang murals through image classification
Zeng, Z., Sun, S., Li, T., Yin, J., Shen, Y., & Huang, Q. (2022) · Journal of Information Science · doi:10.1177/01655515221074336 · Cited by 17
Kiss, I. Z., Kenah, E., & Rempała, G. A. (2023) · Journal of Mathematical Biology · doi:10.1007/s00285-023-01967-9 · Cited by 15
Generating random graphs in biased Maker-Breaker games
Ferber, A., Krivelevich, M., & Naves, H. (2015) · Random Structures and Algorithms · doi:10.1002/rsa.20619 · Cited by 16
Neural complexity: A graph theoretic interpretation
Barnett, L., Buckley, C. L., & Bullock, S. (2011) · Physical Review E · doi:10.1103/physreve.83.041906 · Cited by 16
Data preservation under spatial failures in sensor networks
Azimi, N. H., Gupta, H., Hou, X., et al. (2010) · ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) · doi:10.1145/1860093.1860117 · Cited by 16
“It can be shown [7] that for successful recovery from a failure, there must be a matching between the set of destroyed data nodes and the set of surviving storage nodes that covers all the destroyed data nodes [3,4].”
BackgroundDouble-dealing behavior potentially promotes cooperation in evolutionary prisoner's dilemma games
Dai, Q., Li, H., Cheng, H., Li, Y., & Yang, J. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/11/113015 · Cited by 16
The small-community phenomenon in networks
Li, A., & PENG, P. (2012) · Mathematical Structures in Computer Science · doi:10.1017/s0960129511000570 · Cited by 18
Kupavskii, A. B. (2014) · Izvestiya Mathematics · doi:10.1070/im2014v078n01abeh002680 · Cited by 16
Moussawi, A., Derzsy, N., Lin, X. S., Szymanski, B. K., & Korniss, G. (2017) · Scientific Reports · doi:10.1038/s41598-017-11765-1 · Cited by 16
“we randomly choose two nodes with available edge stubs and connects them to form an edge. The process is repeated until all edge stubs are connected. Erd}os-Renyi (ER) graphs We construct ER graphs [44] of size Nby connecting every pair of nodes with probability p, parameter used to control the average degree of the n…”
MethodStatistical analysis of articulation points in configuration model networks
Tishby, I., Biham, O., Kühn, R., et al. (2018) · Physical review. E · doi:10.1103/physreve.98.062301 · Cited by 16
Privacy of Dependent Users Against Statistical Matching
Takbiri, N., Houmansadr, A., Goeckel, D., & Pishro-Nik, H. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.2985059 · Cited by 15
“[53] studied different algorithms such as maximum degree algorithms to match two identical graphs for the case where each edge of the graph has a fixed probability of being present or absent which is in the range of [ ω ( log n/n 5 ) , 1 − ω ( log n/n 5 )] , where n is the number of vertices in the graph.”
BackgroundMethod
Metadata
- 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
- 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
- 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
