Efficient Community Detection for Large Scale Networks via Sub-sampling
| dc.contributor.author | Bellam, Venkata Pavan Kumar | en |
| dc.contributor.committeechair | Sengupta, Srijan | en |
| dc.contributor.committeechair | Huang, Jia-Bin | en |
| dc.contributor.committeemember | Abbott, A. Lynn | en |
| dc.contributor.department | Electrical and Computer Engineering | en |
| dc.date.accessioned | 2018-01-19T09:00:53Z | en |
| dc.date.available | 2018-01-19T09:00:53Z | en |
| dc.date.issued | 2018-01-18 | en |
| dc.description.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. | en |
| dc.description.degree | Master of Science | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:14071 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/81862 | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | Spectral clustering | en |
| dc.subject | Extreme points | en |
| dc.subject | Sub-sampling | en |
| dc.subject | PABM | en |
| dc.title | Efficient Community Detection for Large Scale Networks via Sub-sampling | en |
| dc.type | Thesis | en |
| thesis.degree.discipline | Computer Engineering | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | masters | en |
| thesis.degree.name | Master of Science | en |
Files
Original bundle
1 - 1 of 1