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

From Wikiversity
Jump to: navigation, search

Modelling-graphs-with-linear-algebra

Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Learning-goals.svg

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
Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Video.svg

Video

Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Script.svg

Script

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

Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Quiz.svg

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.

Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Further-readings.svg

Further reading

  1. tba
Wikiversity-Mooc-Icon-Discussion.svg

Discussion