Complex Systems Helpsheet: Probability and Network Formulas

Complex Systems · 8/8 · Series index · Notation

Helpsheet: Six Core Formula Blocks

The same letter may have different meanings in different formulas; use its local definition and check the stated assumptions.

1. Probability, the CLT, and MGFs

Write $S_n=\sum_{i=1}^nX_i$ and $\overline X=S_n/n$. The second parameter of $N(\mu,\sigma^2)$ is the variance.

$$\begin{aligned} \int p(x)\,dx&=1,\\ \mu&=E[X],\\ \sigma^2&=E[X^2]-\mu^2,\\ p_N(x)&=\frac{e^{-(x-\mu)^2/(2\sigma^2)}}{\sigma\sqrt{2\pi}}. \end{aligned}$$

CLT: if the $X_i$ are independent and identically distributed, with $0<\sigma^2<\infty$, then

$$\begin{aligned} Z_n&=\frac{S_n-n\mu}{\sigma\sqrt n} =\frac{\sqrt n(\overline X-\mu)}{\sigma},\\ Z_n&\xrightarrow{d}N(0,1),\qquad n\to\infty,\\ S_n&\approx N(n\mu,n\sigma^2),\\ \overline X&\approx N(\mu,\sigma^2/n). \end{aligned}$$

MGFs and raw moments:

$$\begin{aligned} M_X(t)&=E[e^{tX}],\\ M_X^{(r)}(0)&=E[X^r],\\ M_{aX+b}(t)&=e^{bt}M_X(at),\\ M_{\sum_iX_i}(t)&=\prod_iM_{X_i}(t)\qquad\text{if independent},\\ M_N(t)&=e^{\mu t+\sigma^2t^2/2}. \end{aligned}$$

The standard normal raw moments are $(m_0,m_1,m_2,m_3,m_4)=(1,0,1,0,3)$. With $Y=(X-\mu)/\sigma$, the proof proceeds through

$$\begin{aligned} \left[M_Y\!\left(\frac{t}{\sqrt n}\right)\right]^n &=\left[1+\frac{t^2}{2n}+o(n^{-1})\right]^n\\ &\longrightarrow e^{t^2/2}. \end{aligned}$$

The MGF proof additionally requires the MGF to be finite in a neighborhood of $0$; the Taylor derivatives are evaluated at $0$. Independence is required to express the MGF of a sum as a product.

$$\begin{aligned} \text{skewness}&=\frac{E[(X-\mu)^3]}{\sigma^3},\\ \text{kurtosis}&=\frac{E[(X-\mu)^4]}{\sigma^4},\\ \text{excess kurtosis}&=\text{kurtosis}-3. \end{aligned}$$

Symmetric random walk: $P(X=1)=P(X=-1)=1/2$, with independent steps,

$$\begin{aligned} M_X(t)&=\cosh t,\\ S_n&\approx N(0,n),\\ P(S_n=s)&=2^{-n}\binom{n}{(n+s)/2},\\ s&=-n,-n+2,\ldots,n. \end{aligned}$$

2. Stable Distributions, Power Laws, and Pareto

Stability and characteristic functions: for a sum of i.i.d. variables, stability is written $S_n\overset{d}{=}a_nX+b_n$. The characteristic function (CF), $\varphi_X(q)=E[e^{iqX}]$, always exists.

For the symmetric stable family centered at $0$, take $c>0$ and $0<\alpha\le2$:

$$\begin{aligned} \varphi_X(q)&=e^{-c|q|^\alpha},\\ S_n&\overset{d}{=}n^{1/\alpha}X,\\ \overline X&\overset{d}{=}n^{1/\alpha-1}X. \end{aligned}$$

At $\alpha=2$, the distribution is Gaussian with variance $2c$. At $\alpha=1$, it is Cauchy:

$$\begin{aligned} p_C(x)&=\frac{c}{\pi(x^2+c^2)},\\ \varphi_C(q)&=e^{-c|q|},\\ \overline X&\overset{d}{=}X. \end{aligned}$$

The Cauchy mean is undefined. A symmetric principal value of $0$ does not establish the existence of an expectation. The sample mean does not become concentrated as sample size increases.

Power-law tails and moments:

$$\begin{aligned} p(x)&\propto x^{-\gamma}=x^{-(1+\alpha)},\\ \overline F(x)&\propto x^{-\alpha},\\ \gamma&=1+\alpha,\\ E|X|^r<\infty &\iff r<\alpha\iff\gamma>r+1,\qquad r>0. \end{aligned}$$

The PDF and CCDF have log-log slopes $-\gamma$ and $-\alpha$, respectively. Moments diverge at equality. A power-law tail with tail index $\alpha=2$ still has a divergent second moment. Within the stable family, the power-law tail and this moment criterion apply only for $0<\alpha<2$. Stability index $\alpha=2$ is the Gaussian exception, with finite moments of every order.

Pareto: for $x\ge x_m>0$ and $\alpha>0$,

$$\begin{aligned} p(x)&=\frac{\alpha x_m^\alpha}{x^{1+\alpha}},\\ \overline F(x)&=(x_m/x)^\alpha,\\ E[X^r]&=\frac{\alpha x_m^r}{\alpha-r},\qquad r<\alpha,\\ E[X]&=\frac{\alpha x_m}{\alpha-1},\qquad\alpha>1,\\ \operatorname{Med}(X)&=x_m2^{1/\alpha},\\ \operatorname{Var}(X)&=\frac{\alpha x_m^2}{(\alpha-1)^2(\alpha-2)},\qquad\alpha>2,\\ G&=\frac1{2\alpha-1},\qquad\alpha>1. \end{aligned}$$

Scale-free behavior is expressed by $p(ax)/p(x)=a^{-\gamma}$ within the range where the power law holds. A finite upper cutoff makes all positive-order moments finite.

3. Relaxing the CLT and Application Reminders

Lyapunov condition for independent, nonidentically distributed variables: let $s_n^2=\sum_{i=1}^n\sigma_i^2$. If there is a $\delta>0$ such that

$$\frac{\sum_{i=1}^nE|X_i-\mu_i|^{2+\delta}}{s_n^{2+\delta}}\longrightarrow0,$$

then

$$\frac{\sum_{i=1}^n(X_i-\mu_i)}{s_n}\xrightarrow{d}N(0,1).$$

Gutenberg–Richter law:

$$\log_{10}N(M_{\mathrm{mag}}\ge u)=a-bu.$$

Using $M_{\mathrm{mag}}=\log_{10}A+\mathrm{const}$ gives

$$\overline F_A(A)\propto A^{-b},\qquad p_A(A)\propto A^{-b-1}.$$

Omori's law: $r(t)=K/(t+c)^p$ describes an event rate; it cannot directly be treated as a probability density.

St Petersburg paradox:

$$P(N=j)=2^{-j},\qquad W=2^{j-1},\qquad j=1,2,\ldots,$$

which gives $E[W]=\infty$.

Complex-systems keywords: many-body, autonomous, nonlinear interaction, emergence. Observing a power law alone does not establish its generating mechanism.

4. BA and ER Networks

Let $n$ be the number of nodes, $M$ the total number of edges, and $m$ the number of edges introduced by each new node in the BA model.

BA: growth plus linear preferential attachment.

$$\begin{aligned} n&=n_0+t,\\ M&=M_0+mt,\\ \Pi_i&=\frac{k_i}{\sum_jk_j},\\ \sum_jk_j&\simeq2mt. \end{aligned}$$

In the continuum approximation,

$$\begin{aligned} \dot k_i&=m\Pi_i=\frac{k_i}{2t},\\ k_i(t_i)&=m,\\ k_i(t)&=m\sqrt{t/t_i}. \end{aligned}$$

Birth times are approximately uniform. For $k\ge m$, inversion gives $t_i=t(m/k)^2$, hence

$$\begin{aligned} F(k)&=1-(m/k)^2,\\ p_{\mathrm{cont}}(k)&=2m^2k^{-3},\\ \gamma&=3. \end{aligned}$$

Master equation: $N_k$ is the expected number of nodes of degree $k$, and $\delta_{km}$ is the new-node birth term.

$$\begin{aligned} \Delta N_k&=\frac{(k-1)N_{k-1}-kN_k}{2t}+\delta_{km},\\ N_k&\simeq tp_k. \end{aligned}$$

The boundary value, recurrence, and closed-form solution are

$$\begin{aligned} p_m&=\frac2{m+2},\\ p_k&=\frac{k-1}{k+2}p_{k-1},\qquad k>m,\\ p_k&=\frac{2m(m+1)}{k(k+1)(k+2)},\qquad k\ge m,\\ P(K\ge q)&=\frac{m(m+1)}{q(q+1)},\qquad q\in\mathbb Z,\ q\ge m,\\ \langle k\rangle&\longrightarrow2m. \end{aligned}$$

ER random graph $G(n,p)$: each pair of distinct nodes is connected independently with probability $p$,

$$\begin{aligned} E[M]&=\frac{pn(n-1)}2,\\ P(K=k)&=\binom{n-1}{k}p^k(1-p)^{n-1-k},\\ c&=(n-1)p. \end{aligned}$$

Keep $c$ fixed and let $p=c/(n-1)$ and $n\to\infty$ to obtain the Poisson limit:

$$p_k\longrightarrow\frac{e^{-c}c^k}{k!}.$$

For this limiting distribution, $E[K]=\operatorname{Var}(K)=c$. The Poisson limit is not the CLT. A normal approximation requires a further regime in which $c$ is large. ER tails decay rapidly, whereas BA networks develop prominent hubs.

5. Graph Theory, Matrices, and Components

Use $A_{ij}=1$ to mean $i\to j$. For an undirected graph, $A=A^{\mathsf T}$. For simple graphs without self-loops,

$$\begin{aligned} k_i^{\mathrm{out}}&=\sum_jA_{ij},\\ k_i^{\mathrm{in}}&=\sum_jA_{ji}. \end{aligned}$$

For undirected graphs, the degree sum and mean degree are

$$\sum_i k_i=2M,\qquad \langle k\rangle=2M/n.$$

Directed graphs satisfy $\sum_i k_i^{\mathrm{in}}=\sum_i k_i^{\mathrm{out}}=M$. Undirected and directed densities are, respectively,

$$\rho_u=\frac{2M}{n(n-1)},\qquad \rho_d=\frac{M}{n(n-1)}.$$

Matrix powers and distance: $(A^\ell)_{ij}$ counts walks of length $\ell$. A node at shortest-path distance exactly $2$ from $i$ must satisfy

$$(A^2)_{ij}>0,\qquad A_{ij}=0,\qquad j\ne i.$$

For an undirected simple graph, $(A^2)_{ii}=k_i$.

Graph counts and structure:

• A tree is connected and acyclic, with $M=n-1$.
• A forest with $C$ components has $M=n-C$.
• A $k$-regular graph has $M=nk/2$.
• A complete graph has $M=n(n-1)/2$.
• A bipartite graph has no odd cycle. Its adjacency matrix can be written as

$$A_{\mathrm{bip}}=\begin{pmatrix}0&B\\B^{\mathsf T}&0\end{pmatrix}.$$

The matrices $BB^{\mathsf T}$ and $B^{\mathsf T}B$ count shared neighbors in the two respective projections. Remove the diagonal and replace positive entries by $1$ to obtain unweighted projections.

Connectivity and other network types: an SCC requires mutual directed reachability; a WCC ignores edge directions. When each reachability set includes its starting node,

$$\mathrm{IN}(v)\cap\mathrm{OUT}(v)=\mathrm{SCC}(v).$$

A hyperedge can connect several objects simultaneously. A multiplex network represents different relations among the same set of nodes in multiple layers. A planar graph can be redrawn without edge crossings.

Storage and search complexity: a dense adjacency matrix requires $O(n^2)$ space, and an adjacency list requires $O(n+M)$ space. One BFS takes $O(n+M)$; running BFS separately from every node takes $O(n(n+M))$.

6. Network Metrics

For the distance formulas below, assume a connected, undirected, unweighted graph, with $d_{ij}$ denoting shortest-path distance.

$$\begin{aligned} L&=\frac{\sum_{i\ne j}d_{ij}}{n(n-1)},\\ \varepsilon_i&=\max_jd_{ij},\\ D&=\max_i\varepsilon_i,\\ R&=\min_i\varepsilon_i. \end{aligned}$$

Degree, closeness, and betweenness centrality:

$$\begin{aligned} C_D(i)&=\frac{k_i}{n-1},\\ C_C(i)&=\frac{n-1}{\sum_{j\ne i}d_{ij}},\\ C_B(i)&=\frac{2}{(n-1)(n-2)} \sum_{\substack{s<t\\s,t\ne i}}\frac{\sigma_{st}(i)}{\sigma_{st}}. \end{aligned}$$

Here $\sigma_{st}$ is the number of shortest paths from $s$ to $t$, and $\sigma_{st}(i)$ counts those passing through $i$ as an internal node. The betweenness formula requires $n>2$.

Eigenvector centrality and Katz centrality: use $B=A^{\mathsf T}$ for incoming-link importance and $B=A$ for undirected graphs.

$$\begin{aligned} B\boldsymbol x&=\rho(B)\boldsymbol x,\\ \boldsymbol x&=aB\boldsymbol x+\beta\boldsymbol 1,\\ \boldsymbol x&=\beta(I-aB)^{-1}\boldsymbol 1,\\ a&\ge0,\qquad a\rho(B)<1,\qquad\beta>0. \end{aligned}$$

PageRank: let $0<d<1$ and use the row-stochastic matrix $P_{ij}=A_{ij}/k_i^{\mathrm{out}}$. For a node with no outgoing edges, replace its entire row by $\boldsymbol v^{\mathsf T}$.

$$\begin{aligned} \boldsymbol p&=dP^{\mathsf T}\boldsymbol p+(1-d)\boldsymbol v,\\ \sum_i p_i&=1,\qquad v_i=1/n. \end{aligned}$$

Clustering and transitivity: $t_i$ is the number of triangles containing node $i$, and $T$ is the total number of triangles in the graph.

$$\begin{aligned} C_i&=\frac{2t_i}{k_i(k_i-1)},\qquad k_i\ge2,\\ C_i&=0,\qquad k_i<2,\\ \overline C&=\frac1n\sum_iC_i,\\ C_{\mathrm{trans}}&=\frac{3T}{\sum_i\binom{k_i}{2}}. \end{aligned}$$

When there are no connected triples, transitivity is defined to be $0$. A $k$-core is obtained by repeatedly removing nodes whose current degree is less than $k$.

Assortativity: $r=\operatorname{Corr}_{\mathrm{edge}}(k_i,k_j)$. Positive values indicate assortativity, and negative values indicate disassortativity. Calculate the correlation across edge endpoints, counting each undirected edge in both directions.

Modularity and the largest-component fraction:

$$\begin{aligned} Q&=\sum_C\left[\frac{l_C}{M}-\left(\frac{K_C}{2M}\right)^2\right],\\ K_C&=\sum_{i\in C}k_i,\\ S&=|C_{\max}|/n. \end{aligned}$$

Here $l_C$ is the number of edges internal to community $C$, and $K_C$ is the sum of its nodes' degrees in the original graph. Modularity requires $M>0$. The quantity $S$ is the fraction of all nodes belonging to the largest component.

---

← Comprehensive practice · Series index