Computing the $p$-Laplacian eigenpairs of signed graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910782842732544 |
|---|---|
| author | Ge, Chuanyuan Qin, Ouyuan |
| author_facet | Ge, Chuanyuan Qin, Ouyuan |
| contents | As a nonlinear extension of the graph Laplacian, the graph $p$-Laplacian has various applications in many fields. Due to the nonlinearity, it is very difficult to compute the eigenvalues and eigenfunctions of graph $p$-Laplacian. In this paper, we establish the equivalence between the graph $p$-Laplacian eigenproblem and the tensor eigenproblem when $p$ is even. Building on this result, algorithms designed for tensor eigenproblems can be adapted to compute the eigenpairs of the graph $p$-Laplacian. For general $p>1$, we give a fast and convergent algorithm to compute the largest eigenvalue and the corresponding eigenfunction of the signless graph $p$-Laplacian. As an application, we provide a new criterion to determine when a graph is not a subgraph of another one, which outperforms existing criteria based on the linear Laplacian and adjacency matrices. Our work highlights the deep connections and numerous similarities between the spectral theories of tensors and graph $p$-Laplacians. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07929 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing the $p$-Laplacian eigenpairs of signed graphs Ge, Chuanyuan Qin, Ouyuan Numerical Analysis Combinatorics Spectral Theory 05C50, 15A18, 15A69, 05C22 As a nonlinear extension of the graph Laplacian, the graph $p$-Laplacian has various applications in many fields. Due to the nonlinearity, it is very difficult to compute the eigenvalues and eigenfunctions of graph $p$-Laplacian. In this paper, we establish the equivalence between the graph $p$-Laplacian eigenproblem and the tensor eigenproblem when $p$ is even. Building on this result, algorithms designed for tensor eigenproblems can be adapted to compute the eigenpairs of the graph $p$-Laplacian. For general $p>1$, we give a fast and convergent algorithm to compute the largest eigenvalue and the corresponding eigenfunction of the signless graph $p$-Laplacian. As an application, we provide a new criterion to determine when a graph is not a subgraph of another one, which outperforms existing criteria based on the linear Laplacian and adjacency matrices. Our work highlights the deep connections and numerous similarities between the spectral theories of tensors and graph $p$-Laplacians. |
| title | Computing the $p$-Laplacian eigenpairs of signed graphs |
| topic | Numerical Analysis Combinatorics Spectral Theory 05C50, 15A18, 15A69, 05C22 |
| url | https://arxiv.org/abs/2501.07929 |