Dominant Eigenvalue-Eigenvector Pair Estimation via Graph Infection

We present a novel method to estimate the dominant eigenvalue and eigenvector pair of any non-negative real matrix via graph infection.

The algorithm only requires a few lines of code:

#!/usr/bin/env python3

for i in range(num_steps):
    x_new = x_old + A @ x_old * Delta_t
    I_new = np.sum(x_new)

    m = (math.log(I_new) - math.log(I_old)) / Delta_t
    dominant_eigenval = (math.exp(m * Delta_t) - 1) / Delta_t

    x_old = x_new
    I_old = I_new

# DONE

Set up and Run

Python

pip install numpy networkx
python3 graph_infection_method.py

R Lang

Rscript graph_infection_method.r

Publication

Research paper accepted by Proc. 16th International Conference on Graph Transformation (ICGT 2023), Leicester, UK.

Extended abstract accepted by the Graph Signal Processing (GSP) Workshop 2023, Oxford, UK

Please see our arvix paper for more details: Arvix https://arxiv.org/abs/2208.00982

Citation

@inproceedings{yangxia2023eigen,
  title={Dominant Eigenvalue-Eigenvector Pair Estimation via Graph Infection},
  author={Yang, Kaiyuan and Xia, Li and Tay, YC},
  booktitle={International Conference on Graph Transformation},
  pages={243--260},
  year={2023},
  organization={Springer}
}