Network Analysis Workshop: From Edge List to Laplacian

From an Edge List to Matrices

A network can be recorded compactly as a list of its vertices and the weighted edges joining them. Matrices make the same information available to systematic calculations: an adjacency matrix records which pairs are connected and with what weights, a degree matrix records the total weight incident to each vertex, and the Laplacian combines the two. These representations are useful only when the vertex order and the meaning of each entry are kept explicit.

In this tutorial, a network is a finite, undirected graph with no loops. Every edge has a positive real weight, and each unordered pair of vertices appears at most once in the edge list. If an input lists the same pair more than once, combine those weights before building the matrices. Fix an order \(v_1,\dots,v_n\) of all vertices, including any isolated vertices. Two vertices are neighbors if an edge joins them.

Because the graph is undirected, \(a_{ij}=a_{ji}\), so \(\mathbf{A}\) is symmetric. The no-loops assumption gives \(a_{ii}=0\). A vertex’s number of neighbors is not generally the same as its weighted degree: the number counts adjacent vertices, whereas the weighted degree adds the incident edge weights. An isolated vertex has a zero row and column in \(\mathbf{A}\), and its diagonal entry in \(\mathbf{D}\) is zero.

To build the matrices, choose and keep one vertex order, place each edge weight in both corresponding off-diagonal positions of \(\mathbf{A}\), and leave all other entries zero. Then add each row of \(\mathbf{A}\) to obtain its weighted degree, place those degrees on the diagonal of \(\mathbf{D}\), and subtract \(\mathbf{A}\) from \(\mathbf{D}\). The following example shows every entry.

Reading Neighbors and Checking Connectivity

Once the vertex order is fixed, row \(i\) of \(\mathbf{A}\) gives the weights of the edges incident to \(v_i\). Its nonzero positions identify the neighbors, and the corresponding values give the edge weights. In the first example, row \(C\) is \((1,3,0,4)\): \(C\) is adjacent to \(A\), \(B\), and \(D\), with weights \(1\), \(3\), and \(4\). Its weighted degree is their sum, \(8\), while it has three neighbors.

A graph is connected if every pair of vertices can be joined by a path of edges; otherwise it is disconnected. Edge weights do not change this definition here: every listed edge has positive weight, so connectivity depends on whether an edge exists, not on its numerical weight. For example, in the first network, \(A\) connects to \(B\) and \(C\), and \(C\) connects to \(D\). Hence every vertex can be reached from \(A\), so the network is connected.

Proof. Since \(\mathbf{D}\) is diagonal, \(\mathbf{x}^{\top}\mathbf{D}\mathbf{x}=\sum_{i=1}^n d_i x_i^2\). Each edge \(\{i,j\}\) of weight \(a_{ij}\) contributes \(a_{ij}x_i^2\) to this sum through \(d_i\), and contributes another \(a_{ij}x_j^2\) through \(d_j\). Because the graph is undirected, \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}=\sum_{i,j}a_{ij}x_ix_j\); the edge \(\{i,j\}\) contributes \(2a_{ij}x_ix_j\), once from each of the two symmetric positions. There are no loop contributions. Subtracting the adjacency expression from the degree expression therefore gives, edge by edge, \(a_{ij}x_i^2+a_{ij}x_j^2-2a_{ij}x_ix_j=a_{ij}(x_i-x_j)^2\). Summing over the edges proves the identity. \(\square\)

Proof. Suppose first that \(\mathbf{L}\mathbf{x}=\mathbf{0}\). Then \(\mathbf{x}^{\top}\mathbf{L}\mathbf{x}=0\). By the energy identity, this is a sum of terms \(a_{ij}(x_i-x_j)^2\). Every edge weight is positive and every square is nonnegative, so a zero sum forces \(x_i=x_j\) across every edge. Along any path, equality carries from one vertex to the next; therefore the entries are constant on each connected component.

Conversely, suppose the entries of \(\mathbf{x}\) are constant on each connected component. In row \(i\) of \(\mathbf{L}\mathbf{x}\), the result is \(\sum_{j:\{i,j\}\text{ an edge}}a_{ij}(x_i-x_j)\). Each neighbor \(j\) lies in the same component as \(i\), so \(x_i-x_j=0\) for every term. Thus every row gives zero and \(\mathbf{L}\mathbf{x}=\mathbf{0}\). If the graph is connected, it has one component, so the solutions are exactly the constant vectors. If it is disconnected, assign value \(1\) on one component and \(0\) on another; this is a nonconstant vector that is constant on each component and hence solves \(\mathbf{L}\mathbf{x}=\mathbf{0}\). This proves both directions of the connectivity statement. \(\square\)

This result gives a matrix-based test in principle: inspect the solutions of \(\mathbf{L}\mathbf{x}=\mathbf{0}\). In a small network, it is often quicker to trace paths directly from the edge list or to inspect the nonzero pattern of \(\mathbf{A}\). The theorem explains why the Laplacian carries the same component information: vectors in its null space may choose one constant value per component, but cannot vary across an edge.

Extracting a Local Neighborhood

Common Mistake: Forgetting the Undirected Pair

A common error is to enter an undirected edge in only one position of \(\mathbf{A}\). For the edge \(AB\) of weight \(2\), a mistaken entry \(a_{AB}=2\) with \(a_{BA}=0\) makes the matrix asymmetric. It also makes the row sums disagree with the intended weighted degrees: vertex \(B\) would appear to receive no weight from \(A\). The correction is to enter both \(a_{AB}=2\) and \(a_{BA}=2\), then sum each complete row.

A second check catches errors early: every row sum of \(\mathbf{A}\) must equal the corresponding diagonal entry of \(\mathbf{D}\). Consequently, every row sum of \(\mathbf{L}=\mathbf{D}-\mathbf{A}\) is zero. In an undirected, loop-free weighted graph, \(\mathbf{A}\) and \(\mathbf{L}\) must also be symmetric. These checks do not replace careful construction, but they expose many misplaced or omitted entries.