Erdős–Rényi random graph

GPTKB entity

Statements (49)
Predicate Object
gptkbp:instanceOf random graph model
gptkbp:application gptkb:percolation_theory
computer science
social network analysis
epidemic modeling
modeling random networks
gptkbp:describes random graphs with n vertices
gptkbp:edgeCount M
gptkbp:edgeProbability p
gptkbp:field gptkb:probability_theory
graph theory
gptkbp:G(n,_M) graph with n vertices and M edges chosen uniformly at random
gptkbp:G(n,_p) graph with n vertices, each edge included independently with probability p
gptkbp:hasDegreeDistribution Poisson (in large n limit)
binomial
gptkbp:hasLimitingBehavior appearance of cycles
emergence of connected component
giant component appears at p = 1/n
graph becomes connected at p = (log n)/n
gptkbp:hasModel G(n, M)
G(n, p)
gptkbp:hasNoMultipleEdges true
gptkbp:hasNoSelfLoops true
https://www.w3.org/2000/01/rdf-schema#label Erdős–Rényi random graph
gptkbp:introducedIn 1959
gptkbp:isSimpleGraph true
gptkbp:isUndirected true
gptkbp:isUnweighted true
gptkbp:namedAfter gptkb:Paul_Erdős
gptkb:Alfréd_Rényi
gptkbp:parameter M
n
p
gptkbp:property phase transition
Poisson degree distribution
giant component
threshold functions
gptkbp:publishedIn gptkb:On_Random_Graphs_I
gptkb:On_the_Evolution_of_Random_Graphs
gptkbp:relatedTo gptkb:Barabási–Albert_model
gptkb:Gilbert_random_graph
random regular graph
small-world network
gptkbp:usedIn combinatorics
statistical physics
network science
gptkbp:vertices n
gptkbp:bfsParent gptkb:Paul_Erdős
gptkbp:bfsLayer 4