% ----------------------------------------------------------------------
%                   LATEX TEMPLATE FOR PhD THESIS
% ----------------------------------------------------------------------

% based on Harish Bhanderi's PhD/MPhil template, then Uni Cambridge
% http://www-h.eng.cam.ac.uk/help/tpl/textprocessing/ThesisStyle/
% corrected and extended in 2007 by Jakob Suckale, then MPI-CBG PhD programme
% and made available through OpenWetWare.org - the free biology wiki


%: Style file for Latex
% Most style definitions are in the external file PhDthesisPSnPDF.
% In this template package, it can be found in ./Latex/Classes/

%\documentclass[twoside,11pt]{Latex/Classes/PhDthesisPSnPDF}
\documentclass[oneside,11pt]{Latex/Classes/PhDthesisPSnPDF}
%: ----- font
\fontencoding{T1} \fontfamily{bch} \selectfont
%: ----- title of chapters
\usepackage{sectsty} \titleformat{\chapter}[block]{\Huge\bfseries}{\thechapter}{20pt}{} \titlespacing*{\chapter}{0pt}{10pt}{40pt}
\setcitestyle{square}
\usepackage[toc]{glossaries}
%\usepackage{txfonts}
\usepackage{ifthen}
\usepackage{amsmath}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\usepackage{tikz}
\usepackage{textcomp} 
\usepackage{pgfplots}
\usepackage{pgfplotstable}
%\usepackage{enumitem}
\usepackage{tabularx}
\usepackage{multirow}
\usepackage[normalem]{ulem}
\usetikzlibrary{positioning}

\usepackage[toc,page]{appendix}

% added by CFK, Nov 2013:
\usepackage{enumerate}
\usepackage{multirow}
\usepackage{subfig}
\usepackage{graphicx}
\usepackage[nottoc]{tocbibind}

%\usepackage{algorithm}
%\usepackage{algorithmic}


\DeclareFontFamily{OT1}{pzc}{}
\DeclareFontShape{OT1}{pzc}{m}{it}{<-> s * [1.10] pzcmi7t}{}
\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}

\newenvironment{proof}{\paragraph{Proof:}}{\hfill$\square$}

%end added by CFK

\makeglossaries
% use makeglossaries thesis in terminal

%: ----- theorem environment
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{definition}{Definition}


%: Macro file for Latex
% Macros help you summarise frequently repeated Latex commands.
% Here, they are placed in an external file /Latex/Macros/MacroFile1.tex
% An macro that you may use frequently is the figuremacro (see introduction.tex)
\include{Latex/Macros/MacroFile1}
\include{Latex/Macros/AlexMacro}
\include{Latex/Macros/PanayotMacro}

\newcommand{\todo}[1]{}%{\textcolor{red}{TODO: #1}}
%\newcommand{\corr}[1]{\textcolor{blue}{#1}}
\newcommand{\corr}[1]{#1}
%\newcommand{\myTitle}{Block Preconditioners and Algebraic Splittings for Saddle Point Problems, an Application to Incompressible Fluid-dynamics}
%\newcommand{\myTitle}{Fast Finite Element Solvers and Scalable Preconditioners for Incompressible Flows}
\newcommand{\myTitle}{Centrality and Communicability Measures in Complex Networks: Analysis and Algorithms}
\newcommand{\myTwoLinesTitle}{Centrality and Communicability Measures in Complex Networks: \\ Analysis and Algorithms}
%: ----------------------------------------------------------------------
%:                  TITLE PAGE: name, degree,..
% ----------------------------------------------------------------------
% below is to generate the title page with crest and author name

%if output to PDF then put the following in PDF header
\ifpdf  
    \pdfinfo { /Title  (\myTitle)
               /Creator (TeX)
               /Producer (pdfTeX)
               /Author (Christine Klymko cklymko@emory.edu)
               /CreationDate (D:20120508)  %format D:YYYYMMDDhhmmss
               /ModDate (D:20120508)
               /Subject (computational mathematics)
               /Keywords (network analysis, matrix functions, centrality, communicability, adjacency matrix, Gauss quadrature, hubs, authorities, HITS, PageRank, directed networks) }
    \pdfcatalog { /PageMode (/UseOutlines)
                  /OpenAction (fitbh)  }
\fi


\title{\myTitle}



% ----------------------------------------------------------------------
% The section below defines www links/email for author and institutions
% They will appear on the title page of the PDF and can be clicked
\ifpdf
  \author{\href{mailto:cklymko@emory.edu}{Christine Klymko}}
%  \cityofbirth{born in XYZ} % uncomment this if your university requires this
%  % If city of birth is required, also uncomment 2 sections in PhDthesisPSnPDF
%  % Just search for the "city" and you'll find them.
  \collegeordept{\href{http://www.mathcs.emory.edu}{Mathematics and Computer Science Department}}
  \university{\href{http://www.emory.edu}{Emory University}}

  % The crest is a graphics file of the logo of your research institution.
  % Place it in ./0_frontmatter/figures and specify the width
  \crest{\includegraphics[width=4cm]{logo}}
  
% If you are not creating a PDF then use the following. The default is PDF.
\else
  \author{Christine Klymko}
%  \cityofbirth{born in XYZ}
  \collegeordept{Mathematics and Computer Science Department}
  \university{Emory University}
  \crest{\includegraphics[width=4cm]{logo}}
\fi

%\renewcommand{\submittedtext}{change the default text here if needed}
\degree{Philosophi\ae Doctor (PhD) in Computational Mathematics}
\degreedate{2013 December}


% ----------------------------------------------------------------------
       
% turn of those nasty overfull and underfull hboxes
\hbadness=10000
\hfuzz=50pt


%: --------------------------------------------------------------
%:                  FRONT MATTER: dedications, abstract,..
% --------------------------------------------------------------



\begin{document}


%\language{english}

% sets line spacing
\renewcommand\baselinestretch{1.2}
\baselineskip=18pt plus1pt


%: ----------------------- distribution agreement ------------------------
\pagestyle{empty}
\noindent {\bf Distribution Agreement}\\

\noindent In presenting this thesis or dissertation as a partial fulfillment of the requirements for an
advanced degree from Emory University, I hereby grant to Emory University and its agents
the non-exclusive license to archive, make accessible, and display my thesis or dissertation
in whole or in part in all forms of media, now or hereafter known, including display on
the world wide web. I understand that I may select some access restrictions as part of
the online submission of this thesis or dissertation. I retain all ownership rights to the
copyright of the thesis or dissertation. I also retain the right to use in future works (such
as articles or books) all or part of this thesis or dissertation.

\vspace{3cm}

\noindent Signature:

\vspace{.5cm}

\noindent \line(1,0){200} \hspace{1.5cm} \line(1,0){100} \\
\noindent Christine Klymko \hspace{5.9cm} Date


\cleardoublepage
\newpage

%: ----------------------- approval sheet ------------------------
\begin{center}

\large{\myTwoLinesTitle}

\vspace{.5cm}

\large{by}

\vspace{.5cm}

\large{Christine Klymko}

\large{Doctor of Philosophy}

\vspace{.5cm}

\large{Mathematics and Computer Science}\\

\vspace{1.cm}

\line(1,0){250}

\large{Michele Benzi, Ph.D.}

\large{Advisor}

\vspace{1.cm}

\line(1,0){250}

\large{Ronald Gould, Ph.D.}

\large{Committee Member}

\vspace{1.cm}

\line(1,0){250}

\large{James Nagy, Ph.D.}

\large{Committee Member}

\vspace{1.cm}

Accepted:

\line(1,0){250}

\large{Lisa A. Tedesco, Ph.D.}

\large{Dean of the James T. Laney School of Graduate Studies}

\vspace{1.5cm}

\line(1,0){120}

\large{Date}

\end{center}

%: ----------------------- abstract ------------------------
\cleardoublepage
\newpage

\begin{singlespace}
\begin{center}
\myTitle
\vspace{2cm}

By

\vspace{0.7cm}

Christine Klymko

M.S. in Computer Science, Emory University, 2013

M.S. in Mathematics, Emory University, 2012

B.S. in Mathematics, Xavier University, 2008

\vspace{2cm}

Advisor: Michele Benzi, Ph.D.

\vspace{4cm}

An abstract of

A dissertation submitted to the Faculty of the

James T. Laney School of Graduate Studies of Emory University

in partial fulfillment of the requirements for the degree of

Doctor of Philosophy

in Mathematics and Computer Science

2013

\end{center}
\end{singlespace}


\cleardoublepage
\newpage
%: ----------------------- abstract text ------------------------
\begin{singlespace}
\begin{center}

{\bf Abstract}\\

\vspace{1cm}

\myTitle\\

By Christine Klymko
\end{center}

\vspace{1cm}


Complex systems are ubiquitous throughout the world, both in nature and within man-made structures. Over the past decade, large amounts of network data have become available and, correspondingly, the analysis of complex networks has become increasingly important.  One of the fundamental questions in this analysis is to determine the ``most important'' elements in a given network. Measures of node importance are usually referred to as {\em node centrality} and measures of how well two nodes are able to communicate with each other are referred to as the {\em communicability} between pairs of nodes.  Many measures of node centrality and communicability have been proposed over the years.  Here, we focus on the analysis and computation of centrality and communicability measures based on matrix functions.

First, we examine a node centrality measure based on the notion of {\em total communicability}, defined in terms of the row sums of the exponential of the adjacency matrix of the network. We argue that this is a natural metric for ranking nodes in a network, and we point out that it can be computed very rapidly even in the case of large networks. Furthermore, we propose a measure of the {\em total network communicability}, based on the total sum of node communicabilities, as a useful measure of the connectivity of the network as a whole.

Next, we compare various parameterized centrality rankings based on the matrix exponential and matrix resolvent with degree and eigenvector centrality.  The centrality measures we consider are {\em exponential and resolvent subgraph centrality} (defined in terms of the diagonal entries of the matrix exponential and matrix resolvent, respectively), total communicability, and {\em Katz centrality} (defined in terms of the row sums of the matrix resolvent). We demonstrate an analytical relationship between these rankings and the degree and subgraph centrality rankings which helps to explain the observed robustness of these rankings on many real world networks, even though the scores produced by the centrality measures are not stable.

Finally, we propose an extension of subgraph centrality to directed networks, and we apply this extension to the problem of ranking hubs and authorities. The extension is achieved by {\em bipartization}, i.e., the directed network is mapped onto a bipartite undirected network with twice as many nodes in order to obtain a network with a symmetric adjacency matrix. We explicitly determine the exponential of this adjacency matrix in terms of the adjacency matrix of the original, directed network, and we give an interpretation of centrality and communicability in this new context, leading to a technique for ranking hubs and authorities.  This method is compared to the well-known {\em HITS} algorithm as well as to several other ranking algorithms.
  
\end{singlespace}

\cleardoublepage
\newpage

%: ----------------------- dissertation ------------------------

\begin{singlespace}
\begin{center}
\myTitle

\vspace{2cm}

By

\vspace{0.7cm}

Christine Klymko

M.S. in Computer Science, Emory University, 2013

M.S. in Mathematics, Emory University, 2012

B.S. in Mathematics, Xavier University, 2008

\vspace{2cm}

Advisor: Michele Benzi, Ph.D.

\vspace{4cm}

A dissertation submitted to the Faculty of the

James T. Laney School of Graduate Studies of Emory University

in partial fulfillment of the requirements for the degree of

Doctor of Philosophy

in Mathematics and Computer Science

2013

\end{center}
\end{singlespace}



\begin{doublespace}

\cleardoublepage
\newpage

%\frontmatter
\include{0_frontmatter/acknowledgement}

\cleardoublepage
\newpage

%\include{0_frontmatter/dedication}


%: ----------------------- contents ------------------------

\pagestyle{empty}
%\setcounter{secnumdepth}{3} % organisational level that receives a numbers
%\setcounter{tocdepth}{3}    % print table of contents for level 3
\tableofcontents            % print the table of contents
% levels are: 0 - chapter, 1 - section, 2 - subsection, 3 - subsection


%: ----------------------- list of figures/tables ------------------------
\cleardoublepage
\listoffigures	% print list of figures

\listoftables  % print list of tables

%\listofalgorithms


%: --------------------------------------------------------------
%:                  MAIN DOCUMENT SECTION
% --------------------------------------------------------------

% the main text starts here with the introduction, 1st chapter,...

\mainmatter
\setboolean{@twoside}{true} 
\pagestyle{fancy}
\renewcommand{\chaptername}{} % uncomment to print only "1" not "Chapter 1"

%: ----------------------- glossary ------------------------

% Tie in external source file for definitions: /0_frontmatter/glossary.tex
%% Glossary entries can also be defined in the main text. See glossary.tex
\include{0_frontmatter/glossary} 
%
%\begin{multicols}{2} % \begin{multicols}{#columns}[header text][space]
\begin{small} % scriptsize(7) < footnotesize(8) < small (9) < normal (10)
%
%\printnomenclature[1.5cm] % [] = distance between entry and description
%\label{nom} % target name for links to glossary
%

\printglossaries
\end{small}
%\end{multicols}


%: ----------------------- subdocuments ------------------------

% Parts of the thesis are included below. Rename the files as required.
% But take care that the paths match. You can also change the order of appearance by moving the include commands.

\include{1_introduction/introduction}	% background information
\include{2_chapter2/main}				
\include{3_chapter3/main}								
\include{4_chapter4/main}						
\include{5_conclusion/conclusion}
\begin{appendices}
\include{Appendix/appendixA}
\include{Appendix/appendixB}
\end{appendices}

%\include{References/references}
%\addcontentsline{toc}{section}{References}

\end{doublespace}

\setboolean{@twoside}{false} 
\cleardoublepage
\newpage

% --------------------------------------------------------------
%:                  BACK MATTER: appendices, refs,..
% --------------------------------------------------------------

% the back matter: appendix and references close the thesis
%\include{9_backmatter/appendix}

%: ----------------------- bibliography ------------------------

% The section below defines how references are listed and formatted
% The default below is 2 columns, small font, complete author names.
% Entries are also linked back to the page number in the text and to external URL if provided in the BibTex file.

% PhDbiblio-url2 = names small caps, title bold & hyperlinked, link to page 
%\begin{multicols}{2} % \begin{multicols}{ # columns}[ header text][ space]
%\begin{tiny} % tiny(5) < scriptsize(7) < footnotesize(8) < small (9)
\bibliographystyle{Latex/Classes/PhDbiblio-url2} % Title is link if provided
\renewcommand{\bibname}{References} % changes the header; default: Bibliography

\include{9_backmatter/bibliography} % adjust this to fit your BibTex file

%\end{tiny}
%\end{multicols}

% --------------------------------------------------------------
% Various bibliography styles exit. Replace above style as desired.

% in-text refs: (1) (1; 2)
% ref list: alphabetical; author(s) in small caps; initials last name; page(s)
%\bibliographystyle{Latex/Classes/PhDbiblio-case} % title forced lower case
%\bibliographystyle{Latex/Classes/PhDbiblio-bold} % title as in bibtex but bold
%\bibliographystyle{Latex/Classes/PhDbiblio-url} % bold + www link if provided

% % calls style file jmb.bst
% \bibliographystyle{Latex/Classes/jmb} in-text refs: author (year) without brackets
% ref list: alphabetical; author(s) in normal font; last name, initials; page(s)

%\bibliographystyle{plainnat} % calls style file plainnat.bst
% in-text refs: author (year) without brackets
% (this works with package natbib)
% --------------------------------------------------------------

\end{document}
