Large-Scale Community Detection on YouTube for Topic Discovery and Exploration

Ullas Gargi, Wenjun Lu, Vahab Mirrokni, Sang‐Ho Yoon

Abstract

Detecting coherent, well-connected communities in large graphs provides insight into the graph structure and can serve as the basis for content discovery. Clustering is a popular technique for community detection but global algorithms that examine the entire graph do not scale. Local algorithms are highly parallelizable but perform sub-optimally, especially in applications where we need to optimize multiple metrics. We present a multi-stage algorithm based on local-clustering that is highly scalable, combining a pre-processing stage, a local clustering stage, and a post-processing stage. We apply it to the YouTube video graph to generate named clusters of videos with coherent content. We formalize coverage, coherence, and connectivity metrics and evaluate the quality of the algorithm for large YouTube graphs. Our use of local algorithms for global clustering, and its implementation and practical evaluation on such a large scale is a first of its kind.

Introduction

As of 2011, YouTube's video library presented a massive graph-theoretical challenge. With tens of millions of nodes and hundreds of millions of edges, traditional global clustering algorithms—such as spectral clustering or modularity-based methods—were computationally infeasible. While local clustering algorithms offer scalability through parallelization, they often yield "noisy" results where topically unrelated content is merged due to incidental graph connectivity. This paper proposes a three-stage framework to achieve both scalability and topical purity.

Methodology

The proposed system utilizes a three-stage pipeline designed for MapReduce environments:

  1. Pre-processing (Seed Selection): To ensure broad coverage, the system identifies "seeds" using a greedy heuristic based on view counts, ensuring seeds are sufficiently distant in the graph to minimize redundancy.
  2. Local Graph Clustering: Two primary algorithms were evaluated: Dense Partitioning (DP), which seeks the densest subgraphs, and Evolving Set (ES), a Markov chain-based approach focusing on low conductance.
  3. Post-processing: This stage refines clusters using natural language processing. Clusters are split if their video titles and descriptions indicate multiple sub-topics and merged if they exhibit high overlap.

Evaluation and Metrics

The framework was tested on a proprietary YouTube co-watch graph. A critical metric for graph quality is conductance, which measures the ratio of edges leaving a cluster to the total number of edges incident to it. Lower conductance indicates a more "bottlenecked" or distinct community.

Conductance comparison across different algorithm variants.

The Evolving Set (ES) algorithm generally outperformed Dense Partitioning (DP) in terms of initial conductance, providing cleaner boundaries between topics. Furthermore, post-processing significantly improved text coherence, reaching 99.6% for ES-based clusters.

Results and Topic Discovery

By mapping cluster keywords to the Freebase knowledge base, the system automatically assigned human-readable labels to the detected communities. This transformed raw graph data into an explorative topic map.

Examples of detected clusters, including sample video titles and their automatically assigned annotation names.

The system successfully processed tens of millions of videos, demonstrating that treating community detection as a series of independent local problems is a viable path for web-scale graph analysis.

Conclusion

While text-based refinement is powerful, future work aims to incorporate audio-visual similarity to handle videos with sparse metadata. Additionally, these global topic maps could serve as the foundation for personalized recommendation systems.

Summary updated

Abstract

Detecting coherent, well-connected communities in large graphs provides insight into the graph structure and can serve as the basis for content discovery. Clustering is a popular technique for community detection but global algorithms that examine the entire graph do not scale. Local algorithms are highly parallelizable but perform sub-optimally, especially in applications where we need to optimize multiple metrics. We present a multi-stage algorithm based on local-clustering that is highly scalable, combining a pre-processing stage, a lo- cal clustering stage, and a post-processing stage. We apply it to the YouTube video graph to generate named clusters of videos with coherent content. We formalize coverage, co- herence, and connectivity metrics and evaluate the quality of the algorithm for large YouTube graphs. Our use of local algorithms for global clustering, and its implementation and practical evaluation on such a large scale is a first of its kind.
BibTeX
@inproceedings{gargi2021large,
  author = {Ullas Gargi and Wenjun Lu and Vahab Mirrokni and Sang‐Ho Yoon},
  title = {{Large-Scale Community Detection on YouTube for Topic Discovery and Exploration}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/icwsm.v5i1.14191},
}
Figure