A Visibility-based Model for Link Prediction in Social Media

A core task of social network analysis is to predict the for-mation of new social links. In the context of social media, link prediction serves as the foundation for forecasting the evolution of the follower graph and predicting interactions and the flow of information between users. Previous link prediction methods have generally represented the social network as a graph and leveraged topological and seman-tic measures of similarity between two nodes to estimate the probability of a new link between them. In this work, we suggest another link creation mechanism for social me-dia that is based on the ease of discovering the new node. Specifically, a user v creates a link to another user u af-ter seeing u’s name on his or her screen; in other words, visibility of a user (name) is a necessary condition for new link formation. We propose a model for link prediction, which estimates the probability a user will see another user’s name, and use this model to predict new links. We estimate a set of parameters in the proposed model using Maximum-Likelihood and Minorize-Maximize methods. Empirical re-sults show that the proposed model can more accurately predict both follow and co-mention links than alternative state-of-the-art methods. Our work suggests that the effort required to discover a new social contact is negatively cor-related with link formation, and the easier it is to discover a user, the higher the likelihood a link will be created.