Modelling-graphs-with-linear-algebra Learning goals

1. Be able to read and build an adjacency matrix of a graph
2. Know some basic matrix vector multiplications to generate some statistics out of the adjacency matrix
3. Understand what is encoded in the components of the k-th power of the Adjacency matrix of a graph Video Script

The slide deck can be found at File:Linear Algebra for graphs.pdf Quiz

1

what information is encoded within the i-th row of the adjacency matrix?

 the pages linking to the i-th node the pages that are linked by the i-th node number of common neighbors with the i-th node the indegree distribution of the i-th node

2

Let $A$ be the adjacency matrix of a graph what information is stored in the components $a_{ij}$ of $A^{k}$ ?

 the number of paths that exist to go from node i to node j. the number of paths of length k that go from node i to node j. the number of paths of length up to k that go from node i to node j. the number of common neighbros between node i and node j. non of the above.

3

Let $A$ be the adjacency matrix of a graph and $a_{ij}$ be the components of $A^{k}$ . Which of the following is true?

 if $a_{ij}=0$ then node i and j are in different connected components. if $a_{ij}=0$ then there is no path of length k connecting node i and node j. if $a_{ij}=0$ then there is no path of length shorter than k connecting node i and node j. there could be a path between node i and node j if k is bigger than the amount of vertices node i and node j are in two different connected components.  