Seminar Information

Seminar Description: In this seminar, we study a number of approaches for determining the relative importance of nodes in networks. The problem of relative relevance or importance in network and graphical data appears in a very broad spectrum of applications, such as: (1) Given a directed graph of web pages linking to other web pages, which web page is the most "relevant" given a certain keyword query? (2) Given a social network with undirected friendships between users: Which user in the network is the most "similar" to a chosen user? (3) Given an interaction network of users on eBay with a subset of nodes identified as fraudsters (labeled training data), which are the most likely other users that are fraudsters too based on common interaction patterns? (4) Given an electrical network and assuming independent failure of edges: which node from a chosen subset is the one that is most likely reachable (i.e. connected) to the source set ("source-terminal reliability")?

Our goal is to understand the connections between seemingly unconnected scenarios and algorithms by studying the workings, assumptions, and limitations of a few selected approached in depth, then trying to find common properties and differences. In doing so, our analysis and discussions will be guided by questions, such as:
Recommended Background Knowledge: The seminar is targeted towards PhD students with a good understanding of the following topics (or willingness to get up to speed during the seminar). We will, at time, read sections of these books:
  1. Linear Algebra
  2. Probability Theory
  3. Fundamentals of network theory
  4. Graphical models
  5. Complexity theory

Instructor: Wolfgang Gatterbauer
Assistant Professor of Business Technologies, Tepper School of Business, CMU.
Courtesy Assistant Professor, School of Computer Science, CMU.
Email: First 4 letters of family name at
Office: Tepper 354
Office Hours: via email

Seminar Requirements

1. Presentations and in-class contributions (50%): We will study the workings and predictions of several different approaches. Everybody will read the papers upfront, and analyze the methods on suggested example graphs in the manner they find most appropriate (e.g., simulation in Matlab, or handwritten drawings). Students are given 20-30min at the beginning of each class to discuss their findings with another student that is randomly assigned by the instructor. Each team is expected to be able present their findings to the class (ideally on the overhead projector with handwritten slides). One pair of students are announced in the previous class and is in lead of the topic for each class. The lead team is expected to understand the paper more thoroughly then everybody else. Material from each students is handed in each class. Important: you do not need to hand in digitally prepared slides, often drawing by pen on paper together with your assigned partner is far more effective. Goal is to understand the paper, and to help others understand your insights, not to produce fancy slides. Thus come with your pen and lots of paper. We may also possibly use Baiboard for collaborative drawing in class by students and instructors (to be determined). Here are some guiding questions:
2. Written research proposal or small research project with presentation. (50%): Minimum 1000 words and 3 drawings, maximum 5000 words (no limit on drawings). Students will hand in and present their research proposals on the last day of class. The discussion will be very interactive, i.e. questions will be posed during presentation, not only after.

Class schedule

Below is a tentative calendar. I may modify this list as we go along. Please see the date at the bottom of this page to learn if this post has been updated.

1. Oct 24: Random walks and variations
2. Oct 31: From Random walks to Label Propagation
3. Nov 7: Belief Propagation and variations
4. Nov 14: Network reliability and electrical networks / Structural Similarity
5. Nov 21: Modeling the brain
6. Dec 5: From Graphs to Hypergraphs and Databases
7. Dec 12: Student presentations and comparative review