Global Centrality Measures are defined on the entire network.
Freeman Centralization
$$
C_G = \frac{\sum_{i=1}^{n} \left[ C(v^*) - C(v_i) \right]}{\max \sum_{i=1}^{n} \left[ C(v^*) - C(v_i) \right]}
$$
Where $C(v^*)$ is the maximum centrality value in the network, and $C(v_i)$ is the centrality value of
vertex $v_i$.
Erdős–Rényi and Stochastic Block
Erdős–Rényi Model
A Erdős–Rényi model, is a random graph with $n$ vertices, and
each
pair of
vertices are
connected by
an edges with probability $p$.
Local Properties
For any vertices $v$ in $G(n,p)$
$$
\P{deg(v) = k} = \binom{n-1}{k} p^k (1-p)^{n-1-k}
$$
$$
\P{|np-deg(v)|\ge \epsilon } \le 3e^{-\epsilon^2 /(8np)}
$$
$$
\P{v\in \text{ some triangle}} = \binom{n-1}{2} p^3
$$
Let $G(n,p)$ denote the Erdős–Rényi random graph. Then:
For $p = \frac{1+\epsilon}{n}$, a constant $\epsilon > 0$ :
$$\Pr[\exists \text{ component of size } \Theta(n) \text{ and all others of size } O(\log n)] \to 1
\text{ as } n \to \infty$$
For $p < \frac{1}{n}$: $$\Pr[\text{all components have size } O(\log n)] \to 1 \text{ as } n \to
\infty$$
Connection to Semicircle Law
Let $A(n,p)$ denote the (random) adjacency matrix of $G(n,p)$, the normalized version of
$A(n,p)$ is defined by the following
$$\underline{A(n,p)}:=\frac{A(n,p) - \E{[A(n,p)]} }{\sqrt{np(1-p)}}$$
In the example, we are considering the adjacency matrix of $G(200,p)$. After "normalizing" the
adjacency matrix,
i.e. make the matrix entries mean $0$ and variance $1/n$. By the Semicircle
Law that we discussed in an earlier page,
the eigenvalues of the "normalized" matrix is expected to follow the semi-circle law for
large $n$.
It is interesting to observe in the example, that the speed of convergence to the semi-circle depends
not only on the size $n$ but also the parameter $p$.
For a certain values of $p$, the convergence is happening at much smaller $n$.
Stoachastic Block Model
We can generalize the Erdős–Rényi model by considering a graph with $n$ vertices,
and $2$ blocks, where each
block has $n/2$ vertices,
and each pair of vertices in the same block are connected with probability $p$,
and each pair of vertices in different blocks are connected with probability $q$. We will denote this
model
by $G(n,p,q)$, and its adjacency matrix by
$A(n,p,q)$.
Supposed the vertices are ordered by blocks, i.e. the first $n/2$ vertices are in the first block, and
the
last $n/2$ vertices are in the second block.
Then $$
\E{A(n,p,q)} = \begin{bmatrix}
P & Q \\
Q & P
\end{bmatrix}
$$
where $P$ is the $n/2 \times n/2$ matrix with all entries $p$, and $Q$ is the $n/2 \times n/2$ matrix
with
all entries $q$.
Start with $n d$ points $\{1,2, \ldots, n d\}$ (nd even) in $n$ groups. Put $U=\{1,2,
\ldots, n d\}$.
Repeat the following until no suitable pair can be found:
$\qquad$ Choose two random points
$i$ and $j$ in $U$, and if they are suitable, pair $i$ with $j$ and delete $i$ and
$j$ from $U$.
A pair is suitable if they lie in different groups and no
currently existing pair contains points in the same two groups.
Create a graph $G$ with edge from vertex $r$ to vertex $s$ if and only if there is a pair
containing points in the $r$ 'th and $s$ 'th groups. If $G$ is $d$-regular, output it,
otherwise return to Step 1 .