多层网络中的连通k-核社区发现和搜索问题研究

发布时间：2020-05-11 15:54

【摘要】：随着互联网应用的日益普及,越来越多的大数据应用问题采用图来表示其数据结构。图(graph),也被称为网络(network),是一种重要的数据结构。在传统的图模型中,节点为单一类型,例如,商品,用户等;边也为单一类型,表示两个节点的关系,如好友关系等。社区是图中的一组顶点集合,其内部节点间联系较内部与外部节点间联系更为紧密。k-核是一种社区,由于其简洁的定义和高效的算法而被广泛采用。k-核社区发现和搜索是两类基于图的重要问题。以往对这两类问题的研究都是基于传统的图模型。随着应用问题的复杂,一些问题使用传统的图模型难以表达,例如,社交网络中,人们想要找到物理位置接近,同时互为好友关系的那些用户,而这种问题通常可以采用多层网络中的k-核社区来建模。多层网络的各层中共享顶点,具有不同类型的边。不同的层表示系统中顶点之间不同方面的交互关系,从而能够表达更为广泛的概念和更复杂的问题。因此,近年来,多层网络的相关研究成为新的研究热点。针对基于多层网络的研究还刚刚起步,相关研究还比较少,本文研究了多层网络中的连通k-核社区发现和搜索问题。本文提出了一种新的模型:连通k-核,用于建模多层网络中的k-核社区。本文主要研究三类问题:连通k-核社区发现问题,最大连通k-核社区发现问题和连通k-核社区搜索问题。(1)连通k-核社区发现问题指的是给定多层网络G和向量k,找到多层网络上所有连通k-核。本文提出了一种近似线性的算法,用于发现多层网络G中的所有连通k-核。(2)最大连通k-核社区发现问题是指找出多层网络上所有最大连通k-核。最大连通k-核是图中所有连通k-核中度数阈值k最大的连通k-核。对于多层网络的特殊情况双层网络,本文提出了最大连通k-核社区发现的自底向上和自顶向下的算法,并在最后提出了一种高效的二分搜索算法。对于一般的多层网络,本文提出了基于宽度优先搜索策略的多层最大连通k-核社区发现的高效算法。(3)连通k-核社区搜索问题是找出图中包含给定顶点集合的连通k-核的问题。在多层网络中,本文设计了高效的索引结构来查找包含一组查询顶点的连通k-核。基于所提出的索引结构,本文给出了高效的查询处理算法和多项式时间索引构造算法。本文在包括引用网络,推荐网络,地理社交网络,社交网络等多种领域的大型公开真实数据集对本文所提出的算法性能和有效性进行了评估。同时,通过公开的满足典型的社会网络的模式的随机图生成器合成了大型合成数据集,对算法的性能和可扩展性进行了评估。本文的实验结果证实了本文提出的算法在各个场景下均具有良好的性能,在数据集规模增加时,算法仍然具有良好的可扩展性和鲁棒性,不会发生时间开销不可接受的情况。同时,在Gowalla[7]数据集上进行的与最稠密连通子图[28]进行比较的案例分析证实了本文提出的连通k-核模型具有良好的性质。连通k-核中各个顶点均具有较高度数,不会出现度数较低的离群点,能够更好地表示网络中具有内聚属性的社区。
【图文】：

山东大学硕士学位论文简单情况，本文首先研宄了双层网络。在双层网络组分别只包含一层网络，因此可以将其称为物图１－１中的双层网络，该网络是根据社交网络构用户之间的物理联系，，因此被构造为物理网络。用户之间兴趣爱好的相似程度。当相似度大于一被构造为概念网络。值得注意的是，两个拥有相

钾3刁
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP311.12

【相似文献】

相关期刊论文 前10条

1 王林;李阳;周媛媛;于文涛;;基于层次覆盖的多层网络社团发现算法[J];计算机测量与控制;2018年07期

2 马夏夏;蔡永明;;基于复杂网络的铁路-航空多层网络的鲁棒性研究[J];山东科学;2017年05期

3 周铁柱;周春艳;;多层网络结构系统安全的几个关键技术[J];山西电子技术;2007年01期

4 李守伟;解一苇;杨坤;龚晨;;商业银行多层网络结构对系统性风险影响研究[J];东南大学学报(哲学社会科学版);2019年04期

5 龚晨;何建敏;李守伟;;银行多层网络与系统性风险研究进展[J];现代经济探讨;2018年11期

6 李守伟;文世航;王磊;;基于多层网络视角的企业担保结构研究[J];复杂系统与复杂性科学;2018年04期

7 刘晓燕;王晶;单晓红;杨娟;;基于多层网络的创新网络节点间技术融合机理[J];科学学研究;2019年06期

8 石兵;闵帆;周明天;李兴明;;多层网络抗毁机制的研究[J];计算机科学;2002年01期

9 张鸿宾;;训练多层网络的样本数问题[J];自动化学报;1993年01期

10 陆君安;;从单层网络到多层网络——结构、动力学和功能[J];现代物理知识;2015年04期

相关会议论文 前3条

1 邹庆云;李树丞;李林;李信儒;;多层网络与局部连接[A];发展的信息技术对管理的挑战——99’管理科学学术会议专辑（上）[C];1999年

2 胡海龙;邱倩琳;;立体多层网络架构在CBD覆盖中的应用[A];2012全国无线及移动通信学术大会论文集（下）[C];2012年

3 刘丁;;组合神经网络的非线性最优控制方法[A];1993中国控制与决策学术年会论文集[C];1993年

相关重要报纸文章 前1条

1 中兴通讯 庞玲;开启融合组网新纪元[N];通信产业报;2014年

相关博士学位论文 前8条

1 鲁立;异构多层网络中资源优化[D];华中科技大学;2017年

2 朱亮;核反应系统的多层网络结构特征研究[D];中国科学院研究生院(上海应用物理研究所);2016年

3 李圆媛;基于网络的复杂疾病的研究[D];武汉大学;2016年

4 张晓光;网络拓扑结构与传播动力学分析[D];中北大学;2014年

5 苏扬;多层通信网络业务流疏导问题研究[D];西安电子科技大学;2007年

6 颜登程;基于人类动力学和复杂网络的开发者行为及兴趣研究[D];中国科学技术大学;2017年

7 王赢飞;复杂动力网络的拓扑识别：从单层到多层[D];武汉大学;2016年

8 王云艳;基于多层网络模型的全极化SAR图像分类[D];武汉大学;2015年

相关硕士学位论文 前10条

1 岳灵茜;多层网络中的连通k-核社区发现和搜索问题研究[D];山东大学;2019年

2 安宁波;多层网络上传播动力学与偏好游走的相互作用[D];安徽大学;2019年

3 刘倩;多层网络中的混沌同步[D];北京邮电大学;2019年

4 王德华;基于机器学习及多层网络的SNP位点探究及可靠性分析[D];哈尔滨工业大学;2017年

5 王小东;二分及多层网络上的社团检测算法研究[D];西安电子科技大学;2018年

6 于莹莹;基于疾病—基因—药物数据的多层网络构建和分析[D];西安电子科技大学;2018年

7 姚顺宇;基于多层网络模块性的复杂疾病相关模式研究[D];西安电子科技大学;2018年

8 刘敏;基于多层网络的银行系统性风险研究[D];东南大学;2018年

9 杨远景;中国金融系统性风险的多层网络特征及其传染机制研究[D];湖南大学;2017年

10 马蒙周;基于多层网络的关键基因识别方法研究[D];西安理工大学;2018年

本文编号：2658705