Residuals-Based Subgraph Detection with Cue Vertices

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 30, 2015
Accession Number
AD1034504

Entities

People

  • Benjamin A. Miller
  • Rajmonda S. Caceres
  • Stephen J. Kelley
  • Steven T Smith

Organizations

  • MIT Lincoln Laboratory

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Boundary Value Problems
  • Communities
  • Computer Programming
  • Detection
  • Eigenvalues
  • False Alarms
  • Matrix Theory
  • Normal Distribution
  • Numbers
  • Phase Transformations
  • Probability
  • Quadratic Programming
  • Random Walk
  • Square Roots
  • Standards
  • United States

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Seismology
  • Systems Analysis and Design