Reciprocal versus parasocial relationships in online social networks

Many online social networks are fundamentally directed, i.e., they consist of both reciprocal edges (i.e., edges that have already been linked back) and parasocial edges (i.e., edges that have not been linked back). Thus, understanding the structures and evolutions of reciprocal edges and parasocial ones, exploring the factors that influence parasocial edges to become reciprocal ones, and predicting whether a parasocial edge will turn into a reciprocal one are basic research problems. However, there have been few systematic studies about such problems. In this paper, we bridge this gap using a novel large-scale Google+ dataset (available at http://www.cs.berkeley.edu/~stevgong/dataset.html/) crawled by ourselves as well as one publicly available social network dataset. First, we compare the structures and evolutions of reciprocal edges and those of parasocial edges. For instance, we find that reciprocal edges are more likely to connect users with similar degrees while parasocial edges are more likely to link ordinary users (e.g., users with low degrees) and popular users (e.g., celebrities). However, the impacts of reciprocal edges linking ordinary and popular users on the network structures increase slowly as the social networks evolve. Second, we observe that factors including user behaviors, node attributes, and edge attributes all have significant impacts on the formation of reciprocal edges. Third, in contrast to previous studies that treat reciprocal edge prediction as either a supervised or a semi-supervised learning problem, we identify that reciprocal edge prediction is better modeled as an outlier detection problem. Finally, we perform extensive evaluations with the two datasets, and we show that our proposal outperforms previous reciprocal edge prediction approaches.