BEGIN:VCALENDAR
BEGIN:VEVENT
SUMMARY:PhD Defense - Alana Shine
DESCRIPTION:PhD Defense - Alana Shine\n
Tues, Jul 14, 2020\n
3:30 PM - 5:30 PM\n
Ph.D. Defense - Alana Shine 7/14 3:30 pm Generative graph models subject to global similarity\n
\n
Ph.D. Candidate: Alana Shine\n
Date: Tuesday, July 14, 2020\n
Time: 3:30 pm - 5:30 pm\n
Committee: David Kempe (chair), Aram Galstyan, Xiang Ren, Kayla de la Haye\n
Title: Generative graph models subject to global similarity\n
Zoom: https://usc.zoom.us/j/8333742899\n
\n
Abstract:\n
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.\n
\n
\n
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.\n
DTSTART:20200714T153000
LOCATION:
URL;VALUE=URI:
DTEND:20200714T173000
END:VEVENT
END:VCALENDAR