Algorithms and applications of Link Mining: Making Sense of Network Data

点击翻译按钮获取中文摘要

Link mining refers to a set of data mining algorithms and techniques by which we can learn non-trivial patterns from a network or linked data. Links can be represented by various dimensions. Links can be directional or bi-directional, signed or unsigned, weighted or unweighted. The link mining task is to use one or more link dimensions (link existence, direction, sign, weight, class and content) to predict another missing dimension. Another well-studied link mining task is related to the hyper-structure analysis of the networks such as community detection and clustering. Link mining includes several challenging tasks such as link prediction, sign and direction prediction, node ranking, and community detection. Other tasks include weak-tie analysis, detecting information brokers and node ranking. All the above-mentioned tasks are conducted using link dimensions using node characteristics and exchanging content. Among the link mining task, link prediction has drawn much attention. Link prediction is an algorithm that predicts the likelihood of new ties among existing or new nodes. Link prediction has many applications such as: analyzing network growth, expert identification in collaboration networks such as citation and co-authorship networks, finding perfect matches in online dating, and revealing missing links in social networks in which some of the links intentionally removed. Link prediction is implemented either in a cold start or warm start scenario. Cold start scenario refers to a problem in which we want to find the underlying network or social fabric (in the present time or future) among a set of non-connected nodes. On the other hand, a warm start is a problem of recommending links to new or existing users based on other available links (or network structure). Link mining has applications in social network analysis, epidemic analysis, recommender systems, sports analytics, and entity link extraction in natural language processing. The majority of natural and man-made networks have sparse architectures. The network sparsity increases the complexity of link mining algorithms especially when supervised learning techniques are employed. The other challenge in link mining tasks is the lack of training data. One alternative approach is to advance semi-supervised learning and distant supervision. The objectives of the proposed research are four-fold: 1) Introducing link mining and prediction tasks to new applications such as legal research, epidemiology and sports analytics. 2) Adopting language modelling techniques and powerful NLP and deep learning tools for learning about latent patterns in complex networks. 3) Developing a modern meta-learning algorithm to deal with training data complexities in link prediction tasks. 4) Leveraging line graphs to transform complex networks and to directly perform link embedding.