Activity Number:
|
131
|
Type:
|
Contributed
|
Date/Time:
|
Monday, August 1, 2016 : 8:30 AM to 10:20 AM
|
Sponsor:
|
Section on Statistical Learning and Data Science
|
Abstract #318873
|
View Presentation
|
Title:
|
Orthogonal Symmetric Non-Negative Matrix Factorization Under Stochastic Block Model
|
Author(s):
|
Subhadeep Paul* and Yuguo Chen
|
Companies:
|
University of Illinois at Urbana-Champaign and University of Illinois at Urbana-Champaign
|
Keywords:
|
Community detection ;
Invariant subspaces ;
Non-negative matrix factorization ;
Stochastic block model
|
Abstract:
|
In this article we propose a method based on the Orthogonal symmetric non-negative matrix tri-factorization (OSNTF) of the laplacian matrix for community detection in complex networks. We establish the connection of the factors obtained through this factorization to a non-negative basis of an invariant subspace of the matrix. Using such factorization for clustering is motivated by analyzing a block-diagonal laplacian matrix with the blocks representing the connected components of a graph. The method is shown to be consistent for community detection in graphs generated from the stochastic block model (SBM) and the degree corrected stochastic block model (DCSBM). Simulation results and real data analysis show the effectiveness of these methods under a wide variety of situations including highly sparse and highly heterogeneous graphs where the usual spectral clustering is known to fail.
|
Authors who are presenting talks have a * after their name.