Principled and Scalable Methods for Analysis of Higher-Order Networks

Other Titles
Graphs have enjoyed immense success as a model for analyzing pairwise interactions, such as friendships on Facebook, where people are encoded as nodes and friendships as edges that link nodes. However, many datasets exhibit higher-order interactions that go beyond the scope of the pairwise graph model, such as product co-purchasing data on Amazon. We lose important information by ignoring this higher-order structure. Currently, few methods for directly analyzing higher-order data exist. In this dissertation, we present principled and scalable methods for analyzing higher-order information. We first focus on the hypergraph perspective, where the hyperedges representing an interaction can connect two or more nodes at once. In the first part of the thesis, we introduce methods for analyzing hypergraphs that have multiple types of interactions. In particular, in Chapter 2 we develop a framework for detecting communities of nodes in hypergraphs that have different types or categories of hyperedges. In Chapter 3, we use the theory from Chapter 2 to construct a method for diverse recommender systems that scales to large datasets. In the next part of the thesis, we present some novel methods for dealing with hypergraphs that have special structure. In particular, in Chapter 3 we present a principled method for recovering planted "core" nodes. In the last part of the thesis, we present higher-order methods for graphs that come with edge flow metadata. In particular, in Chapter 4 we show that their associated Laplacian harmonic vectors exhibit spacial localization, and leverage this insight to create a principled algorithm that allows us to efficiently localize holes in these complexes.
Journal / Series
Volume & Issue
186 pages
Date Issued
Effective Date
Expiration Date
Union Local
Number of Workers
Committee Chair
Benson, Austin Reilley
Committee Co-Chair
Committee Member
Townsend, Alex John
Damle, Anil
Degree Discipline
Applied Mathematics
Degree Name
Ph. D., Applied Mathematics
Degree Level
Doctor of Philosophy
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
Link(s) to Reference(s)
Previously Published As
Government Document
Other Identifiers
Rights URI
dissertation or thesis
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record