Influence Ranking Improvement via Link Addition in Social Networks

1 Introduction

• The work addresses limited understanding of how small structural changes affect IM-based rankings, shifting focus from platform-side selection to users seeking higher ranks.The introduction notes that users may have incentives to increase perceived influence as influencer recognition gains social and professional value.Source: §1 · p. 2
• LSP-IRI selects a fixed-budget set of outgoing links to maximize a target user’s rank improvement under an IM-based measure.The formulation also provides a way to assess ranking robustness to limited local structural changes.Source: §1 · pp. 2, 4
• The search is combinatorial, influence evaluation is computationally expensive, and relative ranking requires accounting for changes in other nodes’ ranks.The passage notes that exact expected influence under the IC model is #P-hard.Source: §1 · p. 3
• The paper examines greedy link selection for direct rank improvement and random search, which reduces computational overhead and scales to larger link budgets.Greedy repeatedly evaluates candidate links; random search samples candidate link sets across trials.Source: §1 · pp. 3–4
• A small number of added links can substantially improve target-node rankings, revealing sensitivity of IM-based rankings to local changes and a gain–efficiency trade-off.The paper presents this as evidence that rankings may be susceptible to local structural modifications.Source: §1 · p. 4

2 Related Work

• Influence maximization selects seed nodes for expected spread, and later work extends it to practical recommendation and optimization settings that remain primarily platform-focused.The cited examples include fairness- and topic-aware recommendation and multi-objective influence maximization.Source: §2 · pp. 4–5
• Prior link interventions target global diffusion, misinformation suppression, or centrality rankings, rather than a target node’s IM-based rank.The examples include increasing spread, reducing misinformation diffusion [12], and manipulating centrality rankings.Source: §2 · p. 5
• The paper identifies limited understanding of how local link additions affect a target node’s relative ranking under an IM-based measure.The cited centrality rankings capture structural prominence rather than diffusion-based influence.Source: §2 · p. 5

3.1 Preliminaries

• A social network is modeled as a directed graph whose nodes represent users and whose edges represent relationships such as following or information flow.Source: §3.1 · p. 5
• Under the Independent Cascade model, each newly activated node gets one chance to activate each inactive out-neighbor, independently with edge-specific probability.Source: §3.1 · p. 5
• Influence Maximization seeks a seed set of size k that maximizes expected influence spread under a given graph and diffusion model.Source: §3.1 · p. 5

3.2 Link Selection Problem for Influence Ranking Improvement (LSP-IRI)

• A node’s influence ranking is the smallest seed budget at which the IM algorithm selects it.Source: §3.2 · p. 6
• Candidate links are non-existing outgoing edges from the target node to other nodes, excluding self-loops.Source: §3.2 · p. 6
• LSP-IRI selects exactly l candidate links to maximize the target’s rank improvement, measured by the change in its ranking after the links are added.Source: §3.2 · p. 6

• RIS-based heuristics approximate rank improvement with fewer evaluations because exhaustively evaluating feasible link sets is computationally infeasible.Source: §4 · p. 7
• Greedy selection adds one link at a time to maximize rank improvement, requiring O(lMv) rank evaluations and up to O(l|V|) in the worst case.Source: §4 · p. 7
• Random search samples feasible link sets of size l and returns the sampled set with the greatest evaluated rank improvement.Source: §4 · pp. 7–8
• O(n) rank evaluations make random search less costly, though it may miss high-quality solutions; it remains practical for larger link budgets and large networks.Source: §4 · p. 8

5.1 Datasets

• Four networks—GRQC, NetHEPT, DBLP, and Epinions—are evaluated using their largest connected components, or largest weakly connected component for directed Epinions.The first three are co-authorship networks; Epinions is a directed trust network.Source: §5.1 · p. 8, Table 1 · p. 8

5.2 Comparison Methods

• The evaluation is a proof-of-concept comparison of two basic search strategies against a uniformly sampled naive-random baseline.The baseline averages performance over 100 repeated samples to mitigate stochastic variance.Source: §5.2 · p. 9

5.3 Experimental Settings

• The experiments use Weighted Cascade probabilities, target ranks 50 and 100 or specified ranking percentiles, and link budgets of 3, 10, or 30.For directed edges, activation probability is the reciprocal of the receiving node’s indegree; undirected networks use degree.Source: §5.3 · p. 9

5.4 Evaluation Metrics

• Effectiveness is measured by rank improvement and RIR, which normalizes improvement by the maximum possible gain; runtime measures computational efficiency.RIR near one indicates movement close to the top of the ranking, while negative RIR indicates a worse rank after link addition.Source: §5.4 · p. 10

6.1 Rank Improvement

• Figure 3 omits DBLP’s top-25%, top-50%, and top-75% settings because many peripheral nodes have zero estimated influence, and omits greedy l = 30 because l = 10 already placed all evaluated targets at rank 1.Figure 3 compares RIR by initial-rank setting across network and link-budget panels.Source: §6.1 · p. 10
• Greedy achieves the largest rank improvements, while randomized methods narrow the gap as link budgets rise; lower-ranked targets in larger networks may still gain little.The figures show these patterns across representative GRQC cases and, broadly, across networks, budgets, and initial-rank settings.Source: §6.1 · pp. 10–11, Figure 2 · p. 11, Figure 3 · p. 12

6.2 Computational Efficiency

• Greedy has the longest runtime across datasets, while random search evaluates a fixed number of sampled link sets and provides a more efficient alternative with meaningful gains in many settings.The naive random baseline is fastest because it performs no optimization during link selection.Source: §6.2 · pp. 11–12

7 Discussion

• A small number of local link additions can substantially alter IM-based influence rankings, revealing their sensitivity to local interventions.The discussion also frames this sensitivity as a potential vulnerability of influence-based ranking mechanisms.Source: §7 · p. 13
• Random search reduces computational overhead by evaluating sampled link sets, while its gains may remain moderate for small relative budgets or very low-ranked targets.The greedy method incurs substantially higher runtime, particularly as link budgets and network sizes grow.Source: Figure 4 · p. 13, §7 · p. 14
• The experiments cover a limited set of real-world networks smaller than very large online social platforms, limiting evidence about generalizability and scalability.The authors call for evaluation on larger and more diverse networks.Source: §7 · p. 14
• The proposed methods have no theoretical guarantees, leaving conditions for substantial rank improvement uncharacterized beyond empirical observations.The authors identify theoretical analysis as needed to clarify when such gains can be expected.Source: §7 · p. 14
• The experiments use the IC model with the Weighted Cascade setting, so robustness under alternative diffusion models and behavior-based propagation probabilities remains to be examined.Source: §7 · p. 14
• The evaluation covers two heuristics and a naive random baseline, making the results a proof of concept rather than a comprehensive benchmark.Existing link-intervention methods may optimize different objectives.Source: §7 · p. 14
• Candidate links are assumed to have equal cost and to be addable when selected; heterogeneous costs, feasibility, and acceptance probabilities are not modeled.Source: §7 · p. 14

8 Conclusion

• LSP-IRI formalizes how limited link additions can modify a target node’s influence ranking under the IM framework.Source: §8 · p. 14
• The paper examines a greedy strategy that directly optimizes rank improvement and a random search strategy that reduces computational cost.Source: §8 · p. 14
• Experiments on multiple real-world networks show that a small number of added links can substantially improve target-node rankings, indicating susceptibility to local structural changes.The formulation is presented as a framework for analyzing how IM-based rankings can be modified through limited local additions.Source: §8 · p. 14