Glossary

12.2 Random graphs and their properties

3 min read•august 9, 2024

are mathematical models that generate networks with specific properties. They help us understand complex systems in the real world, from social networks to biological structures. These models provide insights into how network structures emerge and evolve.

This section explores two key random graph models: Erdős–Rényi and Gilbert. We'll dive into their characteristics, connectivity thresholds, and the emergence of giant components. We'll also look at graph coloring, cliques, and the in networks.

Random Graph Models

Erdős–Rényi and Gilbert Models

Top images from around the web for Erdős–Rényi and Gilbert Models

  • Survey on graph embeddings and their applications to machine learning problems on graphs [PeerJ] View original

    Is this image relevant?

  • Survey on graph embeddings and their applications to machine learning problems on graphs [PeerJ] View original

    Is this image relevant?

1 of 2

Top images from around the web for Erdős–Rényi and Gilbert Models

  • Survey on graph embeddings and their applications to machine learning problems on graphs [PeerJ] View original

    Is this image relevant?

  • Survey on graph embeddings and their applications to machine learning problems on graphs [PeerJ] View original

    Is this image relevant?

1 of 2
  • generates random graphs with fixed number of vertices and edges
    • Denoted as G(n,m) where n is number of vertices and m is number of edges
    • Selects graph uniformly at random from all possible graphs with n vertices and m edges
    • Useful for studying average-case behavior of graph algorithms
  • produces random graphs based on
    • Represented as G(n,p) where n is number of vertices and p is probability of edge existence
    • Each potential edge exists independently with probability p
    • Allows for varying and connectivity in generated graphs
  • Both models create graphs with similar for large n
    • Expected number of edges in Gilbert model E[∣E∣]=(n2)pE[|E|] = \binom{n}{2}p
    • Probability distribution of edge count in Gilbert model follows binomial distribution

Connectivity Threshold

  • determines probability at which random graph becomes connected
  • For Erdős–Rényi model G(n,m), threshold occurs when m ≈ ½n log n
  • In Gilbert model G(n,p), threshold happens when p ≈ log n / n
  • Below threshold, graph likely consists of multiple disconnected components
  • Above threshold, graph becomes increasingly likely to be fully connected
  • applies to various graph properties (clique formation, )

Graph Components and Properties

Giant Component and Connectivity

  • emerges in random graphs as size and edge density increase
    • Largest connected subgraph containing a significant fraction of all vertices
    • Appears suddenly at a critical threshold in edge probability or density
    • In G(n,p) model, giant component emerges when np > 1
  • Connectivity of random graphs influenced by edge probability
    • Low p results in many small, disconnected components
    • As p increases, components merge and giant component forms
    • Further increase in p leads to fully connected graph

Graph Coloring and Cliques

  • represents size of largest complete subgraph in a graph
    • Increases with edge probability in random graphs
    • For G(n,p), expected clique number ≈ 2 log n / log(1/p) for large n
  • indicates minimum number of colors needed to color graph vertices
    • No adjacent vertices share same color
    • In random graphs, chromatic number grows with edge density
    • For G(n,1/2), chromatic number ≈ n / (2 log n) with high probability

Graph Diameter

  • Diameter measures maximum shortest path length between any two vertices
  • In random graphs, diameter tends to be small relative to graph size
    • For G(n,p) with p > (1 + ε) log n / n, diameter ≈ log n / log(np) with high probability
  • Diameter shrinks as edge probability increases
    • Dense random graphs have smaller diameters than sparse ones
  • Studying diameter helps understand information spread and network efficiency

Network Phenomena

Small-World Phenomenon

  • Small-world phenomenon describes short average path lengths in large networks
    • Popularized by "six degrees of separation" concept in social networks
    • Observed in various real-world networks (social, biological, technological)
  • Random graphs often exhibit small-world properties
    • grows logarithmically with network size
    • In G(n,p) model, average path length ≈ log n / log(np) for p > log n / n
  • measures local connectivity in networks
    • Random graphs typically have low clustering coefficients
    • Real-world networks often combine short path lengths with high clustering
  • Watts-Strogatz model generates graphs with small-world properties
    • Interpolates between regular lattices and random graphs
    • Produces networks with high clustering and short average path lengths

Key Terms to Review (16)

Average path length: Average path length is a measure used in graph theory that quantifies the average number of edges in the shortest path connecting any two vertices in a graph. It provides insight into how easily information or resources can be transferred across a network, which is essential for understanding the connectivity and efficiency of random graphs and their properties.
Chromatic Number: The chromatic number of a graph is the smallest number of colors needed to color the vertices of the graph so that no two adjacent vertices share the same color. This concept is crucial in graph theory and has significant implications in various applications, including scheduling problems, map coloring, and resource allocation.
Clique number: The clique number of a graph is defined as the size of the largest complete subgraph within that graph. This term is crucial when analyzing random graphs, as it helps determine how densely connected the vertices are, impacting various properties such as connectivity and colorability. Understanding the clique number aids in exploring the overall structure of a graph, revealing insights about its potential configurations and the behavior of networks.
Clustering Coefficient: The clustering coefficient is a measure that quantifies the degree to which nodes in a graph tend to cluster together. It indicates how well-connected a node's neighbors are to each other, reflecting the presence of tightly knit groups within a network. A high clustering coefficient suggests that the network has many triangles, meaning that if two nodes are connected to a common node, they are likely to be connected to each other as well.
Connectivity threshold: The connectivity threshold refers to the critical point in a random graph where the likelihood of the graph being connected significantly increases as the number of edges or vertices grows. Below this threshold, the graph is likely to be fragmented into several disconnected components, while above it, a giant component typically emerges that connects a substantial portion of the graph, influencing properties like robustness and network dynamics.
Edge density: Edge density is a measure that indicates the proportion of edges in a graph relative to the maximum possible number of edges. It is calculated by dividing the number of actual edges by the total number of possible edges in a graph, giving insight into how connected the graph is. This concept is important for understanding properties of random graphs, as it helps determine how likely certain structures and behaviors will appear as the number of vertices grows.
Edge probability: Edge probability is the likelihood that a particular edge will exist between two vertices in a random graph. This concept is central to understanding random graphs, as it influences their structural properties, such as connectivity and the presence of specific subgraphs. In random graph models, this probability can be fixed or can vary based on certain parameters, leading to different types of graph behavior and characteristics.
Erdős–rényi model: The Erdős–Rényi model is a foundational framework in probability theory and combinatorics that describes how random graphs are generated. In this model, a graph is formed by taking a set of 'n' vertices and connecting them with edges, where each edge is included with a certain probability 'p'. This concept helps in understanding the emergence of random structures and their properties.
Giant Component: A giant component is a large connected subgraph that emerges in a network when the number of edges exceeds a certain threshold, resulting in a significant fraction of vertices being part of this large cluster. This phenomenon is crucial for understanding the structure and behavior of networks, as it signifies the presence of connectivity and robustness within random graphs and other combinatorial structures.
Gilbert Model: The Gilbert Model is a fundamental random graph model that helps to understand the formation and properties of graphs by randomly adding edges between a set of vertices. It serves as a basis for studying random graphs, particularly focusing on how the structure of these graphs evolves as edges are added, leading to different connectivity properties and phase transitions.
Graph diameter: The graph diameter is the longest distance between any pair of vertices in a graph, measured in terms of the number of edges in the shortest path connecting them. This concept is crucial for understanding the overall structure and efficiency of a graph, particularly in random graphs, where the relationships between vertices can significantly influence properties like connectivity and clustering.
Hamiltonian Cycles: A Hamiltonian cycle is a closed loop within a graph that visits every vertex exactly once and returns to the starting vertex. Understanding Hamiltonian cycles is crucial when analyzing the properties of graphs, especially in random graphs, where the likelihood of such cycles occurring can vary dramatically based on graph density and structure.
Random graphs: Random graphs are mathematical structures that model networks where edges between vertices are formed randomly, allowing for the analysis of their properties and behaviors under various probabilistic conditions. These graphs provide insights into the behavior of complex networks in real-world applications, such as social networks, biological systems, and computer networks, and facilitate the understanding of various combinatorial structures.
Small-world phenomenon: The small-world phenomenon refers to the idea that in a large network, most nodes can be reached from any other node through a surprisingly small number of steps. This concept is crucial in understanding how random graphs behave, highlighting properties like clustering and the average path length between nodes, which can lead to unexpected shortcuts in large networks.
Statistical properties: Statistical properties are characteristics that describe the behavior and structure of random graphs through numerical measures. These properties help to analyze how graphs change as their size or edge density varies, revealing insights about connectivity, clustering, and other structural features. Understanding these statistical properties is essential for examining the relationships and patterns formed within random graphs.
Threshold behavior: Threshold behavior refers to a dramatic change in the properties of a random graph when a certain parameter crosses a critical value. This behavior is significant in understanding how the structure of networks transitions from one regime to another, affecting connectivity, component sizes, and the emergence of large subgraphs as parameters like edge density vary.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide