Knowra Random graph Random graph A random graph is a graph sampled from a probability distribution over possible vertex sets or edge sets. Its randomness describes uncertainty about the graph, not necessarily randomness in a physical network.
Erdős–Rényi model : A random graph model in which edges are independently included with a fixed probability, or the graph has a fixed number of edges. Its independent-edge rule is the standard baseline for random graph generation.
Graph theory : The mathematical study of vertices, edges, and the structures formed by their connections. Random graphs are probability-distributed instances of the structures studied here.
Paul Erdős : A Hungarian mathematician known for major contributions to combinatorics, number theory, and probability. His work with Rényi established foundational probabilistic methods for graph structure.
Network science : An interdisciplinary field that studies the structure, dynamics, and function of networks. Random graphs provide baseline models for comparing observed network structure.
Small-world network : A network with short paths between vertices and usually stronger local clustering than a comparable random graph. Its combination of clustering and short paths exposes limits of basic random graphs.
Configuration model : A random graph construction that pairs prescribed vertex half-edges to produce a chosen degree sequence. It introduces degree variation that the basic independent-edge model does not control.
Probability theory : The mathematical study of random outcomes, probability distributions, and their consequences. A probability distribution over graphs supplies the defining randomness.
Alfréd Rényi : A Hungarian mathematician whose work shaped probability theory, information theory, and combinatorics. His joint papers with Erdős developed the classic random graph framework.
Social network analysis : The analysis of relationships among people, groups, or other social entities using network methods. Random graph null models help test whether social ties show nonrandom structure.
Scale-free network : A network whose degree distribution follows a power law over a substantial range. Heavy-tailed degrees differ sharply from the typical degrees of classic random graphs.
Show all 27