Balanced Bidirectional Breadth-First Search on Scale-Free Networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910677392687104 |
|---|---|
| author | Cerf, Sacha Dayan, Benjamin De Ambroggio, Umberto Kaufmann, Marc Lengler, Johannes Schaller, Ulysse |
| author_facet | Cerf, Sacha Dayan, Benjamin De Ambroggio, Umberto Kaufmann, Marc Lengler, Johannes Schaller, Ulysse |
| contents | To find a shortest path between two nodes $s_0$ and $s_1$ in a given graph, a classical approach is to start a Breadth-First Search (BFS) from $s_0$ and run it until the search discovers $s_1$. Alternatively, one can start two Breadth-First Searches, one from $s_0$ and one from $s_1$, and alternate their layer expansions until they meet. This bidirectional BFS can be balanced by always expanding a layer on the side that has discovered fewer vertices so far. This usually results in significant speedups in real-world networks, and it has been shown that this indeed yields sublinear running time on scale-free graph models such as Chung-Lu graphs and hyperbolic random graphs.
We improve this layer-balanced bidirectional BFS approach by using a finer balancing technique. Instead of comparing the size of the two BFS trees after each layer expansion, we perform this comparison after each vertex expansion. This gives rise to two algorithms that run faster than the layer-balanced bidirectional BFS on scale-free networks with power-law exponent $τ\in (2,3)$. The first one is an approximate shortest-path algorithm that outputs a path of length at most 1 longer than the shortest path in time $n^{(τ-2)/(τ-1)+o(1)}$. The second one is an exact shortest-path algorithm running in time $n^{1/2+o(1)}$. These runtime bounds hold with high probability when $s_0$ and $s_1$ are chosen uniformly at random among the $n$ vertices of the graph. We also develop an edge-balanced bidirectional BFS algorithm that works under adversarial conditions. This approximate shortest-path algorithm runs in time $n^{1/2+o(1)}$ with high probability when the adversary is allowed to choose $s_0$ and $s_1$ based on their (expected) degree. We complement our theoretical results with experiments on Chung-Lu graphs, Geometric Inhomogeneous Random Graphs, and real-world networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22186 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Balanced Bidirectional Breadth-First Search on Scale-Free Networks Cerf, Sacha Dayan, Benjamin De Ambroggio, Umberto Kaufmann, Marc Lengler, Johannes Schaller, Ulysse Social and Information Networks Combinatorics Probability To find a shortest path between two nodes $s_0$ and $s_1$ in a given graph, a classical approach is to start a Breadth-First Search (BFS) from $s_0$ and run it until the search discovers $s_1$. Alternatively, one can start two Breadth-First Searches, one from $s_0$ and one from $s_1$, and alternate their layer expansions until they meet. This bidirectional BFS can be balanced by always expanding a layer on the side that has discovered fewer vertices so far. This usually results in significant speedups in real-world networks, and it has been shown that this indeed yields sublinear running time on scale-free graph models such as Chung-Lu graphs and hyperbolic random graphs. We improve this layer-balanced bidirectional BFS approach by using a finer balancing technique. Instead of comparing the size of the two BFS trees after each layer expansion, we perform this comparison after each vertex expansion. This gives rise to two algorithms that run faster than the layer-balanced bidirectional BFS on scale-free networks with power-law exponent $τ\in (2,3)$. The first one is an approximate shortest-path algorithm that outputs a path of length at most 1 longer than the shortest path in time $n^{(τ-2)/(τ-1)+o(1)}$. The second one is an exact shortest-path algorithm running in time $n^{1/2+o(1)}$. These runtime bounds hold with high probability when $s_0$ and $s_1$ are chosen uniformly at random among the $n$ vertices of the graph. We also develop an edge-balanced bidirectional BFS algorithm that works under adversarial conditions. This approximate shortest-path algorithm runs in time $n^{1/2+o(1)}$ with high probability when the adversary is allowed to choose $s_0$ and $s_1$ based on their (expected) degree. We complement our theoretical results with experiments on Chung-Lu graphs, Geometric Inhomogeneous Random Graphs, and real-world networks. |
| title | Balanced Bidirectional Breadth-First Search on Scale-Free Networks |
| topic | Social and Information Networks Combinatorics Probability |
| url | https://arxiv.org/abs/2410.22186 |