Link Inference in Dynamic Heterogeneous Information Network: A Knapsack-Based Approach
- 18 July 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Social Systems
- Vol. 4 (3) , 80-92
Abstract
Link inference, i.e., inferring links between vertices in a heterogeneous information network with heterogeneous vertices and edges, has been extensively studied in recent years. So far, many machine learning-based methods have been proposed for link inference, which can be classified into two categories, namely, supervised and unsupervised. Supervised methods perform well but highly rely on feature selection and training data. Although unsupervised methods are inferior to supervised ones, they work in a relatively simple way without considering the class distribution of the training data. In this paper, we investigate the link inference problem in heterogeneous information networks by proposing a knapsack-constrained inference method. Specifically, we integrate dynamic information into the heterogeneous information network and further formalize the link inference problem as a knapsack-like problem. We then solve it by the virtue of a 0-1 knapsack analogous optimization approach and investigate the time complexity of the proposed approach. Finally, experimental results show that the proposed unsupervised method can obtain high performance comparable to supervised method for some cases.Keywords
Funding Information
- National Key Research and Development Program of China (2016YFB1000902)
- National Grand Fundamental Research 973 Program of China (2012CB316303, 2014CB340401)
- National Natural Science Foundation of China (61402442, 61572469, 91646120, 61572473, 61303244, 61402124)
This publication has 31 references indexed in Scilit:
- Mining heterogeneous information networksACM SIGKDD Explorations Newsletter, 2013
- Triangle listing in massive networksACM Transactions on Knowledge Discovery From Data, 2012
- Mining Heterogeneous Information Networks: Principles and MethodologiesSynthesis Lectures on Data Mining and Knowledge Discovery, 2012
- REXProceedings of the VLDB Endowment, 2011
- The Time-Series Link Prediction Problem with Applications in Communication SurveillanceINFORMS Journal on Computing, 2009
- Learning to create data-integrating queriesProceedings of the VLDB Endowment, 2008
- The link‐prediction problem for social networksJournal of the American Society for Information Science and Technology, 2007
- Discovering informative connection subgraphs in multi-relational graphsACM SIGKDD Explorations Newsletter, 2005
- Friends and neighbors on the WebSocial Networks, 2003
- Quadratic knapsack problems1980