Appendix - Brief Introduction to igraph

Author

Sadamori Kojaku

Published

August 14, 2025

1 Erdős-Rényi Random Graphs

The Erdős-Rényi random graph model is one of the fundamental models in network science, serving as our baseline for understanding what makes small-world networks special. There are two variants of this model: G(n,m) which creates n vertices with exactly m randomly chosen edges, and G(n,p) which creates n vertices where each possible edge exists with probability p. We focus on the G(n,p) model because it provides better analytical tractability for deriving mathematical properties.

Figure 1: Erdős-Rényi random graph model.

2 Clustering Coefficient

The clustering coefficient measures the probability that two neighbors of a node are also connected to each other. For Erdős-Rényi random graphs, we can derive the expected clustering coefficient analytically by exploiting the independence of edge formation.

Consider a node i with degree k_i in an Erdős-Rényi graph G(n,p). The local clustering coefficient is defined as C_i = \frac{2e_i}{k_i(k_i-1)}, where e_i is the number of edges between neighbors of node i. The key insight is that in the G(n,p) model, each possible edge exists with probability p independently of all other edges.

For a node with k neighbors, there are \binom{k}{2} = \frac{k(k-1)}{2} possible edges between its neighbors. Since each potential edge exists with probability p, the expected number of edges between neighbors is E[e_i | k_i = k] = \frac{k(k-1)}{2} \cdot p. Therefore, the expected local clustering coefficient for a node with degree k becomes:

E[C_i | k_i = k] = \frac{2 \cdot \frac{k(k-1)}{2} \cdot p}{k(k-1)} = p

This result shows that the expected local clustering coefficient is simply p, independent of the node degree. Since this holds for all vertices regardless of their degree, the expected global clustering coefficient is also E[C] = p = \frac{\langle k \rangle}{n-1}, where \langle k \rangle = p(n-1) is the expected degree.

3 Average Path Length Derivation

The average path length in Erdős-Rényi graphs can be derived using a tree-expansion argument that reveals why these networks exhibit the small-world property of short distances.

Consider an Erdős-Rényi model with average degree k = p(n-1). We can analyze the network structure by imagining a breadth-first expansion from any starting node, treating the resulting structure as a tree (this approximation works well because triangles and cycles are rare in sparse random graphs). From the root node, we can reach approximately 1 + k nodes in the first step. In the second step, each of these k nodes connects to roughly k new nodes (avoiding already-visited nodes), giving us 1 + k + k^2 total reachable nodes. Continuing this pattern, after h steps we can reach approximately 1 + k + k^2 + \ldots + k^h \approx k^h nodes.

The critical insight is that since Erdős-Rényi random graphs have few triangles and local clusters, most nodes in the network are reached only at the final step of this expansion process. When the expansion covers the entire network, we have k^h \approx n. Solving for h: h \approx \log_{k}(n) = \frac{\log(n)}{\log(k)} = \frac{\log(n)}{\log(p(n-1))}.

This derivation reveals that the average shortest path length (diameter) of an Erdős-Rényi graph scales logarithmically with network size: \langle d \rangle \approx \frac{\log(n)}{\log(k)}. This logarithmic scaling demonstrates the “small-world” property inherent even in random graphs: even in large networks, the typical distance between nodes grows only logarithmically with network size, making the world surprisingly small despite its size.

--- title: "Appendix - Brief Introduction to igraph" jupyter: advnetsci --- ## Erdős-Rényi Random Graphs The Erdős-Rényi random graph model is one of the fundamental models in network science, serving as our baseline for understanding what makes small-world networks special. There are two variants of this model: $G(n,m)$ which creates $n$ vertices with exactly $m$ randomly chosen edges, and $G(n,p)$ which creates $n$ vertices where each possible edge exists with probability $p$. We focus on the $G(n,p)$ model because it provides better analytical tractability for deriving mathematical properties. ::: {#fig-erdos-renyi} ![](https://upload.wikimedia.org/wikipedia/commons/6/6e/Critical_1000-vertex_Erd%C5%91s%E2%80%93R%C3%A9nyi%E2%80%93Gilbert_graph.svg){width=30%} Erdős-Rényi random graph model. ::: ## Clustering Coefficient The clustering coefficient measures the probability that two neighbors of a node are also connected to each other. For Erdős-Rényi random graphs, we can derive the expected clustering coefficient analytically by exploiting the independence of edge formation. Consider a node $i$ with degree $k_i$ in an Erdős-Rényi graph $G(n,p)$. The local clustering coefficient is defined as $C_i = \frac{2e_i}{k_i(k_i-1)}$, where $e_i$ is the number of edges between neighbors of node $i$. The key insight is that in the $G(n,p)$ model, each possible edge exists with probability $p$ independently of all other edges. For a node with $k$ neighbors, there are $\binom{k}{2} = \frac{k(k-1)}{2}$ possible edges between its neighbors. Since each potential edge exists with probability $p$, the expected number of edges between neighbors is $E[e_i | k_i = k] = \frac{k(k-1)}{2} \cdot p$. Therefore, the expected local clustering coefficient for a node with degree $k$ becomes: $$E[C_i | k_i = k] = \frac{2 \cdot \frac{k(k-1)}{2} \cdot p}{k(k-1)} = p$$ This result shows that the expected local clustering coefficient is simply $p$, independent of the node degree. Since this holds for all vertices regardless of their degree, the expected global clustering coefficient is also $E[C] = p = \frac{\langle k \rangle}{n-1}$, where $\langle k \rangle = p(n-1)$ is the expected degree. ## Average Path Length Derivation The average path length in Erdős-Rényi graphs can be derived using a tree-expansion argument that reveals why these networks exhibit the small-world property of short distances. Consider an Erdős-Rényi model with average degree $k = p(n-1)$. We can analyze the network structure by imagining a breadth-first expansion from any starting node, treating the resulting structure as a tree (this approximation works well because triangles and cycles are rare in sparse random graphs). From the root node, we can reach approximately $1 + k$ nodes in the first step. In the second step, each of these $k$ nodes connects to roughly $k$ new nodes (avoiding already-visited nodes), giving us $1 + k + k^2$ total reachable nodes. Continuing this pattern, after $h$ steps we can reach approximately $1 + k + k^2 + \ldots + k^h \approx k^h$ nodes. The critical insight is that since Erdős-Rényi random graphs have few triangles and local clusters, most nodes in the network are reached only at the final step of this expansion process. When the expansion covers the entire network, we have $k^h \approx n$. Solving for $h$: $h \approx \log_{k}(n) = \frac{\log(n)}{\log(k)} = \frac{\log(n)}{\log(p(n-1))}$. This derivation reveals that the average shortest path length (diameter) of an Erdős-Rényi graph scales logarithmically with network size: $\langle d \rangle \approx \frac{\log(n)}{\log(k)}$. This logarithmic scaling demonstrates the "small-world" property inherent even in random graphs: even in large networks, the typical distance between nodes grows only logarithmically with network size, making the world surprisingly small despite its size.