Decomposition of a Sparse Directed Graph

• Activity Number: 465
• Type: Contributed
• Date/Time: Wednesday, August 1, 2012 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Sungmin Kim*+ and Tao Shi
• Companies: The Ohio State University and The Ohio State University
• Keywords: Network ; Directed graph ; Clustering ; Sparse SVD ; Bipartite graph

Abstract

This talk introduces a method of decomposing a directed graph and its use in clustering of a directed graph in hierarchical way. A directed graph can be expressed as a bipartite graph, and a node in a bipartite graph plays the role of source or terminal of edges in the graph. By extending this idea, we introduce a concept of directional component that allows us to decompose a directed graph into a set of bipartite graphs. Given a decomposition of a directed graph, one problem is how to investigate the relationship between the directional components. We tackle this problem by building another directed graph on top of the directional components and applying the directional component decomposition algorithm on the graph again. The second problem is how to break further apart a giant directional component. We use sparse SVD decomposition on a modified Laplacian of a directional component to separate out strongly connected sub-components. Simulation studies show that our method succeeds in revealing hierarchical configuration of a directed network. As an application, we demonstrate the practical use of our method in the problem of finding groups in a social network.