Web Science/Part2: Emerging Web Properties/Modeling the Web as a graph/Reviewing terms from graph theory

30

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/Reviewing terms from graph theory

• edit MOOC index

Reviewing terms from graph theory

Learning goals

Video

Script

Quiz

Further reading

Discussion

Learning goals

1. Be familiar with a set theoretic way of denoting a graph
2. Know at least 4 different types of graphs
3. Have practiced your abilities in reading and writing mathematical formulas

Video

Script

the script can be downloaded at File:Reviewing terms from graph theory.pdf

Quiz

1 Which of these terms describe the axioms for a bipartite graph $G(V,E)$ with $U_{1},U_{2}$ being the disjoint split of the vertices?

	$\forall e=(u,v)\in E:\exists w\in V:(u,w),(w,u)\in E$
	$\forall e=(u,v)\in E:(v,u)\in E$
	$\forall e=(u,v)\in E:u\in U_{1}\land v\in U_{2}\lor v\in U_{1}\land u\in U_{2}$
	$\forall e=(u,v)\in E:u\in U_{1}\lor v\in U_{2}\land v\in U_{1}\lor u\in U_{2}$
	$\forall e=(u,v)\in E:u\in U_{1}\lor v\in U_{2}\lor v\in U_{1}\lor u\in U_{2}$

2 What kind of mathematical object is used to describe a graph labeling?

	set
	element
	function
	matrix
	vector
	String

3 which of the following are types of graphs that you know?

	heavy graphs
	complex graphs
	directed graphs
	difficult graphs
	bipartite graphs
	robust graphs
	web graphs
	weighted graphs

Further reading

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

The standard web graph model