Seminar on Information Networks

Computer Science 7850
Cornell University
Fall 2020

  • Time: MW 1:50-2:40pm

  • Zoom link: (Cornell NetID sign-in required)

  • Office hours Mondays 9-10am via (Cornell NetID sign-in required)

  • Course home page:

  • Course material (slides and videos) can be found on CMS.

    Course Staff


    This is a seminar focusing on models for networks and for some of the fundamental processes that take place within them. Topics will include the small-world phenomenon, decentralized search, contagion, cascading behavior, graph partitioning, and spectral analysis.

    The seminar is structured as a 2-credit S/U-only class at the 7000-level, and in keeping with this format the classwork will consist of lecture participation and supplementary reading of papers, but no graded material.

    Course Outline

    (1) Cascading Behavior in Networks

    We can think of a network as a large circulatory system, through which information continuously flows. This diffusion of information can happen rapidly or slowly; it can be disastrous -- as in an epidemic disease or cascading failure -- or beneficial -- as in the spread of an innovation. Work in several areas has proposed models for such processes, and investigated when a network is more or less susceptible to their spread. This type of diffusion or cascade process can also be used as a design principle for network protocols. This leads to the idea of epidemic algorithms, also called gossip-based algorithms, in which information is propagated through a collection of distributed computing hosts, typically using some form of randomization.

    (2) Small-World Phenomena in Networks

    A major goal of the course is to illustrate how networks across a variety of domains exhibit common structure at a qualitative level. One area in which this arises is in the study of `small-world properties' in networks: many large networks have short paths between most pairs of nodes, even though they are highly clustered at a local level, and they are searchable in the sense that one can navigate to specified target nodes without global knowledge. These properties turn out to provide insight into the structure of large-scale social networks, and, in a different direction, to have applications to the design of decentralized peer-to-peer systems.

    (3) Spectral Analysis of Networks

    One can gain a lot of insight into the structure of a network by analzing the eigenvalues and eigenvectors of its adjacency matrix. The connection between spectral parameters and the more combinatorial properties of networks and datasets is a subtle issue, and while many results have been established about this connection, it is still not fully understood. This connection has also led to a number of applications, including the development of link analysis algorithms for Web search.