二分图中高效计算top-n maximalα-biclique的方法研究

针对当二分图中一类节点的数量固定时,如何搜索另一类型节点数量排序为前n的maximalα-biclique的问题,提出了一种基础搜索算法和一种基于共同邻居概念的改进搜索算法。在使用(1,α)-core剪枝方法加快搜索的算法基础上,基于共同邻居搜索算法使用共同邻居的概念对算法进行了改进,该算法只遍历节点的二跳邻居,并利用节点顺序和最小阈值提高搜索效率。实验结果表明,两种算法都可以有效且高效地搜索节点数量排名为前n的maximalα-biclique。与基础搜索算法相比,基于共同邻居搜索算法的搜索效率提升了80%,在实际应用场景中更具优势。

结合邻居影响和资源分配的链路预测算法

传统的资源分配算法在进行链路预测时只考虑了共同邻居对资源分配的影响,却忽略了两个节点之间的二级节点对资源分配的影响。为了探究共同邻居和二级节点对预测两个节点之间连边存在可能性的影响,提出了一种结合邻居影响和资源分配的链路预测算法。实验结果表明,在多数网络中若两个节点接收更多由共同邻居分配给它们的资源,则可以提升预测它们之间连边存在可能性的准确率。在四个生态网络和一些平均聚类系数较低的网络中,若两个节点接收更多通过二级节点分配给它们的资源,则可以提升预测它们之间连边存在可能性的准确率。

基于共邻节点相似度改进的DPoS共识算法

针对委托权益证明(delegated proof of stake,DPoS)中节点投票不积极和恶意节点操纵选举结果的问题,提出一种基于共邻节点相似度改进的DPoS(DPoS based on similarity of common neighbor nodes,S-DPoS)共识算法。首先,引入共邻节点相似度模型实现社区划分,缩短投票周期,提高共识效率。其次,计算节点的信誉度,各社区选出一个信誉度最高的节点作为见证节点且负责生产区块,通过节点身份转换机制及时更新节点类别。最后,通过奖惩机制对节点进行奖惩,快速剔除错误节点。仿真实验结果表明,S-DPoS共识算法的节点参与度比DPoS算法提高30%~40%,并且能够有效降低恶意节点操纵选举结果的可能性,增强了系统的安全性。

基于共邻节点相似度的社区划分算法

复杂网络中的社区结构能帮助人们认识网络的基本结构及其功能。针对目前多数社区划分算法准确率低、复杂度高的问题,提出了一种基于共邻节点相似度的社区划分算法。首先,为了计算节点间相似度值,提出了相似度模型,该模型通过将被测节点对的邻居节点引入一并计算,提高了相似度度量的准确性;然后,计算节点局部影响力值,能客观地表现出节点在所处网络中的重要性;其次,结合节点相似度值和节点局部影响力值对节点进行层次聚类,完成网络社区结构的初步划分;最后,通过聚合初步划分的子社区,获得复杂网络的最优模块度值。仿真结果表明,在网络的社区特征模糊时,与新的基于局部相似度的社区发现算法(CDALS)相比,所提算法的准确率提高了14%,证明了所提提法更能够准确、有效地划分复杂网络的社区结构。

一种基于加权共同邻居相似度的局部社区发现算法

传统的社区发现算法能够找出网络中所有的社区,其时间复杂度取决于网络的规模.挖掘大网络中的全局社区结构因为时间复杂度高而难以实现,局部社区发现作为一种不需要知道网络的整体结构,从给定的节点逐步向外扩展,寻找该节点所在社区的方法,在大网络时代具有重要的应用意义.目前这方面的研究已经获得广泛关注,并提出了很多局部社区发现算法.针对已有局部社区发现算法需要人工设置参数、准确率低的问题,提出一种新的局部社区发现算法.首先,提出一种加权邻居节点的共同邻居相似度指标,用于计算网络中两个节点间的相似度;然后,基于该相似度指标,给出一种新的局部社区质量度量指标,在保证社区度量指标不下降的前提下,不断选择与当前局部社区嵌入度最大的节点加入到局部社区,逐步找出给定节点所在的社区;最后,在真实网络和仿真网络数据集上进行了实验.实验结果表明,该算法能有效地挖掘出给定节点所在的局部社区,相比具有代表性的Clauset,LWP,GMAC等局部社区发现算法有更高的准确率.

面向信誉的自组网节点合作方法

针对移动自组网中自私节点出于节省资源而表现出不合作行为及丢弃待转发数据等问题，提出了一种面向信誉的自组网节点合作（CMC）方法，且第一次引入了共同邻居监听技术．看门狗在对下一跳转发节点进行监听的同时，可对周围不相关的数据流进行监听，从而加快了系统对不合作节点的检测速度．在路由发现过程中，CMC对路由控制消息进行了过滤，丢弃含有不合作节点的路由请求包和路由应答包，使源节点发现的路由能尽量绕过不合作节点．在ns-2下的仿真结果表明，当网络中存在10％～60％的不合作节点时，CMC能够使合作节点的吞吐率提高lO％～40％．

差分化社会网络节点角色的链路预测模型

以经典的Common Neighbor算法为例,提出了一种基于社区划分的差分化节点角色的链路预测模型,该模型首先采用Clauset-Newman-Moore算法挖掘社会网络结构属性,同时引入节点连接度和社区整体参与度的定义,差分处理社区内外邻接节点和不同社区的贡献,采用有监督的学习训练方法分别对社区内节点对和社区间节点对进行链路预测.人工网络和真实网络中的实验证明,该模型能够提高基于相似度算法对节点对链路预测的准确率,并为该类模型的研究提供一种新的方案.

基于共同邻居相似度的改进标签传播算法

标签传播算法是一种重要的社区发现算法,具有不需要先验知识、时间复杂度低的优点.针对传统标签传播算法随机性强导致社区发现结果稳定性差的问题,提出基于共同邻居相似度的改进标签传播算法LPACN,在选择邻居节点中出现次数最多的标签时,将邻居节点与该节点的相似度一并考虑,降低了标签选择的随机性,提高了算法的稳定性.在4个基准网络数据集上进行了对比实验,实验结果表明基于共同邻居相似度的改进标签传播算法能够得到更好的社区划分.

链路预测中的一种局部结构相似度算法

随着复杂网路理论的不断完善,对网络结构及演化模型的研究具有重要的应用价值,而链路预测作为复杂网络的研究热点越来越受到人们的重视.由于在大规模网络中,节点的属性等信息较难获取且相对不完整,因此现有的链路预测算法大都基于局部信息的相似度指标.这些算法往往计算简单、复杂度低,且能取得较好的预测效果,比较适合大规模的网络应用.但是由于其往往仅考虑到了不同节点之间的共同邻居数量,以及节点的度数影响,在个别网络中很难取得较好的预测效果.本文通过分析、比较现有的相似度指标算法,验证各算法的侧重点以及预测效果.对不同的网络结构模型进行提取以及比较,提出了一个新的基于邻节点结构相似度的LSCN指标算法.通过节点与其对应节点的邻居节点的结构相似度来计算节点对之间的连接概率,从而预测两个节点之间产生连接的可能性.通过在多个不同的网络结构中进行重复试验,由平均预测结果得出在部分网络中,算法的预测效果与其他依据节点结构相似性的算法相比得到了明显提升.

基于用户紧密度的在线社会网络社区发现算法

针对在线社会网络潜在社区难以检测的问题,根据在线社会网络的独有特性,提出一种基于用户紧密度的在线社会网络社区发现算法。创建初步用户图,依据节点属性相似性算法计算用户个体紧密度,基于共有邻居相似性算法计算用户社区紧密度,从而构造出完整用户图,利用层次聚类算法对完整用户图进行处理,发现潜在社区。实验结果表明,与NAS、CNS算法相比,该算法的社区凝聚度与正确率更高,分别达到0.67和97.1%。

一种改进共同邻居的节点遍历链路预测算法

链路预测是网络信息挖掘和预测领域的一个重要研究方向.由于网络拓扑结构信息容易获取使得基于拓扑结构的链路预测算法成为研究的热点,目前常用的链路预测算法没有分析真实网络链接形成的机制,并且利用的网络中节点的信息有限,导致预测精度受限.因此本文在已有算法基础上分析网络中每个节点对链接产生的作用,提出了一种改进共同邻居的全局节点遍历的链路预测算法.该算法不仅利用共同邻居平均度改善了大度节点的消极影响,而且考虑了同时与两个待预测节点都有共同邻居的节点的作用.在六个真实网络上经过大量实验表明该算法与六种经典的链路预测算法相比具有更高的预测精度,而且在食物链网络上预测精度提高了30%.

链路预测中一种改进的相似度指标算法

网络中的链路预测是指,如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生连接的可能性.而基于节点属性及局部信息的相似性的方法,往往计算简单而直接,计算复杂度低,且能取得较好的预测效果,比较适合大规模的网络应用.但往往各相似度算法只分别考虑到了,终节点自身的度数以及共同邻居的度数在相似指标中发挥的作用,而没有考虑到共同邻居对不同终节点自身的影响.本文通过分析、比较,现有的根据节点度数及共同邻居数量的相似度指标算法,验证各算法的侧重点以及预测效果.并且提出了一个新的CRA指标算法,进一步区分了计算相似指标时不同邻居节点对两个终节点的贡献.通过在多个不同的真实网络中进行重复试验,由平均预测结果得出算法的预测效果与其他依靠共同邻居指标的算法相比都得到了不同程度的提升.

无人机自组网中基于节点差异的AOMDV协议

AOMDV协议采用路由跳数为选择标准,在用于无人机自组网时存在链路不稳定和路由修复效率低的问题。为此,提出基于节点差异的路由协议ND-AOMDV。通过GPS获得无人机的方向和速度,以速度为向量构建无人机组模型。在此基础上,通过比较无人机速度向量的变化,选择节点差异最小的路径作为路由路径,并在路由修复时从断裂处寻找上下游节点能量最高的共同邻居节点重建链路。仿真结果表明,ND-AOMDV可有效增强路由稳定性和网络性能,与AOMDV和PE-AOMDV协议相比,其剩余能量分别提高42.7%、35.1%,平均端到端时延分别降低90.3%、89.5%,路由恢复频率分别降低79.1%、79.7%,路由开销分别降低50.3%、26.9%。

融合朴素贝叶斯方法的复杂网络链路预测

近来复杂网络成为了众多学者的研究热点。但真实网络中的连边信息并不完整,不利于网络的分析研究,链路预测可以挖掘网络中的缺失连边,为网络重构提供基本依据。本文认为网络中链接的产生不仅受外部因素——共同邻居的影响,还受其自身因素的影响。其中,共同邻居的影响可以通过文献中的局部朴素贝叶斯(LNB)模型量化,节点的影响则根据其自身的度量化。本文将两者综合考虑,提出了融合朴素贝叶斯(SNB)模型,然后用共同邻居(CN)、Adamic-Adar(AA)和资源分配(RA)指标进行推广。在美国航空网(USAir)上的实验结果表明,该方法的预测准确度比LNB和基准方法均有所提高,从而证明了该方法的有效性。

基于共同邻居的小度节点有利链路预测算法

现有的局部链路预测CN算法只是简单统计共同邻居的数目,忽视了在网络结构不同的前提下共同邻居的度对预测算法准确性的影响。针对上述问题,提出共同邻居的小度节点有利链路预测算法(CND),该算法在共同邻居的基础上考虑小度节点的优先性,对于规模过大的网络需要分块处理;然后,给共同邻居的度分配不同的权重,通过实验找出最优权重值。最后将新算法对比了AA、RA、CN、LHN、HDI算法的AUC,实验结果表明,共同邻居的小度节点有利链路预测算法比现有的局部信息链路预测算法的预测准确性有一定的提高。

基于节点相似度的加权网络社团结构划分算法

针对加权网络的社团结构划分问题,提出了一种基于节点相似度的划分算法.构造一种新型加权网络的节点相似度矩阵,基于该相似度矩阵,随机选取一个节点作为初始社团,搜索与该节点相似度值最大的节点合并成一个新的社团.反复迭代,形成划分.该算法具有较低的计算复杂度.用经典复杂网络的社团划分算例验证了该算法的有效性.

社交属性网下基于链路预测及节点度的推荐算法

社交网络的出现使现代人们沟通交流的方式发生了颠覆性的变化。不断有研究者从社会角度和技术角度对社交网络进行研究。链路推荐是一个非常重要的任务,一方面增强网络内部联系,另一方面改善用户体验。目前,在考虑网络结构信息和节点属性信息的社交属性拓展网络模型中链路预测算法中还没有很好的综合利用两种信息对链路生成的影响。本文在基于局部信息的链路预测算法下考虑不同类型共同邻居节点对链路生成的影响,并将其应用于社交属性拓展网络模型中。在改进的算法中,用户共同邻居节点和属性共同邻居节点对链接相关性的影响被给予不同的处理。在Google+社交数据集的实验表明,在社交属性拓展网络模型下,本文改进算法优于不考虑共同邻居节点影响的算法。在总结实验结果中用户共同邻居节点和属性共同邻居节点对链接生成的不同影响后,对不同类型节点的处理方法提出指导性建议。