Efficient Community Detection for Large Scale Networks via Sub-sampling

TR Number

Date

2018-01-18

Journal Title

Journal ISSN

Volume Title

Publisher

Virginia Tech

Abstract

Many real-world systems can be represented as network-graphs. Some of the networks have an inherent community structure based on interactions. The problem of identifying this grouping structure given a graph is termed as community detection problem which has certain existing algorithms. This thesis contributes by providing specific improvements to various community detection algorithms such as spectral clustering and extreme point algorithm. One of the main contributions is proposing a new sub-sampling method to make existing spectral clustering method scalable by reducing the computational complexity. Also, we have implemented extreme points algorithm for a general multiple communities detection case along with a sub-sampling based version to reduce the computational complexity. We have also developed spectral clustering algorithm for popularity-adjusted block model (PABM) model based graphs to make the algorithm exact thus improving its accuracy.

Description

Keywords

Spectral clustering, Extreme points, Sub-sampling, PABM

Citation

Collections