Show simple item record

dc.contributor.advisorAthreya, Avantien_US
dc.contributor.authorPao, Henryen_US
dc.date.accessioned2015-09-16T03:36:19Z
dc.date.available2015-09-16T03:36:19Z
dc.date.created2015-05en_US
dc.date.issued2015-01-26en_US
dc.date.submittedMay 2015en_US
dc.identifier.urihttp://jhir.library.jhu.edu/handle/1774.2/37911
dc.description.abstractGraphs are widely used in many fields of research, ranging from natural sciences to computer and mathematical sciences. Graph inference is an area of intense research. In this dissertation, we propose several methodologies in graph inference. We focus on statistical inference using graph invariants, vertex nomination, and a divide-and-conquer graph matching technique. We present a comparative power analysis of various graph invariants for testing the hypothesis that the graph has a subgraph with higher edge probability. Given a graph drawn from a kidney-egg random graph model, the null hypothesis is that all edge probabilities are equal. The alternative hypothesis is that there exists a subset of vertices which are more likely to be adjacenct to each other than the rest of the graph. Using Monte Carlo simulations, we estimate the power of several graph invariants acting as test statistics. We discovered that for many choices of parameters in the random graph model, the scan statistic and clustering coefficient often dominate other graph invariants. However, our results indicates that none of the graph invariants considered is uniformly most powerful. Given a graph drawn from a stochastic block model where one block is of particular interest, vertex nomination is the task of creating a list of vertices such that there are an abundance of vertices from the block of interest at the top of the list. Vertex nomination is useful in situations where only a limited number of vertices can be examined and have their block membership checked. We propose several vertex nomination schemes, derive theoretical results for performance, and compare the schemes on simulated and real data. Given two graphs, graph matching is to create a mapping from one set of vertices to the other, such that the edge structure of the graphs is preserved as best as possible. We develop a new method for scaling graph matching algorithms, and prove performance guarantees. Any graph matching algorithm can be scaled using our divide-and-conquer technique. The performance of this technique is demonstrated on large simulated graphs and human brain graphs.en_US
dc.format.mimetypeapplication/pdfen_US
dc.languageen
dc.publisherJohns Hopkins University
dc.subjectGraphen_US
dc.subjectgraph inferenceen_US
dc.subjectgraph matchingen_US
dc.subjectvertex nominationen_US
dc.subjectmetropolis-hastingsen_US
dc.subjectspectral embeddingen_US
dc.subjectspectral partitioningen_US
dc.subjectparallelizationen_US
dc.subjectdivide and conqueren_US
dc.subjecten_US
dc.titleGraph Inference and Graph Matchingen_US
dc.typeThesisen_US
thesis.degree.disciplineApplied Mathematics & Statisticsen_US
thesis.degree.grantorJohns Hopkins Universityen_US
thesis.degree.grantorWhiting School of Engineeringen_US
thesis.degree.levelDoctoralen_US
thesis.degree.namePh.D.en_US
dc.type.materialtexten_US
thesis.degree.departmentApplied Mathematics and Statisticsen_US
dc.contributor.committeeMemberFishkind, Donniell E.en_US
dc.contributor.committeeMemberPriebe, Carey E.en_US
dc.contributor.committeeMemberLyzinski, Vinceen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record