Finding Cheeger Cuts in Hypergraphs via Heat Equation
| Autor: | Ikeda, Masahiro, Miyauchi, Atsushi, Takai, Yuuki, Yoshida, Yuichi |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Cheeger's inequality states that a tightly connected subset can be extracted from a graph $G$ using an eigenvector of the normalized Laplacian associated with $G$. More specifically, we can compute a subset with conductance $O(\sqrt{\phi_G})$, where $\phi_G$ is the minimum conductance of a set in $G$. It has recently been shown that Cheeger's inequality can be extended to hypergraphs. However, as the normalized Laplacian of a hypergraph is no longer a matrix, we can only approximate to its eigenvectors; this causes a loss in the conductance of the obtained subset. To address this problem, we here consider the heat equation on hypergraphs, which is a differential equation exploiting the normalized Laplacian. We show that the heat equation has a unique solution and that we can extract a subset with conductance $\sqrt{\phi_G}$ from the solution. An analogous result also holds for directed graphs. Comment: 22 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|