Introduction

Hierarchy on Twitter

Who are the power players on Twitter (or in a Twitter community)? A good indicator of power is the number of followers a user has. But an identification of the powerful users based solely on the number of followers would miss the users with few but powerful followers. We describe a measure of a user’s power which incorporates the power of the user’s followers.

Consider the directed graph with vertices the users in a Twitter community and an arrow from user \(A\) to user \(B\) if and only if \(A\) follows \(B\). In this graph, the powerful users will have many in neighbors (followers), and many of their out neighbors (friends) will be powerful themselves. On the other hand, the average user will have many out nieghbors but few in neighbors. Thus the Twitter graph may exhibit high hierarchy as defined below.

Let \(G = (V, E)\) be a directed graph. Write \(n = |V|\), \(m = |E|\). All of the following definitions are (directly or adapted) from [FHSN].

Definition

A ranking of \(G\) is a map \(V \to {\bf N}\) where \({\bf N}\) is the natural numbers, and the value of a vertex under the map is called the rank of the vertex. Denote the set of rankings of \(G\) by \(R(G)\).

Definition

The agony of a ranking \(r \in R(G)\) is

\[A(r) := \sum_{(u, v) \in E} \max \{ r(u) - r(v) + 1, 0\}.\]

Definition

The hierarchy of a ranking \(r \in R(G)\) is

\[h(r) := 1 - (1/m)A(r).\]

The agony of a ranking counts the arrows in the graph which don’t go up in rank (counted with one more than the difference in ranks). The naive ranking by the zero map has agony \(m\), so any ranking at least as good as the naive one has hierarchy between 0 and 1.

If a ranking of the graph of a Twitter community has high hierarchy, then the graph exhibits hierarchal structure and rank is a good indicator of power. In the next section, we describe an algorithm to find a ranking of a graph with high hierarchy. In the next chapter, we document an implementation of that algorithm.

[FHSN]

M. Gupte, P. Shankar, J. Li, S. Muthukrishnan, L. Iftode, Finding hierarchy in directed online social networks.

The descent algorithm

Let \(G = (V,E)\) be a directed graph and let \(r\) be a ranking of \(G\). Pick a vertex \(v \in V\). Will updating \(r\) by increasing or decreasing the rank of \(v\) by 1 decrease the agony of \(r\)? The change in agony if the rank of \(v\) is increased by 1 is

\[\begin{split}i(v) := \big|\{w \in V\ |\ v \to w \in E \ \& \ r(w) \leq r(v) + 1\}\big| - \big|\{w \in V\ |\ w \to v \in E \ \& \ r(w) \geq r(v)\}\big|\end{split}\]

while the change in agony if the rank of \(v\) is decreased by 1 is

\[\begin{split}d(v) := \big|\{w \in V\ |\ w \to v \in E\ \& \ r(w) \geq r(v) - 1\}\big| - \big|\{w \in V\ |\ v \to w \in E\ \& \ r(w) \leq r(v)\}\big|.\end{split}\]

If \(i(v) \leq -1\), then increasing the rank of the vertex by 1 will decrease the agony of the ranking, as will decreasing the rank by 1 if \(d(v) \leq -1\).

Our algorithm, which we call the descent algorithm, starts with the naive ranking (all ranks are 0) and iteratively picks a vertex at random and changes its rank by 1 if doing so will decrease the agony of the ranking.