CS Paper Radar

Influence Ranking Improvement via Link Addition in Social Networks

Taiki Ikemoto, Sho Tsugawa

cs.SI ·submitted 2026-09-29 06:02 UTC · v1
published

Abstract

Social media platforms increasingly rely on influential users for information dissemination in domains such as marketing and political campaigns. As the value of being recognized as influential grows, users may have incentives to strategically enhance their influence. In this study, we investigate whether and to what extent the influence ranking of a target node can be improved by adding a limited number of outgoing links in the context of influence maximization (IM). We formulate the Link Selection Problem for Influence Ranking Improvement (LSP-IRI) as the problem of selecting a fixed-size set of additional outgoing links from a target node in order to maximize its rank improvement. To examine this problem, we consider two representative heuristic strategies: a greedy method that directly optimizes rank improvement and a computationally efficient random search method. We conduct experiments on four real-world networks ranging from thousands to hundreds of thousands of nodes. The results show that even a few added links can substantially improve IM-based influence rankings. In particular, the greedy method improves the ranks of nodes initially ranked around 50 by several tens of positions on average with only three added links, sometimes moving them into the top 10. The random search method achieves smaller gains under strict budgets but reduces computation time by up to approximately 98% compared with the greedy method and becomes effective when larger budgets are allowed. These findings show that IM-based influence rankings are sensitive to limited local structural modifications and highlight a trade-off between ranking improvement and computational efficiency.

Comment
15 pages; accepted at ASONAM 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Algorithmic Fairness for Influence Maximization: A Survey of Models, Metrics, and Optimization Techniques

cs.SI ·2026-10-14 ·Shashank Sheshar Singh, Sunil Kumar Meena, Kuldeep Singh, krati Saxena
survey similarity 0.71
Abstract

Influence maximization (IM) has become a basis of modeling information spread across social networks, with applications in viral marketing, public health, and political campaigns. However, classical IM algorithms often prioritize the spread of overall influence and ignore its fairness, resulting in disadvantages for marginalized or underrepresented communities. This survey provides a detailed look at fairness-aware influence maximization, focusing on important challenges, models, and methods designed to ensure fair influence maximization. We categorize existing methods into five groups based on their fairness objectives, including parity, diversity, and utility, and discuss how they handle biased network structure, protected attributes, and seeding constraints. We also examine how fairness-aware influence maximization methods perform on real-world data to highlight the importance of combining fairness with classical influence maximization methods. By bridging the gap between influence spread and social equity, this survey lays the foundation for designing fair algorithms that ensure fair representation in large-scale diffusion processes. The survey concludes by outlining emerging trends, open challenges, and prospective future directions in the domain, highlighting the need for expertise spanning multiple disciplines.

0.07

Influence Enhancement in Opinion Dynamics Using Edge Modification: A Kron Reduction-Based Approach

eess.SY ·2026-09-12 ·Aashi Shrinate, Aravind Seshadri, Twinkle Tripathy, Laxmidhar Behera, Lingfei Wang +1 more
similarity 0.66
Abstract

With the emergence of online social networks as a primary platform for advertising and advocacy, enhancing a user's influence has become of significant interest. In this paper, we investigate this problem under the Friedkin Johnsen opinion dynamics model, wherein stubborn agents influence the opinions of other agents in the network. Unlike most of the existing works, we leverage topological properties of the network to increase the influence of a desired stubborn agent. Specifically, we introduce the notion of edge modification, which mimics the mechanism of recommendations in social networks. First, we present a topology-based condition that identifies edge modifications that always increase the influence of a desired stubborn agent. It is shown that the impact of the chosen edge modifications remains robust to changes in parameters such as stubbornness and the interaction weights. Thereafter, we formulate a discrete optimisation problem to identify a set of edge modifications that maximise the agent's influence centrality. We present a computationally efficient approximate solution to the optimisation problem. Finally, we demonstrate the effectiveness of our approach on the Friedkin-Johnsen opinion dynamics over the Erdos Renyi random graph.

0.31

Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions

cs.SI ·2026-11-04 ·Parth Gupta, Abhinav Jain, Avishek Mukhopadhyay, Amitabha Bagchi, Sayan Ranu +1 more
similarity 0.65
Abstract · 16 pages, 12 figures

PageRank is widely used to quantify the importance of nodes in directed networks. In applications such as recommendation systems, it is increasingly important that the PageRank distribution provides a fair representation of node exposure. This motivates the problem of making minimal changes to a graph so that the PageRank values of a given set of target nodes $T$ match a desired vector $\boldsymbol{t}$. In this paper, we study this problem under an edge-addition budget $B$, where exactly $B$ edges may be added to the graph. We show that deciding whether a multiset of exactly $B$ added edges can make the target nodes attain their desired absolute PageRank scores is NP-complete. After this, we define the $\ell_1$ Target PageRank problem in which we seek to minimize the $\ell_1$ distance between the target vector and resultant vector. We show that this optimization problem admits no polynomial-time multiplicative constant-factor approximation unless $P=NP$. Motivated by these hardness results, we propose two greedy heuristics for approaching the target PageRank vector. We additionally propose a Random Walk Hungarian (RWH) heuristic that addresses the addition of edges between dissimilar nodes by incorporating a penalty for such edges. Finally, we evaluate the proposed heuristics on several real-world and synthetic datasets and compare their performance in terms of PageRank accuracy, computational efficiency, and the relevance of the added edges.

0.17

Optimal and heuristic strategies for evaluating the influence of coordinated behavior in information cascades and retweet networks

cs.SI cs.CY ·2026-09-21 ·Niccolò Di Marco, Matteo Cinelli, Shinichi Nakano, Andrea Frosini
theory similarity 0.65
Abstract

Coordinated Inauthentic Behavior (CIB) has become a major concern in online social platforms, yet its actual impact on information diffusion remains poorly understood. Existing research has primarily focused on detecting coordinated activity, while comparatively little attention has been devoted to quantifying its influence once detected. In this work, we introduce two complementary frameworks for the post-hoc evaluation of coordinated accounts. First, we formulate the problem on information cascades as a constrained influence maximization problem over directed trees and develop a polynomial-time dynamic programming algorithm that computes the optimal placement of coordinated nodes, providing an upper bound on their achievable influence. Second, motivated by the limited availability of diffusion cascades in real-world platforms, we propose a network-based framework that estimates influence directly from retweet networks using the independent cascade model and compares the observed placement of coordinated accounts against established heuristic baselines. We evaluate both approaches on Twitter/X data from the 2019 UK General Election and on a collection of verified state-backed information operation campaigns spanning multiple countries. While coordinated accounts exhibit limited influence in the UK cascades, the network-based analysis reveals substantial differences across campaigns, with several operations achieving influence comparable to or exceeding that of structurally central seed sets. Finally, by reconstructing cascades from the retweet networks, we show that the two frameworks produce consistent results, suggesting that the observed effects reflect intrinsic structural properties of coordinated activity rather than artifacts of the underlying methodology.

0.28

Rewiring the Majority: Structural Median Opinion Control in the Friedkin-Johnsen Model

cs.SI ·2026-10-15 ·Elisabetta Biondi, Chiara Boldrini, Andrea Passarella, Marco Conti
similarity 0.62
Abstract · 11 pages,5 figures

Opinion control under the Friedkin-Johnsen (FJ) model has traditionally focused on modifying individual users, for example by changing their opinions or susceptibility to social influence. We study a complementary problem: can collective outcomes be steered by modifying the interaction network instead? We formulate structural median control as an edge-addition problem aimed at moving the equilibrium median beyond a target threshold. We show that the problem is NP-hard even under highly restricted settings and propose both continuous optimization methods and computationally lighter opinion-aware heuristics for selecting edge additions. Experiments on synthetic and real-world networks reveal that intervention success depends jointly on network topology, the placement of favorable opinions, and user susceptibility. Structural interventions produce the largest shifts when opinion placement and network structure allow added edges to create useful influence pathways toward the target outcome. Finally, under a homogeneous reference setting, we compare structural and node-level interventions using normalized budgets and a degree-weighted cost model. We show that, although node interventions often appear stronger under normalized budgets, structural interventions become competitive and frequently more cost-effective once the higher cost of targeting high-reach users is taken into account.

0.26

Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach

cs.LG cs.SI ·2026-09-12 ·Erfan Ahmadi, Mina Shirazi, Behnam Bahrak
similarity 0.62
Abstract · 16 pages, 1 figure, 4 tables. Submitted to the International Journal of Data Science and Analytics

The Minimum Dominating Set (MDS) problem is a classic NP-hard combinatorial optimization problem with critical applications in social network analysis, including viral marketing, influence maximization, public health interventions, and information dissemination. Identifying a minimal set of influential individuals whose reach covers an entire social network is central to these applications, yet remains computationally challenging at scale. Graph neural networks (GNNs) have emerged as powerful tools for learning over graphs, and recent work explores their application to hard combinatorial problems. This paper presents a novel unsupervised GNN framework for the MDS problem that eliminates the need for ground-truth solutions during training. Trained on 12,000 synthetic graphs with diverse structural properties, our method achieves up to 55x faster inference than metaheuristic baselines and up to 14x faster inference than supervised learning approaches, while finding optimal or near-optimal dominating sets on real-world social network benchmarks. Our learned heuristic generalizes effectively to unseen graph distributions, demonstrating strong practical applicability for large-scale social network analysis.

0.23

Efficient Influence Minimization via Source-Integrated Sampling

cs.SI cs.DS ·2026-11-11 ·Jingbang Chen, Junyao Wang
theory similarity 0.61
Abstract · 14 pages

Influence minimization by node blocking is a fundamental problem in graph data management that seeks a small set of vertices whose removal minimizes the expected spread from a fixed source set. It supports decisions about where to intervene in large interaction networks to control harmful propagation, such as the spread of rumors and infectious diseases. Under the Independent Cascade (IC) model, selecting blockers requires comparing a large number of candidate sets, and estimating their effects on propagation can be costly. We propose SIG (Source-Integrated Greedy), a sampling framework for efficiently finding high-quality approximate solutions. Our key idea is to group the possible sets of neighbors directly activated by the sources according to their effects on blocker selection. SIG represents these groups in a compact weighted tree and computes their probabilities directly, allowing each sample to account for all source outcomes without enumerating them. We prove that SIG produces unbiased estimates of the lower-bound objective without increasing variance for fixed blocking plans, and establish a high-probability quality guarantee through independent validation. Extensive experiments on real-world networks show that SIG has the lowest mean total running time in all main comparisons, with speedups of up to 583x over the fastest baseline. SIG produces solutions competitive with those of prior methods and achieves the highest influence reduction in multiple settings, including on many of the largest networks, where several baselines exceed the runtime limit. Additional experiments show that SIG maintains consistently low running times as graph size and the blocking budget increase, while delivering stronger blocking solutions at larger budgets.

0.18

Optimizing Marketing Budgets for Social Influence: A Generalized Fractional Incentives Framework

cs.SI cs.AI ·2026-10-19 ·Abhishek K. Umrawal, Akhil Bhimaraju, Eliot W. Robson, Lav R. Varshney
similarity 0.59
Abstract · 28 pages, 2 figures, and 2 tables

Marketing managers routinely allocate limited budgets across individuals in social networks whose responsiveness and influence vary substantially. We study the problem of Budgeted Generalized Fractional Influence Maximization (BGFIM), which captures the allocation of continuous levels of marketing spend across users in the presence of heterogeneous response and network spillovers. In this framework, adoption probabilities are governed by user-specific response functions that capture both baseline propensity and marginal responsiveness, while incentive costs vary across users. We propose a scalable solution approach based on a discrete greedy procedure with provable approximation guarantees, enabling tractable optimization under realistic budget constraints. Our formulation generalizes prior influence maximization models by allowing heterogeneous response and cost structures, providing a more flexible representation of targeted marketing interventions. Using experiments on multiple large-scale networks, we show that continuous allocation strategies can outperform standard heuristics and improve influence outcomes under heterogeneous conditions, and we illustrate how the framework can support profit-oriented decision making by identifying budget levels that balance marginal returns and costs. Overall, our results highlight the value of fine-grained budget allocation in networked marketing environments and offer a scalable approach for data-driven marketing resource allocation.

0.16