Web Science/Part2: Emerging Web Properties/Modeling the Web as a graph/Modelling-graphs-with-linear-algebra

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 be the adjacency matrix of a graph what information is stored in the components of ?

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 be the adjacency matrix of a graph and be the components of . Which of the following is true?

if then node i and j are in different connected components.
if then there is no path of length k connecting node i and node j.
if 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.


Further reading

  1. tba

Discussion