Computer Science
Tel-Aviv University

0368.331501
Undergraduate seminar on mathematical tools for analyzing large networks

Instructor: Ronitt Rubinfeld
Fall 2014
Shenkar 105, Sundays 13:00-15:00.

Course Description

This seminar course will study the ``connectedness'' of modern society in terms of the phenomena of networks, incentives, aggregate behaviors of groups. We will consider the essential ideas from graph theory, game theory, and behavioral sciences in a unified manner. We will cover selected topics from the text ``Networks, Crowds and Markets'' by Easley and Kleinberg, with students presenting sections of the text for their seminars.

Grading

will be based on the student presentation and class participation. If you choose to do a significant part of your presentation on the blackboard, I would like you to type up notes with a level of detail that is similar to that in a slide presentation (in text or latex format).

Prerequisites

Some knowledge of algorithms and the basics of probability.

Time and location

The course will take place on Sundays, 13:00-15:00, in Shenkar 105.

Announcements (none yet)

Lectures

  1. Introduction (Chapters 1,2) slides
  2. November 9. Barak Gross on Game Theory. Roy Mitz on Graph theory: strong and weak ties.
  3. November 30. Eyal Feder on the structure of the web. Tamir Shasha on Pagerank.
  4. December 7. Assaf Alon on Cascading Networks. Chapter 16.
  5. December 14. OPEN.
  6. December 21. Chanukah.
  7. December 28. Noa Shafir on Sponsored Search Markets. Chapter 15. Amir Shavitt on Power laws and rich-get-richer phenomena. Chapter 18.
  8. January 4. Almog Gal. Epidemics. Chapter 21.
  9. January 11. Sapir Caduri. Small World Phenomenon. Chapter 20.
  10. January 18. Gilad. Lemons and horses.

Tentative superset of topics

  1. Introduction (Chapters 1,2,3)
  2. Networks in context (Chapters 4,5)
  3. Games (Chapter 6)
  4. Power in social networks (Chapter 12)
  5. The structure of the web (Chapter 13)
  6. Link analysis and web search (Chapter 14)
  7. Sponsored search markets (Chapter 15) (needs background from chapters 9,10)
  8. Information Cascades (Chapter 16)
  9. Network effects (Chapter 17)
  10. Power laws and rich-get-richer phenomena (Chapter 18)
  11. Cascading behavior in networks (Chapter 19)
  12. Small-world phenomenon (Chapter 20)
  13. Epidemics (Chapter 21)
  14. Markets and information (Chapter 22)
  15. Voting (Chapter 23)
  16. Property Rights (Chapter 24)

Useful Advice on Giving Talks

(Much more can be found on the web using google)
  1. How to give a talk Prof. Bruce Randall Donald
  2. How to give a bad talk Prof. David A. Patterson
  3. Oral Presentation Advice Prof. Mark Hill
  4. The Short Talk Prof. Charles Van Loan
  5. Giving an academic talk Prof. Jonathan Shewchuk