SUBJECT

Title

Mathematics of networks and the WWW

Type of instruction

lecture

Level

master

Part of degree program
Credits

3

Recommended in

Semesters 1-4

Typically offered in

Autumn/Spring semester

Course description

Anatomy of search engines. Ranking in search engines.  Markov chains and random walks in graphs. The definition of PageRank and reformulation. Personalized PageRank, Simrank.

Kleinberg’s HITS algorithm. Singular value decomposition and spectral graph clustering. Eigenvalues and expanders.

Models for social networks and the WWW link structure. The Barabási model and proof for the degree distribution. Small world models.

Consistent hashing with applications for Web resource cacheing and Ad Hoc mobile routing.

Readings
  • Searching the Web. A Arasu, J Cho, H Garcia-Molina, A Paepcke, S Raghavan. ACM Transactions on Internet Technology, 2001
  • Randomized Algorithms, R Motwani, P Raghavan, ACM Computing Surveys, 1996
  • The PageRank Citation Ranking: Bringing Order to the Web, L. Page, S. Brin, R. Motwani, T. Winograd. Stanford Digital Libraries Working Paper, 1998.
  • Authoritative sources in a hyperlinked environment, J. Kleinberg. SODA 1998.
  • Clustering in large graphs and matrices, P Drineas, A Frieze, R Kannan, S Vempala, V Vinay
  • Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, 1999.
  • David Karger, Alex Sherman, Andy Berkheimer, Bill Bogstad, Rizwan Dhanidina, Ken Iwamoto, Brian Kim, Luke Matkins, Yoav Yerushalmi:  Web Caching and Consistent Hashing, in Proc. WWW8 conference  Dept. of Appl. Analysis and Computational Math.