Most recent message posted: 5/02/2013
Thanks in large part to the Internet and World Wide Web, we are now seeing an explosion in networked resources, and in particular of networked information. The network structure and information content interact in many ways, creating challenging and exciting problems. A sample of the questions we will examine in the course: How does link structure between documents help us evaluate content, relevance, relatedness, or importance? What are natural models for the growth of networks? What graph-theoretic properties do these networks have? What properties of networks allow for easy routing or searching? How should we design networks to allow searching for information? How should we disseminate information through a network if we can design the network? How should we do it if we can't? Using tools from graph theory, linear algebra and probabilistic analysis, we will examine these questions focusing on the theoretical aspects.
The readings for the course will be mostly recent (and a few not so recent) research papers from the areas covered. A preliminary reading list is available, and will be updated as needed.
A good overview of the course material is given in Lecture notes for this course, but keep in mind that the original papers often contain significant additional material that will be of interest to students in the class. Thus, the lecture notes are meant as a guide, but not as a substitute for reading the original papers.
The grade will be based mostly on a substantial final project. In addition a few shorter reaction papers are assigned during the semester. There will not be a midterm or final exam.
The final project should be done in groups of usually 2-4 students. Individual projects or larger groups will only be approved in exceptional cases. Your project should draw on ideas from the class, and will often (but not necessarily) be based on ideas that one or more of you included in your discussion papers. It must have at least a small theory component, although it is acceptable if the bulk of the project is experimental, e.g., building a tool or exploring a particular data set. About 1 week into the project, your group should present a short (3-5 page) proposal to me, mostly so that I can provide feedback on the viability of your proposed work. At the end of the semester, the final project report is due, which should be about 10-15 pages long, and report on your results (and possibly also unsucessful ideas) in detail.