Analyze sampling methods to large-scale community detection based on measurements of the quality for the community structure of sampled and original graph

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Title: "Analyze sampling methods to large-scale community detection based 
on measurements of the quality for the community structure of sampled and 
original graph"

by

Mr. Dai Jie

Abstract:
As the social network size has expanded greatly, the size of network may
have millions of nodes. Present clustering
algorithms focus more on a relatively smaller size, and not applicable on
large community detection; hence, we would like
to sample the graph and then infer community structure from the sample
graph.

This project mainly discusses the sampling qualities of the present
sampling algorithms: Random Node Sampling, Forest
Fire Sampling and Snowball Expansion Sampler. After evaluating these three
algorithms, we found that Random Node Sampling
had the best behavior, Forest Fire Sampling ranked the second and Snowball
Expansion Sampler behaved the worst.

Date            :       11 May 2012 (Friday)

Time            :       3pm to 3:40pm

Venue           :       5487 (lift 25-26)

Advisor         :       Prof. D.Y. Yeung

2nd reader      :       Prof. Nevin Zhang