基于有偏向的重启随机游走链路预测算法

链路预测中,基于随机游走过程的相似性指标往往设定游走粒子转移到相邻节点的概率是相等的,忽略了节点度值对粒子转移概率的影响。针对此问题,提出一种有偏向的重启随机游走链路预测算法。首先借鉴有偏向随机游走过程,重新定义游走粒子的转移概率,然后将其运用到有重启的随机游走中,探究粒子在游走过程中节点度值对其转移的作用,最后在粒子有偏向转移的基础上,将提出的指标同6个经典的相似性指标进行对比。通过对6个真实数据集进行链路预测,结果表明:与无偏向性转移相比,有偏向性转移的预测算法具有更高的预测精度,且高于其他相似性指标的预测值。

基于知识图谱和重启随机游走的跨平台用户推荐方法

针对单一社交网络平台中推荐相似用户结果单一,对用户兴趣和行为信息了解不够全面的问题,提出了基于知识图谱和重启随机游走的跨平台用户推荐方法(URCP-KR)。首先,在分割、匹配出的目标平台图谱和辅助平台图谱的相似子图中,利用改进的多层循环神经网络(RNN)预测出候选用户实体,再综合利用拓扑结构特征相似度和用户画像相似度筛选出相似用户;然后,将辅助平台图谱中的相似用户的关系信息补全到目标平台图谱;最后,计算目标平台图谱中的用户游走到社区内每个用户的概率,从而得到用户之间的兴趣相似度来实现用户推荐。实验结果表明,与协同过滤(CF)算法、基于跨平台的在线社交网络用户推荐算法(URCP)和基于多开发者社区的用户推荐算法(UR-MC)相比,URCP-KP在推荐精确率及推荐多样性等方面均有所提高,推荐精确率最高可达95.31%,推荐覆盖率最高可达88.42%。

一种基于MH改进的重启随机游走链路预测算法

基本随机游走相似性指标由于其转移概率仅由当前节点的度决定,影响链路预测效果.鉴于此,在MH(Metropolis-Hasting)算法的基础上,充分利用邻居节点的度信息,并采用将当前节点的自环率按邻居节点的度值加权分配给邻居节点的方法重构转移概率矩阵,再融合重启随机游走(Random Walk with Restart,RWR)相似性指标,提出一种改进MH的链路预测算法.首先,根据当前节点与邻居节点的度信息重新定义节点间的转移概率;然后,将新的转移概率重构成概率矩阵;最后,融合RWR相似性指标进行链路预测实验.结果表明,新算法相较于RWR、CN(Common Neighbors)等7种基准算法在AUC指标上均有提升,在排序分指标上也有所改善;AUC指标上最高可提升3.98%,排序分指标上最高下降1.92%,提升了链路预测的准确性.

基于重启随机游走的图自编码器

针对现有的图自编码器无法捕捉图中节点之间的上下文信息的问题,提出基于重启随机游走的图自编码器。首先,构造两层图卷积网络编码图的拓扑结构和特征,同时进行重启随机游走捕捉节点之间的上下文信息;其次,为了聚合重启随机游走和图卷积网络获得的表示,设计自适应学习策略,根据两种表示的重要性自适应地分配权重。为了证明该方法的有效性,将图最终的表示应用于节点聚类和链路预测任务。实验结果表明,与基线方法相比,提出的方法实现了更先进的性能。

基于最低度偏置重启随机游走的链路预测方法

链路预测是数据挖掘主题中的一个重要问题。基于随机游走的相似性方法一般设定游走粒子转移到相邻节点的概率是相等的,忽略了节点度值对转移概率的影响。针对此问题,提出一种基于lowest-degree偏置重启随机游走的链路预测方法。首先引入最低度偏置函数,对游走粒子的转移概率进行重新定义,然后将最低度偏置随机游走策略运用到重启随机游走中,探究粒子在游走过程中最低度偏向策略对节点相似度的影响。在九个真实网络数据集上进行链路预测,结果表明,所提方法具有良好的预测精度,且挖掘了更多网络拓扑结构信息,证明该算法在节点相似性的评估上具有一定的优势。

基于重启随机游走算法的生物信息学关联预测模型

本文提出了基于重启随机游走算法的预测模型(RWRCMF)经实验证明可以高效地预测人类miRNA与自身疾病之间的潜在关联。首先,在数据预处理阶段,本文针对疾病的语义相似性和miRNA的功能相似性运用重启随机游走算法得到二者的拓扑网络相似性。其次,利用加权K最近邻(WKNKN)算法降低了已知miRNA-疾病关联矩阵的稀疏性,再通过高斯核函数计算得出miRNA和疾病各自的高斯核相似性。最终通过协同矩阵分解完成目标函数的构造得到miRNA-疾病之间的关联预测得分。最终模型经过机器学习中的留一交叉验证和五折交叉验证后得到的AUC值分别为0.9506和0.9468,并通过对比实验证明了该模型相较于以往的关联预测模型有着较高的预测性能。

融合卷积神经网络和重启随机游走的实体链接方法

提出了一种融合卷积神经网络和重启随机游走的实体链接方法.该方法首先对文本中的指称进行识别,然后生成指称的候选实体集,随后使用融合卷积神经网络和重启随机游走的实体链接方法对候选实体进行选择,最后对在知识库中无对应实体的指称进行聚类.该方法在TAC-KBP2016的实体识别与链接评测数据集上的FCEAFm值为0.652,2016年评测第1名的FCEAFm为0.643,实验结果表明,使用融合卷积神经网络和重启随机游走的实体链接方法能够有效地进行实体链接.

基于二元网络异步重启随机游走算法预测肺癌风险致病基因

肺癌致病基因的发现及预测有助于认识肺癌的发生机理、诊断与防治,是人类基因组研究的重要目标。应用现有二元网络重启随机游走算法预测致病基因时,一般先在疾病表型网络、蛋白质作用网络及疾病-蛋白质二分图网络内随机游走一步,然后进行网络间跳转,这种策略不仅搜索效率较低,还可能遗漏蛋白质(或疾病)网络中的局部拓扑信息。鉴于此,作者提出一种二元网络异步重启游走(asynchronously random walk with restart,ARWRH)算法,构建疾病表型-蛋白质异构网络,深层次挖掘潜在肺癌风险致病基因。ARWRH算法首先在疾病表型网络、蛋白质作用网络及疾病表型-蛋白质二分图网络内随机游走不同步数,然后进行网络间跳转,迭代形成稳态概率向量,从而获得候选致病基因。仿真实验表明,ARWRH算法可有效预测肺癌潜在风险致病基因,多数预测结果获得了文献证据支持。

基于重启型随机游走模型的图上关键字搜索

摘要:基于重启型随机游走模型和个人化PageRank算法,提出一种新的图上关键字搜索算法。该算法将向量空间模型和随机游走模型进行有效的结合,使查询搜索得到的结果可以匹配查询关键字,通过充分挖掘利用图中隐含的结构信息,更好地提供搜索结果。实验结果证明了该算法的有效性。

基于网络表示学习与随机游走的链路预测算法

现有的基于随机游走链路预测指标在无权网络上的转移过程存在较强随机性,没有考虑在网络结构上不同邻居节点间的相似性对转移概率的作用。针对此问题,提出一种基于网络表示学习与随机游走的链路预测算法。首先,通过基于深度学习的网络表示学习算法——Deep Walk学习网络节点的潜在结构特征,将网络中的各节点表征到低维向量空间;然后,在重启随机游走(RWR)和局部随机游走(LRW)算法的随机游走过程中融合各邻居节点在向量空间上的相似性,重新定义出邻居节点间的转移概率;最后,在5个真实数据集上进行大量实验验证。实验结果表明:相比8种具有代表性的基于网络结构的链路预测基准算法,所提算法链路预测结果的AUC值均有提升,最高达3.34%。

基于用户相似度的随机游走社交网络事件推荐算法

针对基于社交网络的事件推荐覆盖性和准确性不够高的问题,提出了基于用户相似度Si-user Walker算法.该算法利用基于事件的社交网络特征,将线上用户群组数据抽象为图,以重启随机游走算法为基础,改变了传统的完全基于图的拓扑结构进行随机游走的策略.根据地理位置划分事件类型,提出了新的用户相似度计算方法,然后根据用户相似度矩阵作为随机游走的转移概率,既保留了图的传递性,又保证了图节点游走的真实性.与其他推荐算法在真实的数据集上实验表明,该算法在均方根误差、准确率及覆盖率上均得到提升.

融合相似度图和随机游走模型的多标签短文本分类算法

提出一种融合相似度图和随机游走模型的多标签短文本分类算法。首先,以样本数据和标签为节点创建相似度图,借助外部知识库计算样本与标签之间的权重,得到预测样本与标签集合之间的匹配度。然后,将多标签数据映射成多标签依赖图,在图上进行重启随机游走,并将已获得的匹配度作为初始预测值,计算每个节点的概率分布,直到概率分布趋于稳定时,节点的概率分布即为标签的概率分布,进而确定预测文本的标签集。实验结果表明,本文提出的算法有较好的多标签文本分类性能,与同类算法相比较,分类性能显著提升。

结合重要节点信任传播的社会化推荐算法

融合社交信息的推荐算法有效缓解了推荐算法中的数据稀疏性问题和冷启动问题,近年来受到极大的关注。但社交信息依然存在数据稀疏性问题,而且社交网络提供的二值数据无法衡量不同用户间的信任程度。针对这些问题,利用重启随机游走算法获取社交网络中的重要节点。提出重要节点信任传播算法建立重要节点和其他用户节点之间的信任关系,同时利用节点的结构信息进一步量化用户间的信任权重,以得到更精确的推荐结果。在三个公开数据集上的实验表明,结合重要节点信任传播的社会化推荐算法(INTP-Rec)丰富了社交信息,有效地提高了推荐算法的准确率和召回率。

基于网络药理学研究一贯煎治疗肝纤维化的有效成分及作用机制

背景中药复方具有多成分综合调节的特点,在肝纤维化防治中显示出独特的优势.一贯煎始载于魏之琇所著《续名医类案》,是滋阴疏肝的著名方剂,能够改善肝纤维化症状,研究其抗肝纤维化机制有助于药物开发和推广.目的通过网络药理学探究一贯煎治疗肝纤维化的机制并实验验证.方法利用文献和TCMSP数据库收集一贯煎成分及靶点,GeneCard、OMIM数据库收集肝纤维化疾病靶点.通过STRING数据库构建一贯煎-肝纤维化蛋白互作网络(protein-protein interaction,PPI)子网络,应用重启随机游走算法获得关键基因,通过DAVID数据库进行基因本体(gene ontology,GO)富集分析及京都基因和基因组百科全书(Kyoto encyclopedia of genes and genomes,KEGG)富集分析.动物实验验证,18只SD大鼠随机分为正常组、模型组、一贯煎组.模型组、一贯煎组大鼠采用腹腔注射50%四氯化碳(carbon tetrachloride,CCl_(4))橄榄油溶液造模6周,正常组注射等量橄榄油.造模结束后一贯煎组每天灌胃一贯煎溶液(6.67 g/kg)共4 wk,其他组灌胃等量蒸馏水,取血和肝脏.全自动生化仪检测血清丙氨酸转氨酶(alanine aminotransferase,ALT)和天冬氨酸转氨酶(aspartate aminotransferase,AST).HE、Masoon染色观察肝脏病理学变化.Western blot法和qRT-PCR法检测肝脏关键蛋白表达水平和mRNA转录水平.结果筛选得到一贯煎成分52个,潜在作用靶点186个,肝纤维化疾病靶点1080个,得到一贯煎治疗肝纤维化的关键基因,其中亲和度前10的基因为STAT6、SRC、MAPK3、STX1A、EP300、STAT3、PLG、CTNNB1、CDKN1B、CANX,亲和度前50的基因KEGG富集得到PI3K-Akt信号通路、FoxO信号通路等134条.动物实验结果发现,一贯煎能够改善CCL4肝纤维化大鼠肝功能和减轻纤维化,降低α-肌动蛋白表达,促进信号转导和转录激活因子6(signal transducer and activator of transcription 6,STAT6)磷酸化,提高过氧化物酶体增殖物激活受体-γ(peroxisome proliferator activated receptor-γ,PPAR-γ)、白细胞分化抗原163(cluster of differentiation 163,CD163)蛋白表达和精氨酸酶1、白细胞分化抗原206、CD163mRNA转录水平,降低白细胞介素6的mRNA转录水平.结论一贯煎治疗肝纤维化作用涉及多个成分、多条信号通路,其中包括STAT6/PPAR-γ通路.

超图环境下链路预测问题的探究

超图作为图的扩展,可以表示多种实体间的关系,使得其表达能力大大强于图,该优势吸引人们的关注并日益成为研究热点.链路预测作为图数据挖掘中的常见任务,也在超图上扩展为超链路预测.超链路预测通过已知超边或节点的属性来估计新超边出现的可能性,但是由于超边内节点数量的任意性,其可能的超边由O(n^(2))暴增至O(2^(n)),这大大增加了算法的复杂度.本文使用下采样方法以减少候选超边集的大小,将图上的带重启的随机游走算法扩展到超图上.还将图上的其他指标,如CN、CE、Jaccard等,扩展到超图进行比较.结果表明,带重启的随机游走指标在精确率和召回率上要明显优于其他指标,并且观察到演化良好的超图其超边内部的联系强度随节点数的增加而增加,由此可知超链路预测的主要难点在于对小尺寸超边的预测.

结合用户关系网和标签共现网的微博用户标签推荐研究

标签是Web2．0网站的主要组成部分。在新浪微博上，用户标签可用于用户检索、用户推荐，可帮助更好地理解用户行为和用户兴趣，但目前大多数微博用户缺少标签，为此本文提出结合用户关系网和标签共现网进行微博用户标签的预测。该方法首先在用户关系网上使用带重启的随机游走模型计算用户相似度，然后根据标签对用户的重要程度获得各个用户的候选标签集。在用户候选标签集得到后，结合标签共现网使用基于标签链的方法抽取候选标签推荐给用户。经在新浪微博真实数据集上的测试，表明本文提出的标签预测方法在准确率上有一定提高。

基于扩展起始节点和加权融合策略预测肺癌风险致病基因

肺癌风险致病基因预测有助于了解疾病发病机制、提高临床治疗效果.目前,以重启游走为框架的风险致病基因预测算法,普遍存在起始节点少、节点转移概率相同、信息源单一的问题.为此,本文提出一种基于扩展起始节点和加权融合策略的风险致病基因预测算法(命名为AFMFSC),并在肺癌中验证算法有效性.首先,基于增广模糊测量思想,计算疾病表型近似基因间的增广功能相似得分,从中选出重要基因与致病基因作为扩展起始节点;其次,采用节点拓扑相似度转移矩阵及基因表达差异相关性转移矩阵,分别在蛋白质网络中重启随机游走,并将两种结果加权融合排序;最后,通过富集分析排名靠前基因,得到有显著意义的风险致病基因.AFMFSC算法预测的73个肺癌风险致病基因,均与肺癌发生、发展有密切联系,生物学意义显著.与其他排序算法相比,AFMFSC算法的Top 1%、Top 5%和AUC值比较大,平均排名和受拓扑特性偏差影响程度小;融合策略排名性能优于单一转移矩阵或普通邻接矩阵游走排名.AFMFSC算法不仅能准确有效地预测肺癌风险致病基因,而且可推广预测其他疾病风险致病基因,为探索癌症致病机理提供新视角及依据.

基于网络方法确定乳腺癌转移相关基因

乳腺癌是女性最常见的恶性肿瘤之一,其发展是一个长期的、多阶段、多基因改变积累的过程。临床及实验研究发现,在乳腺癌发展与转移的过程中,许多原癌基因、抑癌基因及相关蛋白质发生改变。本文提出了一种结合随机游走重启算法的综合模型,并将其应用于乳腺癌骨转移关键候选基因的鉴定中,在蛋白质相互作用网络上识别乳腺癌转移候选基因。首先利用RWR算法和置换检验规则对基因进行预选,得到候选基因集。然后构建一个候选基因间的关键子网并计算关键子网中节点的介数中心性。最后,利用交互得分规则对基因筛选,选择介数得分排名前三十的基因作为乳腺癌骨转移关键基因。相互作用分析、富集分析及文献挖掘的结果表明26个潜在的关键基因都参与了乳腺癌骨转移的起始或进程,验证了该综合模型的有效性。

基于ESU图的活动社交网络用户参加活动推荐

活动社交网络(EBSNs)为用户提供了方便的组织、参加和分享社交活动的平台。该文面向EBSNs活动推荐问题,提出了包含活动(Event)、主办方(Sponsor)和用户(User)的ESU图模型,深入揭示了EBSNs的实体及其社交关系。因为用户参加活动受多个因素影响,我们提出了基于ESU图的活动推荐多因素决策模型,包括社交影响力、活动内容、活动地点及活动时间。根据ESU图特点,提出了基于双向重启随机游走算法BD-RWR的实体重要度计算方法。选取真实的EBSNs平台-豆瓣同城验证所提方法的有效性。实验结果表明,该文提出的ESU图模型及融合了多因素的活动推荐模型,与已有最新方法相比,有效地提升了用户参加活动的推荐效果。

基于二次传播的开源软件缺陷定位方法

为了提高开源软件缺陷定位的准确度,提出一种基于二次传播的开源软件缺陷定位方法TPA。将重启随机游走算法与标签传播算法相结合,在基于信息检索方法的基础上,从开源软件中各个模块的调用关系、模块风险度和历史缺陷报告三个方面分析缺陷存在的具体位置,将缺陷定位分为风险度传播和标签传播两个部分。通过软件模块之间的相关度和调用关系,结合开源软件的历史修改信息评估模块风险度;通过已修改的缺陷报告构造缺陷标签,并采用标签传播定位软件缺陷。在Eclipse 3.1缺陷报告数据集中,top-N rank和MRR指标均高于同类缺陷定位方法。实验表明,TPA方法具有较高的准确度。