CS Paper Radar

From Propagation to Protection: Risk-Aware Diffusion for Harm Minimization in Signed Social Networks

Aaqib Zahoor, Janibul Bashir, Iqra Altaf Gillani

cs.SI ·submitted 2026-08-21 12:35 UTC · v1
theory

Abstract

Real-world social relationships are not uniformly supportive. Information through hostile connections can increase resistance, anxiety, or misinformation rather than adoption. Classical models such as Independent Cascade and Linear Threshold, together with Influence Maximization (IM), which maximizes spread from a limited seed set, treat activation as discrete and irreversible. Its counterpart, Influence Minimization (Inf-Min), limits undesirable spread but similarly relies on simplified activation assumptions. Signed extensions incorporate polarity but largely retain this irreversibility, leaving no room for beliefs to weaken, reverse, or recover under competing influence. Moreover, both objectives typically treat individuals uniformly, without accounting for differences in vulnerability or prioritizing protection of those most at risk. We introduce RASH, a signed, susceptibility-aware diffusion model in which node awareness is continuous, bounded, and non-monotonic, and prove that despite this added expressiveness it remains monotone and γ-weakly submodular where only positive or negative edges exist, preserving tractable greedy approximation guarantees where strict submodularity provably fails. Building on RASH, we formulate Harm Minimization (HM), which maximizes aggregate reach while minimizing the awareness shortfall (harm). We prove HM is NP-hard, yet its harm-reduction formulation inherits the same monotonicity and weak-submodularity structure, admitting a greedy algorithm with a bounded approximation ratio. Across six structurally diverse signed networks, RASH is the only diffusion model tested to our knowledge that ever allows awareness to reverse after activation, letting sustained discouraging influence drive awareness from positive toward negative, and HM achieves the highest harm reduction of any method evaluated, including its own boundary cases (IM and Inf-Min)

Closest papers

Nearest neighbours by meaning across the whole index.

How Social Reinforcement Shapes Word-of-Mouth: A Conviction-Based Model for Marketing Diffusion and Network Targeting

cs.SI ·2026-10-09 ·Abhishek K. Umrawal, Curt Stutsman, Camille Woods, Eliot W. Robson
similarity 0.64
Abstract · 44 pages, 10 figures, and 2 tables

Organizations increasingly rely on social networks to drive product adoption and word-of-mouth diffusion, yet a central challenge is that consumers differ not only in whether they adopt but also in how strongly they subsequently advocate. In particular, individuals who adopt under strong social reinforcement often develop greater conviction and become more persuasive. Existing diffusion models largely abstract away from this mechanism by treating influence strength as static. We introduce a conviction-based diffusion framework, the Pressure Threshold (PT) model, that captures how social reinforcement shapes both adoption and subsequent advocacy. In this model, an individual's influence increases with the cumulative social pressure experienced at adoption, providing a tractable representation of conviction formation while preserving the interpretability of classical threshold-based models. We study the managerial implications of this mechanism through marketing targeting and seeding. We show that accounting for reinforcement fundamentally alters optimal targeting strategies, shifting emphasis toward consumers in cohesive network regions where repeated exposure can amplify downstream word-of-mouth. While reinforcement introduces nonstandard features into the optimization problem, we demonstrate that scalable heuristics remain effective and provide data-dependent performance guarantees. Across synthetic and real-world networks, we find that reinforcement often substantially increases the effectiveness of seeding interventions, particularly in dense and clustered environments where opportunities for social validation are abundant. Using time-stamped social media cascades, we further show that the PT model improves predictive accuracy relative to standard diffusion models, highlighting the empirical relevance of conviction-driven amplification.

0.47

Robust Action Clusters and Cascades in Opinion Dynamics with Heterogeneous Action Thresholds

eess.SY ·2026-11-16 ·Hassan Munif, Anthony Couthures, Vineeth Satheeskumar Varma, Samson Lasaulce, Irinel-Constantin Morarescu
similarity 0.64
Abstract

We study the preservation and propagation of public actions in networks whose agents hold continuous private opinions. Agents update their opinions from their neighbors' observed actions and express them through action rules whose thresholds differ across agents. We characterize groups of agents that preserve a given common action regardless of the outsiders' actions. We call such a group, paired with that action, a robust action cluster. We show that a group is a robust action cluster for that action if and only if each member places enough of its influence weight on the group, where the required influence depends on the member's own action rule. We further give a sufficient condition under which an agent outside the cluster permanently adopts the cluster's action, and we iterate it to obtain a cascade of agents that are guaranteed to adopt that action. Finally, numerical examples show that replacing heterogeneous thresholds by their mean can change both the propagation of an action and the presence of robust action clusters.

0.20

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.62
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

Fast and Scalable Influence Estimation in the Independent Cascade Model: a unified framework

cs.SI ·2026-10-23 ·Matic Požar, Miklós Krész
benchmark similarity 0.62
Abstract

Computing diffusion processes on networks is fundamental to applications including influence maximization, epidemic modeling, information propagation, and diffusion inference. The Independent Cascade (IC) model is one of the most widely used models of progressive diffusion, yet exact computation of its activation probabilities is #P-hard, while Monte Carlo simulation becomes costly when accurate estimates are required repeatedly. Despite its central role, analytical approximation of the IC diffusion function has received comparatively little systematic attention relative to the extensive literature on influence-maximization algorithms. We present a comprehensive study of analytical approximations for the IC model. We review a wide range of existing approaches and unify them through a common framework based on temporal representation, retained propagation information, and aggregation rule. This perspective exposes connections between previously distinct approximation families and motivates several new methods. We further conduct, to our knowledge, the first large-scale cross-family comparison of analytical IC approximations for node-level marginal activation probabilities. Our benchmark spans real-world and synthetic networks with systematically varied topology, seed-set size, edge-probability model, and diffusion strength. The proposed second-order dynamic message-passing method achieves the lowest pooled median error and the lowest dataset- or graph-family-level median error on every network considered. The results reveal systematic differences between approximation families, identify regimes in which higher-order corrections are most beneficial, and establish analytical IC approximation as a rich accuracy-efficiency design space rather than a collection of isolated methods.

0.15

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.61
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

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.61
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

Disparity in Influence: A Fairness Evaluation of Centrality Measures in Complex Networks

cs.SI ·2026-11-15 ·Kirtidev Mohapatra, Harsh Vardhan Singh, Rishi Ranjan Singh, Akrati Saxena
similarity 0.59
Abstract

Social networks are shaped by homophily-driven connections, which naturally lead to the emergence of communities with uneven sizes and influence. Such structural imbalances impact the fairness of network analysis tools, particularly centrality measures that are widely used to identify influential nodes for tasks like information diffusion and network robustness. In this work, we conduct a comprehensive assessment of fairness in centrality measures, using influence spreading across networks with heterogeneous community structures. We first analytically show that disparity is bounded by outreach; cross-community outreach is bounded by the inter-community cut; and when all seeds lie in one community, disparity approaches the normalized outreach within that community as cross-community transmission vanishes. This explains why attenuation concentrates influence in the community where diffusion starts. We further evaluate a broad spectrum of centrality measures, including local, semi-local, global, and community-aware measures, on both synthetic network generative models and real-world datasets, using the Independent Cascade and Linear Threshold Models. The results consistently show that influence tends to concentrate within larger communities, with disparities becoming more pronounced under constrained or deterministic diffusion settings. We further observe that fairness is highly sensitive to the choice of centrality measure rather than its general category. In particular, fairness-aware adaptations of PageRank demonstrate a strong balance between maximizing influence reach and maintaining equitable distribution across communities. On real networks, these conclusions are largely stable under random removal or addition of up to 3% of the edges. Our findings highlight the need to explicitly account for fairness when designing and selecting centrality-based strategies in networked systems.

0.19

Maximizing Social Influence in Almost Linear Time

cs.DS cs.GT ·2026-09-28 ·Saeed Seddighin
similarity 0.58
Abstract

Influence maximization is a central algorithmic challenge in network analysis, aiming to identify a set of $k$ seed nodes in a graph with $n$ nodes and $m$ edges that maximizes the expected cascade of information under standard diffusion models. The seminal work of Borgs, Brautbar, Chayes, and Lucier (SODA'14) yielded a fundamental breakthrough\footnote{The conference version of their paper originally claimed a runtime of $\tilde O_ε(n+m)$, but this was subsequently corrected to a runtime of $\tilde O_ε((n+m)k)$ in an updated version of the paper that is available online. We validate the necessity of this additional factor $k$ in Section~\ref{sec:lowerbound} by demonstrating that if their algorithm is restricted to a runtime budget of $\tilde{O}_ε(n+m)$, the approximation ratio deteriorates to $O(k^{-1/4})$.} for this problem by achieving an $\tilde O_ε((n+m)k)$ time algorithm for approximating the solution within a factor of $1-1/e-ε$. In the years since, numerous efforts have attempted to improve the runtime of this algorithm; however, these works have been successful in only shaving logarithmic factors or improving the dependence on $ε$, leaving the existence of an almost linear-time algorithm as an open question. In this work, we resolve this long-standing open question. We present a novel algorithm that approximates the influence maximization problem within a factor of $1-1/e-ε$ in time $\tilde{O}_ε(n+m)$, effectively removing the multiplicative dependence on $k$ from the time complexity.

0.30