Fast Query of Biharmonic Distance in Networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914922531651584 |
|---|---|
| author | Liu, Changan Zehmakan, Ahad N. Zhang, Zhongzhi |
| author_facet | Liu, Changan Zehmakan, Ahad N. Zhang, Zhongzhi |
| contents | The \textit{biharmonic distance} (BD) is a fundamental metric that measures the distance of two nodes in a graph. It has found applications in network coherence, machine learning, and computational graphics, among others. In spite of BD's importance, efficient algorithms for the exact computation or approximation of this metric on large graphs remain notably absent. In this work, we provide several algorithms to estimate BD, building on a novel formulation of this metric. These algorithms enjoy locality property (that is, they only read a small portion of the input graph) and at the same time possess provable performance guarantees. In particular, our main algorithms approximate the BD between any node pair with an arbitrarily small additive error $\eps$ in time $O(\frac{1}{\eps^2}\text{poly}(\log\frac{n}{\eps} ))$. Furthermore, we perform an extensive empirical study on several benchmark networks, validating the performance and accuracy of our algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13538 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Query of Biharmonic Distance in Networks Liu, Changan Zehmakan, Ahad N. Zhang, Zhongzhi Social and Information Networks The \textit{biharmonic distance} (BD) is a fundamental metric that measures the distance of two nodes in a graph. It has found applications in network coherence, machine learning, and computational graphics, among others. In spite of BD's importance, efficient algorithms for the exact computation or approximation of this metric on large graphs remain notably absent. In this work, we provide several algorithms to estimate BD, building on a novel formulation of this metric. These algorithms enjoy locality property (that is, they only read a small portion of the input graph) and at the same time possess provable performance guarantees. In particular, our main algorithms approximate the BD between any node pair with an arbitrarily small additive error $\eps$ in time $O(\frac{1}{\eps^2}\text{poly}(\log\frac{n}{\eps} ))$. Furthermore, we perform an extensive empirical study on several benchmark networks, validating the performance and accuracy of our algorithms. |
| title | Fast Query of Biharmonic Distance in Networks |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2408.13538 |