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

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

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

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

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

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

一种基于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,并通过对比实验证明了该模型相较于以往的关联预测模型有着较高的预测性能。

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

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

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

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

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

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

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

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

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

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

基于RWR的自然图像抠图

提出了一种基于图论的自然图像抠图方法。该算法首先在图像上建立图的模型,并用不同颜色标记目标种子点和背景种子点;接着采用有重启概率的随机游走方法计算像素点之间的相似性,进而提出一个线性概率模型;最后求解模型并分别估计前景和背景物体。与目前的抠图方法相比,该算法具有以下特点:将RWR方法结合图论用于自然图像抠图中;减小了RWR算法在图像分割中迭代求逆的高复杂度,大大提高了抠图速度;解决了"弱"边界的问题。

基于均衡化概率模型的特征匹配及其应用

通过对匹配模型中邻接矩阵的均衡化分析,在概率框架下提出一种新的特征匹配算法。采用重启动的随机游走方法建立并求解概率模型,并对匹配邻接矩阵进行了均衡化分析,提出了一种有效的双向均衡方法。方法不仅考虑了两个待匹配特征点的全部几何关联以及各项关联之间的权重值,而且考虑了关联权重的均衡性,从而可加强匹配的区分度,提高匹配的准确性。经实验证明,所提出的算法对几何畸变干扰和异常值都具有很好的鲁棒性,且适用于多种点匹配场合,在目标定位和目标识别中具有较强的适应性,有较好的实用价值。

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

融合社交信息的推荐算法有效缓解了推荐算法中的数据稀疏性问题和冷启动问题,近年来受到极大的关注。但社交信息依然存在数据稀疏性问题,而且社交网络提供的二值数据无法衡量不同用户间的信任程度。针对这些问题,利用重启随机游走算法获取社交网络中的重要节点。提出重要节点信任传播算法建立重要节点和其他用户节点之间的信任关系,同时利用节点的结构信息进一步量化用户间的信任权重,以得到更精确的推荐结果。在三个公开数据集上的实验表明,结合重要节点信任传播的社会化推荐算法(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等,扩展到超图进行比较.结果表明,带重启的随机游走指标在精确率和召回率上要明显优于其他指标,并且观察到演化良好的超图其超边内部的联系强度随节点数的增加而增加,由此可知超链路预测的主要难点在于对小尺寸超边的预测.

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

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

基于蛋白质相互作用网络的肺癌骨转移基因识别方法

肿瘤转移通常发生在癌症晚期,是一个复杂且致命的过程,发现与肿瘤转移相关的基因对肿瘤的治疗和预后有着至关重要的作用。通过计算方法发现肿瘤转移基因,相对于昂贵且耗时的生物学方更加高效。基于蛋白质-蛋白质相互作用网络(PPIN),论文提出了一种结合随机游动重启(RWR)算法的模型来识别肺癌骨转移相关基因。此外,通过置换检验规则、交互得分规则和富集分析三种方法对基因进一步筛选,最终获得了12个与肺癌骨转移有关的关键基因。文献挖掘的结果证明大部分基因直接或间接参与了肺癌骨转移过程,验证了该计算方法的有效性。这一项工作有望为肿瘤转移的临床试验提供靶标基因。