One way to get some understanding of a graph is to peel away nodes, starting with the least connected. The k-core of a graph is the maximal subgraph such that every vertex has degree at least k. The k-shell is the set of vertices that are part of the k-core but not part of the (k+1)-core.

For example, the 0-core of a graph is simply the entire graph since every vertex has at least zero edges; a vertex can’t have a negative number of edges. The 1-core of a graph contains the vertices that are connected to other vertices. You form the 1-core by throwing away the 0-shell, the set of isolated vertices. You move from the 1-core to the 2-core by removing nodes of degree 1 until everything that’s left has degree at least 2.

NB: You do not form the k-core simply by discarding nodes of degree less than k. For example, consider the star graph below.

If you peel off the nodes of degree 1, eventually you have nothing left. There is no 2-core, even though the original graph had a node of degree 5. Or going back to the definition, there is no subgraph such that every vertex has degree 2, and so no maximal subgraph. The node of degree 5 only has degree five because it is connected to nodes of degree 1.

The k-cores of a complete graph of degree n are simply the entire graph, for k ≤ n. The k-shells are empty for k < n.

Keyword overlap

Let’s see what the k-cores and k-shells look like for some more complex graphs. First, let’s go back to the post looking at the overlap in keywords.  The edges of the graph are the 200 search terms that have lead visitors to the site at least twice. We connect two search terms if they share a word. The 56-core of the graph has 57 vertices, and the 57-core is empty. So the 56-core is a complete graph. Here’s the distribution of the k-shell sizes.

Random graphs

Next let’s look at a random graph. As in the post on spectra of random graphs, we look at an Erdős-Rényi graph G_n,p. First we start with n = 1000 and p = 0.01. So we start with 1000 nodes, and there’s a 0.01 that any particular pair of nodes is connected. Here are the core sizes for one such random graph:

[1000 1000  999  999  990  970  914  793]

So the 7-core has 793 nodes, then the 8-core is empty. I ran this ten times and the 7-core sizes ranged from size 709 to 849. But every time the 8-core was empty. The largest value of k such that the k-core is non-empty is called the degeneracy of the graph, so we could say the degeneracy was 7 every time.

I reran with n = 2000. The degeneracy was 14 every time. The 14-cores were in the range 1723 to 1810.

Finally I set n = 4000 and ran again. The degeneracy was 29 three times and 30 seven times. The final core sizes ranged from 3451 to 3714.

The experiments above suggest that the k-core size abruptly drops to zero, at a predictable value of k, and with a fairly predictable core size. There are papers on k-core size of random graphs, but I have not yet read any. (I have one in my to-read queue that someone let me know about after posting this article.)

The vertices of a bipartite graph can be divided into two sets where edges only go from one set to the other; there are no edges within each set. For example, in the graph below edges connect blue to green nodes, but not blue to blue or green to green.

In this example there are two connected bipartite components. There is a variation on the graph Laplacian called the signless Laplacian whose eigenvalues can tell you how many bipartite components a graph has.

The graph Laplacian is L = D – A where D is the diagonal matrix whose entries are the degrees of each node and A is the adjacency matrix. The signless Laplacian is Q = D + A. Since D and A have only non-negative entries, so does Q.

The smallest eigenvalue of the Laplacian L is always zero, and the second smallest eigenvalue is positive if and only if the graph is connected. The smallest eigenvalue of the signless Laplacian Q is positive if and only if the graph is connected and bipartite. The multiplicity of zero as an eigenvalue equals the number of connected bipartite components.

The graph above has two connected bipartite components. Zero is a double eigenvalue of the signless Laplacian, and the next eigenvalue is 0.2603.

Next we connect two of the blue nodes. Now the graph is connected and bipartite.

Zero is now a single eigenvalue, and the second eigenvalue is 0.0968. This second eigenvalue is positive because there is only one component now, but it is small because the graph can almost be separated into two bipartite components.

Next we remove the edge connecting the two components, but we draw an edge between two of the green vertices.

Now there are two components, but only one of them is bipartite. The smallest eigenvalue is zero, with multiplicity 1, and the second eigenvalue is 0.2015.

Next we repeat the examples above with more edges. Now each component of the graph is a complete bipartite graph.

The smallest eigenvalue is 0, with multiplicity 2. But now the next eigenvalue is 3, This value is larger than before because the components are better connected.

As before, we now join two of the blue nodes.

Now there is one bipartite component. The smallest eigenvalue is 0 with multiplicity 1. The second eigenvalue is 0.2103.

Finally, we remove the edge connecting the two components and connect two of the green vertices.

Now the smallest eigenvalue is 0 with multiplicity 1. While there are two components, there’s only one bipartite component. The next eigenvalue is 0.4812.

More spectral graph theory

• Matrices associated with a graph
• Measuring connectivity with eigenvalues

Create a graph by first making a set of n vertices and then connecting nodes i and j, i > j, with probability p. This is known as the Erdős-Rényi graph G_n,p. Here’s such a graph with n = 100 and p = 0.1.

Then the spectrum of the adjacency matrix A of the graph bounces around the spectrum of the expected value of A. This post will illustrate this to give an idea how close the two spectra are.

The adjacency matrix A for our random graph has zeros along the diagonal because the model doesn’t allow loops connecting a vertex with itself. The rest of the entries are 1 with probability p and 0 with probability 1-p. The entries above the diagonal are independent of each other, but the entries below the diagonal are determined by the entries above by symmetry. (An edge between i and j is also an edge between j and i.)

The expected value of A is a matrix with 0’s along the diagonal and p‘s everywhere else. This matrix has one eigenvalue of p(n – 1) and (n – 1) eigenvalues –p. Let’s see how close the spectra of a dozen random graphs come the spectra of the expected adjacency matrix. As above, n = 100 and p = 0.1.

Because the eigenvalues are close together, I jittered each sample horizontally to make the values easier to see. Notice that the largest eigenvalue in each sample is around 10. The expected value is p(n – 1) = 9.9, so the values are close to their expected value.

The other eigenvalues seem to be centered around 0. This is consistent with the expected value of  –p = -0.1.  The most obvious thing about the smaller eigenvalues is not their mean but their range. How far can might the eigenvalues be from their expected value? Fan Chung and Mary Radcliffe give the following estimate in their paper On the Spectra of General Random Graphs.

For  G_n,p, if  p > 8 log(√2 n)/9n, then with probability at least 1 – 1/n we have

Here J is the matrix of all 1’s and I is the identity matrix. In our case the theorem says that with probability at least 0.99, we expect the eigenvalues of our random graph to be within 19.903 of their expected value. This is a pessimistic bound since no value is much more than 5 away from its expected value.

A few examples help build intuition for what the eigenvalues of the graph Laplacian tell us about a graph. The smallest eigenvalue is always zero (see explanation in footnote here).

For a complete graph on n vertices, all the eigenvalues except the first equal n. The eigenvalues of the Laplacian of a graph with n vertices are always less than or equal to n, this says the complete graph has the largest possible eigenvalue. This makes sense in light of the previous post: adding edges increases the eigenvalues. When you add as many edges as possible, you get the largest possible eigenvalues.

Conversely, if all the non-zero eigenvalues of the graph Laplacian are equal, the graph is complete.

Next we look at the case of a star with n-1 vertices connected to a central vertex. The smallest eigenvalue is zero, as always, and the largest is n. The ones in the middle are all 1. In particular, the second eigenvalue, the algebraic connectivity, is 1. It’s positive because the graph is connected, but it’s not large because the graph is not well connected: if you remove the central vertex it becomes completely disconnected.

Finally, we look at a cyclical graph, a ring with n vertices. Here the eigenvalues are 2 – 2 cos(2πk/n) where 0 ≤ k ≤ n/2. In particular, smallest non-zero eigenvalue is 2 – 2 cos(2π/n) and so as n increases, the algebraic connectivity approaches zero. This is curious since the topology doesn’t change at all. But from a graph theory perspective, a big ring is less connected than a small ring. In a big ring, each vertex is connected to a small proportion of the vertices, and the average distance between vertices is larger.

When you add an edge to a graph, each of the eigenvalues of the graph Laplacian either increases or stays the same.

As I wrote in my previous post, the smallest eigenvalue is always 0. The second smallest eigenvalue is 0 if and only if the graph is disconnected. So no edge will increase the smallest eigenvalue, nor will it increase the second eigenvalue if the matrix is still disconnected after adding it. Adding some edges will have more impact on the second eigenvalue than others.

To illustrate this, we start with the graph below.

The second eigenvalue of the Laplacian is 1.2679. When we connect node 2 to node 4, the second eigenvalue increases to 1.4384.

If we connect node 2 to node 3 instead, the second eigenvalue goes up to 1.6972. This makes sense because node 3 is better connected than node 4. Connecting node 2 to node 3 increases the overall connectivity of the graph more than connecting it to node 4. (The second eigenvalue of the graph Laplacian is sometimes called the algebraic connectivity of the graph because it is so strongly associated with the graph’s connectivity.)

Now let’s look at the rest of the eigenvalues. The full set of eigenvalues for the three graphs are given below.

original [0.0000  1.2679  2.0000  4.0000  4.0000  4.7321]
2 -> 4   [0.0000  1.4384  3.0000  4.0000  4.0000  5.5616]
2 -> 3   [0.0000  1.6972  2.3820  4.0000  4.6180  5.3028]

Notice that adding an edge between nodes 2 and 4 or between nodes 2 and 3 increased some of the eigenvalues relative to their original values and left others unchanged.

Swapping the edge between nodes 2 and 4 with an edge between nodes 2 and 3 increases the 2nd and 5th eigenvalue, but lowers the 3rd and 6th.

Related post: Social networks in fact and fiction

If a graph can be split into two components with no links between them, that’s probably easy to see. It’s also unlikely, unless there’s a good reason for it. The less obvious and more common case is a graph that can almost be split into two components. Spectral graph theory, looking at the eigenvalues of the graph Laplacian, can tell us not just whether a graph is connected, but also how well it’s connected.

The graph Laplacian is the matrix L = D – A where D is the diagonal matrix whose entries are the degrees of each node and A is the adjacency matrix. The smallest eigenvalue of L, λ₁, is always 0. (Why? See footnote [1].) The second smallest eigenvalue λ₂ tells you about the connectivity of the graph. If the graph has two disconnected components, λ₂ = 0. And if λ₂ is small, this suggests the graph is nearly disconnected, that it has two components that are not very connected to each other. In other words, the second eigenvalue gives you a sort of continuous measure of how well a graph is connected.

To illustrate this, we’ll start with a disconnected graph and see what happens to λ₂ as we add edges connecting its components.

The first two eigenvalues of L are zero as expected. (Actually, when I computed them numerically, I got values around 10^-15, about 15 orders of magnitude smaller than the next eigenvalue, so the first two eigenvalues are zero to the limits of floating point precision.)

Next, we add an edge between nodes 4 and 9 to form a weak link between the two clusters.

In this graph the second eigenvalue λ₂ jumps to 0.2144.

If we connect nodes 3 and 8 instead of 4 and 8, we create a stronger link between the components since nodes 3 and 8 have more connections in their respective components. Now λ₂ becomes 0.2788.

Finally if we add both, connecting nodes 4 and 9 and nodes 3 and 8, λ₂ increases to 0.4989.

More graph theory

• Graph Laplacian and other matrices associated with a graph
• Complex networks

[1] To see why the smallest eigenvalue is always 0, note that v = (1, 1, 1, …, 1) is an eigenvector for 0. Multiplying the ith row of D by v picks out the degree of node i. Multiplying the ith row of A by v sums that row, which is also the degree of node i.