  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 haven't 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 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.
