Browsing by Author "Bellam, Venkata Pavan Kumar"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Efficient Community Detection for Large Scale Networks via Sub-sampling
    Bellam, Venkata Pavan Kumar (Virginia Tech, 2018-01-18)
    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.