9.4 Graph Theory - Introduction

1Reading¶

Material related to this page can be found in

2Learning Objectives¶

By the end of this page, you should know:

what is a consensus problem and its key components
how a consensus problem is used to model the evolution of multiple agents in real life applications
the formal definition of a graph and an example highlighting the key components
connectedness of graphs
the definition of different matrices used in graph theory

3Introduction to Graph Theory and Consensus¶

Many applications in engineering involve coordinating groups of agents to behave in a desirable way. Examples abound in a wide range of areas:

Transportation: air traffic control and intelligent transportation systems
Military: distributed aperture imaging and battlespace management
Scientific: animal coordination and group opinion dynamics (e.g. on social networks)
Sensor networks: adaptive ocean sampling, building sensor networks in green buildings
General networks: communication, power, and supply chain networks

Many, but not all, of these problems can be posed as consensus problems. In this case, we assume there are $n$ agents, with each agent state $x_i(t) \in \mathbb{R}$ evolving according to the following differential equation:

\dot{x}_i = f_i(x_i) + \sum_{j \in N_i} u_i(x_i, x_j), \quad i = 1,\ldots,n

(1)

In (1):

the function $f_i: \mathbb{R} \to \mathbb{R}$ defines the dynamics of agent $i$ , i.e., how the internal state of agent $i$ evolves in the absence of other agents.
the neighbor set $N_i$ of agent $i$ are those agents that are directly connected to agent $i$ , as specified by a connection graph $G$ with nodes $i = 1,\ldots,n$ corresponding to agents, and edges defining inter-agent communication.
the coordination rule $u_i: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ , which we are to design so that the collective state of the agents $\vv x(t) := (x_1(t),\ldots,x_n(t))$ converges to a desired goal state $\vv x^*$ .

In many settings of interest, each agent is a computer that is trying to compute or estimate a shared value. This is a common model adopted in distributed optimization and learning (want to compute a shared prediction), sensor networks (compute a shared estimate), and opinion dynamics (compute shared opinion). In these settings, it makes sense to set the local dynamics function $f_i(x) = 0$ , so that an agent’s state is determined solely by interactions with its neighbors. Agent $i$ ’s dynamics then become

\dot{x}_i = \sum_{j \in N_i} u_i(x_i, x_j), \quad i = 1,\ldots,n

(2)

A common goal for such systems is for all agents to converge to the same value, i.e., that eventually $x_1 = x_2 = \cdots = x_n = m$ , for some value $m$ . If this happens, system (2) is said to achieve consensus with consensus value $m$ .

Studying the behavior of system (2) will require us to bring together all of the ideas that we’ve seen over the past few lectures on eigenvalues, dynamical systems, and spectral decomposition of symmetric matrices. We start with a summary of relevant facts from graph theory, which will help us model the flow of information in (2).

4A Primer on Graph Theory¶

We have used graphs before, but we pause now to describe formal linear algebraic representations thereof.

Some important notation and terminology for graphs include:

The order of a graph is the number of nodes $|\mathcal{V}|$
Nodes $v_i$ and $v_j$ are adjacent if there exists $e = (v_i, v_j) \in \mathcal{E}$ (i.e., if node $i$ is directly connected to node $j$ via an edge $e$ )
An adjacent node $v_j$ for a node $v_i$ is called a neighbor of $v_i$
The set of all neighbors of $v_i$ is denoted by $N_i$
A graph $G$ is called complete if all nodes are adjacent

We will focus our study on the class of undirected graphs, that is graphs satisfying the property that if $e_{ij} \in \mathcal{E}$ then $e_{ji} \in \mathcal{E}$ . In words, this means that all edges are bidirectional: if $v_j$ is a neighbor of $v_i$ , then $v_i$ is a neighbor of $v_j$ . Although we won’t focus on them, a graph that is not undirected is called directed.

5Connectedness of Graphs¶

We start by defining a path in $G$ , which is a subgraph $\pi = (\mathcal{V}_\pi, \mathcal{E}_\pi)$ , with distinct nodes $\mathcal{V}_\pi = \{v_1, v_2, ..., v_m\}$ and $\mathcal{E}_\pi = \{(v_1,v_2),(v_2,v_3),...,(v_{m-1},v_m)\}$ . The length of a path π is defined as $|\mathcal{E}_\pi| = m-1$ . For example, in the graph above, the path π defined by $\mathcal{V}_\pi = \{v_5, v_1, v_6, v_2\}$ and $\mathcal{E}_\pi = \{(v_5,v_1),(v_1,v_6),(v_6,v_2)\}$ is the path that goes from node 5 to node 1 to node 6 to node 2. It has length 3, the number of edges traversed. An undirected graph $G$ is called connected if there exists a path π between any two distinct nodes of $G$ .

6Matrices Associated with a Graph¶

In our study of network flow problems, we encountered the incidence matrix associated with a graph. This is but one matrix we can associate with a graph $G$ , and while the incidence matrix is convenient for encoding flow conservation, we will see that the Graph Laplacian Matrix is more natural for defining consensus algorithms.

Example 3 (Adjacency and Laplacian matrices)

The adjacency matrix and Laplacian for the directed graph above are:

A = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \end{bmatrix} \quad L = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & -1 \\ -1 & 3 & -1 & 0 & 0 & -1 \\ 0 & 0 & 2 & -1 & 0 & -1 \\ 0 & 0 & -1 & 2 & -1 & 0 \\ -1 & 0 & 0 & 0 & 1 & 0 \\ -1 & -1 & 0 & -1 & 0 & 3 \end{bmatrix}

(5)

The adjacency and Laplacian for the udirected graph

are

\begin{align*} & \quad \quad \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \\ A &= \begin{bmatrix} 0 & 1& 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \quad \text{and} \quad L &= \begin{bmatrix} 2 & -1 & -1 & 0 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ 0 & 0 & 1 & 1 \end{bmatrix} \end{align*}

(6)

7Python Break: Programming with Graphs!¶

In this section, we’ll detail how we can build our own framework for working with graphs in Python. Recall that graphs are determined by a set of vertices $\{v_1, v_2, \dots, v_n \}$ and a set of edges $\{e_1, e_2, \dots, e_m\}$ , so to represent a graph in Python we need to find ways of representing these objects:

Traditionally, the vertices are not explictly stored. Instead, the number of vertices $n$ in the graph is stored, and the vertices are assumed to be the integers $0, 1, \dots, n - 1$ .
There are two common ways of representing the edges:
- Adjacency matrix representation. Here, we store the adjacency matrix (defined above) as a 2D array adj[n][n], such that adj[i][j] = 1 if there is an edge from i to j in the graph and adj[i][j] = 0 otherwise.
- Adjacency list representation. Here, we store adjacency information as an array of sets neighbors[n] such that j in neighbors[i] if and only if there is an edge from i to j in the graph. This is common when the graph is sparse, i.e., when there aren’t a lot of edges, because storing the entire adjacency matrix can take a lot of space if $n$ is large.

Below is a Python snippet implementing an adjacency list representation of an undirected graph:

class Graph:
    def __init__(self, n):
        self.n_vertices = n
        self.neighbors = [set() for _ in range(n)]

    def add_edge(self, i, j):
        self.neighbors[i].add(j)
        self.neighbors[j].add(i)

    def n_edges(self):
        return int(sum([len(s) for s in self.neighbors]) / 2)

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(3, 4)

print('Number of edges in g:', g.n_edges())

Number of edges in g: 4
Number of edges in g: 4

Here, we just have some code to add edges to a graph and count the number of edges in it. Can you try to draw the graph that this represents?

There are many interesting problems that we can solve on graphs; to name a few:

finding the shortest path between vertices $i$ and $j$ (known to be efficiently solvable);
deciding whether there is a path between every vertex in a graph (known to be efficiently solvable);
deciding whether a graph has a given subgraph (known to be NP-complete);
deciding whether two graphs are isomorphic, i.e., if we can “renumber” their vertices to get the same graph (unknown computational complexity).

This isn’t even the tip of the iceberg, and if you take a computer science class like CIS 1210, CIS 2620, or CIS 3200, then you’ll study graph problems and their practical applications in much more detail. In the next page, in light of our study of the consensus problem, we’ll describe how to solve the second problem: deciding whether there is a path between every vertex if a graph (deciding if the graph is “connected”).