Abstract
Social influence can be described as power—the ability of a person to influence the thoughts or actions of others. Identifying influential users on online social networks such as Twitter has been actively studied recently. In this paper, we investigate a modified k-shell decomposition algorithm for computing user influence on Twitter. The input to this algorithm is the connection graph between users as defined by the follower relationship. User influence is measured by the k-shell level, which is the output of the k-shell decomposition algorithm. Our first insight is to modify this k-shell decomposition to assign logarithmic k-shell values to users, producing a measure of users that is surprisingly well distributed in a bell curve. Our second insight is to identify and remove peering relationships from the network to further differentiate users. In this paper, we include findings from our study.
Introduction
Measuring "influence" on social media is notoriously difficult. Simple metrics like follower counts are easily gamed, while more complex algorithms like PageRank can be computationally expensive for massive graphs. Furthermore, standard graph analysis tools often struggle with the "long tail" distribution of social networks. When applying traditional k-shell decomposition—an algorithm that identifies the "core" of a network by iteratively pruning low-connectivity nodes—most users end up lumped into the lowest levels, while a few outliers stretch out over thousands of empty shells. This makes it nearly impossible to perform meaningful statistical analysis or differentiate between different tiers of influencers.
Methodology: Logarithmic Mapping and Peering
The authors propose two primary modifications to the standard k-shell decomposition to better handle the scale and structure of Twitter's network:
- Logarithmic Mapping: Instead of assigning shells linearly based on connection count, the authors use a logarithmic scale. In their model, a user is placed in shell $k$ if they have $2^k - 1$ (or fewer) connections. This effectively "compresses" the higher shells, transforming a skewed power-law distribution into a manageable bell curve.
- Peering vs. Non-Peering: The authors distinguish between Reach (total audience, including reciprocal followers) and Authority (unidirectional followers). By removing "peers"—users who follow each other—they create a "non-peered" network. Running the algorithm on this pruned graph reveals users who are followed because of their status or content, rather than social obligation.
Key Insights and Results
The study utilized a snapshot of the Twitter ecosystem containing 41.7 million user profiles and 1.47 billion social relations, validated against a sample of 80 million tweets.
The Bell Curve Breakthrough
The most surprising finding was that logarithmic mapping produced a near-perfect bell curve distribution of users across k-shell levels. This makes the metric far more useful for ranking and categorization than traditional linear methods.
High Impact and Authority
The "non-peered" (authority) measure proved significantly more effective at identifying high-impact users than the "peered" (reach) measure. Removing reciprocal links acts as a natural noise filter against "follow-back" culture. The algorithm successfully identified a small, elite group of users (the "k8/K11" bucket) with fewer than 1,200 members. These users averaged over 190,000 recipients per tweet and nearly 400 retweets per message. Qualitative analysis revealed a high concentration of CEOs, corporate founders, news feeds, and major media hosts in this top tier.
Conclusion
Because the modified algorithm uses logarithmic steps, it converges much faster than the original. If a standard algorithm takes $n$ iterations, the modified version requires only $\log_2 n$ iterations, making it viable for nightly runs on massive datasets. While susceptible to certain forms of self-promotion via bots, the modified k-shell decomposition offers a robust, scalable framework for identifying genuine social authority in massive networks.
Summary updated