Optimizing Probabilistic Propagation in Graphs by Adding Edges
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_ | 1866918088400699392 |
|---|---|
| author | Bhaskara, Aditya Crane, Alex Jain, Shweta Mazumder, Md Mumtahin Habib Ullah Sullivan, Blair D. Yalamanchili, Prasanth |
| author_facet | Bhaskara, Aditya Crane, Alex Jain, Shweta Mazumder, Md Mumtahin Habib Ullah Sullivan, Blair D. Yalamanchili, Prasanth |
| contents | Probabilistic graphs are an abstraction that allow us to study randomized propagation in graphs. In a probabilistic graph, each edge is "active" with a certain probability, independent of the other edges. For two vertices $u,v$, a classic quantity of interest, that we refer to as the proximity $\mathcal{P}_{G}(u, v)$, is the probability that there exists a path between $u$ and $v$ all of whose edges are active. For a given subset of vertices $V_s$, the reach of $V_s$ is defined as the minimum over pairs $u \in V_s$ and $v \in V$ of the proximity $\mathcal{P}_{G}(u,v)$. This quantity has been studied in the context of multicast in unreliable communication networks and in social network analysis.
We study the problem of improving the reach in a probabilistic graph via edge augmentation. Formally, given a budget $k$ of edge additions and a set of source vertices $V_s$, the goal of Reach Improvement is to maximize the reach of $V_s$ by adding at most $k$ new edges to the graph. The problem was introduced in earlier empirical work in the algorithmic fairness community. We provide the first approximation guarantees and hardness results for Reach Improvement.
We prove that the existence of a good augmentation implies a cluster structure for the graph. We use this structural result to analyze a novel algorithm that outputs a $k$-edge augmentation with an objective value that is poly($β^*$), where $β^*$ is the objective value for the optimal augmentation. We also give an algorithm that adds $O(k \log n)$ edges and yields a multiplicative approximation to $β^*$. Our arguments rely on new probabilistic tools for analyzing proximity, inspired by techniques in percolation theory; these tools may be of broader interest. Finally, we show that significantly better approximations are unlikely, under known hardness assumptions related to gap variants of the classic Set Cover problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_02624 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimizing Probabilistic Propagation in Graphs by Adding Edges Bhaskara, Aditya Crane, Alex Jain, Shweta Mazumder, Md Mumtahin Habib Ullah Sullivan, Blair D. Yalamanchili, Prasanth Data Structures and Algorithms Social and Information Networks Probabilistic graphs are an abstraction that allow us to study randomized propagation in graphs. In a probabilistic graph, each edge is "active" with a certain probability, independent of the other edges. For two vertices $u,v$, a classic quantity of interest, that we refer to as the proximity $\mathcal{P}_{G}(u, v)$, is the probability that there exists a path between $u$ and $v$ all of whose edges are active. For a given subset of vertices $V_s$, the reach of $V_s$ is defined as the minimum over pairs $u \in V_s$ and $v \in V$ of the proximity $\mathcal{P}_{G}(u,v)$. This quantity has been studied in the context of multicast in unreliable communication networks and in social network analysis. We study the problem of improving the reach in a probabilistic graph via edge augmentation. Formally, given a budget $k$ of edge additions and a set of source vertices $V_s$, the goal of Reach Improvement is to maximize the reach of $V_s$ by adding at most $k$ new edges to the graph. The problem was introduced in earlier empirical work in the algorithmic fairness community. We provide the first approximation guarantees and hardness results for Reach Improvement. We prove that the existence of a good augmentation implies a cluster structure for the graph. We use this structural result to analyze a novel algorithm that outputs a $k$-edge augmentation with an objective value that is poly($β^*$), where $β^*$ is the objective value for the optimal augmentation. We also give an algorithm that adds $O(k \log n)$ edges and yields a multiplicative approximation to $β^*$. Our arguments rely on new probabilistic tools for analyzing proximity, inspired by techniques in percolation theory; these tools may be of broader interest. Finally, we show that significantly better approximations are unlikely, under known hardness assumptions related to gap variants of the classic Set Cover problem. |
| title | Optimizing Probabilistic Propagation in Graphs by Adding Edges |
| topic | Data Structures and Algorithms Social and Information Networks |
| url | https://arxiv.org/abs/2407.02624 |