Network Basics: Graphs, Matrices, Projections, and Connectivity

Complex Systems · 4/8 · Series index · Notation

Network Basics: Representations, Graph Types, Connectivity, and Matrix Calculations

Unless stated otherwise, graphs are finite and have no self-loops or parallel edges. Directed and weighted cases are identified explicitly.

Basic Terminology and Two Graph Representations

Write a graph as $G=(V,E)$, with node set $V$ and edge set $E$. An undirected edge $\{i,j\}$ represents a symmetric relation; a directed edge $(i,j)$ represents $i\to j$. A simple graph has no self-loops or parallel edges; "simple" does not mean that its structure is regular. Complex networks often model systems with heterogeneous degrees and intricate connectivity. The word "complex" is not itself a unique graph-theoretic test.

Adjacency Matrices and Adjacency Lists

First specify the node ordering, then define the adjacency matrix. Rows are sources and columns are targets:

$$A_{ij}=\begin{cases}1,&i\to j\text{ exists (undirected: }i\text{ adjacent to }j\text{)},\\ 0,&\text{otherwise.}\end{cases}$$

For an undirected graph, the first case means that the two nodes are adjacent. An adjacency list records each node's neighbors. For directed graphs it usually lists out-neighbors; in-neighbors can be stored separately when needed. A simple undirected graph satisfies $A=A^{\mathsf T}$ and $A_{ii}=0$. Each edge appears twice in the matrix and once in the adjacency list of each endpoint.

Consider a four-node graph with edge set $\{12,13,23,34\}$. Ordering the nodes as $1,2,3,4$ gives

$$A=\begin{bmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{bmatrix}, \qquad(k_1,k_2,k_3,k_4)=(2,2,3,1).$$

The adjacency lists are $1:\{2,3\}$, $2:\{1,3\}$, $3:\{1,2,4\}$, and $4:\{3\}$. Row sums give the degrees; their total is $8$, so $M=4$.

Walks, Paths, Cycles, and Subgraphs

• A walk is a sequence of adjacent nodes and may repeat nodes or edges. Its length is the number of traversed edges.

• A path conventionally has no repeated nodes. If a question uses a broader informal definition, state the convention you adopt. Each consecutive pair must be joined by an edge, and directions must also match in a directed graph.

• A cycle returns to its starting node without repeating any other node. In a simple undirected graph, a cycle contains at least $3$ edges.

• A subgraph selects some nodes and some of the original edges between them. An induced subgraph selects nodes and retains every original edge between the selected nodes.

Two nodes are connected if there is a path between them. A connected graph has a path between every pair of nodes. A connected component is a maximal connected subgraph: no additional node can be included while preserving connectivity. An isolated node is itself a component. The largest connected component has the greatest number of nodes; "maximal" and "largest" are different concepts.

Multiple Components and Block Matrices

Group nodes from the same component together. Reordering both rows and columns gives

$$A'=PAP^{\mathsf T}=\begin{bmatrix}A_1&0&\cdots\\0&A_2&\cdots\\\vdots&\vdots&\ddots\end{bmatrix}.$$

$P$ represents only a node permutation. There are no edges between components, so the off-diagonal blocks are zero. This applies to undirected components and to distinct weak components of a directed graph. Different strong components can have one-way edges between them, so ordering nodes by strong components need not make the adjacency matrix block diagonal.

Worked Example: A Six-Node Undirected Graph

Consider the edge set

$$E=\{12,14,15,23,24,34,35,36,46\},\qquad n=6,\quad M=9.$$

Here $12$ denotes the undirected edge $\{1,2\}$, not the number twelve. If edges $1$–$4$ and $2$–$3$ cross in a drawing, their crossing does not create an extra node.

1. Adjacency Matrix and Adjacency Lists

Use the node ordering $1,2,3,4,5,6$:

$$A=\begin{bmatrix} 0&1&0&1&1&0\\ 1&0&1&1&0&0\\ 0&1&0&1&1&1\\ 1&1&1&0&0&1\\ 1&0&1&0&0&0\\ 0&0&1&1&0&0 \end{bmatrix}.$$

$$\begin{array}{lll} 1:\{2,4,5\},&2:\{1,3,4\},&3:\{2,4,5,6\},\\ 4:\{1,2,3,6\},&5:\{1,3\},&6:\{3,4\}. \end{array}$$

2. Node Degrees

Row sums give $(k_1,k_2,k_3,k_4,k_5,k_6)=(3,3,4,4,2,2)$. Check that $\sum_i k_i=18=2M$. The mean degree is $3$, and the density is $9/\binom62=0.6$.

3. Classifying Paths and Cycles

• $6$–$3$–$2$–$4$–$5$: neither, because $4$–$5$ is not an edge.

• $1$–$4$–$6$–$3$–$2$: a path of length $4$, because every consecutive pair is joined and no node repeats.

• $5$–$1$–$2$–$3$–$5$: a cycle of length $4$. All four edges exist, and only the initial/final node $5$ repeats.

4. All Connected Three-Node Subgraphs

For three-node induced subgraphs, check the $\binom63=20$ possible node sets. A three-node graph is connected whenever it has at least two edges. There are 14 connected induced subgraphs. The triangles have node sets

$$\{1,2,4\},\quad\{2,3,4\},\quad\{3,4,6\};$$

The other 11 are two-edge paths, with node sets

$$\begin{aligned} &\{1,2,3\},\ \{1,2,5\},\ \{1,3,4\},\ \{1,3,5\},\ \{1,4,5\},\ \{1,4,6\}, \\ &\{2,3,5\},\ \{2,3,6\},\ \{2,4,6\},\ \{3,4,5\},\ \{3,5,6\}. \end{aligned}$$

If the question allows deleting original edges while retaining the same node set, each triangle additionally produces three connected paths, one for each edge removed. The total is then $11+3(1+3)=\mathbf{23}$ labeled connected subgraphs. If only distinct shapes are required, ignoring labels, there are just two types: the path $P_3$ and the triangle $K_3$. State which definition of subgraph is being used.

5. Delete Nodes 3 and 4 Simultaneously

Deleting a node also deletes every incident edge. The remaining nodes are $\{1,2,5,6\}$ and the remaining edges are $\{12,15\}$, so the components are $\{1,2,5\}$ and $\{6\}$. With ordering $1,2,5,6$, the matrix has a connected $3\times3$ block in the upper left and a single zero block in the lower right.

Graph Types, Tests, and Real-World Examples

A graph can belong to several classes at once: for example, an even cycle is regular, bipartite, and planar.

Complete Graphs

Every pair of distinct nodes is joined by an edge. The complete graph is denoted $K_n$; every node has degree $n-1$, and $M=n(n-1)/2$. For example, a friendship graph of a small group is complete if every pair of members knows each other directly. Being able to reach all other nodes by paths only means connectedness; it does not mean that every pair is directly joined.

Regular Graphs

A graph in which every node has the same degree $k$ is called $k$-regular. The handshaking lemma gives

$$\boxed{M=\frac{nk}{2}}.$$

Therefore $nk$ must be even, and a simple graph also requires $0\leq k\leq n-1$. An unbroken ring communication network, with each node connected to its left and right neighbors, is $2$-regular. For $n=10,k=4$, the edge count is $M=20$. A square lattice with open boundaries usually has different degrees at the boundary, so it is not automatically regular.

Bipartite Graphs

The nodes can be split into disjoint sets $U,V$ so that every edge crosses between the sets and no edge joins two nodes in the same set. Not every possible cross-set edge needs to exist. Examples include user–movie, student–course, and actor–movie networks. To test bipartiteness, try coloring nodes with two colors so that the endpoints of every edge have different colors. Any odd cycle rules out bipartiteness. In particular, a triangle is not bipartite, while every tree is bipartite.

Trees and Forests

A tree is an undirected graph that is connected and acyclic. An acyclic graph with several components is a forest. A tree satisfies

$$\boxed{M=n-1},\qquad \text{a unique path between every pair of nodes.}$$

A forest with $C$ components has $M=n-C$. Examples of trees include an organizational hierarchy without cross-reporting and a directory hierarchy; a tree with $n=10$ has $9$ edges. The edge count $M=n-1$ alone does not prove that a graph is a tree: a further condition such as connectedness or acyclicity is needed. A triangle plus an isolated node has $n=4,M=3$ but is not a tree.

Planar Graphs

A graph is planar if it can be drawn in the plane so that edges meet only at shared endpoints and never cross elsewhere. An idealized road network without overpasses, with intersections treated as nodes, is an example; every tree is planar. Crossings in one drawing do not show that a crossing-free drawing is impossible. Merely seeing a crossing is therefore not a proof of nonplanarity.

Multilayer Networks

A multilayer network consists of layers representing different node or relation types, together with interlayer connections. For example, a power-grid layer and a communication layer can be connected through power-supply and control dependencies. Different layers may have different node sets. Explain what both the within-layer and between-layer edges represent.

Multiplex Networks

A multiplex network is a special multilayer network in which each layer represents the same objects but a different relation. Examples are friendship, coworker, and family layers on the same people, or airline and railway layers on the same cities. The layers provide different representations of the same objects. A multiplex network is not the same as a multigraph, which allows parallel edges between a pair of nodes.

Identifying a Graph Type from Its Meaning

State what the nodes represent, what the edges represent, and why the definition is satisfied. For example: "In a student–course network, the two node types are students and courses; enrollment edges only join students to courses, so the graph is bipartite." The phrase "social network" alone does not establish whether a graph is complete, regular, or bipartite.

Bipartite Matrices and Projections: A Worked Example

A bipartite graph can be represented by a rectangular incidence matrix $B$: rows correspond to objects in one set, columns to objects in the other, and $B_{u a}=1$ indicates an association. Ordering all nodes in $U$ before all nodes in $V$ gives the square adjacency matrix

$$\boxed{A_{\rm bip}=\begin{bmatrix}0&B\\B^{\mathsf T}&0\end{bmatrix}}.$$

$B$ is the rectangular bipartite representation. Distinguish it explicitly from the square adjacency matrix containing all nodes.

Specifying the Bipartite Graph

Let the row nodes be $A,B,C,D$, and the column nodes be $1,2,3,4,5,6,7$. The associations are

$$A:\{1,2,3\},\quad B:\{2,3,4,5\},\quad C:\{4,6\},\quad D:\{5,6,7\},$$

Thus, distinguishing the matrix named $B$ from the node named $B$,

$$B=\begin{bmatrix} 1&1&1&0&0&0&0\\ 0&1&1&1&1&0&0\\ 0&0&0&1&0&1&0\\ 0&0&0&0&1&1&1 \end{bmatrix}.$$

The original bipartite graph has $11$ nodes and $12$ edges. Its full $11\times11$ adjacency matrix is obtained by substituting this $B$ into the block matrix above.

Projection onto $A,B,C,D$

Two row nodes are joined in the row projection whenever they share a column neighbor. Matrix multiplication gives the number of shared neighbors:

$$BB^{\mathsf T}=\begin{bmatrix}3&2&0&0\\2&4&1&1\\0&1&2&1\\0&1&1&3\end{bmatrix}.$$

The diagonal entries are the row nodes' degrees in the original bipartite graph; they should not be treated as projection self-loops. Set the diagonal to zero, then replace every positive entry by $1$ to obtain the unweighted projection:

$$A_U=\begin{bmatrix}0&1&0&0\\1&0&1&1\\0&1&0&1\\0&1&1&0\end{bmatrix}, \qquad E_U=\{AB,BC,BD,CD\}.$$

In the weighted projection, the edge between $A$ and $B$ has weight $2$, since they share associations with $2,3$; every other existing projection edge has weight $1$.

Projection onto $1,\ldots,7$

For the column projection use $B^{\mathsf T}B$, again removing the diagonal and binarizing:

$$A_V=\begin{bmatrix} 0&1&1&0&0&0&0\\ 1&0&1&1&1&0&0\\ 1&1&0&1&1&0&0\\ 0&1&1&0&1&1&0\\ 0&1&1&1&0&1&1\\ 0&0&0&1&1&0&1\\ 0&0&0&0&1&1&0 \end{bmatrix}.$$

For example, nodes $2,3$ both connect to row nodes $A,B$, so their weighted projection edge has weight $2$; all other projection edges have weight $1$. A user–movie recommender can use shared movies to express user similarity, or shared users to express movie similarity; a ratings matrix can retain numerical weights. Projection loses information about which particular group created an association and can turn one group into a complete subgraph.

Directed and Weighted Networks, and Directed Components

Direction and weight are independent properties: a graph can be undirected and unweighted, undirected and weighted, directed and unweighted, or directed and weighted.

Directed Adjacency Matrices

We still use $A_{ij}=1$ for $i\to j$, and generally $A\ne A^{\mathsf T}$. A directed graph can nevertheless have every edge paired with its reverse, making its adjacency matrix symmetric. Thus, a directed adjacency matrix need not be asymmetric. Without self-loops,

$$\boxed{k_i^{\rm out}=\sum_jA_{ij},\qquad k_i^{\rm in}=\sum_jA_{ji}},$$

$$\sum_i k_i^{\rm out}=\sum_i k_i^{\rm in}=M,\quad \langle k^{\rm out}\rangle=\langle k^{\rm in}\rangle=\frac Mn.$$

A node's total degree is $k_i^{\rm in}+k_i^{\rm out}$, so summing total degrees over the network still gives $2M$. If a question adopts the transposed adjacency convention, interchange the row-sum and column-sum rules accordingly.

Weighted Adjacency Matrices

Use $W_{ij}=w_{ij}$ to record edge strength, distance, capacity, flow, or another numerical attribute. An absent edge is usually represented by $0$, but if zero is a valid edge weight, store connectivity separately. Undirected weights satisfy $W=W^{\mathsf T}$. Unweighted degree counts edges; the sum of edge weights is called strength:

$$s_i^{\rm out}=\sum_jW_{ij},\qquad s_i^{\rm in}=\sum_jW_{ji}.$$

For example, if $1\to2$ has weight $4$ and $1\to3$ has weight $2$, then $k_1^{\rm out}=2$ but $s_1^{\rm out}=6$. When weights represent distance, adding them along a path is meaningful for shortest-path calculations. When weights represent similarity or connection strength, a larger value usually does not mean a longer path; explain how the weights are interpreted.

Strong and Weak Connectivity

A strongly connected component (SCC) is a maximal node set in which every pair is mutually reachable along directed paths. A weakly connected component (WCC) is a maximal connected component after all edge directions are ignored. Every SCC belongs to one WCC, but a WCC need not be strongly connected. A single node without a self-loop can be an SCC because a path of length $0$ from a node to itself is allowed.

A Node's In-Component and Out-Component

$$\operatorname{Out}(v)=\{u:v\leadsto u\},\qquad \operatorname{In}(v)=\{u:u\leadsto v\}.$$

Using paths of length zero, both sets include $v$ itself. They generally overlap and do not form a disjoint partition of the graph. Their intersection is exactly the SCC containing $v$:

$$\boxed{\operatorname{SCC}(v)=\operatorname{In}(v)\cap\operatorname{Out}(v)}.$$

Find the out-component by following arrows forward; find the in-component by tracing arrows backward.

Example: Distinguishing the Four Concepts

Consider edges $1\to2,2\to3,3\to1,3\to4,5\to4$. Ignoring directions connects all five nodes, so there is one WCC. The SCCs are $\{1,2,3\}$, $\{4\}$, and $\{5\}$. For node $3$,

$$\operatorname{Out}(3)=\{1,2,3,4\},\qquad \operatorname{In}(3)=\{1,2,3\}.$$

Although node $5$ is weakly connected to $3$, it cannot reach $3$ and cannot be reached from $3$. Having a common destination, node $4$, does not imply mutual reachability.

Degrees and Two-Step Neighbors: A Worked Example

Consider a six-node directed graph with edges $1\to3,2\to6,3\to2,4\to1,4\to5,5\to3,6\to4,6\to5$. With node ordering $1,\ldots,6$,

$$A=\begin{bmatrix} 0&0&1&0&0&0\\0&0&0&0&0&1\\0&1&0&0&0&0\\ 1&0&0&0&1&0\\0&0&1&0&0&0\\0&0&0&1&1&0 \end{bmatrix}.$$

The row sums and column sums respectively give

$$\mathbf k^{\rm out}=(1,1,1,2,1,2),\qquad \mathbf k^{\rm in}=(1,1,2,1,2,1).$$

Both vectors sum to $8$, so $M=8$. Ignoring directions produces an undirected adjacency matrix, whose degrees are $(2,2,3,3,3,3)$ and total degree is $16$. The directed graph is itself strongly connected: $1\to3\to2\to6\to4\to1$ forms a cycle through five nodes, and $4\to5\to3$ makes node $5$ mutually reachable with that cycle.

Why Compute $A^2$?

By the definition of matrix multiplication,

$$(A^2)_{ij}=\sum_\ell A_{i\ell}A_{\ell j}.$$

Each intermediate node $\ell$ contributes $1$ when $i\to\ell\to j$ exists. Thus, $(A^2)_{ij}$ counts walks of length exactly $2$ from $i$ to $j$. More generally, $(A^r)_{ij}$ counts walks of length exactly $r$. It does not automatically exclude repeated nodes, and it does not directly count neighbors whose shortest-path distance is $r$.

For this example,

$$A^2=\begin{bmatrix} 0&1&0&0&0&0\\0&0&0&1&1&0\\0&0&0&0&0&1\\ 0&0&2&0&0&0\\0&1&0&0&0&0\\1&0&1&0&1&0 \end{bmatrix}.$$

For example, $(A^2)_{43}=2$ because the two walks $4\to1\to3$ and $4\to5\to3$ end at the same node $3$. Node $4$ therefore has just one distinct two-step destination, $3$; a row sum of $2$ does not mean two distinct second neighbors.

Extracting Neighbors at Exactly Distance Two

If a second neighbor is defined as a node whose shortest-path distance is exactly $2$, then for an unweighted simple graph, or for directed reachability following the given arrows,

$$\boxed{\mathcal N_2(i)=\{j:(A^2)_{ij}>0,\ A_{ij}=0,\ j\ne i\}}.$$

Binarize the positive entries, then remove the starting node and nodes already adjacent to it. In this example, $6\to5$ is a direct edge, but $6\to4\to5$ is also a two-step walk. Hence $5$ is not an exact-distance-two neighbor of $6$; $\mathcal N_2(6)=\{1,3\}$. Matrix powers count walks; exact-distance neighbours require these additional exclusions.

Two Checks for Undirected Graphs

In a simple undirected graph, $(A^2)_{ii}=k_i$, since every neighbor supplies a returning walk $i\to\ell\to i$. For $i\ne j$, $(A^2)_{ij}$ counts the common neighbors of $i,j$. For a weighted matrix $W$, $(W^2)_{ij}$ is a sum of products of weights along two-step routes, not generally a count of walks or a shortest-path distance.

Hypergraphs, Sparsity, and Computational Representations

Hypergraphs Represent Group Relations

An ordinary edge joins two nodes; a hyperedge can join several nodes at once and is a subset of the node set. A hypergraph may contain hyperedges of size $2$ as well as sizes greater than $2$; their sizes need not all be equal. For example, the complete author list of a paper, the cast of a movie, or the participants in an event can each form one hyperedge.

Treating every hyperedge as an additional node produces a bipartite graph of original nodes and hyperedge nodes. Join an original node to a hyperedge node exactly when it belongs to that hyperedge. The incidence matrix is

$$H_{ie}=\begin{cases}1,&i\text{ belongs to }e,\\0,&\text{otherwise.}\end{cases}$$

The row sum $\sum_eH_{ie}$ is the number of hyperedges containing a node; the column sum $\sum_iH_{ie}$ is the size of a hyperedge. Off-diagonal entries of $HH^{\mathsf T}$ count how many hyperedges a pair of nodes shares. Removing the diagonal and binarizing gives an ordinary graph projection, but loses group structure.

For example, "one event attended by three people" and "three events each attended by a pair" can both project to a triangle, although the hypergraphs differ. The bipartite incidence representation preserves this distinction. Other examples are directors and company boards, keywords and pages on which they occur, stations and train routes, metabolites and reaction participant sets, and users and the items they like.

Density and Mean Degree

Density is the fraction of all allowed edges that are present. A simple undirected graph allows at most $\binom n2$ edges, so

$$\boxed{\rho=\frac{M}{\binom n2}=\frac{2M}{n(n-1)} =\frac{\langle k\rangle}{n-1}\simeq\frac{\langle k\rangle}{n}}.$$

The final approximation requires large $n$. A directed graph without self-loops allows $n(n-1)$ ordered edges, giving

$$\rho_{\rm dir}=\frac{M}{n(n-1)}.$$

If a bipartite graph has part sizes $n_U,n_V$, only cross-part edges are allowed. Defining density relative to these allowed pairs gives $\rho_{\rm bip}=M/(n_Un_V)$. Always specify which edges are permitted: the undirected formula cannot be transferred unchanged to directed graphs, multigraphs, or graphs with self-loops.

Sparsity as a Scaling Property

If $M=O(n)$, the mean degree remains $O(1)$ and the density satisfies $\rho=O(1/n)\to0$. A large graph can therefore contain many edges and still be sparse. For example, $n=10^6,\langle k\rangle=10$ gives $M=5\times10^6$ but only $\rho\simeq10^{-5}$. BA has $M\simeq mn$, so $\rho\simeq2m/n$: a network can have both hubs and very low density.

The Cost of Adjacency Matrices and Lists

A conventional dense adjacency matrix takes $O(n^2)$ storage, whereas an adjacency list takes $O(n+M)$. The latter reduces to $O(n)$ only when $M=O(n)$. A matrix can answer an edge-existence query in $O(1)$, but enumerating all neighbors of a node generally requires scanning its row in $O(n)$. An adjacency list enumerates a node's neighbors in $O(k_i)$. Breadth-first and depth-first traversals using adjacency lists usually take $O(n+M)$. Sparse matrix formats can also save storage: using a matrix representation does not require allocating a dense array.

Final Self-Check

Core graph-analysis tasks are to convert a graph into an adjacency matrix and adjacency lists and cross-check its degrees and edge count; distinguish paths, cycles, induced subgraphs, and components; calculate edge counts for complete graphs, regular graphs, and trees; construct bipartite projections; obtain in- and out-degrees from row and column sums; identify SCCs, WCCs, in-components, and out-components by following arrows; explain $A^2$ and extract neighbors at exactly distance two; use the correct density formula for each graph type; and state when adjacency lists provide linear storage.

---

← Scale-free networks · Series index · Network metrics and algorithms →