Complex Systems Practice: Eight Problems and Worked Solutions

Complex Systems · 7/8 · Series index · Notation

For definitions and derivations, use the series index; the helpsheet collects the formulas and their conditions.

Comprehensive Practice and Revision Checks

Attempt each problem before reading its worked solution.

Eight Comprehensive Questions

1. The $X_i$ are i.i.d. with mean 2 and variance 9. For $n=100$, what are the approximate distributions of $S_n$ and $\bar X_n$? How would you calculate $P(\bar X_n>2.6)$?

2. A density on $x\ge2$ is $p(x)=Cx^{-5/2}$. Find $C$, calculate $P(X>8)$, and determine whether the mean and variance are finite.

3. A CCDF has slope $-1.6$ on a log-log plot. What is the PDF tail exponent? Can the ordinary finite-variance CLT be applied directly?

4. Does the mean of independent standard Cauchy samples concentrate at zero as sample size increases? Explain using the scaling law and the finite-mean condition.

5. A BA model adds one node with three edges per step. A node was born at $t_i=100$. What is its continuum-approximation expected degree at $t=2500$? What are the asymptotic PDF and CCDF exponents?

6. For the directed graph $E=\{1\to2,2\to1,2\to3,3\to4,4\to3\}$, find the adjacency matrix, in/out-degrees, strong and weak components, and node 2's in/out-components.

7. A star has one center and five leaves. Find the center's and leaves' degree, closeness, and betweenness centralities and core numbers. Also find the graph's $L,D,R$.

8. An unweighted sparse network with $n$ nodes is stored as an adjacency list. Which algorithm finds distances from one node to all others, and with what time complexity? What is the complexity of repeating this for every node?

Answers and Essential Working

Question 1

$S_{100}\approx N(200,900)$ and $\bar X_{100}\approx N(2,0.09)$. The sample mean has standard deviation $0.3$, so $P(\bar X>2.6)\approx1-\Phi(2)\approx0.0228$. These are CLT approximations under the stated assumptions, not exact finite-sample results for every parent distribution.

Question 2

$C=(\gamma-1)x_{\min}^{\gamma-1}=(3/2)2^{3/2}$. The tail probability is $(8/2)^{-3/2}=1/8$. Since $\gamma=2.5>2$, the mean is finite and equals $\frac{\gamma-1}{\gamma-2}x_{\min}=6$. Since $\gamma\le3$, the variance is not finite.

Question 3

The CCDF exponent is $\alpha=1.6$ and the PDF exponent $\gamma=2.6$. The mean is finite but the second moment is infinite, so the ordinary finite-variance CLT does not apply directly. The exponent relation follows by integrating the PDF from $x$ to infinity; the two slopes are not identical.

Question 4

No. $S_n\overset d=nX$ and $\bar X_n\overset d=X$. The Cauchy mean is undefined and the sample-mean distribution retains its width. The integrability needed by the usual law of large numbers fails.

Question 5

$k_i(t)\approx m\sqrt{t/t_i}=3\sqrt{25}=15$. The BA asymptotic PDF exponent is three and its CCDF exponent is two. Changing $m$ changes the mean degree and distribution amplitude, but not the basic BA exponent three.

Question 6

$$\begin{aligned} A&=\begin{pmatrix}0&1&0&0\\1&0&1&0\\0&0&0&1\\0&0&1&0\end{pmatrix},\\ k^{\mathrm{out}}&=(1,2,1,1),\\ k^{\mathrm{in}}&=(1,1,2,1). \end{aligned}$$

The strongly connected components are $\{1,2\}$ and $\{3,4\}$; the entire graph is one weakly connected component. Including the node itself, $\mathrm{IN}(2)=\{1,2\}$ and $\mathrm{OUT}(2)=\{1,2,3,4\}$. Both the total in-degree and the total out-degree equal the number of directed edges, five.

Question 7

There are $n=6$ nodes and $M=5$ edges. For the center, $C_D=C_C=C_B=1$. For each leaf, $C_D=1/5$, $C_C=5/9$, and $C_B=0$. The center's distance sum is five, while a leaf's is $1+4\times2=9$.

Among 15 unordered node pairs, five have distance one and ten have distance two. Thus $L=25/15=5/3$, $D=2$, and $R=1$. Every node has core number one and local clustering zero. A high original degree does not necessarily imply high coreness.

Question 8

Use BFS. With an adjacency list, one search costs $O(n+M)=O(n)$ for a sparse graph. Repeating for all sources costs $O(n(n+M))=O(n^2)$. State the assumptions—adjacency-list representation, unweighted edges, and sparsity—because they determine these orders.

What You Should Be Able to Reproduce Without the Answers

• Derive the CLT normalization from the expectation and variance of $S_n$. Explain the constant, linear, and quadratic terms in the MGF expansion.
• Derive the power-law normalization constant, then use $\int x^{q-\gamma}\,dx$ to determine moment existence. Explain the logarithmic divergences at $\gamma=2,3$.
• Derive BA's degree-growth equation from attachment probability, apply the initial condition, transform node age to degree, and obtain $p(k)$. Recover the discrete $p_k$ from the master equation.
• Convert a graph into its adjacency matrix and adjacency list, calculate degrees and components, and explain why $A^\ell$ counts walks rather than neighbours at distance exactly $\ell$.
• State a network metric's interpretation and conditions before substituting values. Check matrix transposes, the factor of two in betweenness, the factor of three in transitivity, and total PageRank probability.

Final List of Common Mistakes

1. “Identically distributed” means the same distribution, not the same realized value. Independence means factorization of the joint distribution and is stronger than zero correlation.
2. The CLT concerns a standardized sum or mean approaching a normal distribution; it does not turn each original observation into a normal random variable.
3. A finite sample variance does not establish a finite variance for the underlying unbounded distribution. Cauchy symmetry does not give a mean of zero.
4. PDF and CCDF log-log slopes differ by one. Earthquake magnitude, amplitude, and energy are different variables; a change of variable requires a Jacobian.
5. A power law does not by itself prove preferential attachment or self-organized criticality. The sparse Poisson limit and a CLT normal approximation are different limits.
6. A tree is connected and acyclic; a general acyclic undirected graph is a forest. Planarity concerns whether a crossing-free drawing exists, not whether the current drawing has crossings.
7. With $A_{ij}$ representing $i\to j$, row sums give out-degrees, column sums give in-degrees, and incoming-edge propagation uses $A^{\mathsf T}$.
8. Mean local clustering weights nodes equally, while transitivity weights neighbour pairs. Assortativity samples attributes at edge endpoints.
9. Degree, eigenvector centrality, Katz, PageRank, and core number measure different properties. A node's position near the center of a drawing does not determine any of these values.

---

← Working with NetworkX · Series index · Helpsheet →