Skip navigation
Please use this identifier to cite or link to this item:
Title: Tensor Methods for Network Analysis
Authors: Gitelman, Daniel
Advisors: Fan, Jianqing
Contributors: Operations Research and Financial Engineering Department
Keywords: community detection
power method
Subjects: Statistics
Applied mathematics
Issue Date: 2022
Publisher: Princeton, NJ : Princeton University
Abstract: In this dissertation, we study two canonical statistical problems in the hypergraph setting -- community detection and non-parametric estimation. We focus on the stochastic hypergraph block model, where each vertex belongs to a community, and hyperedge probabilities are dependent on the communities of its corresponding vertices. Our main algorithmic tool for community detection is the tensor power method, in which a tensor map is repeatedly applied until convergence. Despite being a direct generalization of the matrix power method, the tensor power method has interesting differences compared to the matrix power method, which we explore in this work. We begin by showing that in certain parameter ranges, the tensor power method succeeds in recovering eigenvectors when applied to expected adjacency tensor. Since the expected adjacency tensor is not orthogonally decomposable, this is already a nontrivial result, as most of the tensor decomposition that exist in the literature are for orthogonally decomposable tensors. Next, interpreting the adjacency tensor as a perturbation of the expected adjacency tensor, we show that applying the tensor power method to the adjacency tensor can be used to recover the underlying communities of the stochastic hypergraph block model, by way of recovering the eigenvectors of the expected adjacency tensor. For this step, we require a tensor concentration result, and we show that the adjacency tensor concentrates around the expected adjacency tensor in spectral norm by using an enhanced ε-net argument. Regarding non-paremetric estimation, we study statistical and algorithmic aspects of using hypergraphons, which are limits of large hypergraphs, for modeling higher-order interactions. Although hypergraphons are extremely powerful from a modeling perspective, we consider a restricted class of Simple Lipschitz Hypergraphons (SLH), which are more amenable to efficient estimation. We also provide rates of convergence for our estimator that are optimal for the class of SLH. Simulation results are provided to corroborate the theory.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Operations Research and Financial Engineering

Files in This Item:
File Description SizeFormat 
Gitelman_princeton_0181D_14136.pdf1.06 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.