Link prediction and recommendation in signed social networks

• Main Author: Li, Xiaoming
• Other Authors: Zhang, Jie
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/141719
• Institution: Nanyang Technological University

Link prediction is a fundamental research issue in social networks, which aims to infer the formation of a possible link in the near future. This topic is well studied in the last few years as its significant contributions to improve and enhance online experiences, in the form of further facilitating applications such as recommenders for products or friends, trust-aware business applications and viral marketing campaigns. With the rise of signed networks, the link prediction problem becomes more complex and challenging as it introduces negative relations among users. Instead of predicting future relation for a pair of users, however, the current research focuses on distinguishing whether a certain link is positive or negative, on the premise of the link existence. The situation that two users do not have relation (i.e., no-relation) is also not considered, which actually is the most common case in reality. To fulfill this gap, we first redefine the link prediction problem in signed social networks by also considering "no-relation" as future status of a node pair. To understand the underlying mechanism of link formation in signed networks, we propose a feature framework on the basis of a thorough exploration of potential features for the newly identified problem. We find that features derived from social theories can well distinguish these three social statuses, which are positive, negative and no-relation. Grounded on the feature framework, we adopt a multiclass classification model to leverage all the features, and experiments show that our method outperforms the state-of-the-art methods. Despite the success of the feature-based method, we find that online users are different regarding their activeness and popularity, which actually influence the link formation probability. Besides, "no-relation" status is diverse in social networks. In signed networks, no-relation is the social status apart from positive links and negative links. It is conceivable that most pairs of users with no-relation have limited common connections, however, in reality, many user pairs keep no-relation status even though they have many common connections. It is easy to mispredict no-relation having many common neighbors as a linked status. Therefore, we take a deep investigation on the diversity of "no-relation" status and we propose a novel Framework of Integrating both Latent and Explicit features (FILE), to better deal with the no-relation status and improve the overall link prediction performance in signed networks. In particular, we design two latent features to represent users' intrinsic personality, and two explicit features by extending social theories to represent external social influence. We learn these features for each user via matrix factorization with a specially designed ranking-oriented loss function. The effectiveness of our approach is verified by the experiments. Further, we study the user ranking problem in signed networks, which tries to optimize the link recommendation performance from a personalized perspective. For a certain user, we aim to rank his potential "friends" on the top whereas rank "enemies" on the bottom. Current approaches focus on global ranking thus cannot provide effective personalized ranking results. Besides, they have a relatively unrealistic assumption that each user treats her neighbors' social strengths indifferently. In this work, we propose a supervised method based on random walk to learn social strengths between each user and her neighbors, in which the random walk more likely visits "potential friends" and less likely visits "potential enemies". We learn the personalized social strengths by optimizing on a particularly designed loss function oriented on ranking. Experimental results demonstrate the superiority of our approach over the state-of-the-art approaches. To sum up, we have proposed a series of approaches for link prediction in the signed network scenario. These approaches are constructed in a more realistic setting and can be used in real-world applications.