Compressive network analysis

Xiaoye Jiang, Yuan Yao, Han Liu, Leonidas Guibas

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

Modern data acquisition routinely produces massive amounts of network data. Though many methods and models have been proposed to analyze such data, the research of network data is largely disconnected with the classical theory of statistical learning and signal processing. In this paper, we present a new framework for modeling network data, which connects two seemingly different areas: network data analysis and compressed sensing. From a nonparametric perspective, we model an observed network using a large dictionary. In particular, we consider the network clique detection problem and show connections between our formulation with a new algebraic tool, namely Randon basis pursuit in homogeneous spaces. Such a connection allows us to identify rigorous recovery conditions for clique detection problems. Though this paper is mainly conceptual, we also develop practical approximation algorithms for solving empirical problems and demonstrate their usefulness on real-world datasets.

Original languageEnglish (US)
Article number6883133
Pages (from-to)2946-2961
Number of pages16
JournalIEEE Transactions on Automatic Control
Volume59
Issue number11
DOIs
StatePublished - Nov 1 2014

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Clique detection
  • Radon basis pursuit
  • compressive sensing
  • network data analysis
  • restricted isometry property

Fingerprint Dive into the research topics of 'Compressive network analysis'. Together they form a unique fingerprint.

  • Cite this

    Jiang, X., Yao, Y., Liu, H., & Guibas, L. (2014). Compressive network analysis. IEEE Transactions on Automatic Control, 59(11), 2946-2961. [6883133]. https://doi.org/10.1109/TAC.2014.2351712