论文标题
增加图形的代数连接性
Augmenting the Algebraic Connectivity of Graphs
论文作者
论文摘要
For any undirected graph $G=(V,E)$ and a set $E_W$ of candidate edges with $E\cap E_W=\emptyset$, the $(k,γ)$-spectral augmentability problem is to find a set $F$ of $k$ edges from $E_W$ with appropriate weighting, such that the algebraic connectivity of the resulting graph $H=(V,E\cup F)$ is least $γ$。由于代数连接性与许多其他图参数之间存在紧密的连接，包括图中图的电导率和随机步行的混合时间，在过去的15年中研究了少量的边缘，从而最大程度地提高了所得图的代数连接性。 在这项工作中，我们提出了$（k，γ）$ - 光谱可增强性问题的近似和高效算法，并且我们的算法在广泛的参数方面几乎是线性的。我们的主要算法基于本文中开发的以下两种新技术，该技术可能具有$（k，γ）$ - 光谱可增强性问题的应用。 （1）我们提出了一种快速算法，用于求解[GB06]中代数连通性最大化问题的SDP的可行性版本。我们的算法基于求解SDP的经典原始二重式框架，该框架又使用了乘法更新算法。我们提出了一种统一不同矩阵和向量变量的SDP约束的新方法，并相应地给出了良好的分离甲骨文。 （2）我们提出了一个有效的算法，该算法是针对子图弹药问题的有效算法，对于多种参数，我们的算法在几乎线性的时间内运行，与以前最著名的算法在至少$ω（n^2MK）$ $ $ $ $ time [kmst10]中运行的算法相反。我们的分析表明，如何在子图弹药的设置中概括随机BSS框架，以及如何将电势函数应用于大致跟踪不同子空间。
For any undirected graph $G=(V,E)$ and a set $E_W$ of candidate edges with $E\cap E_W=\emptyset$, the $(k,γ)$-spectral augmentability problem is to find a set $F$ of $k$ edges from $E_W$ with appropriate weighting, such that the algebraic connectivity of the resulting graph $H=(V,E\cup F)$ is least $γ$. Because of a tight connection between the algebraic connectivity and many other graph parameters, including the graph's conductance and the mixing time of random walks in a graph, maximising the resulting graph's algebraic connectivity by adding a small number of edges has been studied over the past 15 years. In this work we present an approximate and efficient algorithm for the $(k,γ)$-spectral augmentability problem, and our algorithm runs in almost-linear time under a wide regime of parameters. Our main algorithm is based on the following two novel techniques developed in the paper, which might have applications beyond the $(k,γ)$-spectral augmentability problem. (1) We present a fast algorithm for solving a feasibility version of an SDP for the algebraic connectivity maximisation problem from [GB06]. Our algorithm is based on the classic primal-dual framework for solving SDP, which in turn uses the multiplicative weight update algorithm. We present a novel approach of unifying SDP constraints of different matrix and vector variables and give a good separation oracle accordingly. (2) We present an efficient algorithm for the subgraph sparsification problem, and for a wide range of parameters our algorithm runs in almost-linear time, in contrast to the previously best known algorithm running in at least $Ω(n^2mk)$ time [KMST10]. Our analysis shows how the randomised BSS framework can be generalised in the setting of subgraph sparsification, and how the potential functions can be applied to approximately keep track of different subspaces.
