Web graphs and retrieval

Lecture 1.

Various empirical data about the structure of the link web-graph and similar graphs: the "small world" property, power law distribution, the preferential attachment, etc. Review of existing models of random graphs and web-graphs.

Lecture 2.

Comparison of different random web-graph models.

Lecture 3.

Degree distribution and the diameter of the random web-graph models in Barabasi-Albert model (Bollobas-Riordan theorem).

Lecture 4.

Random walks on graphs and corresponding models.

Lecture 5.

Different types of PageRank.

Lecture 6.

Empirical processes and percolation.

Lecture 7.

Graph clustering.

Bibliography

  1. R. Durrett, «Random graph dynamics», Cambridge, 2007.
  1. L.-A. Barabasi, R. Albert, H. Jeong, «Scale-free characteristics of random networks: the topology of the world-wide web», Physica, A281 (2000), 69-77.
  1. R. Albert, H. Jeong, L.-A. Barabasi, «Diameter of the world-wide web», Nature, 401 (1999), 130-131.
  1. A. Broder et al., «Graph structure in the Web», Computer Networks, 33 (2000), 309-320.
  1. J. Leskovec, J. Kleinberg, Ch. Faloutsos, «Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations», Proc. of KDD'05, August 21-24, 2005, Chicago, Illinois, USA.
  1. R. Kumar et al., «Stochastic models for the web graph», 41st Annual Symposium on Foundations of Computer Science, 2000.
  1. B. Bollobas, O. Riordan, J. Spencer, G. Tusnady, «The degree sequence of a scale-free random graph process», Random Structures Algorithms, 18 (2001), N3, 279-290.
  1. B. Bollobas, O. Riordan, «Mathematical results on scale-free random graphs», Handbook of graphs and networks, 1 - 34, Wiley-VCH, Weinheim, 2003.
  1. B. Bollobas, O. Riordan, «Robustness and vulnerability of scale-free random graphs», Internet Math., 1 (2003), N1, 1-35.
  1. B. Bollobas, O. Riordan, «The diameter of a scale-free random graph», Combinatorica, 24 (2004), N1, 5-34.
  1. R. Karp, C. Schindelhauer, S. Shenker, B. Vocking. Randomized Rumor Spreading. 41st IEEE Symposium on Foundations of Computer Science, 2000.
  1. L. Lovasz. Random Walks on Graphs: A Survey. Combinatorics: Paul Erdos is Eighty (vol. 2), 1996, pp. 353-398.
  1. S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web. 27th International Conference on Very Large Data Bases, 2001.
  1. Gary Flake, K. Tsioutsiouliklis, R.E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Internet Mathematics, 2002.