Fast Connectivity Minimization on Large-Scale Networks
Fast Connectivity Minimization on Large-Scale Networks
复制标题
DOI：
10.1145/3442342
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Chen Chen-Chen;Ruiyue Peng;Lei Ying;Hanghang Tong
中科院分区：
文献类型：
--
作者：
Chen Chen-Chen;Ruiyue Peng;Lei Ying;Hanghang Tong
网络的连通性在许多高影响力的应用中得到了广泛的研究，从免疫接种，关键基础设施分析，社交网络挖掘到生物信息学系统研究。无论终端应用程序域如何，连接性最小化一直是有效控制底层系统功能的基本任务。连通性最小化问题的组合性质施加了指数计算复杂性来找到最优解，这在大型系统中是难以处理的。为了解决计算障碍，贪婪算法被广泛使用，以确保一个接近最优的解决方案，利用收益递减性质的问题。尽管取得了经验上的成功，但这些问题的理论和算法挑战仍然是开放的。在理论方面，除了少数特殊情况外，一般连通性最小化问题的内在困难和可逼近性仍然是未知的。在算法方面，现有的算法很难在优化质量和计算效率之间取得平衡。在这篇文章中，我们解决了两个挑战：（1）证明一般的连接最小化问题是NP-难的，是任何多项式算法的最佳近似比，（2）提出算法CONTAIN及其变体CONTAIN+，可以很好地平衡优化效率和计算效率在大型网络中基于特征函数的连接最小化问题。
The connectivity of networks has been widely studied in many high-impact applications, ranging from immunization, critical infrastructure analysis, social network mining, to bioinformatic system studies. Regardless of the end application domains, connectivity minimization has always been a fundamental task to effectively control the functioning of the underlying system. The combinatorial nature of the connectivity minimization problem imposes an exponential computational complexity to find the optimal solution, which is intractable in large systems. To tackle the computational barrier, greedy algorithm is extensively used to ensure a near-optimal solution by exploiting the diminishing returns property of the problem. Despite the empirical success, the theoretical and algorithmic challenges of the problems still remain wide open. On the theoretical side, the intrinsic hardness and the approximability of the general connectivity minimization problem are still unknown except for a few special cases. On the algorithmic side, existing algorithms are hard to balance between the optimization quality and computational efficiency. In this article, we address the two challenges by (1) proving that the general connectivity minimization problem is NP-hard and is the best approximation ratio for any polynomial algorithms, and (2) proposing the algorithm CONTAIN and its variant CONTAIN+ that can well balance optimization effectiveness and computational efficiency for eigen-function based connectivity minimization problems in large networks.