Source-linked AI summary
Leaders in Social Networks, the Delicious Case
Linyuan Lu, Yi-Cheng Zhang, Chi Ho Yeung, Tao Zhou
TL;DR
Social networks need methods that identify influential users for collective information discovery, while PageRank is less effective for people-centered networks. The paper introduces adaptive, parameter-free LeaderRank and reports stronger ranking effectiveness and robustness than PageRank. It concludes that LeaderRank may support information-spreading applications and ranking in evolving, noisy social networks.
Problem
Identifying influential users is difficult because social-network influence depends on complex relationships, noisy data, and possible manipulations rather than simple fan counts.
Method
LeaderRank adaptively ranks users through resource flow on a leadership network augmented with a ground node, without external parameters.
Results
LeaderRank outperforms PageRank in ranking users who enable quick and extensive spreading and is more tolerant of noisy data and manipulations.
Takeaways & Limitations
LeaderRank may serve as a prototype for ranking users in rapidly evolving social networks and applications involving information spreading.
Takeaways & Limitations
The paper notes that weighting ground-node links by node significance or other criteria could further improve LeaderRank.
Abstract
from arXiv · showhide
Finding pertinent information is not limited to search engines. Online communities can amplify the influence of a small number of power users for the benefit of all other users. Users' information foraging in depth and breadth can be greatly enhanced by choosing suitable leaders. For instance in delicious.com, users subscribe to leaders' collection which lead to a deeper and wider reach not achievable with search engines. To consolidate such collective search, it is essential to utilize the leadership topology and identify influential users. Google's PageRank, as a successful search algorithm in the World Wide Web, turns out to be less effective in networks of people. We thus devise an adaptive and parameter-free algorithm, the LeaderRank, to quantify user influence. We show that LeaderRank outperforms PageRank in terms of ranking effectiveness, as well as robustness against manipulations and noisy data. These results suggest that leaders who are aware of their clout may reinforce the development of social networks, and thus the power of collective search.
Introduction
Social networks contain influential users who can expand collective information discovery beyond individual search. The paper studies delicious.com’s leadership network and proposes LeaderRank to identify such users despite complex relationships.
- Influential users can help online communities discover information more deeply and broadly than individuals can alone.
- In delicious.com, users subscribe to leaders whose bookmarked collections are automatically delivered, creating leader-fan relationships.The leadership network contains about half a million linked users within a seven-million-user community.
- Identifying leaders is difficult because influence depends on entire upstream connections rather than only direct leaders or fan counts.
- LeaderRank is an adaptive, parameter-free ranking algorithm designed for quickly evolving personal relationships.It adapts the random information-acquisition probability when users add or remove leaders.
- The study compares leadership-network ranking with fan-count ranking and examines implications for collective information exploration and online-community design.
Methods and Materials
LeaderRank models user relationships as a directed network and ranks users through resource flow on a graph augmented with a ground node. The method is parameter-free, converges uniquely, and is evaluated against PageRank on a large delicious.com dataset.
- User-to-leader relations are represented as directed links from fans to leaders, corresponding to votes used to rank users by network topology.Information flow is opposite the link direction, moving from leaders to fans.
- A bidirectionally connected ground node links to every user, making the network strongly connected with N + 1 nodes and M + 2N links.
- Each non-ground node starts with one unit of resource, which is repeatedly distributed evenly among neighboring nodes through directed links.
- The process converges to a unique steady state because the ground node makes the transition matrix primitive; its score is then redistributed among users.
- LeaderRank provides parameter-freeness, applicability to any graph, unique-ranking convergence, and independence from initial conditions.
- PageRank introduces a return-probability parameter, creating calibration demands and reduced adaptability for rapidly evolving social networks.
- The delicious.com evaluation uses 582377 users and 1686131 directed links, including 571686 users in the giant component.
Results
LeaderRank identifies influential users more effectively than PageRank and fan-count ranking, while remaining more robust to noisy network data and manipulation. Its advantage appears in bookmark-based activity measures and simulated information spreading.
- Comparison with Ranking by the Number of Fans: Users ranked highly by LeaderRank despite few fans often have high bookmark quality, while heavily followed users with low bookmark quality can receive lower ranks.Bookmark quality is represented by U_i/B_i, the number of times collected bookmarks are saved divided by the number collected.
- Ranking effectiveness: LeaderRank uses network topology more effectively than fan counts because upstream connections contribute to influence beyond direct followers.The entire upstream connection to leaders acts as an information source, whereas merely counting fans or leaders provides no absolute influence measure.
- Effectiveness: LeaderRank-selected users produce faster and wider simulated opinion spreading than PageRank-selected users for top-20, top-50, and top-100 selections.The LeaderRank curves show faster growth and a higher saturated cumulative infected count; similar results hold for the top 50 and top 100.
- Effectiveness: LeaderRank avoids PageRank’s dependence on extensive parameter testing across infection probabilities and achieves broader spreading when λ is large.The LeaderRank/PageRank infected-count quotient favors LeaderRank across a broad indicated range of λ, while both methods are limited when λ is small.
- Tolerance of Noisy Data: LeaderRank remains more tolerant than PageRank when links are randomly added or removed, yielding smaller score and ranking impacts under noisy topology.Score impact increases with the number of modified links, but LeaderRank produces smaller I_S values and smaller ranking differences I_R than PageRank.
Discussion
The paper frames influential-user identification as a broader problem than ranking leaders, requiring algorithms that account for network consequences such as spreading, noise, and manipulation. LeaderRank is presented as an adaptive, parameter-free candidate whose robustness and ranking behavior may support social-network applications.
- Discussion: Influential-user identification must consider ranking consequences, not merely determine who ranks highest.The paper emphasizes noisy data and smart manipulations as important social-network concerns.
- Discussion: LeaderRank may serve as a prototype for ranking users in quickly evolving social networks.Its adaptive, parameter-free design is described as eliminating frequent calibration.
- Discussion: LeaderRank identifies users associated with quick and extensive opinion spreading.The paper connects this result to online applications featuring information spreading.
- Discussion: LeaderRank is tolerant of spurious and missing links and robust against manipulations.These properties are presented as benefits for noisy personal-relationship data and ranking tasks.
- Discussion: Extensions that weight links by node significance or other criteria may further improve LeaderRank.The paper also identifies applications including blog plagiarizer identification and preventing species loss as possible generalizations.
- Discussion: Leader identification may reinforce online communities and facilitate collective search as networks grow larger and ranking becomes more challenging.The paper presents LeaderRank as a potential candidate for this challenge.
Figure Legends
The figures illustrate LeaderRank's construction, user-ranking signals, spreading evaluation, robustness tests, manipulation tests, and comparison tables. Together, they show how the algorithm is applied and evaluated across network structure, influence proxies, diffusion, topology noise, and fake fans.
- Figure 1: Figure 1 illustrates the ground node and LeaderRank on six users connected by 12 directed links.Final ranking scores are labeled beside the corresponding users.
- Figure 2: Figure 2 orders users by LeaderRank rank while encoding fan counts and Ui/Bi through circle size and colored highlights.Red highlights indicate few fans but large Ui/Bi; blue highlights indicate many fans but small Ui/Bi.
- Figure 3: Figure 3 compares four named users ranked 29th, 47th, 91st, and 92nd by LeaderRank.Circle size represents the average number of times their collected bookmarks are saved by others.
- Figure 4: Figure 4 plots cumulative infected users over time for LeaderRank-versus-PageRank initial sets among the top 20, 50, and 100 users.Panel (d) plots the fractional increase, defined as infected users under LeaderRank divided by those under PageRank, across infection probability λ.
- Figure 5: Figure 5 measures score and ranking impacts as links are added or removed, with an inset showing the difference in ranking mobility.The comparison is between LeaderRank and PageRank.
- Figure 6: Figure 6 shows manipulated rank under LeaderRank and PageRank after adding 10, 50, or 100 fake fans.Panels separately report the results for the two algorithms.
- Table 1: Table 1 lists the top 20 users ranked by LeaderRank, PageRank, and number of fans.It provides the tabular comparison underlying the ranking evaluation.
1 Primitivity and Convergence
The ground node makes the transition matrix primitive and yields a unique steady-state ranking. This convergence follows from strong connectivity, positive powers of the matrix, and uniqueness of the eigenvector for eigenvalue 1.
- Primitivity and convergence: The ground node creates loops and paths that make P^6 positive, so the transition matrix P is primitive.Any pair of nodes can be connected in exactly six steps.
- Primitivity and convergence: A heterogeneous eigenvector for eigenvalue 1 would contradict the row-normalized matrix properties.The contradiction establishes uniqueness of the eigenvector associated with eigenvalue 1.
- Primitivity and convergence: The transpose transition matrix P^T therefore has a unique steady state.This steady state is the converged ranking used by LeaderRank.
2 Differences between LeaderRank and PageRank
LeaderRank differs from PageRank by using a ground node to regulate probability flow adaptively according to a user's number of leaders. This produces a flow pattern intended to reduce ranking bias in leadership networks.
- Algorithmic difference: LeaderRank uses a ground node to regulate probability flows, making the algorithm parameter-free, unlike PageRank's externally specified return probability.The ground node receives score flow from users, whereas PageRank sends flow to random nodes.
- Flow dynamics: The LeaderRank flow from a node to the ground node is inversely proportional to its out-degree, while PageRank's random-node flow shows no obvious trend.Here, out-degree is the number of leaders, and Fig. S1 compares both flows as a function of kout.
- Information interpretation: Users with many leaders may acquire less information from each leader, including the centralized ground-node leader.Empirical Delicious data similarly show that the ratio of saved bookmarks to the number of leaders decreases with kout.
- Ranking consequence: LeaderRank assigns smaller voting rights to users with fewer leaders, reducing the bias that could arise when their score is donated to only one or two leaders.The resulting negative correlation between score flow to leaders and out-degree is presented as an advantage over PageRank.
- Ranking consequence: Web users with many hyperlink choices are less likely to jump randomly, a behavior that LeaderRank captures through smaller flow to the ground node.This example connects out-degree-dependent flow to browsing behavior.
3 The top-100 ranked users
The paper reports the top 100 users and corresponding scores under LeaderRank, PageRank, and fan-count ranking. The comparison uses scores normalized so the LeaderRank and PageRank totals equal N.
- Top-100 ranked users: The top 100 users are listed with their scores for LeaderRank, PageRank, and number-of-fans ranking.The final two columns report users with the largest fan counts and their corresponding fan numbers.
- Top-100 ranked users: LeaderRank and PageRank initialize one score unit on every user, so their scores sum to N.Fan-count ranking instead reports the corresponding number of fans.
4 Zipf’s law
All three ranking methods exhibit Zipf's law: user score decreases approximately as a power law with rank. However, the individual users occupying each rank differ across algorithms.
- Zipf's law: All three ranking algorithms show a power-law decay of user score as rank increases.The paper identifies this pattern as Zipf's law.
- Zipf's law: Although the score–rank relationship is similar across methods, the ranking of individual users differs by algorithm.Thus, similar aggregate distributions do not imply identical user rankings.
5 Comparisons among ranking results from different ranking algorithms
LeaderRank and PageRank produce broadly similar rankings, but LeaderRank differs from simple fan-count ranking and changes which individuals receive high ranks.
- LeaderRank rankings overlap more with PageRank than with rankings based solely on the number of fans.
- Both LeaderRank and PageRank positively correlate with the number of fans, although individual rankings differ.
- PageRank consistently assigns top-ranked users fewer leaders on average than LeaderRank does.This suggests PageRank favors users with smaller numbers of leaders, which the authors characterize as unfair to users with many leaders.
6 Negative effect by removal of leaders
Removing all leaders negatively affects many users’ ranks under both LeaderRank and PageRank, indicating that leaders alone do not provide an absolute measure of influence. The supplementary analyses compare rankings, leader counts, upstream removal effects, bookmark ratios, and score distributions.
- 6 Negative effect by removal of leaders: Removing all leaders lowers the rank of many users under both LeaderRank and PageRank.The results indicate that influence depends on the broader upstream connection to leaders, not leaders alone.
- Supplementary ranking analyses: Fig. S2 shows the ratio of saved bookmarks to the number of leaders as a function of kout.
- Supplementary ranking analyses: Fig. S3 plots scores against rank for LeaderRank, PageRank, and fan-count ranking, with Zipf’s law observed for all three algorithms.
- Supplementary ranking analyses: Fig. S4 measures overlap among the top-L users ranked by LeaderRank, PageRank, and number of fans.
- Supplementary ranking analyses: Fig. S5 reports the average number of leaders among top-L users ranked by LeaderRank and PageRank.The inset relates this average to the logarithm of L.
- 6 Negative effect by removal of leaders: Fig. S6 compares users’ original ranks with their ranks after all leaders are removed for LeaderRank and PageRank.The black solid line marks equality between new and original rank.