近年来,随着互联网的高速发展,社交网络已经成为了人们日常生活中必不可少的一部分,例如脸书,推特等,对社交网络的研究也成为了近年来的热点。为了衡量社交网络中子图的稠密程度,许多子图模型被提出,例如k-core,k-truss,k-plex,完全图(clique)等等。其中k-plex,完全图对子图的要求比较严格,而且无法在多项式时间内求解,在实际场景中的应用范围相对比较局限。而k-core和k-truss是两种比较简单的模型,能够在多项时间内求解,在许多实际问题中得到了广泛的应用。在社交网络中,用户之间的关系强弱对社交网络的稳定性有很大的影响。用户是否选择继续使用某个社交网络,往往受到他在这个社交网络中朋友数量的影响,而用户之间的关系,也往往受到他们之间的共同好友数量的影响。所以,对社交网络中关键点,关键边的挖掘,对社交网络的维护,构建都有着重要的意义,这也成为了近年来学术界研究的热点。本文使用k-core,k-truss这两种子图模型来衡量子图的稠密程度,并提出了两个新问题k-core最小化问题和k-truss最小化问题来检测社交网络中的关键边。给定一个图G,一个正整数b,我们需要找到b条关键边,使得删除这b条边后,剩余的k-core,k-truss最小。本文首先证明了这两个问题是NP难问题,并且目标函数不具有子模性,无法在多项式时间内得到一个有近似率保证的解。由于问题的复杂性,本文提出了一种基于贪心的启发式算法,并且提出了一些剪枝策略加快了计算的过程。在k-truss最小化问题中,本文还提出了一种上界算法进一步提高了算法效率。最后,在多个真实社交网络数据集上的对比实验,证明了本文所提出的算法的有效性和高效性。并且本文比较了两种模型寻找稠密子图的效果,证明了 truss模型优于core模型。