基于中医网络的中心性算法研究

中医概念之间的关系极为复杂,采用传统的基于简单数据集的数据挖掘方法显得力不从心。考虑到中医数据的特点,提出了一种基于图结构的挖掘方法,将中医对象之间的复杂关系和潜在的信息提取出来。首先,通过自然语言处理从医案中抽取出的中医概念与中医本体知识库匹配得到中医的知识网络。然后将该中医网络抽象成数学表达方式——图,利用图论的算法来处理。最后,采用中心性算法来分析中医网络,找出在中医诊断网络中具有重要作用的症状。

HHa中心性算法:一种基于h指数和Ha指数的复杂网络节点排序算法

[目的/意义]针对复杂网络中的重要节点的识别,设计一种节点中心性算法,在传染病防控、舆情监控、产品营销、人才发现等方面发挥作用。[方法/过程]同时考虑节点的高影响力邻居的数量及其总体影响,提出HHa节点中心性算法,在真实网络和人工网络上,使用SIR传染病模型模拟信息传播过程,采用单调函数M和肯德尔相关系数作为评价指标验证HHa中心性算法的有效性、准确性以及稳定性。[结果/结论]实验表明,与7种经典的中心性算法相比,HHa中心性算法得出的排序结果M值为0.999等,排名第2;肯德尔系数为0.845等,高于其他算法0.15左右,排名第1且表现稳定。采用HHa中心性算法识别网络中的重要节点具备可行性。

基于知识图谱的中文关键短语提取算法

针对传统的中文关键短语算法没有充分考虑到语义关系、涵盖信息量少和准确率低等问题,提出一种基于知识图谱来提取关键短语的算法。该算法运用知识图谱的语义网络结构来挖掘文本中两个词之间的潜在关系,通过赋予边权值具体量化潜在关系,构建集成近邻传播(Affinity Propagation,AP)聚类和图的中心性算法来提取关键短语的框架。实验表明,与多种传统关键短语提取算法相比,该算法在准确率、召回率和F1值上有较明显的提升。

道路交通网络中的关键节点识别方法研究

在现实世界中,大量复杂系统都可以通过抽象的节点和连边构成的网络来加以刻画。作为城市交通系统的重要组成部分,道路交通网络是一个典型的复杂系统,与人们的生活密切相关。道路交通网络中的关键节点识别问题是复杂网络领域研究中的一个经典难题。传统的度中心性算法和PageRank算法在复杂网络的关键节点的识别中具有较好的应用,考虑到道路交通网络中关键节点的特殊性和彼此关联性,在度中心性算法的基础上引入贪心算法的思想,提出了一个基于贪心策略的度中心性关键节点识别方法;同时,在PageRank算法的基础上引入贪心算法的思想,提出了一种基于贪心策略的PageRank关键节点识别方法,从而使道路交通网络中关键节点识别的结果更合理,在交通道路维护保养、规划设计,以及犯罪分子潜逃阻断等领域都有重要的应用价值。通过公开数据集与经典的关键节点识别方法做比较,验证了算法的有效性。

图计算中遍历类图框架的特性

利用Skylake架构处理器上的性能分析工具perf分析Ligra、Gemini和GraphBIG等3种图计算框架中的单源最短路径(Single Source Shortest Path,SSSP)及介数中心性(Betweenness Centrality,BC)算法的特性,评估了在3种框架下实现两种算法的性能指标,并使用皮尔逊相关系数方法分析了各指标与性能/能耗之间的关系。实验结果表明,当缓存每千条指令的平均未命中数较大且每一时钟周期内执行的指令数较小时,图计算的执行时间较长。若数据移动量较小,则图计算的执行时间和功耗均较小。随着系统处理任务的线程数增加,图数据边的执行时间明显减少,通过增加处理单元个数的方式可以提高硬件加速器的性能。当处理器内核数小于4时,应优先选择Gemini框架实现算法,而当内核数大于4时,选择图框架Ligra能够有效减少执行时间。数据移动量和功耗与性能/能耗表现出极强的相关性。将图数据全部加载到内存中计算能够有效减少数据移动的次数。在处理较稀疏的图数据时,选择Ligra框架实现算法计算量较小。

基于知识图谱和图算法的党史研究

人工智能赋能内容科技是近几年的一个重要研究方向。首先整理了自《新青年》创刊至1949年新中国成立期间的党史中的重大事件和人物,采用知识图谱的技术构建了党史事件-人物图谱,图谱中只包含事件、人物两类实体,同类实体之间不存在关系,只在人物和事件之间存在参与关系;其次通过党史事件-人物二部图投影技术,进一步得到了只有党史人物关系的单部图,采用了度中心性、接近中心性、中介中心性、特征向量中心性四种中心性算法,计算并分析了图谱网络中重要性较高的一些人物节点的中心性;最后,基于DeepWalk的图嵌入技术对人物节点进行了向量化表示,并基于PCA降维实现了节点向量的二维可视化展示。结果显示在党史中具有相似行为的人物,在图嵌入向量空间中的距离非常小。党史图谱的构建在党史教育中也可以起到非常好的作用,通过图谱可以把传统一维时间序列的党史信息转化为网络结构的信息,将党史事件和人物的关系用生动的知识图谱画面展示出来。

基于加权基因共表达网络分析及生物信息学分析鉴定肝细胞癌临床特征关键基因

目的:通过加权基因共表达网络分析鉴定肝细胞癌(hepatocellular carcinoma,HCC)临床特征密切相关模块基因,为临床早期诊断及治疗提供参考。方法:从GEO数据库下载GSE84598芯片数据,综合加权基因共表达网络分析提取与HCC临床特征密切相关的模块基因。通过最大集团中心性(maximal clique centrality,MCC)算法对蛋白相互作用网络分析,鉴定出枢纽基因;最后通过TCGA数据库验证枢纽基因的表达情况、Kaplan-Meier Plotter在线数据库评估枢纽基因与HCC患者的预后关系。结果:通过对比HCC组织样本与正常肝组织样本的基因表达数据,共获得6262个差异表达基因,其中上调2207个,下调4055个。运用加权基因共表达网络分析鉴定出关键模块的120个基因;通过与差异表达基因取交集,得到候选枢纽基因115个。富集分析结果显示,候选枢纽基因与细胞有丝分裂、p53信号通路等密切相关。进一步运用MCC算法对115个候选枢纽基因的蛋白相互作用网络进行分析,鉴定出5个枢纽基因,即NUF2、RRM2、UBE2C、CDC20和MAD2L1。通过TCGA数据库对枢纽基因的验证,结果发现,与正常肝组织相比,在HCC组织中5个枢纽基因均明显上调;而且生存分析显示枢纽基因的高表达与HCC患者的不良预后密切相关。结论:本研究通过结合多个数据库鉴定出了5个枢纽基因,为HCC的临床诊断及治疗提供方向。

INVERSE CENTER LOCATION PROBLEM ON A TREE

This paper discusses the inverse center location problem restricted on a tree with different costs and bound constraints. The authors first show that the problem can be formulated as a series of combinatorial linear programs, then an O（｜V｜^2 log ｜V｜） time algorithm to solve the problem is presented. For the equal cost case, the authors further give an O（｜V｜） time algorithm.