$\lambda_2$ and Connectivity

Math 123: Mathematical Aspects of Data Analysis — Fall 2026

Published

October 29, 2026

The second-smallest eigenvalue $\lambda_2$ of the graph Laplacian is called the algebraic connectivity¹. We know two facts about it. 1) By the kernel of the Laplacian, $\lambda_2=0$ exactly when the graph is disconnected. 2) By Rayleigh–Ritz, \[ \lambda_2=\min\Big\{\bff^\top\bfL\bff:\ \|\bff\|_2=1,\ \bff\perp\mathbf{1}\Big\} =\min\Big\{\textstyle\sum_{\{i,j\}\in E}w_{ij}(f_i-f_j)^2:\ \|\bff\|_2=1,\ \bff\perp\mathbf{1}\Big\}, \] the roughness of the smoothest function that is not constant. In this short example, I want to connect those two facts. In particular, I want to conclude that $\lambda_2$ is small when the graph has a bottleneck, a set of vertices joined to the rest by few edges compared with its size.

import networkx as nx
import numpy as np
import plotly.graph_objects as go
from plotly.subplots import make_subplots

Figure style

# A muted ink colour and a translucent grid read correctly against both the
# light and the dark version of this site, so the figures need no theme switch.
INK = "#7c7c78"
GRID = "rgba(128, 128, 128, 0.28)"
COLOR = ["#2a78d6", "#eb6834", "#2ca25f"]


def style(fig, height=420, title=None, showlegend=None):
    """Apply the shared layout to a plot with axes."""
    fig.update_layout(
        template="simple_white",
        paper_bgcolor="rgba(0,0,0,0)",
        plot_bgcolor="rgba(0,0,0,0)",
        font=dict(color=INK, size=13),
        title=dict(text=title, x=0, xanchor="left", font=dict(size=15)),
        margin=dict(l=70, r=30, t=60 if title else 30, b=55),
        height=height,
        showlegend=showlegend,
        hovermode="closest",
    )
    fig.update_xaxes(gridcolor=GRID, linecolor=GRID, zerolinecolor=GRID)
    fig.update_yaxes(gridcolor=GRID, linecolor=GRID, zerolinecolor=GRID)
    return fig


def graph_traces(G, pos, color=COLOR[0]):
    """Plotly traces drawing the edges and vertices of G at the positions pos."""
    xs, ys = [], []
    for i, j in G.edges():
        xs += [pos[i][0], pos[j][0], None]
        ys += [pos[i][1], pos[j][1], None]
    nodes = list(G.nodes())
    return [
        go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=INK, width=1), opacity=0.6,
                   hoverinfo="skip", showlegend=False),
        go.Scatter(x=[pos[v][0] for v in nodes], y=[pos[v][1] for v in nodes], mode="markers",
                   marker=dict(size=8, color=color, line=dict(color="white", width=0.8)),
                   hoverinfo="skip", showlegend=False),
    ]

Throughout, the Laplacian comes from the adjacency matrix exactly as in lecture.

def laplacian(G):
    W = nx.to_numpy_array(G, nodelist=sorted(G.nodes()))
    return np.diag(W.sum(axis=1)) - W


def lambda_2(G):
    return np.linalg.eigvalsh(laplacian(G))[1]

Six graphs on twenty vertices

Here are six graphs, each with $20$ vertices. The barbell is two complete graphs on $10$ vertices joined by a single edge, very similar to the barbell from lecture.

def circle(n, center=(0.0, 0.0), radius=1.0):
    t = 2 * np.pi * np.arange(n) / n
    return np.column_stack([center[0] + radius * np.cos(t), center[1] + radius * np.sin(t)])


barbell = nx.disjoint_union(nx.complete_graph(10), nx.complete_graph(10))
barbell.add_edge(5, 10)    # the bridge, between the two vertices of the circles that face each other

grid = nx.convert_node_labels_to_integers(nx.grid_2d_graph(4, 5), label_attribute="xy")
shapes = {
    "path": (nx.path_graph(20), {i: (i / 19 * 2 - 1, 0.0) for i in range(20)}),
    "cycle": (nx.cycle_graph(20), dict(enumerate(circle(20)))),
    "4 × 5 grid": (grid, {v: (0.5 * grid.nodes[v]["xy"][1] - 1, 0.5 * grid.nodes[v]["xy"][0] - 0.75)
                         for v in grid}),
    "barbell": (barbell, dict(enumerate(np.vstack([circle(10, (1.2, 0), 0.8),
                                                   circle(10, (-1.2, 0), 0.8)])))),
    "star": (nx.star_graph(19), {0: (0.0, 0.0), **{i: tuple(circle(19)[i - 1]) for i in range(1, 20)}}),
    "complete": (nx.complete_graph(20), dict(enumerate(circle(20)))),
}

for name, (G, _) in shapes.items():
    print(f"{name:>10}: {G.number_of_edges():3d} edges,  lambda_2 = {lambda_2(G):7.4f}")

      path:  19 edges,  lambda_2 =  0.0246
     cycle:  20 edges,  lambda_2 =  0.0979
4 × 5 grid:  31 edges,  lambda_2 =  0.3820
   barbell:  91 edges,  lambda_2 =  0.1690
      star:  19 edges,  lambda_2 =  1.0000
  complete: 190 edges,  lambda_2 = 20.0000

Draw the six graphs

fig = make_subplots(rows=2, cols=3, horizontal_spacing=0.04, vertical_spacing=0.12,
                    subplot_titles=[f"{name}: λ₂ = {lambda_2(G):.3g}, {G.number_of_edges()} edges"
                                    for name, (G, _) in shapes.items()])
for k, (name, (G, pos)) in enumerate(shapes.items()):
    for trace in graph_traces(G, pos):
        fig.add_trace(trace, row=k // 3 + 1, col=k % 3 + 1)
fig.update_xaxes(visible=False, range=[-2.1, 2.1])
fig.update_yaxes(visible=False, range=[-1.2, 1.2])
for i in range(1, 7):
    suffix = "" if i == 1 else str(i)
    fig.layout[f"yaxis{suffix}"].scaleanchor = f"x{suffix}"
style(fig, height=480)
fig.update_annotations(font=dict(size=13, color=INK))
fig.show()

Figure 1: Six graphs on $20$ vertices, with the algebraic connectivity $\lambda_2$ and the number of edges of each.

Two things stand out.

Edges are not connectivity. The barbell has $91$ edges and the grid only $31$, yet the grid has more than twice the algebraic connectivity. Cutting one edge splits the barbell into two halves of $10$ vertices, while no small set of edges splits the grid into big pieces.
A bottleneck means few edges per vertex cut off. The path and the star are both trees with $19$ edges, yet $\lambda_2$ is $0.025$ for the path and $1$ for the star. Removing the middle edge of the path cuts off $10$ vertices with $1$ edge, a ratio of $1/10$. The star looks fragile, since every path between two leaves goes through the center, but that weak point is a single vertex, and $\lambda_2$ only sees edges. Cutting off $s$ leaves takes exactly $s$ edges, a ratio of $1$, so the star has no bottleneck in the sense of the introduction.

Recall the test vector from the relaxed balanced cut. If $S$ is half the vertices and $\bfy=\mathbf{1}_S-\mathbf{1}_{S^c}$, then $\bfy\perp\mathbf{1}$, $\|\bfy\|_2^2=n$, and $\bfy^\top\bfL\bfy=4\operatorname{cut}(S)$, so \[ \lambda_2\leq\frac{\bfy^\top\bfL\bfy}{\|\bfy\|_2^2}=\frac{4\operatorname{cut}(S)}{n}. \] Thus, the existance of a small balanced cut forces a small $\lambda_2$. For the path and the barbell, $\operatorname{cut}(S)=1$ gives $\lambda_2\leq4/20=0.2$, and indeed $\lambda_2$ is $0.025$ and $0.169$. The converse, that a small $\lambda_2$ forces some small cut, is also true up to a square root, and is called Cheeger’s inequality; we might see it later.

Adding bridges

Suppose I have two complete graphs with $m = 10$ vertices. Let’s join them together with $b$ bridge edges, with no vertex on more than one bridge. The bound above, with $S$ one of the two cliques, gives $\lambda_2\leq4b/(2m)=b/5$.

def two_cliques(m, b):
    """Two complete graphs on m vertices, joined by the b bridges {t, m + t}, t < b."""
    G = nx.disjoint_union(nx.complete_graph(m), nx.complete_graph(m))
    G.add_edges_from((t, m + t) for t in range(b))
    return G


m = 10
bridges = np.arange(0, m + 1)
lam2_bridges = np.array([lambda_2(two_cliques(m, b)) for b in bridges])
for b, lam in zip(bridges, lam2_bridges):
    print(f"b = {b:2d}:  lambda_2 = {lam:.3f},  bound 2b/m = {2 * b / m:.1f}")

b =  0:  lambda_2 = 0.000,  bound 2b/m = 0.0
b =  1:  lambda_2 = 0.169,  bound 2b/m = 0.2
b =  2:  lambda_2 = 0.343,  bound 2b/m = 0.4
b =  3:  lambda_2 = 0.523,  bound 2b/m = 0.6
b =  4:  lambda_2 = 0.708,  bound 2b/m = 0.8
b =  5:  lambda_2 = 0.901,  bound 2b/m = 1.0
b =  6:  lambda_2 = 1.101,  bound 2b/m = 1.2
b =  7:  lambda_2 = 1.310,  bound 2b/m = 1.4
b =  8:  lambda_2 = 1.528,  bound 2b/m = 1.6
b =  9:  lambda_2 = 1.757,  bound 2b/m = 1.8
b = 10:  lambda_2 = 2.000,  bound 2b/m = 2.0

Here are those graphs. Move the slider to add bridges, drawn in green. Each vertex is colored by its entry of the Fiedler vector $\bfu_2$, so blue and orange mark the two signs.

Draw the graphs with a slider over b

def fiedler(G):
    """The Fiedler vector of G, with the sign chosen so that vertex 0 is positive."""
    L = laplacian(G)
    # Adding the all-ones matrix moves the eigenvalue of the constant vector from 0 to n
    # and keeps the rest, so the smallest eigenvector is u_2, even when b = 0.
    u2 = np.linalg.eigh(L + np.ones_like(L))[1][:, 0]
    return u2 if u2[0] > 0 else -u2


# Vertex t of the left clique sits at angle order[t] * 36 degrees, so the first bridges
# join the vertices that face each other. Its partner m + t sits at the mirror image in
# the right clique, which makes every bridge horizontal.
order = np.array([0, 1, -1, 2, -2, 3, -3, 4, -4, 5])
left = np.column_stack([-1.2 + 0.8 * np.cos(2 * np.pi * order / m), 0.8 * np.sin(2 * np.pi * order / m)])
pos = np.vstack([left, left * [-1, 1]])


def segments(edges, pos):
    """Coordinates for drawing the edges as one plotly line trace."""
    xs, ys = [], []
    for i, j in edges:
        xs += [pos[i, 0], pos[j, 0], None]
        ys += [pos[i, 1], pos[j, 1], None]
    return xs, ys


u2s = [fiedler(two_cliques(m, b)) for b in bridges]
cmax = max(np.abs(u).max() for u in u2s)
diverging = [[0, COLOR[1]], [0.5, "#a8a8a3"], [1, COLOR[0]]]

fig = go.Figure()
xs, ys = segments(two_cliques(m, 0).edges(), pos)
fig.add_trace(go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=INK, width=1), opacity=0.35,
                         hoverinfo="skip", showlegend=False))
for b, u2 in zip(bridges, u2s):
    xs, ys = segments([(t, m + t) for t in range(b)], pos)
    fig.add_trace(go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=COLOR[2], width=3),
                             hoverinfo="skip", showlegend=False, visible=bool(b == 1)))
    fig.add_trace(go.Scatter(
        x=pos[:, 0], y=pos[:, 1], mode="markers", showlegend=False, visible=bool(b == 1),
        marker=dict(size=13, color=u2, colorscale=diverging, cmin=-cmax, cmax=cmax,
                    line=dict(color="white", width=1),
                    colorbar=dict(title="u₂ entry", thickness=12, len=0.8)),
        customdata=np.column_stack([np.arange(2 * m), u2]),
        hovertemplate="vertex %{customdata[0]}<br>u₂ = %{customdata[1]:.3f}<extra></extra>",
    ))


def title(b, lam):
    return f"b = {b} bridge{'' if b == 1 else 's'}:  λ₂ = {lam:.3f}"


steps = [dict(method="update", label=str(b),
              args=[{"visible": [True] + [bool(k == b) for k in bridges for _ in range(2)]},
                    {"title.text": title(b, lam)}])
         for b, lam in zip(bridges, lam2_bridges)]
fig.update_xaxes(visible=False, range=[-2.2, 2.2])
fig.update_yaxes(visible=False, range=[-1, 1], scaleanchor="x")
style(fig, height=470, title=title(1, lam2_bridges[1]), showlegend=False)
fig.update_layout(
    margin=dict(b=40),
    sliders=[dict(active=1, steps=steps, pad=dict(t=10), font=dict(color=INK),
                  currentvalue=dict(prefix="number of bridges: ", font=dict(color=INK)))],
)
fig.show()

Figure 2: The graphs two_cliques(10, b) for $b=0,\dots,10$; use the slider to change $b$. Bridges are green, and each vertex is colored by its entry of the Fiedler vector $\bfu_2$.

Plot λ₂ against the number of bridges

fig = make_subplots(rows=1, cols=2, horizontal_spacing=0.12,
                    subplot_titles=["λ₂ against the number of bridges", "Fiedler vector"])
fig.add_trace(go.Scatter(x=bridges, y=2 * bridges / m, mode="lines", name="bound 2b/m",
                         line=dict(color=INK, dash="dash")), row=1, col=1)
fig.add_trace(go.Scatter(x=bridges, y=lam2_bridges, mode="markers+lines", name="λ₂",
                         marker=dict(color=COLOR[0], size=8), line=dict(color=COLOR[0])), row=1, col=1)
for k, b in enumerate([1, 10]):
    u2 = np.linalg.eigh(laplacian(two_cliques(m, b)))[1][:, 1]
    u2 = u2 if u2[0] > 0 else -u2
    fig.add_trace(go.Scatter(x=np.arange(2 * m), y=u2, mode="markers+lines", name=f"u₂ for b = {b}",
                             marker=dict(color=COLOR[k + 1], size=7), line=dict(color=COLOR[k + 1])),
                  row=1, col=2)
fig.update_xaxes(title="number of bridges b", row=1, col=1)
fig.update_yaxes(title="λ₂", row=1, col=1)
fig.update_xaxes(title="vertex", row=1, col=2)
style(fig, height=380, showlegend=True)
fig.update_annotations(font=dict(size=13, color=INK))
fig.show()

Figure 3: Left: $\lambda_2$ for two complete graphs on $10$ vertices joined by $b$ bridges, against the test-vector bound $2b/m$. Right: the Fiedler vector for $b=1$ and $b=10$, by vertex; vertices $0$–$9$ form one clique and $10$–$19$ the other.

Each bridge adds about $0.2$ to $\lambda_2$, and $\lambda_2$ stays close to the bound. The Fiedler vector is nearly a step function, a soft indicator of the two cliques, whether there is one bridge or ten.

Where an edge goes matters

Adding an edge never decreases $\lambda_2$ (this is a homework problem), but how much it increases depends on where the edge goes. Start from two random communities of $15$ vertices, each with about $40\%$ of its possible edges, joined by a single edge. Then add $20$ random new edges, either all inside the communities or all across them.

rng = np.random.default_rng(0)
start = nx.disjoint_union(nx.gnp_random_graph(15, 0.4, seed=1), nx.gnp_random_graph(15, 0.4, seed=2))
start.add_edge(0, 15)
community = np.arange(30) < 15

missing = [(i, j) for i in range(30) for j in range(i + 1, 30) if not start.has_edge(i, j)]
pools = {"inside": [e for e in missing if community[e[0]] == community[e[1]]],
         "across": [e for e in missing if community[e[0]] != community[e[1]]]}

growth, added = {}, {}
for name, pool in pools.items():
    G = start.copy()
    values = [lambda_2(G)]
    added[name] = [pool[k] for k in rng.permutation(len(pool))[:20]]
    for e in added[name]:
        G.add_edge(*e)
        values.append(lambda_2(G))
    growth[name] = np.array(values)
    print(f"{name}: lambda_2 from {values[0]:.3f} to {values[-1]:.3f}")

inside: lambda_2 from 0.094 to 0.103
across: lambda_2 from 0.094 to 1.614

Plot λ₂ as edges are added

fig = go.Figure()
for k, (name, values) in enumerate(growth.items()):
    fig.add_trace(go.Scatter(x=np.arange(len(values)), y=values, mode="markers+lines",
                             name=f"edges added {name}", marker=dict(color=COLOR[k], size=7),
                             line=dict(color=COLOR[k])))
fig.update_xaxes(title="number of edges added")
fig.update_yaxes(title="λ₂", rangemode="tozero")
style(fig, height=360, showlegend=True)
fig.update_layout(legend=dict(x=0.02, y=0.98, xanchor="left", yanchor="top"))
fig.show()

Figure 4: $\lambda_2$ as random edges are added one at a time to two communities joined by one edge, either inside the communities or across them.

Here are the graphs themselves. Move the slider to add edges, drawn in green; the left panel adds them inside the communities and the right panel across. As before, each vertex is colored by its entry of the Fiedler vector $\bfu_2$ of the current graph.

Draw the graphs with a slider over the number of added edges

# A spring layout of the starting graph pulls the two communities apart on its own.
# Rotate it so that the first community sits on the left.
P = np.array([nx.spring_layout(start, seed=0)[v] for v in range(30)])
d = P[community].mean(axis=0) - P[~community].mean(axis=0)
c, s = -d / np.linalg.norm(d)
where_pos = (P - P.mean(axis=0)) @ np.array([[c, -s], [s, c]])

steps_k = np.arange(21)
u2_where = {name: [fiedler(nx.Graph(list(start.edges()) + added[name][:k])) for k in steps_k]
            for name in added}
cmax = max(np.abs(u).max() for us in u2_where.values() for u in us)

fig = make_subplots(rows=1, cols=2, horizontal_spacing=0.04,
                    subplot_titles=[name for name in added])
keys = []    # the k at which each trace is visible, or None for always
for col, name in enumerate(added, start=1):
    xs, ys = segments(start.edges(), where_pos)
    fig.add_trace(go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=INK, width=1), opacity=0.45,
                             hoverinfo="skip", showlegend=False), row=1, col=col)
    keys.append(None)
for k in steps_k:
    for col, name in enumerate(added, start=1):
        xs, ys = segments(added[name][:k], where_pos)
        fig.add_trace(go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=COLOR[2], width=2.5),
                                 hoverinfo="skip", showlegend=False), row=1, col=col)
        u2 = u2_where[name][k]
        fig.add_trace(go.Scatter(
            x=where_pos[:, 0], y=where_pos[:, 1], mode="markers", showlegend=False,
            marker=dict(size=11, color=u2, coloraxis="coloraxis", line=dict(color="white", width=1)),
            customdata=np.column_stack([np.arange(30), u2]),
            hovertemplate="vertex %{customdata[0]}<br>u₂ = %{customdata[1]:.3f}<extra></extra>",
        ), row=1, col=col)
        keys += [k, k]


def visible(k):
    return [bool(key is None or key == k) for key in keys]


def panel_titles(k):
    return {f"annotations[{i}].text": f"edges added {name}:  λ₂ = {growth[name][k]:.3f}"
            for i, name in enumerate(added)}


for i, flag in enumerate(visible(20)):
    fig.data[i].visible = flag
steps = [dict(method="update", label=str(k), args=[{"visible": visible(k)}, panel_titles(k)])
         for k in steps_k]
xspan, yspan = np.abs(where_pos).max(axis=0) + 0.12
fig.update_xaxes(visible=False, range=[-xspan, xspan])
fig.update_yaxes(visible=False, range=[-yspan, yspan])
fig.layout.yaxis.scaleanchor = "x"
fig.layout.yaxis2.scaleanchor = "x2"
style(fig, height=380, showlegend=False)
fig.update_annotations(font=dict(size=13, color=INK))
fig.update_layout(
    panel_titles(20),
    margin=dict(b=40),
    coloraxis=dict(colorscale=diverging, cmin=-cmax, cmax=cmax,
                   colorbar=dict(title="u₂ entry", thickness=12, len=0.8)),
    sliders=[dict(active=20, steps=steps, pad=dict(t=10), font=dict(color=INK),
                  currentvalue=dict(prefix="edges added: ", font=dict(color=INK)))],
)
fig.show()

Figure 5: The two communities after $k$ added edges, inside (left) and across (right); use the slider to change $k$. Added edges are green, and each vertex is colored by its entry of the Fiedler vector $\bfu_2$ of the current graph.

Twenty edges inside the communities barely move $\lambda_2$ whereas twenty across multiply it by more than $15$. The quadratic form explains why. Adding the edge $\{i,j\}$ with weight $1$ adds $(f_i-f_j)^2$ to the roughness of every $\bff$. The Fiedler vector is nearly constant on each community, so an edge inside a community barely changes its roughness, and the old Fiedler vector stays almost optimal. An edge across the bottleneck joins two vertices where $\bfu_2$ takes very different values, and makes that vector much rougher. After enough edges across, the two communities stop being a bottleneck at all. In the right panel of Figure 5 at $20$ edges, the Fiedler vector no longer splits the vertices by community.

Footnotes

It heavily relates to a concept known as conductance, but I can’t stuff that in your brain this time around.↩︎

--- title: "$\\lambda_2$ and Connectivity" subtitle: "Math 123: Mathematical Aspects of Data Analysis — Fall 2026" date: 2026-10-29 number-sections: false jupyter: python3 format: html: toc: true toc-depth: 2 code-line-numbers: true code-tools: true out-width: "100%" column: page execute: echo: true draft: false --- The second-smallest eigenvalue $\lambda_2$ of the [graph Laplacian](../../lectures/lecture-13.qmd#def-graph-laplacian) is called the *algebraic connectivity*[^conductance]. We know two facts about it. 1) By [the kernel of the Laplacian](../../lectures/lecture-14.qmd#prp-laplacian-kernel), $\lambda_2=0$ exactly when the graph is disconnected. 2) By [Rayleigh–Ritz](../../lectures/lecture-14.qmd#prp-rayleigh-ritz), $$ \lambda_2=\min\Big\{\bff^\top\bfL\bff:\ \|\bff\|_2=1,\ \bff\perp\mathbf{1}\Big\} =\min\Big\{\textstyle\sum_{\{i,j\}\in E}w_{ij}(f_i-f_j)^2:\ \|\bff\|_2=1,\ \bff\perp\mathbf{1}\Big\}, $$ the roughness of the smoothest function that is not constant. In this short example, I want to connect those two facts. In particular, I want to conclude that $\lambda_2$ is small when the graph has a *bottleneck*, a set of vertices joined to the rest by few edges compared with its size. [^conductance]: It heavily relates to a concept known as conductance, but I can't stuff that in your brain this time around. ```{python} import networkx as nx import numpy as np import plotly.graph_objects as go from plotly.subplots import make_subplots ``` ```{python} #| code-fold: true #| code-summary: "Figure style" # A muted ink colour and a translucent grid read correctly against both the # light and the dark version of this site, so the figures need no theme switch. INK = "#7c7c78" GRID = "rgba(128, 128, 128, 0.28)" COLOR = ["#2a78d6", "#eb6834", "#2ca25f"] def style(fig, height=420, title=None, showlegend=None): """Apply the shared layout to a plot with axes.""" fig.update_layout( template="simple_white", paper_bgcolor="rgba(0,0,0,0)", plot_bgcolor="rgba(0,0,0,0)", font=dict(color=INK, size=13), title=dict(text=title, x=0, xanchor="left", font=dict(size=15)), margin=dict(l=70, r=30, t=60 if title else 30, b=55), height=height, showlegend=showlegend, hovermode="closest", ) fig.update_xaxes(gridcolor=GRID, linecolor=GRID, zerolinecolor=GRID) fig.update_yaxes(gridcolor=GRID, linecolor=GRID, zerolinecolor=GRID) return fig def graph_traces(G, pos, color=COLOR[0]): """Plotly traces drawing the edges and vertices of G at the positions pos.""" xs, ys = [], [] for i, j in G.edges(): xs += [pos[i][0], pos[j][0], None] ys += [pos[i][1], pos[j][1], None] nodes = list(G.nodes()) return [ go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=INK, width=1), opacity=0.6, hoverinfo="skip", showlegend=False), go.Scatter(x=[pos[v][0] for v in nodes], y=[pos[v][1] for v in nodes], mode="markers", marker=dict(size=8, color=color, line=dict(color="white", width=0.8)), hoverinfo="skip", showlegend=False), ] ``` Throughout, the Laplacian comes from the adjacency matrix exactly as in lecture. ```{python} def laplacian(G): W = nx.to_numpy_array(G, nodelist=sorted(G.nodes())) return np.diag(W.sum(axis=1)) - W def lambda_2(G): return np.linalg.eigvalsh(laplacian(G))[1] ``` ## Six graphs on twenty vertices {#sec-shapes} Here are six graphs, each with $20$ vertices. The *barbell* is two complete graphs on $10$ vertices joined by a single edge, very similar to the [barbell from lecture](../../lectures/lecture-13.qmd#fig-barbell). ```{python} def circle(n, center=(0.0, 0.0), radius=1.0): t = 2 * np.pi * np.arange(n) / n return np.column_stack([center[0] + radius * np.cos(t), center[1] + radius * np.sin(t)]) barbell = nx.disjoint_union(nx.complete_graph(10), nx.complete_graph(10)) barbell.add_edge(5, 10) # the bridge, between the two vertices of the circles that face each other grid = nx.convert_node_labels_to_integers(nx.grid_2d_graph(4, 5), label_attribute="xy") shapes = { "path": (nx.path_graph(20), {i: (i / 19 * 2 - 1, 0.0) for i in range(20)}), "cycle": (nx.cycle_graph(20), dict(enumerate(circle(20)))), "4 × 5 grid": (grid, {v: (0.5 * grid.nodes[v]["xy"][1] - 1, 0.5 * grid.nodes[v]["xy"][0] - 0.75) for v in grid}), "barbell": (barbell, dict(enumerate(np.vstack([circle(10, (1.2, 0), 0.8), circle(10, (-1.2, 0), 0.8)])))), "star": (nx.star_graph(19), {0: (0.0, 0.0), **{i: tuple(circle(19)[i - 1]) for i in range(1, 20)}}), "complete": (nx.complete_graph(20), dict(enumerate(circle(20)))), } for name, (G, _) in shapes.items(): print(f"{name:>10}: {G.number_of_edges():3d} edges, lambda_2 = {lambda_2(G):7.4f}") ``` ```{python} #| label: fig-shapes #| fig-cap: "Six graphs on $20$ vertices, with the algebraic connectivity $\\lambda_2$ and the number of edges of each." #| fig-alt: "Six small graph drawings in two rows: a path, a cycle, a 4 by 5 grid, a barbell made of two dense clusters joined by one edge, a star, and a complete graph. Their titles give lambda 2 as 0.025, 0.098, 0.382, 0.169, 1, and 20." #| code-fold: true #| code-summary: "Draw the six graphs" fig = make_subplots(rows=2, cols=3, horizontal_spacing=0.04, vertical_spacing=0.12, subplot_titles=[f"{name}: λ₂ = {lambda_2(G):.3g}, {G.number_of_edges()} edges" for name, (G, _) in shapes.items()]) for k, (name, (G, pos)) in enumerate(shapes.items()): for trace in graph_traces(G, pos): fig.add_trace(trace, row=k // 3 + 1, col=k % 3 + 1) fig.update_xaxes(visible=False, range=[-2.1, 2.1]) fig.update_yaxes(visible=False, range=[-1.2, 1.2]) for i in range(1, 7): suffix = "" if i == 1 else str(i) fig.layout[f"yaxis{suffix}"].scaleanchor = f"x{suffix}" style(fig, height=480) fig.update_annotations(font=dict(size=13, color=INK)) fig.show() ``` Two things stand out. - *Edges are not connectivity.* The barbell has $91$ edges and the grid only $31$, yet the grid has more than twice the algebraic connectivity. Cutting one edge splits the barbell into two halves of $10$ vertices, while no small set of edges splits the grid into big pieces. - *A bottleneck means few edges per vertex cut off.* The path and the star are both trees with $19$ edges, yet $\lambda_2$ is $0.025$ for the path and $1$ for the star. Removing the middle edge of the path cuts off $10$ vertices with $1$ edge, a ratio of $1/10$. The star looks fragile, since every path between two leaves goes through the center, but that weak point is a single vertex, and $\lambda_2$ only sees edges. Cutting off $s$ leaves takes exactly $s$ edges, a ratio of $1$, so the star has no bottleneck in the sense of the introduction. Recall the test vector from the [relaxed balanced cut](../../lectures/lecture-14.qmd#prp-relaxed-bisection). If $S$ is half the vertices and $\bfy=\mathbf{1}_S-\mathbf{1}_{S^c}$, then $\bfy\perp\mathbf{1}$, $\|\bfy\|_2^2=n$, and $\bfy^\top\bfL\bfy=4\operatorname{cut}(S)$, so $$ \lambda_2\leq\frac{\bfy^\top\bfL\bfy}{\|\bfy\|_2^2}=\frac{4\operatorname{cut}(S)}{n}. $$ Thus, the existance of a small balanced cut *forces* a small $\lambda_2$. For the path and the barbell, $\operatorname{cut}(S)=1$ gives $\lambda_2\leq4/20=0.2$, and indeed $\lambda_2$ is $0.025$ and $0.169$. The converse, that a small $\lambda_2$ forces some small cut, is also true up to a square root, and is called Cheeger's inequality; we might see it later. ## Adding bridges {#sec-bridges} Suppose I have two complete graphs with $m = 10$ vertices. Let's join them together with $b$ bridge edges, with no vertex on more than one bridge. The bound above, with $S$ one of the two cliques, gives $\lambda_2\leq4b/(2m)=b/5$. ```{python} def two_cliques(m, b): """Two complete graphs on m vertices, joined by the b bridges {t, m + t}, t < b.""" G = nx.disjoint_union(nx.complete_graph(m), nx.complete_graph(m)) G.add_edges_from((t, m + t) for t in range(b)) return G m = 10 bridges = np.arange(0, m + 1) lam2_bridges = np.array([lambda_2(two_cliques(m, b)) for b in bridges]) for b, lam in zip(bridges, lam2_bridges): print(f"b = {b:2d}: lambda_2 = {lam:.3f}, bound 2b/m = {2 * b / m:.1f}") ``` Here are those graphs. Move the slider to add bridges, drawn in green. Each vertex is colored by its entry of the Fiedler vector $\bfu_2$, so blue and orange mark the two signs. ```{python} #| label: fig-bridges-graphs #| fig-cap: "The graphs `two_cliques(10, b)` for $b=0,\\dots,10$; use the slider to change $b$. Bridges are green, and each vertex is colored by its entry of the Fiedler vector $\\bfu_2$." #| fig-alt: "Two circles of 10 vertices each, every pair within a circle joined by a gray edge, with green horizontal bridge edges between matching vertices of the two circles. A slider below sets the number of bridges from 0 to 10, and the title gives lambda 2. For every number of bridges, the vertices of the left clique are blue and those of the right clique are orange." #| code-fold: true #| code-summary: "Draw the graphs with a slider over b" def fiedler(G): """The Fiedler vector of G, with the sign chosen so that vertex 0 is positive.""" L = laplacian(G) # Adding the all-ones matrix moves the eigenvalue of the constant vector from 0 to n # and keeps the rest, so the smallest eigenvector is u_2, even when b = 0. u2 = np.linalg.eigh(L + np.ones_like(L))[1][:, 0] return u2 if u2[0] > 0 else -u2 # Vertex t of the left clique sits at angle order[t] * 36 degrees, so the first bridges # join the vertices that face each other. Its partner m + t sits at the mirror image in # the right clique, which makes every bridge horizontal. order = np.array([0, 1, -1, 2, -2, 3, -3, 4, -4, 5]) left = np.column_stack([-1.2 + 0.8 * np.cos(2 * np.pi * order / m), 0.8 * np.sin(2 * np.pi * order / m)]) pos = np.vstack([left, left * [-1, 1]]) def segments(edges, pos): """Coordinates for drawing the edges as one plotly line trace.""" xs, ys = [], [] for i, j in edges: xs += [pos[i, 0], pos[j, 0], None] ys += [pos[i, 1], pos[j, 1], None] return xs, ys u2s = [fiedler(two_cliques(m, b)) for b in bridges] cmax = max(np.abs(u).max() for u in u2s) diverging = [[0, COLOR[1]], [0.5, "#a8a8a3"], [1, COLOR[0]]] fig = go.Figure() xs, ys = segments(two_cliques(m, 0).edges(), pos) fig.add_trace(go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=INK, width=1), opacity=0.35, hoverinfo="skip", showlegend=False)) for b, u2 in zip(bridges, u2s): xs, ys = segments([(t, m + t) for t in range(b)], pos) fig.add_trace(go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=COLOR[2], width=3), hoverinfo="skip", showlegend=False, visible=bool(b == 1))) fig.add_trace(go.Scatter( x=pos[:, 0], y=pos[:, 1], mode="markers", showlegend=False, visible=bool(b == 1), marker=dict(size=13, color=u2, colorscale=diverging, cmin=-cmax, cmax=cmax, line=dict(color="white", width=1), colorbar=dict(title="u₂ entry", thickness=12, len=0.8)), customdata=np.column_stack([np.arange(2 * m), u2]), hovertemplate="vertex %{customdata[0]}<br>u₂ = %{customdata[1]:.3f}<extra></extra>", )) def title(b, lam): return f"b = {b} bridge{'' if b == 1 else 's'}: λ₂ = {lam:.3f}" steps = [dict(method="update", label=str(b), args=[{"visible": [True] + [bool(k == b) for k in bridges for _ in range(2)]}, {"title.text": title(b, lam)}]) for b, lam in zip(bridges, lam2_bridges)] fig.update_xaxes(visible=False, range=[-2.2, 2.2]) fig.update_yaxes(visible=False, range=[-1, 1], scaleanchor="x") style(fig, height=470, title=title(1, lam2_bridges[1]), showlegend=False) fig.update_layout( margin=dict(b=40), sliders=[dict(active=1, steps=steps, pad=dict(t=10), font=dict(color=INK), currentvalue=dict(prefix="number of bridges: ", font=dict(color=INK)))], ) fig.show() ``` ```{python} #| label: fig-bridges #| fig-cap: "Left: $\\lambda_2$ for two complete graphs on $10$ vertices joined by $b$ bridges, against the test-vector bound $2b/m$. Right: the Fiedler vector for $b=1$ and $b=10$, by vertex; vertices $0$–$9$ form one clique and $10$–$19$ the other." #| fig-alt: "Left panel: lambda 2 rises almost linearly from 0 at b equals 0 to 2 at b equals 10, just below a dashed straight line for the bound 2b over m, which it touches at b equals 10. Right panel: two step-shaped curves over vertex index 0 to 19. Each is near one constant value on the first clique and near the negative of that value on the second." #| code-fold: true #| code-summary: "Plot λ₂ against the number of bridges" fig = make_subplots(rows=1, cols=2, horizontal_spacing=0.12, subplot_titles=["λ₂ against the number of bridges", "Fiedler vector"]) fig.add_trace(go.Scatter(x=bridges, y=2 * bridges / m, mode="lines", name="bound 2b/m", line=dict(color=INK, dash="dash")), row=1, col=1) fig.add_trace(go.Scatter(x=bridges, y=lam2_bridges, mode="markers+lines", name="λ₂", marker=dict(color=COLOR[0], size=8), line=dict(color=COLOR[0])), row=1, col=1) for k, b in enumerate([1, 10]): u2 = np.linalg.eigh(laplacian(two_cliques(m, b)))[1][:, 1] u2 = u2 if u2[0] > 0 else -u2 fig.add_trace(go.Scatter(x=np.arange(2 * m), y=u2, mode="markers+lines", name=f"u₂ for b = {b}", marker=dict(color=COLOR[k + 1], size=7), line=dict(color=COLOR[k + 1])), row=1, col=2) fig.update_xaxes(title="number of bridges b", row=1, col=1) fig.update_yaxes(title="λ₂", row=1, col=1) fig.update_xaxes(title="vertex", row=1, col=2) style(fig, height=380, showlegend=True) fig.update_annotations(font=dict(size=13, color=INK)) fig.show() ``` Each bridge adds about $0.2$ to $\lambda_2$, and $\lambda_2$ stays close to the bound. The Fiedler vector is nearly a step function, a [soft indicator](../../lectures/lecture-14.qmd#splitting-a-graph-in-two) of the two cliques, whether there is one bridge or ten. ## Where an edge goes matters {#sec-where} Adding an edge never decreases $\lambda_2$ (this is a homework problem), but *how much* it increases depends on where the edge goes. Start from two random communities of $15$ vertices, each with about $40\%$ of its possible edges, joined by a single edge. Then add $20$ random new edges, either all *inside* the communities or all *across* them. ```{python} rng = np.random.default_rng(0) start = nx.disjoint_union(nx.gnp_random_graph(15, 0.4, seed=1), nx.gnp_random_graph(15, 0.4, seed=2)) start.add_edge(0, 15) community = np.arange(30) < 15 missing = [(i, j) for i in range(30) for j in range(i + 1, 30) if not start.has_edge(i, j)] pools = {"inside": [e for e in missing if community[e[0]] == community[e[1]]], "across": [e for e in missing if community[e[0]] != community[e[1]]]} growth, added = {}, {} for name, pool in pools.items(): G = start.copy() values = [lambda_2(G)] added[name] = [pool[k] for k in rng.permutation(len(pool))[:20]] for e in added[name]: G.add_edge(*e) values.append(lambda_2(G)) growth[name] = np.array(values) print(f"{name}: lambda_2 from {values[0]:.3f} to {values[-1]:.3f}") ``` ```{python} #| label: fig-where #| fig-cap: "$\\lambda_2$ as random edges are added one at a time to two communities joined by one edge, either inside the communities or across them." #| fig-alt: "Two increasing curves over 0 to 20 added edges. The curve for edges across the communities climbs steadily from about 0.09 to about 1.6. The curve for edges inside the communities stays nearly flat, ending near 0.1." #| code-fold: true #| code-summary: "Plot λ₂ as edges are added" fig = go.Figure() for k, (name, values) in enumerate(growth.items()): fig.add_trace(go.Scatter(x=np.arange(len(values)), y=values, mode="markers+lines", name=f"edges added {name}", marker=dict(color=COLOR[k], size=7), line=dict(color=COLOR[k]))) fig.update_xaxes(title="number of edges added") fig.update_yaxes(title="λ₂", rangemode="tozero") style(fig, height=360, showlegend=True) fig.update_layout(legend=dict(x=0.02, y=0.98, xanchor="left", yanchor="top")) fig.show() ``` Here are the graphs themselves. Move the slider to add edges, drawn in green; the left panel adds them inside the communities and the right panel across. As before, each vertex is colored by its entry of the Fiedler vector $\bfu_2$ of the current graph. ```{python} #| label: fig-where-graphs #| fig-cap: "The two communities after $k$ added edges, inside (left) and across (right); use the slider to change $k$. Added edges are green, and each vertex is colored by its entry of the Fiedler vector $\\bfu_2$ of the current graph." #| fig-alt: "Two side-by-side drawings of the same graph: two clusters of 15 vertices joined by one gray edge. A slider below sets the number of added edges from 0 to 20, and the panel titles give lambda 2. In the left panel the green added edges stay inside each cluster, and the vertices stay blue in one cluster and orange in the other. In the right panel the green edges run between the clusters, and by 20 edges the two colors no longer follow the clusters." #| code-fold: true #| code-summary: "Draw the graphs with a slider over the number of added edges" # A spring layout of the starting graph pulls the two communities apart on its own. # Rotate it so that the first community sits on the left. P = np.array([nx.spring_layout(start, seed=0)[v] for v in range(30)]) d = P[community].mean(axis=0) - P[~community].mean(axis=0) c, s = -d / np.linalg.norm(d) where_pos = (P - P.mean(axis=0)) @ np.array([[c, -s], [s, c]]) steps_k = np.arange(21) u2_where = {name: [fiedler(nx.Graph(list(start.edges()) + added[name][:k])) for k in steps_k] for name in added} cmax = max(np.abs(u).max() for us in u2_where.values() for u in us) fig = make_subplots(rows=1, cols=2, horizontal_spacing=0.04, subplot_titles=[name for name in added]) keys = [] # the k at which each trace is visible, or None for always for col, name in enumerate(added, start=1): xs, ys = segments(start.edges(), where_pos) fig.add_trace(go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=INK, width=1), opacity=0.45, hoverinfo="skip", showlegend=False), row=1, col=col) keys.append(None) for k in steps_k: for col, name in enumerate(added, start=1): xs, ys = segments(added[name][:k], where_pos) fig.add_trace(go.Scatter(x=xs, y=ys, mode="lines", line=dict(color=COLOR[2], width=2.5), hoverinfo="skip", showlegend=False), row=1, col=col) u2 = u2_where[name][k] fig.add_trace(go.Scatter( x=where_pos[:, 0], y=where_pos[:, 1], mode="markers", showlegend=False, marker=dict(size=11, color=u2, coloraxis="coloraxis", line=dict(color="white", width=1)), customdata=np.column_stack([np.arange(30), u2]), hovertemplate="vertex %{customdata[0]}<br>u₂ = %{customdata[1]:.3f}<extra></extra>", ), row=1, col=col) keys += [k, k] def visible(k): return [bool(key is None or key == k) for key in keys] def panel_titles(k): return {f"annotations[{i}].text": f"edges added {name}: λ₂ = {growth[name][k]:.3f}" for i, name in enumerate(added)} for i, flag in enumerate(visible(20)): fig.data[i].visible = flag steps = [dict(method="update", label=str(k), args=[{"visible": visible(k)}, panel_titles(k)]) for k in steps_k] xspan, yspan = np.abs(where_pos).max(axis=0) + 0.12 fig.update_xaxes(visible=False, range=[-xspan, xspan]) fig.update_yaxes(visible=False, range=[-yspan, yspan]) fig.layout.yaxis.scaleanchor = "x" fig.layout.yaxis2.scaleanchor = "x2" style(fig, height=380, showlegend=False) fig.update_annotations(font=dict(size=13, color=INK)) fig.update_layout( panel_titles(20), margin=dict(b=40), coloraxis=dict(colorscale=diverging, cmin=-cmax, cmax=cmax, colorbar=dict(title="u₂ entry", thickness=12, len=0.8)), sliders=[dict(active=20, steps=steps, pad=dict(t=10), font=dict(color=INK), currentvalue=dict(prefix="edges added: ", font=dict(color=INK)))], ) fig.show() ``` Twenty edges inside the communities barely move $\lambda_2$ whereas twenty across multiply it by more than $15$. The quadratic form explains why. Adding the edge $\{i,j\}$ with weight $1$ adds $(f_i-f_j)^2$ to the roughness of every $\bff$. The Fiedler vector is nearly constant on each community, so an edge inside a community barely changes its roughness, and the old Fiedler vector stays almost optimal. An edge across the bottleneck joins two vertices where $\bfu_2$ takes very different values, and makes that vector much rougher. After enough edges across, the two communities stop being a bottleneck at all. In the right panel of @fig-where-graphs at $20$ edges, the Fiedler vector no longer splits the vertices by community.