Oral Candidacy - Salvador Aguinaga
|Start:||5/4/2016 at 10:00AM|
|End:||5/4/2016 at 12:30PM|
|Location:||315 Stinson Remick|
Faculty and students are welcome to attend the presentation portion of the defense.
May 4, 2016
315 Stinson Remick
Adviser: Tim Weninger, PhD
Dr. Nitesh Chawla Dr. David Chiang Dr. James Evans
Generative Network Models From Finite-State Graph Automata
Information is generated and consumed at break-neck speed across a wide range of disciplines including the natural sciences, engineering, medicine, and the social sciences. For example, a key challenge confronting the scientific community is making sense of an overwhelming volume of published literature. Discovering what underlies these massive collections and being able to model information at any scale requires creative ways of computational thinking and more effective tools.
While a large number of diverse approaches have been developed to address a wide range of challenges that come with massive datasets, most approaches only partially address the issues in different domains. Moreover, a majority of these approaches is often anchored on assumptions that fail to generalize. For example, exponential random graphs fail to scale, but are nevertheless widely used for modeling small networks. Kronecker product graph models, on the other hand, are another approach best suited for larger networks but can be slow at learning the graph model. Using hyperedge replacement grammars, formalism commonly used in natural language processing and compilers, we can address some of the limitations. This approach learns the grammars of graphs, scales, and generalizes across any network. Furthermore, we can generate graphical abstractions that preserve important network properties as observed in the original network with improvement over other models.
My research focus centers on how networks grow and on why they grow. The objective of the proposed research is to i) characterize hyperedge replacement graph grammars models by examining their strengths and weaknesses towards our understanding of network structure, ii) contribute to the extension of these models to dynamic (temporal) graphs using Markov Chains, and iii) introduce a new network metric that examines model degeneracy. These tasks will shed light on how this model’s philosophical assumptions relate to models in different fields. Furthermore, each task will contribute to understanding how well the model fits under latent position models, one of several classes of generative network models. The proposed work will also explore improvements to execution-time, ease of parallelization, and error minimization.