Graphs as Data
Week 7, Problem 1 (live)
This page belongs to Problem 1 of Week 7. Like Choosing k, it runs Python in your browser, so there is nothing to install. The first visit downloads Python, numpy, scipy, networkx, and matplotlib, which can take a minute; wait until the loading message disappears.
Each grey box is a small editor. Press Run Code to run it, then change it and run it again as often as you like. Boxes marked Exercise contain blanks ______ for you to fill in, and running them also checks your answer. Python is not required for this course, so if you get stuck, press Show Hint in the exercise’s toolbar; after the hint, a Show Solution button reveals the full answer. Your edits should be saved in this browser, and Start Over restores the original code.
Every box can use the helpers in graph_tools.py, which build the datasets and draw the pictures. The numbered Questions are things to think about as you go.
Every box on this page starts with the following already imported, so you do not need to import anything yourself.
import numpy as np
import matplotlib.pyplot as plt
import networkx as nxFor reference, the documentation pages you are most likely to want are:
- NumPy: indexing on arrays, including indexing by a boolean mask.
np.diag,np.sumand itsaxisargument, andnp.linalg.matrix_power.np.linalg.eighandnp.linalg.eigvalsh, for symmetric matrices.- NetworkX tutorial and SciPy sparse arrays.
Edge lists and adjacency matrices
Usually, graph data isn’t initially formatted as a matrix. It usually arrives as an edge list. Here is the barbell graph from lecture as an edge list. Python counts from \(0\), so lecture vertex \(k\) is Python vertex \(k-1\).
To do linear algebra, we turn it into the adjacency matrix \(\bfW\), with \(W_{ij}=1\) when \(\{i,j\}\) is an edge.
Each edge is an unordered pair, so \(\bfW\) must be symmetric.
def adjacency_matrix(edges, n):
W = np.zeros((n, n))
for i, j in edges:
W[i, j] = 1
W[j, i] = 1
return W
def adjacency_matrix(edges, n):
W = np.zeros((n, n))
for i, j in edges:
W[i, j] = 1
W[j, i] = 1
return WFrom here on, the boxes outside the exercises build \(\bfW\) with networkx.
The Laplacian
The graph Laplacian is \(\bfL=\bfD-\bfW\), where \(\bfD\) is the diagonal matrix of degrees.
W.sum(axis=1) is the vector of degrees, and np.diag of a vector is the diagonal matrix with that vector on its diagonal. Careful: np.diag of a matrix does the opposite and extracts its diagonal.
def laplacian(W):
return np.diag(W.sum(axis=1)) - W
def laplacian(W):
return np.diag(W.sum(axis=1)) - WThe quadratic form \(\bff^\top\bfL\bff\) is the roughness of \(\bff\), and on an indicator vector it is the cut. The box below checks both on the barbell. Here S is a boolean mask, so ~S is its complement and W[S][:, ~S] is the block of edges from \(S\) to its complement.
Rhetorical Question 2. Change S to the set \(\{0,1\}\), and then to the single vertex \(\{2\}\). What are the cuts, and why? Which \(S\) with \(|S|=3\) has the smallest cut?
For \(\{0,1\}\) the cut is \(2\): the edges \(\{0,2\}\) and \(\{1,2\}\) leave the set. For \(\{2\}\) the cut is \(3\), the degree of vertex \(2\), since every edge at a single vertex leaves it. The left triangle \(\{0,1,2\}\) (or its complement) has cut \(1\), the bridge alone, and no balanced split can do better, because the graph is connected.
Storing big graphs
A dense \(n\times n\) matrix of 64-bit floats takes \(8n^2\) bytes, but most of a real network’s adjacency matrix is zeros. E.g., in the case of a social network, each person knows a few hundred people, not everyone. A sparse matrix stores only the non-zero entries and their positions. Here is a random graph on \(5000\) vertices, built so that, like many social networks, a few vertices have very high degree but most have few neighbours.
Rhetorical Question 3. Why is the number of stored entries twice the number of edges? Facebook has roughly \(3\) billion users with a few hundred friends each. Roughly how much memory would its dense adjacency matrix take, and how much would a sparse one take?
Each edge \(\{i,j\}\) is stored twice, as \(W_{ij}\) and \(W_{ji}\). Dense: \(8\times(3\times10^9)^2\approx7\times10^{19}\) bytes, about \(70\) exabytes, far beyond any computer. Sparse: with \(300\) friends each there are about \(3\times10^9\times300\approx10^{12}\) stored entries, and at roughly \(12\) bytes each (a value and a column index) that is about \(10\) terabytes. That is large, though it would fit on a cluster. Nevertheless, most algorithms for large graphs are built to touch only the edges, for example through products \(\bfW\bfx\) as in the power method.
Counting components
By the kernel of the Laplacian, the number of connected components is the number of zero eigenvalues of \(\bfL\). On a computer, eigenvalues are only computed up to rounding error, so “zero” has to mean “smaller than a tolerance”.
lam < tol is an array of True and False, and summing it counts the True entries. Testing lam == 0 instead is fragile: look at the printed eigenvalues to see why.
def count_components(L, tol=1e-8):
lam = np.linalg.eigvalsh(L)
return int(np.sum(lam < tol))
def count_components(L, tol=1e-8):
lam = np.linalg.eigvalsh(L)
return int(np.sum(lam < tol))Now turn the two rings into an \(m\)-nearest-neighbour graph. The first \(100\) points are the inner ring and the last \(100\) the outer ring. The box prints, for each \(m\), the number of components, the smallest three eigenvalues of \(\bfL\), and the number of edges joining the two rings.
To look at one graph, set m below and run the box.
Rhetorical Question 4. For which \(m\) does the graph have exactly two components, and which components are they? Why does it have so many components for \(m=1\)? At \(m=12\) the graph is connected; what is \(\lambda_2\), and how many edges join the rings?
For \(4\leq m\leq11\) there are exactly two components, the two rings. For \(m=1\) each point is joined only to its nearest neighbour and to whoever has it as their nearest, so the graph breaks into \(63\) small clumps. At \(m=12\) a single edge joins the rings, and \(\lambda_2\approx0.016\). That is far smaller than \(\lambda_3\approx0.41\): almost a second zero eigenvalue, just as the guiding heuristic predicts for a graph that is almost disconnected.
The Fiedler vector is the eigenvector of \(\lambda_2\), and its signs split the graph in two. The box below compares that split with the two rings.
Rhetorical Question 5. For which \(m\) does the Fiedler split recover the rings? What goes wrong as \(m\) grows? Why do we take the larger of the two agreements?
It recovers the rings exactly for \(m=12\) and \(m=15\), where only \(1\) and \(11\) edges join them. By \(m=20\) there are \(137\) edges between the rings, so they are no longer joined by a weak link, and the agreement drops to \(60\%\); at \(m=30\) it is a coin flip.
The karate club
In the 1970s, the sociologist Wayne Zachary recorded which of the \(34\) members of a university karate club met outside the club (Zachary 1977). During his study, a dispute between the instructor, “Mr. Hi” (vertex \(0\)), and the club’s administrator, “the Officer” (vertex \(33\)), split the club in two, and every member joined one side. The question is whether the friendship graph, recorded before the split, predicts who went where. It’s a fun test case for clustering a network.
The eigenvectors are the columns of U, and Python counts from \(0\), so the second one is column 1.
def fiedler_vector(L):
lam, U = np.linalg.eigh(L)
return U[:, 1]
def fiedler_vector(L):
lam, U = np.linalg.eigh(L)
return U[:, 1]The box below splits the club by the sign of \(\bfu_2\), oriented so that Mr. Hi is on the positive side, and compares the split with what happened.
Rhetorical Question 6. How many members does the Fiedler vector place correctly, and who is misplaced? How large are the misplaced members’ entries of \(\bfu_2\) compared with the rest? Count their friends on each side (for example with W[8][mr_hi].sum() and W[8][~mr_hi].sum()); does that explain anything?
It places \(32\) of the \(34\) correctly; the misplaced members are \(2\) and \(8\). Both have small entries (\(-0.023\) and \(-0.052\), against a largest entry of about \(0.42\)), and both are among the five smallest in absolute value. Read as a soft indicator, the Fiedler vector is unsure about exactly the members it gets wrong. Member \(2\) has \(6\) friends who joined Mr. Hi and \(4\) who stayed with the Officer, but sits right next to the boundary in the graph. Member \(8\) has more friends on the Officer’s side (\(3\) against \(2\)) and joined Mr. Hi anyway; Zachary’s own method misplaced this member too.
Rhetorical Question 7. Compare the cuts of the Fiedler split and of the actual split. Is the Fiedler vector “wrong” about members \(2\) and \(8\)? The actual split happens to be balanced (\(17\) and \(17\)); what lower bound does the relaxed balanced cut give for its cut, and how close is it?
The Fiedler split cuts \(10\) friendships and the actual split cuts \(11\). So on its own terms the Fiedler split is the better cut; people did not choose sides by minimizing broken friendships, and the graph cannot see everything about why they chose. The bound is \(\operatorname{cut}(S)\geq n\lambda_2/4=34\times0.4685/4\approx4.0\) for every balanced \(S\), against an actual cut of \(11\). The bound is valid but far from tight here: the relaxation allows real-valued vectors, which can be much smoother than any \(\pm1\) vector.