  Many online social networks allow directed edges: Alice can unilaterally add
an "edge" to Bob, typically indicating interest in Bob or Bob's content,
without Bob's permission or reciprocation. In directed social networks we
observe the rise of two distinctive classes of users: celebrities who accrue
unreciprocated incoming links, and follow spammers, who generate unreciprocated
outgoing links. Identifying users in these two classes is important for abuse
detection, user and content ranking, privacy choices, and other social network
features.
  In this paper we develop SCRank, an iterative algorithm to identify such
users. We analyze SCRank both theoretically and experimentally. The
spammer-celebrity definition is not amenable to analysis using standard power
iteration, so we develop a novel potential function argument to show
convergence to an approximate equilibrium point for a class of algorithms
including SCRank. We then use experimental evaluation on a real global-scale
social network and on synthetically generated graphs to observe that the
algorithm converges quickly and consistently. Using synthetic data with
built-in ground truth, we also experimentally show that the algorithm provides
a good approximation to planted celebrities and spammers.
