随着移动互联网的飞速发展,不断增长的海量运算需求和对实时性的要求也为我们带来了巨大的挑战。网络稳定性,作为衡量网络状态的重要指标之一,在学术界已成为一个被广泛研究的问题。通过研究网络稳定性,我们可以设法增加网络的稳定性,使得网络拥有更高的鲁棒性;我们也可以试图发现网络中的薄弱环节,从而抵御受到外在攻击的风险。而k-Core模型,作为一个流行的稠密子图模型,常被用于衡量网络的结构稳定性。它对应着网络中的一个最大诱导子图,其中每个节点都至少有k个节点邻居。学界常使用网络中k-Core的大小,来近似判断该网络的稳定性。而当我们想要改善网络的稳定性时,也常常会试图通过改变网络的拓扑结构,来使得k-Core变大,例如,向网络中加边。Edge k-Core问题便是用来加强网络稳定性的尝试之一:给定一个图G,一个整数k和一个预算b,我们试图在图G中连接b对不邻接的顶点对,使得k-Core的大小最大化。Edge k-Core问题由Chitnis首个提出,他还给出了在tree-width条件下的对应算法。但很遗憾,至今也没有关于一般图上的Edge k-Core高效算法研究。在这篇文章中,我们首先系统性地研究了 Edge k-Core问题的复杂度,证明了该问题是NP-hard与APX-hard的。然后我们针对性地设计了一种贪心选择策略,并为其设计了大量剪枝策略和计算优化,给出了首个在一般图上的高效近似算法EKC。该算法能在保证高效的前提下,取得和精确解相近似的效果。但即便如此,该算法依旧不能在海量数据集上取得令我们满意的性能表现。我们进一步地分析了 EKC的性能瓶颈,给出了一个面向顶点的启发式策略,并提出一系列的优化技术,设计得到了 VCEK算法。算法VCEK和EKC拥有近似的效果,但前者的运行时间却能在EKC的基础上又快了 1-3个数量级。我们进行了详尽的实验分析,仔细考察了各个算法的执行性能、有效性以及可扩展性。最后的实验结果证明了我们所设计算法的优越性。