Abstract
Graphs appear in a wide range of settings, like computer networks, the world wide web, biological networks, social networks (MSN/FaceBook/LinkedIn) and many more. How to find master-mind criminal given some suspects X, Y and Z? How to find user-specific pattern (like, e.g. a money-laundering ring)? How to track the most influential authors over time? How to automatically associate digital images with proper keywords? How to answer all these questions quickly on large (disk resident) graphs? It turns out that the main tool behind these applications (and many more) is the proximity measurement: given two nodes A and B in a network, how close is the target node B related to the source A?
In this talk, I will cover three aspects of the proximity on graphs: (1) Proximity definitions. I will start with random walk with restart, the main idea behind Google's PageRank algorithm, and talk about its variants and generalizations. (2) Computational issue. Many proximities measurements involve a specific linear system. I will give algorithms on how to efficiently solve such linear system(s) in several different settings. (3) Applications. I will show some applications of the proximity, including link prediction, neighborhood formulation, image caption, center-piece subgraph, pattern match etc.
Bio
Venue, Date, and Time
Venue: NSH 1507
Date: Monday, October 29
Time: 12:00 noon