The Structure of Information Networks

Computer Science 685
Spring 2005

  • Instructor: David P. Williamson

  • Meeting time: MWF 1:25-2:15 pm.

  • Room: Hollister 368.


    This class will look at information networks, with a particular emphasis on the Web, but also studying graphs such as social networks, the email graph, citation graphs, and others. We will look at empirical studies of the properties of these graphs, algorithms for mining information from these graphs, mathematical models of information networks, issues in the search of these networks, and constructing networks to enable decentralized search. An overview of the course topics, including course prerequisites and assignments, can be found in the following handout. The content of the course will be drawn from a number of recent papers in the area. This list will be updated as the term progresses.


    Reaction paper 1. Reaction paper 2. Reaction paper 3.


    (1) Overview and Background.

    What ideas led to the creation of the Web? What can we say about its basic structure?

    (2) Uses of link information.

    What kinds of information can we infer from the existence of links in information networks?

    (3) Finding communities.

    How can we automatically find "communities" of common interests in information networks?

    (4) Rank aggregation and meta-search.

    Given multiple rankings of web pages, can we combine these in a principled way into a single ranking?

    (5) Power law distributions.

    Many properties of information networks obey power law distributions. Where has this been observed? What accounts for it? How can it be modelled?

    (6) Change and decay on the web.

    How is the web changing over time? How can we detect changes? How can we use link structure to decide if a page is no longer being maintained?

    (7) Small-world networks.

    Many social networks appear to have a "small world" property. What is the property? Where has it been observed? What accounts for it? How can it be modelled?

    Interlude: Blogs

    Ravi Kumar gave a presentation on 4/20 about his work on weblogs. Below are the references to some of the papers he mentioned.

    (8) Information diffusion

    How does information and behavior propagate in various kinds of information networks?

    Coda: What's next?

    What might be the next generation of information networks? What kinds of interesting issues arise in these networks?