Abstract Details
Activity Number:
|
439
|
Type:
|
Contributed
|
Date/Time:
|
Tuesday, August 6, 2013 : 2:00 PM to 3:50 PM
|
Sponsor:
|
Section on Statistical Learning and Data Mining
|
Abstract - #309063 |
Title:
|
Scalable Spectral Algorithms for Community Detection in Directed Networks
|
Author(s):
|
Sungmin Kim*+ and Tao Shi
|
Companies:
|
The Ohio State University and The Ohio State University
|
Keywords:
|
Community extraction ;
Graph Laplacian ;
Regularized SVD ;
Scalable algorithm ;
Social networks
|
Abstract:
|
Community detection has been one of the central problems in network studies and directed network is particular challenging due to asymmetry among its links. In this paper, we found that incorporating the direction of links reveals new perspective on communities regarding to two different roles, source and terminal, that a node plays in each community. Intriguingly, such communities appear to be connected with unique spectral property of the graph Laplacian of the adjacency matrix and we exploit this connection by using regularized SVD methods. We propose harvesting algorithms, coupled with regularized SVDs, that are linearly scalable for efficient identification of communities in huge directed networks. The algorithm showed great performance and scalability on benchmark networks in simulations and successfully recovered communities in real networks applications (with ~ 2 million nodes and ~ 50 million edges).
|
Authors who are presenting talks have a * after their name.
Back to the full JSM 2013 program
|
2013 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.
The views expressed here are those of the individual authors and not necessarily those of the JSM sponsors, their officers, or their staff.
Copyright © American Statistical Association.