A Spectral Framework for Graph Sampling
Abstract
This proposal seeks to investigate methodologicaJly and theoretically sound techniques for sampling interdependent data that make analysis feasible and lead to significant improvements in inference. This project will employ techniques from Markov chains, spectral graph theory, and statistical for interdependent data to describe a methodological and theoretical framework for scale-adaptive sampling on graphs. It will examine globally-adaptive Markov chain sampling to obtain a representative sample of the nodes in the graph. It will explore an áanti-transitive" sampling mechanism and attempt to demonstrate that the globally-adaptive property derives from the property that representative samples can be obtained more efficiently than standard link-tracing approaches. It will generate appropriate inferences for a sampled graph by characterizing the spectral sensitivity to sampling-induced edge dependence for two broad classes of sampling mechanisms (link-tracing and motif). ll will develop a class of locally-adaptive sampling mechanisms to test for local structure in massive graphs.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 12, 2017
- Source ID
- W911NF1510423
Entities
People
- Karl Rohe
Organizations
- Army Contracting Command
- United States Army
- University of Wisconsin–Madison