Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#208957] of Joshua Vogelstein

Papers Published

  1. Fishkind, Donniell E. and Sussman, Daniel L. and Tang, Minh and Vogelstein, Joshua T. and Priebe, Carey E., Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown, Arxiv preprint (May, 2012), pp. 20, submitted, arXiv:1205.0309v1 [0309]
    (last updated on 2012/09/19)

    A stochastic block model consists of a random partition of n vertices into blocks 1,2,...,K for which, conditioned on the partition, every pair of vertices has probability of adjacency entirely determined by the block membership of the two vertices. (The model parameters are K, the distribution of the random partition, and a communication probability matrix M in [0,1]\^{}(K x K) listing the adjacency probabilities associated with all pairs of blocks.) Suppose a realization of the n x n vertex adjacency matrix is observed, but the underlying partition of the vertices into blocks is not observed; the main inferential task is to correctly partition the vertices into the blocks with only a negligible number of vertices misassigned. For this inferential task, Rohe et al. (2011) prove the consistency of spectral partitioning applied to the normalized Laplacian, and Sussman et al. (2011) extend this to prove consistency of spectral partitioning directly on the adjacency matrix; both procedures assume that K and rankM are known, even as the rest of the parameters may be unknown. In this article, we prove that the (suitably modified) adjacency-spectral partitioning procedure is consistent even if the only thing that is known about the parameters is any upper bound on rankM. In particular, this result shows a robustness in the adjacency-spectral partitioning procedure.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320