Math @ Duke

Publications [#208957] of Joshua Vogelstein
Papers Published
 Fishkind, Donniell E. and Sussman, Daniel L. and Tang, Minh and Vogelstein, Joshua T. and Priebe, Carey E., Consistent adjacencyspectral 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)
Abstract: 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) adjacencyspectral 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 adjacencyspectral partitioning procedure.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

