  The graph matching problem emerges naturally in various applications such as
web privacy, image processing and computational biology. In this paper, graph
matching is considered under a stochastic model, where a pair of randomly
generated graphs with pairwise correlated edges are to be matched such that
given the labeling of the vertices in the first graph, the labels in the second
graph are recovered by leveraging the correlation among their edges. The
problem is considered under various settings and graph models. In the first
step, the Correlated Erd\"{o}s-R\'enyi (CER) graph model is studied, where all
edge pairs whose vertices have similar labels are generated based on identical
distributions and independently of other edges. A matching scheme called the
\textit{typicality matching scheme} is introduced. The scheme operates by
investigating the joint typicality of the adjacency matrices of the two graphs.
New results on the typicality of permutations of sequences lead to necessary
and sufficient conditions for successful matching based on the parameters of
the CER model. In the next step, the results are extended to graphs with
community structure generated based on the Stochastic Block Model (SBM). The
SBM model is a generalization of the CER model where each vertex in the graph
is associated with a community label, which affects its edge statistics. The
results are further extended to matching of ensembles of more than two
correlated graphs. Lastly, the problem of seeded graph matching is investigated
where a subset of the labels in the second graph are known prior to matching.
In this scenario, in addition to obtaining necessary and sufficient conditions
for successful matching, a polytime matching algorithm is proposed.
