Efficient Community Detection for Large Scale Networks via Sub-sampling

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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Engineering

Department dc:contributor.department

Electrical and Computer Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2018

Author dc:creator

• Bellam, Venkata Pavan Kumar

Chairs dc:contributor.committeechair

• Sengupta, Srijan
• Huang, Jia-Bin

Committee member dc:contributor.committeemember

• Abbott, A. Lynn

• Spectral clustering
• Extreme points
• Sub-sampling
• PABM

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

vt_gsexam:14071

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/81862