Accession Number:

AD1034504

Title:

Residuals-Based Subgraph Detection with Cue Vertices

Descriptive Note:

Technical Report

Corporate Author:

MIT Lincoln Laboratory Lexington United States

Report Date:

2015-11-30

Pagination or Media Count:

6.0

Abstract:

A common problem in modern graph analysis is the detection of communities, an example of which is the detection of a single anomalously dense subgraph. Recent results have demonstrated a fundamental limit for this problem when using spectral analysis of modularity. In this paper, we demonstrate the implication of these results on community detection when a cue vertex is provided, indicating one of the vertices in the community of interest. Several recent algorithms for local community detection are applied in this context, and we compare their empirical performance to that of the simple method used to derive the theoretical spectral limits.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE