The spectral space of the adjacency matrix contains important structural information of a given network (graph), where such information can be leveraged in developing a variety of algorithms in applications such as graph partition, structural hierarchy discovery, and anomaly detection. Although many prominent works have laid the foundation for studying the graph spectra, it is still challenging to analyze the spectral space properties for directed graphs due to possible complex valued decompositions. Matrix factorization techniques such as Laplacian and normalized Laplacian have been widely adopted to study the associated spectral spaces, but network structural properties may not be well preserved in those spectral spaces due to transformations.
In this dissertation work, we explore the adjacency eigenspace of directed graphs using matrix perturbation theory and examine the relationships between graph structures and the spectral projection patterns. We study how to detect dominant structures such as clusters or anomalous nodes by establishing a connection between the connectivity of nodes and the geometric relationships in the adjacency eigenspace. We leverage selected key results from perturbation theory, linear algebra and graph theory as our tools to derive theoretical results that help to elaborate observed graph spectral projection patterns. In order to validate our theoretical results, novel algorithms including spectral clustering for both signed and unsigned networks, asymmetry analysis for network dominance, and anomaly analysis for streaming network data are developed and tested on both synthetic and real datasets. The empirical evaluation results suggest that our algorithms performs better when compared with existing state-of-the-art methods.
|Advisor:||Lu, Aidong, Wu, Xintao|
|Commitee:||Ras, Zbigniew, Wang, Yu, Zhao, Wei|
|School:||The University of North Carolina at Charlotte|
|School Location:||United States -- North Carolina|
|Source:||DAI-B 79/01(E), Dissertation Abstracts International|
|Keywords:||Directed graphs, Dynamic graphs, Graph anomaly detection, Graph spectral analysis, Matrix perturbation, Spectral clustering|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be