检索结果-南通市图书馆

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于k核的紧密子图查询算法研究

基于k核的紧密子图查询算法研究

作者：姚贤标上海海洋大学

学位级别：硕士

紧密子图查询作为图查询的研究热点之一,在很多领域都有着重要的应用。现有的研究中已有许多紧密子图查询方法,如基于模块度优化的算法、谱方法、非负矩阵分解等。对于紧密子图的定义也有多种,常见的有k架(k-truss)、k团(k-clique)、k核... 详细信息

紧密子图查询作为图查询的研究热点之一,在很多领域都有着重要的应用。现有的研究中已有许多紧密子图查询方法,如基于模块度优化的算法、谱方法、非负矩阵分解等。对于紧密子图的定义也有多种,常见的有k架(k-truss)、k团(k-clique)、k核(k-core)等。其中k核的定义要求图中每个节点至少有k个邻接节点,即每个节点的度至少为k。根据该定义,k核可以在线性时间复杂度内计算得到,具有较好的应用基础,已在许多方面有所研究与应用。由于k核只考虑图中节点和边的关系,据此得到的仅是一个边稠密的子图。但在很多场景下的图数据还会包括更多其它属性,若在查询紧密子图时不考虑这些属性则所得到的结果缺乏实际意义。在现有的k核研究中,已有部分文献开始结合图中的其它属性,如:图的关键词属性、图的空间位置属性、图的节点影响力属性等。但目前对于k核紧密子图的查询中,结合图中边权值的研究还较少,而在很多场景下,图中边的权值往往具有很强的语义关系。考虑到这一点,本文提出了一个新的紧密k核子图查询问题。目前对于紧密子图的查询,主要有两个研究方向:社团搜索和社团检测。本文所提出的问题属于紧密子图查询中的社团检测问题,其查询得到所有符合要求的连通子图。并且,本文考虑到查询最紧密子图往往会消耗较多的时间,在一些应用场景下也并不需要查询子图权重的最值。为此,本文所提的问题不局限于社团检测中最值的查询,子图只需满足给定的节点平均权值即可,而该值可以根据实际应用需求给出,具有更高的灵活性,能适应更多的查询场景。本文主要完成的工作如下:(1)提出了在加权图中查询联系紧密的连通k核子图问题,简记为紧密k核子图查询(Query Closely Relatedk-Core Subgraph,QCRkS)问题,其描述如下:给定核值k、节点平均权值,在加权图中查询紧密连通k核子图,该子图节点平均权值大于等于。随后通过多项式规约的方法,证明了QCRkS问题是一个NP-难问题。(2)由于无法为QCRkS问题找到一个在多项式时间复杂度内的最优算法,故本文为该问题设计了启发式算法CRk-G,其先在原图中查询一个最大连通k核作为候选子图,然后采用贪心策略通过在候选子图中不断迭代删除权值最小的节点,从而得到满足条件的紧密k核子图。(3)为提高CRk-G算法的效率,本文在其基础上进行改进,设计了CRk-C和CRk-F算法。CRk-C算法使用图压缩策略,在迭代之前先将权值相近节点进行合并,从而降低候选子图的规模。CRk-F算法使用单次多节点删除策略,每次迭代从候选子图中删除多个节点,从而减少迭代次数。两个算法分别从降低图规模和减少迭代次数两个方面出发,提高了查询效率,其查询速度明显高于CRk-G算法。(4)通过在真实数据集上的实验,对比了3种算法在不同查询场景下的查询效率,验证了算法的误差,分析了图压缩算法的有效性,以及最后通过与传统k核方法的对比和一个实例分析验证了本文所提模型的有效性。

关键词：社团检测 k核加权图紧密子图贪婪策略

社交媒体个人数据资源的多边市场竞争研究——基于k核凝聚子网的实证解析

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

软科学 2019年第6期33卷 1-7页

作者：黄磊赵延东梅亮中国科学技术发展战略研究院科技与社会发展研究所北京100038 南开大学经济与社会发展研究院天津300071 中国人民大学社会与人口学院北京100038 北京大学国家发展研究院北京100871

基于2016~2017年期间连续的用户活跃度相关指标和社交媒体平台API开放状态,构建社交媒体平台链态矩阵,并采取社会网络分析(SNA)方法中的k核分析方法,通过网络模块度、网络聚集系数和网络密度的测定,对选取的31个具有代表性的中国社交媒... 详细信息

基于2016~2017年期间连续的用户活跃度相关指标和社交媒体平台API开放状态,构建社交媒体平台链态矩阵,并采取社会网络分析(SNA)方法中的k核分析方法,通过网络模块度、网络聚集系数和网络密度的测定,对选取的31个具有代表性的中国社交媒体平台个人数据链接网络(PDCN)的汇聚结构进行分析。实证结果显示,样本网络存在网络聚集系数和网络密度较高的k核子网络,处于k核子网络中的平台构成了一个完整的数据资源配置网络。研究认为目前中国社交媒体平台个人数据链接网络汇聚较为显著,社交媒体产业结构性资源的个人数据资源的汇聚直接影响市场竞争状态,处于个人数据链接网络结构中心位置的平台对基于数据资源的多边市场竞争结构具有较强的控制力。

关键词：社交媒体个人数据多边市场市场竞争 k核

基于k核分解的网络知识社区关键用户挖掘研究

在线全文

学校读者我要写书评

暂无评论

情报理论与实践 2019年第6期42卷 149-153页

作者：王闯王亚民西安电子科技大学经济与管理学院

[目的/意义]为了提升关键用户在知识型社区发展中的知识贡献,对知识型社区情景下的关键用户挖掘方法进行研究。[方法/过程]以CSDN社区用户作为研究对象,分析用户交互行为与发布的文本特征,在k核分解方法的基础上,考虑相邻用户节点的影... 详细信息

[目的/意义]为了提升关键用户在知识型社区发展中的知识贡献,对知识型社区情景下的关键用户挖掘方法进行研究。[方法/过程]以CSDN社区用户作为研究对象,分析用户交互行为与发布的文本特征,在k核分解方法的基础上,考虑相邻用户节点的影响力贡献差异,定义网络边的潜在影响力与边的影响因子,综合考虑用户知识贡献者与传播者双重身份,构建关键用户挖掘模型与排序方法。[结果/结论]结果表明,本文方法能够有效识别现实网络知识社区中的关键用户。

关键词：知识社区关键用户 k核用户影响力挖掘方法

在线全文

学校读者我要写书评

暂无评论

基于贪婪策略的紧密k核子图查询

计算机工程 2022年第10期48卷 55-66页

作者：赵丹枫姚贤标包晓光黄冬梅郭伟其上海海洋大学信息学院上海201306 上海电力大学电子与信息工程学院上海200090 国家海洋局东海海洋环境调查勘察中心上海200137

k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k... 详细信息

k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询(CRkSQ)问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRk-G,通过迭代删除节点为CRkSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRk-G算法的优化策略,分别提出使用图压缩策略的算法CRk-C及使用单次多节点删除策略的算法CRk-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRk-G算法,CRk-C、CRk-F算法在查询速度上有较大的提升,且平均误差均在8%以内。

关键词：社团检测 k核加权图紧密子图贪婪策略

基于改进k-Shell的社会网络关键节点挖掘算法

在线全文

学校读者我要写书评

暂无评论

计算机应用与软件 2023年第7期40卷 305-310页

作者：李蜜佳卫红权李英乐刘树新中国人民解放军战略支援部队信息工程大学河南郑州450001

传统的k-Shell分解法具有时间复杂度低的特点,但其划分结果普遍粗粒化,难以满足精细化节点重要性划分的实际需求。基于k-Shell分解法,提出一种改进的重要节点挖掘算法。在充分利用节点的网络位置信息的基础上,考虑节点的度数和节点被删... 详细信息

传统的k-Shell分解法具有时间复杂度低的特点,但其划分结果普遍粗粒化,难以满足精细化节点重要性划分的实际需求。基于k-Shell分解法,提出一种改进的重要节点挖掘算法。在充分利用节点的网络位置信息的基础上,考虑节点的度数和节点被删除时所处的迭代层数,提出改进的k-Shell方法;在用改进的k-Shell对节点排名并提取核心网络后,结合节点的PageRank值,定量分析网络核心层的节点,形成多层级的节点重要性划分。在三种真实网络数据集中的实验验证表明,该方法能显著提高k-Shell分解法的分辨率,并且时间复杂度低,适用于大规模网络的应用。

关键词：关键节点社会网络 k核 PageRank

基于节点分簇的机会网络Ferry节点关键技术研究

在线全文

学校读者我要写书评

暂无评论

基于节点分簇的机会网络Ferry节点关键技术研究

作者：王植飞内蒙古大学

学位级别：硕士

机会网络是一种无需基础设置、依靠节点移动带来的相遇机会,按照“存储-携带-转发”的方式完成消息转发的移动自组织网络。在由节点簇构成的机会网络中,簇间有时不存在消息转发所需的链路,各节点簇处于通讯隔绝的状态,在节点簇间部署往... 详细信息

机会网络是一种无需基础设置、依靠节点移动带来的相遇机会,按照“存储-携带-转发”的方式完成消息转发的移动自组织网络。在由节点簇构成的机会网络中,簇间有时不存在消息转发所需的链路,各节点簇处于通讯隔绝的状态,在节点簇间部署往返于区域间的Ferry节点对实现网络整体连通具有重要意义。在机会网络中识别并部署Ferry节点,以及对Ferry节点进行合理的调度管理可以延长网络寿命,提升网络性能。现有的针对机会网络Ferry节点识别的相关研究较少,且存在识别准确率不高的问题;同时,由于Ferry节点在网络中承担着节点簇间消息转发的工作,与普通节点相比通常具有消息数量多、能量消耗大、转发周期长等特点,因此需要针对Ferry节点的特点设计机会网络路由算法,以实现高效的利用Ferry节点有限的资源。但现有Ferry节点路由算法均没有涉及Ferry节点运动路径规划与Ferry节点协同工作相融合的问题,导致Ferry节点路径规划困难和协同工作效率低下。针对上述问题,本研究的主要贡献和创新性成果如下:1.提出了基于结构洞和k核的Ferry节点集群识别模型。本文构建了一种基于Ferry＿Importance＿Rank(FIR)指标的Ferry节点集群识别模型,在结构洞重要性和k核重要性的基础上提出了用于评价节点对机会网络整体贡献度的FIR指标,并基于该指标设计了Ferry节点集群识别模型。与基于介数中心性的Ferry节点识别算法相比,本模型的识别准确率达到了100%。2.提出了基于主动规划路径的Ferry节点集群协同工作路由策略(ORABAC)。该策略在主动规划节点运动路径的情况下实现了多个Ferry节点的协同工作,减少了Ferry节点对无效区域的访问,降低了不同Ferry节点对同一区域的重复访问次数,减小了消息转发延时,提高了节点资源利用率。与基于固定路径的方法以及基于Ferry节点分层的方法相比,该策略具有更高的消息投递率以及更低的消息转发延迟,Ferry节点的生存时间也更长。

关键词：机会网络 Ferry节点结构洞 k核协同工作

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

局部最大核子图搜索算法研究

电子技术与软件工程 2022年第2期 173-176页

作者：罗碧彤孙晶李源李欣蔚北方工业大学信息学院北京市100144

本文首先通过广度优先搜索和计算最大发生率,将需要探索的邻接点进行排序。然后,基于核数和最大核心度,提出了通过核数上界和最大核心度上界判断顶点是否具有提升当前核数的能力。为了寻找核数最大的包含查询点的极大连通子图,本文分别... 详细信息

本文首先通过广度优先搜索和计算最大发生率,将需要探索的邻接点进行排序。然后,基于核数和最大核心度,提出了通过核数上界和最大核心度上界判断顶点是否具有提升当前核数的能力。为了寻找核数最大的包含查询点的极大连通子图,本文分别基于全局搜索和局部搜索的两种算法。基于真实数据的实验结果证明了本文提出算法的高效性和有效性。

关键词：社区搜索 k核全局搜索局部搜索

在线全文

学校读者我要写书评

暂无评论

基于网络结构及节点活动网络的PSN协议

吉林大学学报（理学版） 2016年第3期54卷 569-574页

作者：黄蔚孙永雄吕巍吉林大学计算机科学与技术学院长春130012

将网络关联结构和位置匹配的思想引入到公共交换网络(PSN)的路由协议设计中,从全局搜索和局部搜索两方面解决了消息报文的路由问题.首先,探索全局搜索时网络关联结构对信息传播的影响,可知在复杂网络中最有效的传播节点应该是位于网络... 详细信息

将网络关联结构和位置匹配的思想引入到公共交换网络(PSN)的路由协议设计中,从全局搜索和局部搜索两方面解决了消息报文的路由问题.首先,探索全局搜索时网络关联结构对信息传播的影响,可知在复杂网络中最有效的传播节点应该是位于网络关联结构的最核心节点,而不是全局社会度高的节点.其次,探讨局部搜索时基于位置匹配度的合理性和可行性.最后,提出一个基于社会结构度和节点活动网络的路由协议,即k核.报文开始时在全局社区进行转发,将报文转发给处于网络中心位置的节点,直至找到转发报文的节点位于报文目的节点的附近,再根据该附近区域的节点位置匹配度进行转发报文.与经典协议相比,该方法可以保证在几乎相同的报文延迟基础上,实现更高的投递成功率及更少的花费.

关键词： k核全局搜索局部搜索公共交换网络路由

在线全文

学校读者我要写书评

暂无评论

奇异性核物理前沿问题

物理学进展 2008年第1期28卷 72-77页

作者：党蕾李磊宁平治南开大学物理系天津300071

简要评述奇异性核物理的几个前沿问题,包括Λ超核能谱精细结构与ΛN相互作用提取问题,自由YN势的改进问题、k核问题、Σ超子-核势问题、Λ超子-Λ超子相互作用强度问题、中子星内部奇异粒子成分问题等。

关键词：奇异性核物理超核 AN相互作用 k核