next up previous
Next: About this document ...

Geoffrey Sanders
Detecting Highly-Cyclic Structure with Complex Eigenpairs

Lawrence Livermore National Laboratory
Center for Applied Scientific Computing
7000 East Avenue
Livermore
Ca 94550
sanders29@llnl.gov
Christine Klymko

Highly 3- and 4-cyclic subgraph topologies are detectable via calculation of eigenvectors associated with certain complex eigenvalues of Markov propagators. We characterize this phenomenon theoretically to understand the capabilities and limitations for utilizing eigenvectors in this venture. We provide algorithms for approximating these eigenvectors and give numerical results, both for software that utilizes complex arithmetic and software that is limited to real arithmetic. Additionally, we discuss the application of these techniques to motif detection.





root 2016-02-26