ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (2): 492-502.doi: 10.7544/issn1000-1239.2016.20148283

• 软件技术 • 上一篇    

大规模演化知识网络中的关联推理

赵泽亚1,2,3,贾岩涛1,王元卓1,靳小龙1,程学旗1   

  1. 1(中国科学院网络数据科学与技术重点实验室(中国科学院计算技术研究所) 北京 100190); 2(解放军信息工程大学 郑州 450000); 3(中国天绘卫星中心 北京 102012) (53414264@qq.com)
  • 出版日期: 2016-02-01
  • 基金资助: 
    国家“九七三”重点基础研究发展计划基金项目(2014CB340405,2013CB329602);国家自然科学基金项目(61173008,61232010,61303244,61402442);北京市科技新星计划项目(Z121101002512063);国家科技支撑计划项目( 2012BAH39B04);北京市自然科学基金青年基金项目(4154086)

Link Inference in Large Scale Evolutionable Knowledge Network

Zhao Zeya1,2,3, Jia Yantao1, Wang Yuanzhuo1, Jin Xiaolong1, Cheng Xueqi1   

  1. 1(Key Laboratory of Network Data Science & Technology (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190); 2(The PLA Information Engineering University, Zhengzhou 450000); 3(TH-Satelite Center of China, Beijing 102012)
  • Online: 2016-02-01

摘要: 网络大数据时代的到来使得知识网络中时空信息越来越丰富.现有的知识网络描述模型对知识的时空信息刻画不足.研究证明,利用网络中知识的时空信息以及相关性,能够提高网络中知识间的关联推理的准确率.针对以上问题,首先提出了一种包含时空信息的演化知识网络表示模型,然后研究在该网络模型上的关联推理问题,提出了一种基于背包问题的知识间关联推理方法.在多个数据集上的实验证明了所提出的关联推理方法的有效性以及对大规模知识网络的适应性.

关键词: 关联推理, 演化知识网络, 背包问题, 链接延展模式, 知识库

Abstract: In the era of network big data, the spatiotemporal information of knowledge is richly stored in knowledge networks, such as the building time of links, the lifetime of vertices, etc. Traditional knowledge network representation models are mostly blind to either the spatial or the temporal information of vertices and links in the network. It has been verified in the literature that considering the spatial or the temporal information of vertices and links can promote the performance of link inference in knowledge networks. In this paper, we propose an evolutionable knowledge network model, i.e., a heterogeneous knowledge network, in which vertices and edges are anchored in both time and space dimensions. Then based on the model, we further study the link inference problem on evolutionable knowledge networks. Specifically, we firstly define the link extendable patterns to characterize the link formation process, and then propose a knapsack constrained link inference method to turn the link inference problem into a combinatorial optimization problem with the knapsack-like constrains. The dynamic programming technique is used to solve the optimization problem in pseudo-polynomial time complexity. Experiments on real data sets suggest the better effectiveness and scalability of our proposed method over large-scale networks than the state-of-the-art methods.

Key words: link inference, evolutionable knowledge network, knapsack problem, link extendable (LE) pattern, knowledge base

中图分类号: