|
|
Title: Four graph partitioning algorithms |
Name: Fan Chung Graham University of California, San Diego |
|
| Time:October 14th (Tuesday) 14:45-15:30 | |
| Location: Lecture Hall, FIT Building, Tsinghua University | |
| Host Unit: ITCS, Tsinghua University |
|
|
Title: Four graph partitioning algorithms |
Name: Fan Chung Graham University of California, San Diego |
|
| Time:October 14th (Tuesday) 14:45-15:30 | |
| Location: Lecture Hall, FIT Building, Tsinghua University | |
| Host Unit: ITCS, Tsinghua University |
We will discuss four partitioning algorithms using eigenvectors, random walks, PageRank and their variations. In particular, we will examine local partitioning algorithms, which find a cut near a specified starting vertex, with a running time that depends on the size of the small side of the cut, rather than on the size of the input graph (which can be prohibitively large). Three of the four partitioning algorithms are local algorithms and are particularly appropriate for applications such as finding hot spots and identifying hidden patterns in social and biological networks.
Fan Chung Graham (professional name: Fan Chung , Chinese name 金芳� is the Akamai Professor in Internet Mathematics at UC San Diego. Previously, she had taught at U Penn, worked at Bell Labs in its glory days, and directed some great research groups at Bellcore.
Her research interests are primarily in graph theory, combinatorITCS and algorithmic design. In particular, she is known for her work in the following areas:
Recently, she has been working on a new topic --- the mathematical analysis of PageRank, which is a new and important graph invariant concerning correlations between vertices in a graph. The analysis of PageRank and its variations uses both probabilistic and spectral methods with special emphasis on graph partitioning. Further variations using the (discrete) heat kernel are examined as well as their implications on local partitioning algorithms.
