Stat260/CS294: Spectral Graph Methods Lecture 5- 02/05/2015 Lecture: Overview of Graph Partitioning

Warning: these notes are still very rough. They provide more details on what we discussed in class, but there may still be some errors, incomplete/imprecise statements, etc. in them. 5 Overview of graph partitioning The problem of graph partitioning or graph clustering refers to a general class of problems that deals with the following task: given a graph G = (V,E), group the vertices of a graph into groups or clusters or communities. (One might be interested in cases where this graph is weighted, directed, etc., but for now let’s consider non-directed, possibly weighted, graphs. Dealing with weighted graphs is straightforward, but extensions to directed graphs are more problematic.) The graphs might be given or constructed, and there may or may not be extra information on the nodes/edges that are available, but insofar as the black box algorithm that actually does the graph partitioning is concerned, all there is is the information in the graph, i.e., the nodes and edges or weighted edges. Thus, the graph partitioning algorithm takes into account the node and edge properties, and thus it typically relies on some sort of “edge counting ” metric to optimize. Typically, the goal is to group nodes in such a manner that nodes within a cluster are more similar to each other than to nodes in different clusters, e.g., more and/or better edges within clusters and relatively few edge