Events Calendar

PhD Defense - Alana Shine

PhD Defense - Alana Shine
Tues, Jul 14, 2020
3:30 PM - 5:30 PM
Ph.D. Defense - Alana Shine 7/14 3:30 pm Generative graph models subject to global similarity

Ph.D. Candidate: Alana Shine
Date: Tuesday, July 14, 2020
Time: 3:30 pm - 5:30 pm
Committee: David Kempe (chair), Aram Galstyan, Xiang Ren, Kayla de la Haye
Title: Generative graph models subject to global similarity
Zoom: https://usc.zoom.us/j/8333742899

Abstract:
This thesis explores how to build generative graph models subject to global features in order to capture connectivity structure. Generative graph models sample from sets of "similar" graphs according to a probability distribution and are important for simulation studies, anomaly detection, and characterizing properties of real world graphs in areas such as social science and network design. The vague notion of generating "similar" graphs has prompted a vast quantity of generative graph models that define similarity according to various graph features. Graph features used include degree distribution, motif counts, and high-level community structure. Typically, these features are local: the property can be segmented into parts with each part being computed entirely from its own subgraph. For example, node degrees. Instead, this work analyzes graph generation subject to global features that require the entire graph to compute. This thesis focuses on global features that capture connectivity because they are critical in determining how information/diseases spread on graphs and simulations of information/disease spread is a prominent application of generative graph models.


A large class of generative graph models are built from a single real world "target" graph and its features. This thesis presents three new generative graph models that target global similarity through matching (1) connectivity across cuts, (2) random walk behavior, and (3) eigenvalues of the symmetric normalized Laplacian matrix. All three of these global graph features are related to a widely used notion of graph connectivity called conductance. We observe on a number of real world target graphs that the global generative graph models perform superior to benchmark generative graph models on a number of similarity objectives.

WebCast Link: https://usc.zoom.us/j/8333742899

Audiences: Everyone Is Invited

Contact: Lizsl De Leon