JSM 2012 Home

JSM 2012 Online Program

The views expressed here are those of the individual authors and not necessarily those of the JSM sponsors, their officers, or their staff.

Online Program Home

Abstract Details

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
Abstract - #305969
Title: Decomposition of a Sparse Directed Graph
Author(s): Sungmin Kim*+ and Tao Shi
Companies: The Ohio State University and The Ohio State University
Address: 653 Tuscarawas Ct., Columbus, OH, 43210, United States
Keywords: Network ; Directed graph ; Clustering ; Sparse SVD ; Bipartite graph

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.

The address information is for the authors that have a + after their name.
Authors who are presenting talks have a * after their name.

Back to the full JSM 2012 program

2012 JSM Online Program Home

For information, contact jsm@amstat.org or phone (888) 231-3473.

If you have questions about the Continuing Education program, please contact the Education Department.