Link Inference in Large Scale Evolutionable Knowledge Network

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.