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

34

Web Science/Part2: Emerging Web Properties

Web Science/Part2: Emerging Web Properties/MoocIndex

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

• edit MOOC index

Modelling-graphs-with-linear-algebra

Learning goals

Video

Script

Quiz

Further reading

Discussion

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.

Further reading

1. tba

Discussion

Navigation

1. How big is the World Wide Web
   1. Problems with the question about the size of the Web
   2. 3 ways to study the Web
   3. A simplistic descriptive model
   4. An unrealistic, simplistic generative model
   5. Summary, further reading, homework
2. Simple statistical descriptive Models for the Web
   1. Counting Words And Documents
   2. Typical length of a document
   3. How to formulate a research hypothesis
   4. Number of words needed to understand most of Wikipedia
   5. Linguists way of checking simplicity of text
3. Advanced statistical descriptive models for the Web
   1. The Zipf law for text
   2. Visually straight lines on log log plots
   3. Fitting a curve on a log log plot
   4. Zipf law powerlaw or pareto law.webm
4. Modelling Similarity of Text
   1. Similarity Measures and their Applications
   2. Jaccard Similarity for Sets
   3. Cosine Similarity For Vectorspaces
   4. Probabilistic Similarity Measures Kullback Leibler Divergence
   5. Comparing Results of Similarity Merasures
5. Generative Models for the Web
   1. Introduction to generative modelling.webm
   2. Sampling from a probability distribution
   3. Evaluating a generative model
   4. Pittfalls when increasing the number of model parameters
6. Modeling the Web as a graph
   1. Reviewing terms from graph theory
   2. The standard web graph model
   3. Descriptive statistics of the web graph
   4. Topology of the web graph
   5. Modelling-graphs-with-linear-algebra

Topology of the web graph