Residuals-Based Subgraph Detection with Cue Vertices

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Miller,Benjamin A, Smith,Steven T, Kelley,Stephen J, Caceres,Rajmonda S
Format: Report
Language:English
Subjects:
algorithms
boundary value problems
clique vertices
COMMUNITIES
eigenvectors
false alarms
graph analysis
graph-based data
graphs
matrix theory
normal distribution
phase transformations
probability
quadratic programming
random walk
RESIDUALS
spectral analysis
square roots
subgraph detection
Theoretical Mathematics
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.