Knowledge Graph (KG) is identified as a major area in artificial intelligence, which is used for many real-world applications. The task of knowledge graph reasoning has been widely used and proven to be effective, which aims to find these reasonable paths for various relations to solve the issue of incompleteness in KGs. However, many previous works on KG reasoning, such as path-based or rein- forcement learning-based methods, are too reliant on the pre-training, where the paths from the head entity and the target entity must be given to pre-train the model, which would easily lead the model to overfit on the given paths seen in the pre-training. To address this issue, we propose a novel reasoning model named MemoryPath with a deep reinforcement learning framework, which incorporates Long Short Term Memory(LSTM) and graph attention mechanism to form the memory component. The well-designed memory component can get rid of the pre-training so that the model doesn’t depend on the given target entity for training. A tailored mechanism of reinforcement learning is presented in this proposed deep reinforcement framework to optimize the training procedure, where two metrics, Mean Selection Rate (MSR) and Mean Alternative Rate (MAR), are defined to quantitatively mea- sure the complexities of the query relations. Meanwhile, three different training mechanisms, Action Dropout, Reward Shaping and Force Forward, are proposed to optimize the training process of the proposed MemoryPath. The proposed MemoryPath is validated on two datasets from FB15K-237 and NELL-995 on different tasks including fact prediction, link prediction and success rate in finding paths. The experimental results demonstrate that the tailored mechanism of reinforcement learning make the MemoryPath achieves state-of-the-art performance comparing with the other models. Also, the qualitative analysis indicates that the MemoryPath can store the learning process and automati- cally find the promising paths for a reasoning task during the training, and shows the effectiveness of the memory component.
Keywords: Knowledge Graph Reasoning | Memory Component | Deep Reinforcement Learning | Link Prediction | Attentional Path | Force Forward

Link prediction has been becoming an important research topic due to the rapid growth of social networks. Community-based link prediction methods are proposed to incorporate community information in order to achieve accurate prediction. However, the performance of such methods is sensitive to the selection of community detection algorithms, and they also fail to capture the correlation between link formulation and community evolution. In this paper we introduce a balanced Modularity-Maximization Link Prediction (MMLP) model to address this issue. The idea of MMLP is to integrate the formulation of two types of links into a partitioned network generative model. We proposed a probabilistic algo rithm to emphasize the role of innerLinks, which correspondingly maximizes the network modularity. Then, a trade-off technique is designed to maintain the network in a stable state of equilibrium. We also present an effective feature aggregation method by exploring two variations of network features. Our proposed method can overcome the limit of sev eral community-based methods and the extensive experimental results on both synthetic and real-world benchmark data demonstrate its effectiveness and robustness.
Keywords: Link prediction | Social network | Community detection | Modularity

Link prediction has become an important task, especially with the rise of large-scale, complex and dynamic networks. The emerging research area of network dynamics and evolution is directly related to predicting new interactions between objects, a possibility in the near future. Recent studies show that the precision of link prediction can be improved to a great extent by including community information in the prediction methods. As traditional community-based link prediction algorithms can run only on stand alone computers, they are not well suited for most of the large networks. Graph parallelization can be one solution to such problems. Bulk Synchronous Parallel (BSP) programming model is a recently emerged framework for parallelizing graph algorithms. In this paper, we propose a hybrid similarity measure for link prediction in real world networks. We also propose a scalable method for community structure-based link prediction on large networks. This method uses a parallel label propagation algorithm for community detection and a parallel community information-based Adamic–Adar measure for link prediction. We have developed these algorithms using Bulk Synchronous Parallel programming model and tested them with large networks of various domains.
Keywords: Parallel computing | Community structure | Link prediction | Bulk synchronous parallel | Social networks

Location-based social discovery networks (LBSD) is an emerging category of location-based social net works (LBSN) that are specifically designed to enable users to discover and communicate with nearby people. In this paper, we present the first measurement study of the characteristics and evolution of location-based communities which are based on a social discovery network and geographic proximity. We measure and analyse more than 176K location-based communities with over 1.4 million distinct members of a popular social discovery network and more than 46 million locations. We characterise the evolution of the communities and study the user behaviour in LBSD by analysing the mobility features of users belonging to communities in comparison to non-community members. Using observed spatio-temporal similarity features, we build and evaluate a classifier to predict location-based community membership solely based on user mobility information.
Keywords: Human mobility | Link prediction | Social discovery networks