基于k-core和k-truss模型的社交网络关键边检测方法研究

发布时间：2020-10-25 23:31

　　 近年来,随着互联网的高速发展,社交网络已经成为了人们日常生活中必不可少的一部分,例如脸书,推特等,对社交网络的研究也成为了近年来的热点。为了衡量社交网络中子图的稠密程度,许多子图模型被提出,例如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模型。
【学位单位】：华东师范大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP301.6;C912.3
【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景
    1.2 研究现状
    1.3 本文主要内容
    1.4 本文组织结构
第二章 背景知识和相关工作
    2.1 准备?作
    2.2 k-core 及相关算法介绍
    2.3 k-truss 及相关算法介绍
    2.4 其他?图模型介绍
    2.5 本章小节
第三章 基于删边方法的k-core最小化问题
    3.1 问题定义
    3.2 问题复杂性证明
    3.3 基础算法
    3.4 剪枝策略
    3.5 实验结果及分析
    3.6 本章小节
第四章 基于删边方法的k-truss最小化问题
    4.1 问题定义
    4.2 问题复杂性证明
    4.3 基础算法
    4.4 剪枝策略
    4.5 上界算法
    4.6 实验结果及分析
    4.7 本章小节
第五章 总结与展望
    5.1 本文工作总结
    5.2 未来工作展望
参考文献
发表论文和科研情况
致谢

【相似文献】

相关硕士学位论文 前3条

1 朱炜杰;基于k-core和k-truss模型的社交网络关键边检测方法研究[D];华东师范大学;2019年

2 杨李;基于扩散K-truss分解算法识别最有影响力节点及其应用研究[D];南京邮电大学;2018年

3 王岩;基于k-truss的图社区发现算法研究[D];燕山大学;2016年

本文编号：2856128