A Brief Taste of Network Science

Videos (~0 mins)

Reading (~0 mins)

Warmup

Problem 1

Introduction

In this class, “matrix” just means “square array of numbers.”

The adjacency matrix of a graph $G$ with $n$ nodes is an $n\times n$ binary matrix that we often call $\mathbf{A}$. It’s entries are given by

\[ \begin{aligned} a_{ij} = \begin{cases} 1 &\quad \text{there is an edge between node $i$ and node $j$} \\ 0 &\quad \text{there is no edge between node $i$ and node $j$} \end{cases} \end{aligned} \]

$a_{ij}$ is the entry of $\mathbf{A}$ that is in the $i$th row and $j$th column.

For example, here is a graph with $n = 6$ nodes:

Here is the adjacency matrix of this graph:

\[ \begin{aligned} \mathbf{A} = \left[\begin{matrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{matrix}\right] \end{aligned} \]

Note that an edge between $i$ and $j$ corresponds to two entries of $\mathbf{A}$: the $a_{ij}$ entry and the $a_{ji}$ entry.

Part A

A walk of length $k$ is a walk that traverses exactly $k$ edges. For example, a walk of length $1$ traverses only a single edge. $(1, 2)$ is a walk of length 1 in the example graph above. $(1, 2), (2, 3)$ is a walk of length 2, but not a walk of length 1.

How many walks of length 1 from node $4$ to node $5$ are there in the example graph?
How many walks of length 1 are there from node $4$ to node $2$?
What is entry $a_{45}$ in the adjacency matrix? What is entry $a_{42}$?
Make a conjecture: what information does entry $a_{ij}$ contain about the the number of walks of length $1$ from node $i$ to node $j$?

Part B

Let’s define a new number with the following formula:

\[ \begin{aligned} b_{ij} = \sum_{k = 1}^n a_{ik}a_{kj}\;. \end{aligned} \]

If you have used matrix multiplication before, $b_{ij}$ is the $ij$th entry of $\mathbf{A}^2$.

Using the example graph, compute the number of walks of length 2 from node 1 to node 2, node 1 to node 4, node 3 to node 4, and node 1 to node 5.
Using the definition, compute $b_{12}$, $b_{14}$, $b_{34}$, and $b_{15}$.
State a conjecture describing the relationship between $b_{ij}$ and the number of walks of length 2.

Part C

The counting principles of addition and multiplication both appear in the formula for the number of walks of length 2 between nodes $i$ and $j$ as given above. Explain the role of each of these principles in this formula. Why do we multiply $a_{ik}$ by $a_{kj}$? Why do we add across all possibilities $k$? In your response, please include the words “sequential” and “disjoint” or similar.