Paper deep dive
Intervention problems in the Linear Threshold Model: A general formulation and new results
Giacomo Como, Fabio Fagnani, Stephane Durand
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 9/16/2026, 7:34:10 AM
Summary
This paper investigates the optimal intervention problem in Linear Threshold Models (LTM), where a planner modifies agent thresholds at a cost to ensure global convergence to an all-active state. The authors introduce a combinatorial reformulation using permutations and define a new graph-theoretic quantity, the 'oriented path number,' which determines the optimal cost when thresholds are equal to 1/2. For general thresholds, this quantity provides a key bound on the intervention cost.
Entities (10)
Relation Signals (6)
Giacomo Como → affiliatedwith → Politecnico di Torino
confidence 99% · Giacomo Como1... 1Department of Mathematical Sciences “G.L. Lagrange”, Politecnico di Torino, Italy
Stephane Durand → affiliatedwith → Université Paris-Saclay
confidence 99% · Stephane Durand2... 2LISN, Université Paris Saclay, France.
Fabio Fagnani → affiliatedwith → Politecnico di Torino
confidence 99% · Fabio Fagnani1... 1Department of Mathematical Sciences “G.L. Lagrange”, Politecnico di Torino, Italy
Oriented Path Number → determines → Optimal Intervention Cost
confidence 95% · When thresholds are all equal to 1/2, the optimal cost is shown to coincide with the oriented path number
Oriented Path Number → bounds → Optimal Intervention Cost
confidence 90% · in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost.
Linear Threshold Model → introducedby → Granovetter
confidence 90% · This model can be interpreted as the best response dynamics... first introduced by Granovetter for fully mixed systems [12]
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study an optimal intervention problem for linear threshold models. This is a popular class of dynamical network systems whereby a number of agents, identified with the nodes of a graph, strategically change their binary action (0 or 1) according to a threshold rule. Specifically, an agent adopts action 1 if and only if the fraction of its neighbors in the interaction graph that do so is greater than or equal to a prescribed threshold. Assuming that a planner can modify the agents' thresholds at a cost equal to the aggregate threshold increase, we study the minimum intervention cost needed to ensure global convergence to the all-1 configuration. Our main contribution is the introduction of a new graph-theoretic quantity, called oriented path number, that is the minimum number of disjoint paths needed to cover the graph that can be oriented to form a directed acyclic graph. When thresholds are all equal to 1/2, the optimal cost is shown to coincide with the oriented path number, whereas, in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost.
Tags
Links
- Source: https://arxiv.org/abs/2609.17146v1
- Canonical: https://arxiv.org/abs/2609.17146v1
Trouble viewing inline? Open PDF directly →
Full Text
41,001 characters extracted from source content.
Expand or collapse full text
Intervention problems in the Linear Threshold Model: a general formulation and new results This work is dedicated to the memory of Sanjoy K. Mitter. Giacomo Como1, Stephane Durand2, Fabio Fagnani1 1Department of Mathematical Sciences “G.L. Lagrange”, Politecnico di Torino, Italy 2LISN, Université Paris Saclay, France. Abstract. We study an optimal intervention problem for linear threshold models. This is a popular class of dynamical network systems whereby a number of agents, identified with the nodes of a graph, strategically change their binary action (00 or 11) according to a threshold rule. Specifically, an agent adopts action 11 if and only if the fraction of its neighbors in the interaction graph that do so is greater than or equal to a prescribed threshold. Assuming that a planner can modify the agents’ thresholds at a cost equal to the aggregate threshold increase, we study the minimum intervention cost needed to ensure global convergence to the all-11 configuration. Our main contribution is the introduction of a new graph-theoretic quantity, called oriented path number, that is the minimum number of disjoint paths needed to cover the graph that can be oriented to form a directed acyclic graph. When thresholds are all equal to 1/21/2, the optimal cost is shown to coincide with the oriented path number, whereas, in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost. Keywords. Network Systems; Linear threshold model; Optimal intervention; Least-cost influence problem. 2020 Mathematics Subject Classification. 90C35, 93A16, 90C27. †footnotetext: E-mail addresses: giacomo.como@polito.it (G. Como), stephane.durand@universite-paris-saclay.fr (S. Durand), fabio.fagnani@polito.it (F. Fagnani). 1. Introduction A prominent feature of network systems is the possible emergence of contagion evolutions in response to localized external shocks. The core of this phenomenon lies in the interplay between the nature of the single agents’ dynamics and the topology of their interaction. A key issue in this regard is to find simple indices capable of measuring the propensity of a system to such behavior and, in a complementary way, of measuring its resilience. Considerable progress has been made for models with pairwise interactions such as, e.g., epidemics and gossip models. For many of them, a reasonably complete theory is available [9], which shows how the extent and the speed of a contagion spreading is essentially related to the Cheeger constant of the underlying interaction network. In these models, a basic straightforward fact is that the addition of connectivity in the graph always increases the propensity for contagion to spread. Pairwise interactions, however, are often inadequate for modelling strategic behaviour in network systems. Examples include, for instance, the spread of innovations or new technologies in social and economic networks or contagion dynamics in financial networks. A popular model in such contexts is the Linear Threshold Model (LTM) of cascades first introduced by Granovetter for fully mixed systems [12] and later extended in various directions [20, 25, 24, 10]. This model can be interpreted as the best response dynamics in a network game whereby agents choose strategically between two actions (00 and 11) and their payoff is an increasing function of the number of their neighbors choosing the same action. Various studies of the LTM model [20, 3, 16, 19, 23, 22, 18] have investigated topological conditions guaranteeing or preventing a full contagion (i.e., a configuration where all agents choose action 11) starting from an initial condition of relatively few agents choosing action 11. Most of these studies concern random networks of a specific type. A remarkable exception is [20] that introduces the concept of cohesiveness, which, for general graphs, can in principle characterize the extent of a spreading phenomenon. Though simple and conceptually elegant, this index is unfortunately not easy to be computed and thus of limited help in the determination of the network properties mostly responsible for triggering cascade propagations. Optimal seeding problems have been studied for LTM: most of them basically consist in forcing a certain number of agents to activate in order to finally maximize in some sense the spread of the activated agents. The optimization problems can be formulated as the problem of targeting a fixed number K of agents so that, if activated, they yield the maximal possible expansion of the contagion [15, 5, 11] . A complementary possibility is the minimal targeting problem that is the determination of the minimum number of agents that, if activated, will lead to a full cascade [2]. Both problems are known to be NP-complete and suboptimal algorithms have been proposed. The problem has also been tackled in the statistical physics literature [1, 13, 21]. In this paper, we propose and study a fundamental intervention problem for LTM models. We imagine that an external planner can intervene on the system by injecting energy in the various agents so as to modify their thresholds. The optimization problem we consider is to find the minimal-cost intervention needed to trigger a full cascade. The problem is fundamentally different from the classical seeding problems as the cost of the intervention depends on continuous parameters instead of just combinatorial ones. In many applications, modeling the intervention in this way turns out to be a more natural choice (e.g., an agent with a very high threshold of activation needs more external energy to push its activation). The minimal-cost intervention problem for the LTM has been recently investigated in [7], where approximate solutions for large-scale networks have been studied. Our first contribution is to show that our optimal problem can be equivalently reformulated as a combinatorial optimization problem on the group of permutations of the set of agents. The idea behind this is that each permutation describes a possible order of activation of the agents for which the minimum intervention cost can be directly computed. In this way, the problem becomes finding the permutation that minimizes the cost. While, not too surprisingly, the derived combinatorial optimization problem is NP-complete (the proof will be proposed elsewhere), fundamental insight can be gained on the problem by exploiting the network structure. 2. The model The linear threshold model (LTM) is one of the most studied models of cascading propagation in networks. It was originally proposed in [12] for fully mixed populations and since then many similar models have been studied. The core of the model and of most of its generalizations can be described as follows. Consider a directed weighted graph =(,ℰ,W)G=(V,E,W) where =1,…,nV=\1,…,n\ is the set of nodes representing interacting agents, ℰ⊆×E ×V is the set of links, and W in ℝ+n×nR_+^n× n is the weight matrix. We require that Wij>0W_ij>0 if and only if (i,j)∈ℰ(i,j) and denote by wi=∑jWijw_i= _jW_ij the weighted degree of node i and let W∗=12∑iwiW^*= 12 _iw_i. In the case when Wij∈0,1W_ij∈\0,1\ for every i,ji,j, we call the graph unweighted. In this case the matrix W coincides with the adjacency matrix of the underlying graph (,ℰ)(V,E), wiw_i is the degree of the node i. If G is a graph, let ↔=(,ℰ↔)G =(V,E ) denote the undirected completion of G formally defining its set of links as ℰ↔=(i,j)∈×|(i,j),(j,i)∩ℰ≠∅.E =\(i,j) ×V\,|\,\(i,j),(j,i)\ ≠ \\,. We identify the nodes of the graph with agents and define a class of discrete-time dynamics where each agent chooses between action 00 and 11 according to the following mechanism. Consider threshold maps fα:ℝ+→[0,1]f_α:R_+→[0,1] fα(x)=0ifx<α1ifx≥α,f_α(x)= \ array[]l0& if\;x<α\\ 1& if\;x≥α\,, array . and consider the following update rule: xi(t+1)=fθiwi(∑jWijxj(t))∀i=1,…,n.x_i(t+1)=f_ _iw_i (Σ _jW_ijx_j(t) ) ∀ i=1,…,n\,. (2.1) The value θi _i in [0,1][0,1] is called the threshold of node i. In words, at every time instant, an agent adopts action 11 if and only if the total weight of links connecting node i to neighbors already adopting action 11 at the previous time exceeds or equals the value θiwi _iw_i. We can compactly represent (2.1) as a dynamical system on 0,1n\0,1\^n: (t+1)=F((t))x(t+1)=F(x(t)) (2.2) An equilibrium point of (2.2) is any z in 0,1n\0,1\^n such that F(z)=zF(z)=z. In this paper, we consider an intervention problem where an external planner can modify the nodes’ thresholds. Formally, given a vector h in ℝ+nR_+^n (to be referred to as the intervention vector), we consider the modified dynamics xi(t+1)=fθiwi−hi(∑jWijxj(t)),x_i(t+1)=f_ _iw_i-h_i (Σ _jW_ijx_j(t) )\,, (2.3) compactly represented as x(t+1)=F(x(t)).x(t+1)=F_h(x(t))\,. (2.4) Consider the related evolution x(t)=Ft(x(0))x(t)=F^t_h(x(0)) starting from a generic initial condition x(0)x(0) and define an intervention h as successful when the evolution converges to the all-11 vector, from every initial condition. Formally, let the set of successful interventions be ℋ=∈ℝ+n|limt→+∞(t)=,∀(0)∈0,1n.H= \h _+^n\,|\, _t→+∞x(t)=1,\; (0)∈\0,1\^n \\,. (2.5) Proposition 2.1. The following facts hold: (a) For (0)=0x(0)=0, the limit l=limt→+∞(t)l= _t→+∞x(t) exists and x(t)=lx(t)=l for t≥nt≥ n; (b) ℋ=∈ℝ+n|(n)=for(0)=0H= \h _+^n\,|\,x(n)=1\; for\,x(0)=0 \. Proof. Consider the standard partial order on ℝnR^n whereby, for two vectors x and y in ℝnR^n, we write that ≤x if xi≤yix_i≤ y_i for every 1≤i≤n1≤ i≤ n and notice that F_h is monotonically nondecreasing with respect to such order. This implies that, since F()≥F_h(0) 0, then (t)=Ft()x(t)=F^t_h(0) is monotonically nondecreasing and thus converges to a limit. Moreover, since every entry of x(t)x(t) changes value at most once, by time t=nt=n, we have reached a point for which Ft()=Ft+1()F^t_h(0)=F^t+1_h(0). From that point on, the sequence is stationary. This proves point (a). Since F_h is monotonically nondecreasing, we have that Ft((0))≥Ft()∀t,∀(0)F^t_h(x(0))≥ F^t_h(0) ∀ t,\, (0) This yields point (b). ∎ We assume that every agent i is equipped with a non-decreasing lower semicontinuous cost function Ci:ℝ+→ℝ+C_i:R_+ _+: we interpret Ci(hi)C_i(h_i) as the cost incurred by the external planner to lower the threshold of agent i of a value hih_i. We gather all cost functions in a vector denoted by C. We formulate the following optimization problem. C∗(,θ,)=min∑iCi(hi)|∈ℋ.C^*(G,θ,C)= \Σ _iC_i(h_i)\,|\,h \\,. (2.6) From representation (b) in Proposition 2.1 and the fact that ↦Fn(0)h F^n_h(0) is a continuous map, we have that ℋH is a compact set. This implies that the minimum above always exists. We refer to the triple (,θ,)(G,θ,C) as to the linear threshold model (LTM) over G with threshold vector θ and vector of cost functions C and to the optimal value C∗(,θ,)C^*(G,θ,C) as to the least activation cost of the LTM (,θ,)(G,θ,C). A special choice of the cost functions leads to a model largely analyzed in the literature. This is the case in which cost functions have the form Ci(x)=cix>0C_i(x)=c_i1_x>0, that is any nonzero intervention on an agent has the same cost. In this case, we can restrict to interventions h where hi∈0,θih_i∈\0, _i\ for the minimization problem (2.6). Such an intervention h can be identified with the subset =i|hi>0W=\i\,|\,h_i>0\ of agents on which the intervention is active. W is called the target set and problem (2.6) is called the target set selection problem (when ci=c_i=c for every i) or, when this homogeneity assumption does not hold, the weighted target set selection problem. This problem has been introduced and studied in [4, 6] where its NP-completeness was proven. In [2], for a more general model encompassing the LTM, a low complexity algorithm for an approximate solution of the weighted target set selection problem was proposed. This approach has then been extended to non-binary super-modular games in [17]. Another special case analyzed in the literature is when the cost functions Ci(x)=cixC_i(x)=c_ix are linear. In [8, 14] the problem has been introduced under the name of least cost influence problem LCIS. Also in this case, the problem is shown to be NP-complete. Further complexity results are proven showing NP-completeness on special families of graphs (e.g., bipartite graphs, trees) and also establishing hardness-of-approximation results. In next section, we show how the general problem (2.6) can be reformulated as a pure combinatorial optimization problem, for every choice of the cost functions. Thereafter, we focus on the least cost influence problem: we present new bounds and a number of examples where an analytical solution can be found. 3. A combinatorial reformulation of the problem In this section, we reformulate the least cost influence problem (2.6) as an optimization problem on the group of permutations of the node set V. This allows us to introduce a number of concepts and energy interpretations that turn out to play a crucial role in the rest of our analysis. Inspired by typical evolutions studied in game theory, where agents modify their behavior unilaterally, best-responding to the strategies of the other agents, we investigate here similar dynamics. Assume that all agents initially adopt action 00 and then update their action one at a time and only once each, as the output of their threshold function fθiwi−hif_ _iw_i-h_i applied to the output of the previously activated agents. Let nS_n be the group of permutations over the agent set =1,…,nV=\1,…,n\. The activation order is determined by the choice of a permutation σ in nS_n. For 1≤t≤n1≤ t≤ n, the following expression is computed fθσtwσt−hσt(wσt(σ)),f_ _ _tw_ _t-h_ _t(w_ _t(σ))\,, where wσt(σ)=∑1≤s<tWσtσs,w_ _t(σ)=Σ _1≤ s<tW_ _t _s\,, (3.1) is the total weight of links connecting agent σt _t to previously activated agents. Given the permutation σ, the minimum value of the intervention hσth_ _t that allows agent σt _t to adopt action 11 is given by hσt(σ)=θσtwσt−wσt(σ).h_ _t(σ)= _ _tw_ _t-w_ _t(σ)\,. (3.2) We assemble these values into a vector (σ)h(σ) in ℝ+nR_+^n to be referred to as the minimum intervention vector associated with σ. Notice that some entries of (σ)h(σ) may be negative. We define the minimum cost associated with the permutation σ as C(σ)=∑1≤i≤nCi([hi(σ)]+)=∑1≤i≤nCi([θiwi−wi(σ)]+)C(σ)=Σ _1≤ i≤ nC_i([h_i(σ)]^+)=Σ _1≤ i≤ nC_i([ _iw_i-w_i(σ)]^+) (3.3) where [x]+=max0,x[x]^+= \0,x\ denotes the positive part of a scalar x. The optimal activation cost computed in this way coincides with the one computed through the synchronous LTM dynamics defined by iterations of the map F_h. Proposition 3.1. For every LTM (,θ)(G,θ), it holds that C∗(,θ)=minσ∈nC(σ)C^*(G,θ)= _σ _nC(σ) (3.4) Proof. We first show that for every permutation σ in nS_n, we have that (σ)∈ℋh(σ) . First, we prove by induction that, for every 0≤t≤n0≤ t≤ n, x(t)≥δσ1+⋯+δσt.x^h(t)≥δ _1+·s+δ _t\,. (3.5) For t=0t=0, relation (3.5) trivially holds true. Moreover, if (3.5) holds true for some t≥0t≥ 0, then, by definition of (σ)h(σ), x(t+1)σt+1=fwσt+1(σ)((Wx(t))σt+1)≥fwσt+1(σ)(wσt+1(σ))=1.x^h(t+1)_ _t+1=f_w_ _t+1(σ)((Wx^h(t))_ _t+1)≥ f_w_ _t+1(σ)(w_ _t+1(σ))=1\,. Since x(t+1)≥x(t)x^h(t+1)≥ x^h(t), this yields relation (3.5) for t+1t+1. Relation (3.5) for t=nt=n implies that (σ)∈ℋh(σ) . By definition, this yields ≤ in formula (3.4). To see that the converse inequality holds true as well, for every h in ℋH, we construct a permutation σ^h in nS_n as follows. Start with (0)=x(0)=0 and, for t=1,…,nt=1,…,n choose iti_t in V such that xit(t−1)=0x_i_t(t-1)=0 and fwitθit+hit(∑jWitjxj(t−1))=1f_w_i_t _i_t+h_i_t( _jW_i_tjx_j(t-1))=1 and put (t)=(t−1)+δit,σt=it.x(t)=x(t-1)+δ^i_t\,, σ^h_t=i_t\,. Notice that such iti_t exists for every 1≤t≤n1≤ t≤ n for otherwise F((t−1))=(t−1)≠F_h(x(t-1))=x(t-1) 1 and ∉ℋh . Moreover, by construction, is≠iti_s≠ i_t for every s≠ts≠ t so that σ^h is indeed a permutation in nS_n. Now, observe that (σ)≤h(σ^h) , so that C(σ)≤∑ihiC(σ^h)≤ _ih_i. By the arbitrariness of h in ℋH this implies that minσ∈nC(σ)≤min∈ℋC(σ)≤min∑i∈ℋhi=C∗(,θ), _σ _nC(σ)≤ _h C(σ^h)≤ _h Σ _ih_i=C^*(G,θ)\,, thus completing the proof. ∎ The set of permutations for which the cost is optimal is denoted (,θ)∗S_(G,θ)^* and we refer to each of them as to an optimal permutation activation. 4. General bounds for the LCIS problem In the rest of this work, we restrict to the case when Ci(x)=cixC_i(x)=c_ix. Since the combinatorial function to optimize C(σ)C(σ) can be rewritten as follows C(σ)=∑1≤i≤nci[θiwi−wi(σ)]+=∑1≤i≤n[θiciwi−ciwi(σ)]+,C(σ)=Σ _1≤ i≤ nc_i[ _iw_i-w_i(σ)]^+=Σ _1≤ i≤ n[ _ic_iw_i-c_iw_i(σ)]^+\,, an equivalent optimization problem can be obtained by changing c to 1 and W to [c]W[c]W. Therefore, from now on we assume that ci=1c_i=1 for every i and thus focus on the combinatorial optimization problem min∑1≤i≤nσ∈nci[θiwi−wi(σ)]+. _σ _nΣ _1≤ i≤ nc_i[ _iw_i-w_i(σ)]^+\,. (4.1) The optimization problem admits the following energy interpretation. For an agent i to be activated, a minimum energy θi _i is needed as input. When a specific permutation σ is chosen, an agent i, at the moment of its activation, receives an amount of energy wi(σ)w_i(σ) from the other previously activated agents and what is left (θiwi−wi(σ))+( _iw_i-w_i(σ))^+ needs to be provided by the external intervention. A strategy, generally suboptimal, is that of maximizing the energy received by previously activated nodes, namely, to consider W∗=max∑i=1nσ∈nwi(σ).W^*= _σ _nΣ _i=1^nw_i(σ)\,. (4.2) Proposition 3.1 yields the following simple bounds (∑i∈θiwi−W∗)+≤C∗(,θ)≤∑i∈θiwi. (Σ _i _iw_i-W^* )^+≤ C^*(G,θ)≤Σ _i _iw_i\,. (4.3) Both bounds can be achieved. Notice that the upper bound corresponds to the cost of an intervention when wi(σ)=0w_i(σ)=0 for every i and is trivially achieved when the agents are totally isolated Wij=0W_ij=0 for every i≠ji≠ j. The lower bound represents instead the cost of an intervention when wi(σ)≤θiwiw_i(σ)≤ _iw_i for every agent i for a permutation maximizing (4.2). This happens for instance in the extreme case where θi=1 _i=1 for every i. Both bounds can be improved. To this aim, we consider the decomposition of the graph G into its connected components, and we denote by k=(k,ℰk)G_k=(S_k,E_k) for k=1,…,qk=1,…,q the sink ones. We put q=q_G=q and we define ik∗∈argmini∈kθiwi,k=1,…,q,ρ=∑k=1qθik∗wik∗,∗=ik∗|k=1,…,qi^*_k∈ _i _k _iw_i, k=1,…,q, ρ=Σ _k=1^q _i^*_kw_i^*_k, ^*=\i^*_k\,|\,k=1,…,q\ (4.4) We now introduce the two values Cmax(,θ)=ρ+∑i∈∖∗(θiwi−w)+,Cmin(,θ)=ρ+(∑i∈∖∗θiwi−W∗)+C^max(G,θ)=ρ+Σ _i ^*( _iw_i-w)^+, C^min(G,θ)=ρ+ (Σ _i ^* _iw_i-W^* )^+ (4.5) and the following set of permutations. Definition 4.1. Given a graph G, a permutation σ is called G-greedy if σt∈⋃s<tNσs− _t∈ _s<tN^-_ _s (4.6) but for the first q_G values of t. Proposition 4.2. Given a graph G, the following facts hold: (1) G-greedy permutations exist (2) For every G-greedy permutation σ, we have that C(σ)≤Cmax(,θ)C(σ)≤ C^max(G,θ). Proof. 1. To prove the existence of G-greedy permutations, it is sufficient to choose arbitrarily σt∈t _t _t for t=1,…,qt=1,…,q and then, successively, to choose the remaining elements imposing (4.6). The fact that this is possible is equivalent to the assumption that no connected component of G different from kG_k for k=1,…,qk=1,…,q is a sink component. 2. If σ is a G-greedy permutation, then wt(σ)≥w_t(σ)≥ w for every t>qt>q and thus C(σ)=∑t=1n(θσtwσt−wt(σ))+=ρ+∑t>q(θσtwσt−wt(σ))+≤ρ+∑t>q(θσtwσt−w)+=Cmax(,θ) array[]rclC(σ)&=&Σ _t=1^n( _ _tw_ _t-w_t(σ))^+\\ &=&ρ+Σ _t>q( _ _tw_ _t-w_t(σ))^+\\ &≤&ρ+Σ _t>q( _ _tw_ _t-w)^+\\ &=&C^max(G,θ) array ∎ We denote by ngS_n^g the subset of the G-greedy permutations. The following result holds. Corollary 4.3 (Basic bound). For the LTM (,θ)(G,θ) on a graph =(,ℰ,W)G=(V,E,W) of order n with θi>0 _i>0 for every i: Cmin(,θ)≤C∗(,θ)≤Cmax(,θ).C^min(G,θ)≤ C^*(G,θ)≤ C^max(G,θ)\,. (4.7) Proof. We only need to prove the lower bound. This follows from the observation that for any permutation σ, the external planner must pay in full for at least q times, each time that it chooses for the first time a node in kS_k for k=1,…,qk=1,…,q. Precisely, define tk∗=mint|σt∈k,=t1∗,…,tq∗,∗=1,…,q∖t^*_k=min\t\,|\, _t _k\, =\t^*_1,…,t^*_q\, ^*=\1,…,q\ The following inequalities hold. C(σ)=∑t∈θσtwσt+∑t∈∗(θσtwσt−wt(σ))+≥OPEN∑t∈θσtwσt+(∑t∈∗θσtwσt−∑t∈∗wt(σ))+) array[]rclC(σ)&=&Σ _t _ _tw_ _t+Σ _t ^*( _ _tw_ _t-w_t(σ))^+\\ &≥&Σ _t _ _tw_ _t+ (Σ _t ^* _ _tw_ _t-Σ _t ^*w_t(σ))^+ )\\ array Since, by construction, ∑t∈θσtwσt≥ρΣ _t _ _tw_ _t≥ρ and ∑t∈θσtwσt+∑t∈∗θσtwσt=∑i∈θiwi=ρ+∑i∈∖∗θiwiΣ _t _ _tw_ _t+Σ _t ^* _ _tw_ _t=Σ _i _iw_i=ρ+Σ _i ^* _iw_i the left-hand side inequality in (4.7) follows. ∎ There is a case where the bounds coincide and equal the least cost intervention. Proposition 4.4. Let =(,ℰ,W)G=(V,E,W) be an unweighted graph of order n and let θ∈(0,1]nθ∈(0,1]^n be a threshold vector such that θiwi≤1 _iw_i≤ 1 for every i. Then, Cmin(,θ)=Cmax(,θ)=C∗(,θ)=ρC^min(G,θ)=C^max(G,θ)=C^*(G,θ)=ρ (4.8) Moreover, any G-greedy permutation is optimal. Proof. Since W∗≥n−qW^*≥ n-q on every unweighted graph with q sink connected components, we obtain that Cmin(,θ)=Cmax(,θ)=ρC^min(G,θ)=C^max(G,θ)=ρ. Moreover, if σ is a G-greedy permutation, then wt(σ)≥1w_t(σ)≥ 1 for every t>qt>q and formula (3.3) yields C(σ)=ρC(σ)=ρ. ∎ Example 4.5 (Directed Acyclic Graphs). Consider any DAG G over the set of nodes =1,2,…,nV=\1,2,…,n\ and any threshold vector θ. Each of the q=q=q_G sink components are in this case composed of a single element: denote them by i1∗,…,iq∗i^*_1,…,i^*_q. As wik∗=0w_i^*_k=0 for k=1,…,qk=1,…,q, we obtain that ρ=0ρ=0. Since G is a DAG, we can find a total order of the nodes k1<k2<⋯<knk_1<k_2<·s<k_n such that for every i,j∈1,…,ni,j∈\1,…,n\, Wkikj>0W_k_ik_j>0 implies i>ji>j. If we now choose σt=kt _t=k_t for every t, we have that wkt(σ)=wktw_k_t(σ)=w_k_t for every t=1,…,nt=1,…,n. Consequently, C(σ)=ρ=0C(σ)=ρ=0. Such a permutation is thus optimal and C∗(,θ)=0C^*(G,θ)=0. 5. LCIS over undirected graphs In this section, we analyze in greater detail the case when the underlying graph G is undirected. A striking result is that in this case the maximization problem in (4.2) is trivial as all permutations σ reach the same value. Precisely, the following conservation law holds. Proposition 5.1. For every undirected weighted graph =(,ℰ,W)G=(V,E,W) of order n, W∗=12∑i∈wiW^*= 12Σ _i w_i Moreover, for every permutation σ in nS_n, ∑iwi(σ)=W∗∑ihi(σ)=∑iθiwi−W∗.Σ _iw_i(σ)=W^* Σ _ih_i(σ)=Σ _i _iw_i-W^*\,. (5.1) Proof. From (3.1) we obtain ∑iwi(σ)=∑1≤t≤nwσt(σ)=∑1≤s<t≤nWσtσs=12∑1≤t≤n∑1≤s≤nWσtσs=12∑iwi,Σ _iw_i(σ)=Σ _1≤ t≤ nw_ _t(σ)=Σ _1≤ s<t≤ nW_ _t _s= 12Σ _1≤ t≤ nΣ _1≤ s≤ nW_ _t _s= 12Σ _iw_i\,, This proves the first formula. The second one is a direct consequence of (3.2) and previous formula. ∎ Symmetry of the interaction among the agents (following from the assumption that W is symmetric) yields an interesting reversibility with respect to a transformation in which agents exchange their thresholds θi _i with the complementary ones 1−θi1- _i. Precisely, for every permutation σ in nS_n, we define the reversed permutation σ¯ σ as σ¯i=σn−i+1,1≤i≤n. σ_i= _n-i+1\,, 1≤ i≤ n\,. The cost of the permutation σ for the LTM (,θ)(G,θ) turns out to be intimately connected to the cost of σ¯ σ for the reversed LTM (,−θ)(G,1-θ). This is clearly stated below. Lemma 5.2. Consider an LTM (,θ)(G,θ) and indicate with C and C¯ C, respectively, the cost functions related to (,θ)(G,θ) and to the reversed LTM (,−θ)(G,1-θ). Then, for every permutation σ in nS_n, C¯(σ¯)=C(σ)−∑i∈θiwi+W∗ C( σ)=C(σ)-Σ _i _iw_i+W^* (5.2) Proof. The key point is to observe that the definition of the reversed permutation σ¯ σ yields wi(σ¯)=wi−wi(σ)w_i( σ)=w_i-w_i(σ). This yields C¯(σ¯)=∑i[(1−θi)wi−wi(σ¯)]+=∑i[θiwi−wi(σ)]−=∑i[θiwi−wi(σ)]+−∑i(θiwi−wi(σ))=C(σ)−(∑iθiwi−W∗), array[]rcl C( σ)&=&Σ _i[(1- _i)w_i-w_i( σ)]^+\\[3.0pt] &=&Σ _i[ _iw_i-w_i(σ)]^-\\[3.0pt] &=&Σ _i[ _iw_i-w_i(σ)]^+-Σ _i( _iw_i-w_i(σ))\\[3.0pt] &=&C(σ)-(Σ _i _iw_i-W^*)\,, array thus proving the result. ∎ Previous result yields a direct connection between the optimization problems relative to the two LTM (,θ)(G,θ) and (,−θ)(G,1-θ). Corollary 5.3 (reversal). Consider an LTM (,θ)(G,θ). Then, C∗(,θ)=C∗(,−θ)−∑i∈θiwi+W∗C^*(G,θ)=C^*(G,1-θ)-Σ _i _iw_i+W^* and σ∈(,θ)∗⇔σ¯∈(,−θ)∗σ _(G,θ)^*\; \; σ _(G,1-θ)^* Proof. Direct consequence of Lemma 5.2. ∎ 5.1. Some basic examples In this subsection, we carry on some exact computation for some simple basic topologies. Throughout this section, we stick to undirected graphs =(,ℰ,W)G=(V,E,W) where Wij∈0,1W_ij∈\0,1\ for every i,ji,j. In this case we refer to G as to an unweighted graph: in this case wiw_i coincides with the degree of node i, namely the cardinality of the neighborhood NiN_i of node i. Example 5.4 (Line and Ring graphs). Consider the line graph LnL_n or the ring graph RnR_n over the set =1,2,…,nV=\1,2,…,n\. Assuming that nodes are numbered in the usual way, as in the top part of Figure 1, the cost of the identity permutation σ=idσ=id for any LTM over LnL_n or RnR_n can be computed as follows C(id)=w1θ1+∑i=2n−1[2θi−1]+C(id)=w_1 _1+Σ _i=2^n-1[2 _i-1]^+ (5.3) Notice that w1=1w_1=1 in the case of a line while w1=2w_1=2 in the case of a ring. In the special case when θi=θ≤1/2 _i=θ≤ 1/2 for all i, we have that C(id)=w1θ1=minwiθiC(id)=w_1 _1= \w_i _i\ and Proposition 4.4 implies that idid is an optimal permutation. The mechanism underlying this result is the following: once the first agent becomes active, the topological structure of the line together with the fact that the threshold is below 1/21/2 leads to a cascade effect that activates the entire line without requiring further intervention energy. If thresholds are different, the identity permutation is in general not optimal. There are two special cases where an exact solution can nevertheless be obtained. This occurs when thresholds are either all below or all above 1/21/2. In the first case, θi≤1/2 _i≤ 1/2 for every i, by Proposition 4.4, we obtain that any permutation satisfying (4.6) is optimal. In particular idid is optimal if and only if w1θ1=minwiθiw_1 _1= \w_i _i\. We now use Corollary 5.3 to solve the case when θi≥1/2 _i≥ 1/2 for all i. The optimal permutation is given by any σ∗σ^* such that σ∗¯ σ^* is the optimal permutation for the model with complementary thresholds 1−θi1- _i. This implies that σ∗σ^* is characterized as follows. σn∗=argmini∈((1−θi)wi),σk∗∈(⋃h≥k+1Nσh∗)∖σk+1∗,…,σn∗σ^*_n= _i ((1- _i)w_i), σ^*_k∈ ( _h≥ k+1N_σ^*_h ) \σ^*_k+1,…,σ^*_n\ Notice that σ1∗σ^*_1 is not necessarily an agent minimizing θiwi _iw_i and σ∗σ^* not necessarily is a G-greedy permutation. Using formula (5.2), the cost of this permutation is given by C(σ∗)=mini∈(1−θi)wi−2∑i∈(1−θi−12)=mini∈(1−θi)wi+∑i∈(2θi−).C(σ^*)= _i (1- _i)w_i-2 _i (1- _i- 12 )= _i (1- _i)w_i+ _i (2 _i-1 )\,. Figure 1. The line graph with n=9n=9 Example 5.5 (Trees). Let =(,ℰ,W)G=(V,E,W) be an unweighted tree of order n and let θ be any threshold vector. Assume that θiwi≥1 _iw_i≥ 1 for every i. Notice that W∗=n−1W^*=n-1 in this case. Using definitions (4.5) we obtain that Cmin(,θ)=Cmax(,θ)C^min(G,θ)=C^max(G,θ) and any G-greedy permutation σ is thus optimal and we obtain C(σ)=θσ1wσ1+∑1≤t≤n(θσtwσt−1)=∑i∈θiwi−(n−1)C(σ)= _ _1w_ _1+Σ _1≤ t≤ n( _ _tw_ _t-1)=Σ _i _iw_i-(n-1) Example 5.6 (Complete graph). Consider the complete graph KnK_n. Let θ be any threshold vector and consider any permutation σ∗σ^* in nS_n such that thresholds are in non-decreasing order, namely, h<k⇒θσh∗≤θσk∗.h<k\; _σ^*_h≤ _σ^*_k\,. (5.4) Then σ∗σ^* is an optimal permutation. Indeed, if σ∈nσ _n is any permutation, consider the quantity ∑i∈|θiwi−wi(σ)|=∑1≤k≤n|θσk(n−1)−(k−1)|,Σ _i | _iw_i-w_i(σ)|=Σ _1≤ k≤ n| _ _k(n-1)-(k-1)|\,, (5.5) and notice that if, for some k, it happens that θσk>θσk+1 _ _k> _ _k+1, then it holds |θσk(n−1)−(k−1)|+|θσk+1(n−1)−k|>|θσk+1(n−1)−(k−1)|+|θσk(n−1)−k|.| _ _k(n-1)-(k-1)|+| _ _k+1(n-1)-k|>| _ _k+1(n-1)-(k-1)|+| _ _k(n-1)-k|\,. In other words, if σ does not satisfy condition (5.4), then there exists another permutation that allows to lower the value (5.5). Since the cost can also be written as C(σ)=∑i∈[θiwi−wi(σ)]+=12(∑i∈θiwi−W∗)+12∑i∈|θiwi−wi(σ)|,C(σ)= _i [ _iw_i-w_i(σ)]^+= 12 (Σ _i _iw_i-W^* )+ 12 _i | _iw_i-w_i(σ)|\,, this implies that if a permutation does not satisfy (5.4), it cannot be optimal. As optimal permutations surely exist, they must necessarily be of the form above. Notice moreover that, whenever θσk=θσk+1 _ _k= _ _k+1, inverting the two agents would not modify the cost. This says that all permutations for which the thresholds are in non-decreasing order in the sense of (5.4) are optimal. 6. Conclusion We have introduced and studied a new and natural optimal intervention problem for the linear threshold model. Future research directions include formally proving the complexity of the resulting combinatorial optimization problem and developing approximation algorithms for its solution. References [1] F. Altarelli, A. Braunstein, L. Dall’Asta, R. Zecchina, Optimizing spread dynamics on graphs by message passing, Journal of Statistical Mechanics: Theory and Experiment, 2013 P09011. [2] G. Como, S. Durand, and F. Fagnani, Optimal targeting in super-modular games, IEEE Transactions on Automatic Control, 67 (2022) 6366–6380. [3] H. Amini, Bootstrap percolation and diffusion in random graphs with given vertex degrees, Electronic Journal of Combinatorics, 17 (2010) R25. [4] N. Chen, On the approximability of influence in social networks, SIAM Journal on Discrete Mathematics, 23 (2009) 1400–1415. [5] W. Chen, Y. Yuan, and L. Zhang, Scalable influence maximization in social networks under the linear threshold model, Proceedings of ICDM’10 (2010) 88–97. [6] W. Chen, C. Castillo, L. Lakshmanan, Information and Influence Propagation in Social Networks, Morgan and Claypool Publishers, Williston, VT, 2013. [7] L. Cianfanelli, S. Messina, G. Como, and F. Fagnani, Optimal interventions on the linear threshold model in large-scale networks, Nonlinear Analysis: Hybrid Systems, 61 (2026) 101740. [8] G. Cordasco, L. Gargano, A. A. Rescigno, U. Vaccaro, Optimizing spread of influence in weighted social networks via partial incentives, in (C. Scheideler, ed.) Structural Information and Communication Complexity, vol. 9439, Lecture Notes in Computer Science, Springer, 2015. [9] M. Draief, L. Massoulié, Epidemics and Rumors in Complex Networks. Cambridge University Press, Cambridge, UK, 2010. [10] D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, Cambridge, UK, 2010. [11] A. Goyal, W. Lu, L. Lakshmanan, Simpath: An efficient algorithm for influence maximization under the linear threshold model, Proceedings of ICDM’11 (2011) 211–220. [12] M. Granovetter, Threshold models of collective behavior, American Journal of Sociology, 83 (1978) 1420–1443. [13] A. Guggiola, G. Semerjian, Minimal contagious sets in random regular graphs, Journal of Statistical Physics, 158 (2015) 300–358. [14] D. Günneç, S. Raghavan, R. Zhang, Least-cost influence maximization on social networks, INFORMS Journal on Computing, 32 (2019) 289–302. [15] D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network, Proceedings of KDD’03 (2003) 137–146. [16] M. Lelarge, Diffusion and cascading behavior in random networks, Games and Economic Behavior, 75 (2012) 752–775. [17] S. Messina, G. Como, and F. Fagnani, Optimal intervention in non-binary super-modular games, IEEE Control Systems Letters, 7 (2023) 2353–2358. [18] S. Messina, L. Cianfanelli, G. Como, F. Fagnani, Optimal seeding in large-scale super-modular network games, IEEE Control Systems Letters, 8 (2024) 1811–1816. [19] M. Moharrami, V. Subramanian, M. Liu, M. Lelarge, Impact of community structure on cascades, Proceedings of the 2016 ACM Conference on Economics and Computation (2016) 635–636. [20] S. Morris, Contagion, The Review of Economic Studies, 67 (2000) 57–78. [21] X. S. Pei, J. Shaman, F. Morone, H. Makse, Efficient collective influence maximization in cascading processes with first-order transitions, Scientific Reports, 7 (2017) 45240. [22] C. Ravazzi, G. Como, M. Garetto, E. Leonardi, A. Tarable, Asynchronous semi-anonymous dynamics over large-scale networks, SIAM Journal on Applied Dynamical Systems, 22 (2023) 1300–1343. [23] W. Rossi, G. Como, F. Fagnani, Threshold models of cascades in large-scale networks, IEEE Transactions on Network Science and Engineering, 6 (2019) 158–172. [24] F. Vega-Redondo, Complex Social Networks, Cambridge University Press, Cambridge, UK, 2007. [25] D.J. Watts, A simple model of global cascades on random networks, Proceedings of the National Academy of Sciences, 99 (2002) 5766–5771.