Vineeth S Varma

Irinel Constantin Morarescu

Yezekael Hayel

Analysis and control of multi-leveled opinions spreading in social networks

Keywords: Opinion dynamics, Social computing and networks, Markov chains, agent based models

This paper proposes and analyzes a stochastic multi-agent opinion dynamics model. We are interested in a multi-leveled opinion of each agent which is randomly influenced by the binary actions of its neighbors. It is shown that, as far as the number of agents in the network is finite, the model asymptotically produces consensus. The consensus value corresponds to one of the absorbing states of the associated Markov system. However, when the number of agents is large, we emphasize that partial agreements are reached and these transient states are metastable, i.e., the expected persistence duration is arbitrarily large. These states are characterized using an N-intertwined mean field approximation (NIMFA) for the Markov system. Moreover we analyze a simple and easily implementable way of controlling the opinion in the network. Numerical simulations validate the proposed analysis.

I. INTRODUCTION

The analysis and control of complex sociological phenomena as consensus, clustering and propagation are challenging scientific problem. In the past decades much progress has been made both on the development and the analysis of new models that capture more features characterizing the social network behavior. A possible classification of the existing models can be done by looking at the evolution space of the opinions. Precisely we find models in which the opinions evolve in a discrete set of values, they come from statistical physics, and the most employed are the Ising [START_REF] Ising | Contribution to the theory of ferromagnetism[END_REF], voter [START_REF] Clifford | A model for spatial conflict[END_REF] and Sznajd [START_REF] Sznajd-Weron | Opinion evolution in closed community[END_REF] models. A second class is given by the models that consider a continuous set of opinion's values [START_REF] Degroot | Reaching a consensus[END_REF], [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF], [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF]. While in some models the interaction network is fixed in some others it is state-dependent. Although some studies propose repulsive interactions [START_REF] Altafini | Consensus problems on networks with antagonistic interactions[END_REF] the predominant tendency of empirical studies emphasize the attractive action of the neighbors opinions. We can also emphasize that many studies in the literature focus on the emergence of consensus in social networks [START_REF] Galam | Towards a theory of collective phenomena: Consensus and attitude changes in groups[END_REF], [START_REF] Axelrod | The dissemination of culture: A model with local convergence and global polarization[END_REF], [START_REF] Fortunato | Vector opinion dynamics in a bounded confidence consensus model[END_REF] while some others point out local agreements leading to clustering [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF], [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF].

Most of the existing models including the aforementioned ones share the idea that an individual's opinion is influenced by the opinions of his neighbors. Nevertheless, it is very hard to estimate these opinions and often one may access only a quantized version of them. Following this idea a mix of continuous opinion with discrete actions (CODA) was proposed in [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF]. This model reflects the fact that even if we often face binary choices or actions which are visible *

CRAN

(CNRS-Univ. of Lorraine), Nancy, France, {vineeth.satheeskumar-varma,constantin.morarescu}@univ-lorraine.fr ‡ University of Avignon, Avignon, France. yezekael.hayel@univavignon.fr

This work was partially funded by the CNRS PEPS project YPSOC.

by our neighbors, the opinions evolve in a continuous space of values which are not explicitly visible to the neighbors. A multi-agent system with a CODA model was proposed and analyzed in [START_REF] Chowdhury | Continuous opinions and discrete actions in social networks: a multi-agent system approach[END_REF]. It was shown that this deterministic model leads to a variety of asymptotic behaviors including consensus and clustering.

In [START_REF] Varma | Modeling stochastic dynamics of agents with multi-leveled opinions and binary actions[END_REF] the model in [START_REF] Chowdhury | Continuous opinions and discrete actions in social networks: a multi-agent system approach[END_REF] was reformulated as a discrete interactive Markov chain. One advantage of this approach is that, it also allows analysis of the behavior of infinite populations partitioned into a certain number of opinion classes. Due to the complexity of the opinion dynamics, we believe that stochastic models are more suitable than deterministic ones. Indeed, we can propose a realistic deterministic update rule but many random events will still influence the interaction network and consequently the opinion dynamics. Following the development in [START_REF] Varma | Modeling stochastic dynamics of agents with multi-leveled opinions and binary actions[END_REF] we propose here a continuous-time interactive Markov chain modeling that approximates the model in [START_REF] Chowdhury | Continuous opinions and discrete actions in social networks: a multi-agent system approach[END_REF]. Although the asymptotic behavior of the model can be given by characterizing the absorbing states of the Markov chain, the convergence time can be arbitrarily large and transient but persistent local agreements, called metastable equilibria, can appear. These equilibria are very interesting because they describe the finite-time behavior of the network. Consequently, we consider in this paper an N-intertwined mean field approximation (NIMFA) based approach in order to characterize the metastable equilibria of the Markov system. It is noteworthy that NIMFA was successfully used to analyze and validate some epidemiological models [START_REF] Van Mieghem | Virus spread in networks[END_REF], [START_REF] Trajanovski | Decentralized protection strategies against sis epidemics in networks[END_REF].

In this work, we model the social network as a multi-agent system in which each agent represents an individual whose state is his opinion. This opinion can be understood as the preference of the agent towards performing a binary action, i.e. action can be 0 or 1. These agents are interconnected through an interaction directed graph, whose edge weights represent the trust given by an agent to his neighbor. We propose continuous time opinion dynamics in which the opinions are discrete and belong to a given set that is fixed a priori. Each agent is influenced randomly by the actions of his neighboring agents and consequently influences its neighbors. Therefore the opinions of agents are an intrinsic variable that is hidden from the other agents, the only visible variable is the action. As an example, consider the opinion of users regarding two products red and blue cars. A user may prefer red cars strongly, while some other users might be more indifferent. However, what the other users see (and is therefore influenced by) is only what the user buys, which is the action taken.

The contributions of this paper can be summarized as follows. Firstly, we formulate and analyze a stochastic version of the CODA model proposed in [START_REF] Chowdhury | Continuous opinions and discrete actions in social networks: a multi-agent system approach[END_REF]. Secondly, we characterize the local agreements which are persistent for a long duration by using the NIMFA for the original Markov system. Thirdly, we provide conditions for the preservation of the main action inside one cluster as well as for the propagation of actions. Finally, we study how an external entity can control the opinion dynamics by manipulating the network edge weights. In particular, we study how such a control can be applied to a cluster for preservation or propagation of its opinion. The rest of the paper is organized as follows. Section II introduces the main notation and concepts and provides a description of the model used throughout the paper. The analysis of the asymptotic behavior of opinions described by this stochastic model is provided in Section III. The presented results are valid for any connected networks with a finite number of agents. Moreover Section III contains the description of the NIMFA model and an algorithm to compute its equilibria. In Section IV we emphasize conditions for the preservation of the main action (corresponding to a metastable state) in some clusters as well as conditions for the action propagation, both without any control and in the presence of some control. The results of our work are numerically illustrated in Section V. The paper ends with some concluding remarks and perspectives for further developments. Preliminaries: We use E for the expectation of a random variable, 1 A (x) the indicator function which takes the value 1 when x ∈ A and 0 otherwise, R + the set of non-negative reals and N = {1, 2, . . . } the set of natural numbers..

II. MODEL

Throughout the paper we consider N ∈ N an even number of possible opinion levels, and the set of agents K = {1, 2, . . . , K} with K ∈ N. Each agent i is characterized at time t ∈ R + by its opinion represented as a scalar X i (t) ∈ Θ where Θ = {θ 1 , θ 2 , . . . , θ N } is the discrete set of possible opinions, such that θ n ∈ (0, 1)\{0.5} and θ n < θ n+1 for all n ∈ {1, 2, . . . , N }. Moreover Θ is constructed such that θ N/2 < 0.5 and θ N/2+1 > 0.5. In the following let us introduce some graph notions allowing us to define the interaction structure in the social network under consideration.

Definition 1 (Directed graph): A weighted directed graph G is a couple (K, A) with K being a finite set denoting the vertices, and A being a K × K matrix, with elements a ij denoting the trust given by i on j. We say that agent j is a neighbor of agent i if a ij > 0. We denote by τ i the total trust in the network for agent i as τ i = K j=1 a ij . Agent i is said to be connected with agent j if G contains a directed path from i to j, i.e. if there exists at least one sequence

(i = i 1 , i 2 , . . . , i p+1 = j) such that a i k ,i k+1 > 0, ∀k ∈ {1, 2, . . . , p}.
Definition 2 (Strongly connected): The graph G is strongly connected if any two distinct agents i, j ∈ K are connected.

In the sequel we suppose the following holds true.

Assumption 1: The graph (K, E) modeling the interaction in the network is strongly connected. The action Q i (t) taken by agent i at time t is defined by the opinion X i (t) through the following relation

Q i (t) = X i (t) ,
where . is the nearest integer function. This means that if an agent has an opinion more than 0.5, it will take the action 1 and 0 otherwise. This kind of opinion quantization is suitable for many practical applications. For example, an agent may support the left or right political party, with various opinion levels (opinions close to 0 or 1 represents a stronger preference), however, in the election, the agent's action is to vote with exactly two choices (left or right). Similarly, an agent might have to choose between two cars or other types of merchandise like cola as mentioned in the introduction. Although its preference for one product is not of the type 0 or 1, its action will be, since it cannot buy fractions of cars, but one of them.

A. Opinion dynamics

In this work, we look at the evolution of opinions of the agents based on their mutual influence. We also account for the inertia of opinion, i.e., when the opinion of the agent is closer to 0.5, he is more likely to shift as he is less decisive, whereas someone with a strong opinion (close to 1 or 0) is less likely to shift his opinion as he is more convinced by his opinion. The opinion of agent j may shift towards the actions of its neighbors with a rate β n while X j (t) = θ n . If no action is naturally preferred by the opinion dynamics, then we construct θ n = 1 -θ N +1-n and assume that β n = β N +1-n for all n ∈ {1, 2, . . . , N }. At each time t ∈ R + we denote the vector collecting all the opinions in the network by X(t) = (X 1 (t), . . . , X K (t)). Notice that the evolution of X(t) is described by a continuous time Markov process with N K states and its analysis is complicated even for small number opinion levels and relatively small number of agents. The stochastic transition rate of agent i shifting its opinion to the right, i.e. to have opinion θ n+1 when at opinion θ n , with n ∈ {1, 2, . . . , N -1}, is given by

β n N j=1 a ij 1 (0.5,1] (X j (t)) = β n K j=1 a ij Q j (t) = β n R i (t).
Similarly, the transition rate to the left, i.e. to shift from θ n to θ n-1 is given by

β n N j=1 a ij 1 [0,0.5) (X j (t)) = β n N j=1 a ij (1-Q j (t)) = β n L i (t).
for n ∈ {2, . . . , N }. Therefore, we can write the infinitesimal generator M i,t (a tri-diagonal matrix of size N × N ) for an agent i as:

M i,t =    -β 1 R i (t) β 1 R i (t) 0 . . . β 2 L i (t) -β 2 τ i β 2 R i (t) . . . . . .    (1)
with elements corresponding the n-th rown and m-th column given by M i,t (m, n) and

∀n ∈ {1, . . . , N -1}, M i,t (n, n + 1) = β n R i (t), ∀n ∈ {2, . . . , N }, M i,t (n, n -1) = β n L i (t), ∀|m -n| > 1, M i,t (m, n) = 0 and Mi,t(n, n) =    -β1Ri(t) for n = 1, -βnτi for n ∈ {2, . . . , N -1}, -βN Li(t) for n = N.
Let v i,n (t) := E[1 {θn} (X i (t))] = Pr(X i (t) = θ n ) be the probability for an opinion level θ n for user i at time t. Then, in order to propose an analysis of the stochastic process introduced above, we may consider the mean-field approximation by replacing the transitions by their expectations. Then, the expected transition rate from state n to state n + 1 for K → ∞, is given by:

β n K j=1 a ij E 1 (0.5,1] (X j (t)) = β n K j=1 a ij N n=N/2+1 v j,n (t).
We have similar expression for transition between state n and n -1.

III. STEADY STATE ANALYSIS

Define by θ-= (θ 1 , . . . , θ 1 ) and θ+ = (θ N , . . . , θ N ) the states where all the agents in the network have an identical opinion, which correspond to the two extreme opinions.

Proposition 1: Under Assumption 1, the continuous time Markov process X(t), with (1) as the infinitesimal generators corresponding to each agent, has exactly two absorbing states X(t) = θ+ and X(t) = θ-.

Proof: Due to space limitation the proof is omitted. Considering the NIMFA approximation, we get that the dynamics of the opinion for an agent i are given by:

vi,1 = -β 1 r i v i,1 + β 2 l i v i,2 vi,n = -β n r i v i,n + β n+1 l i v i,n+1 -β n l i v i,n + β n-1 r i v i,n-1 vi,N = -β N l i v i,N + β N -1 r i v i,N -1 (2)
for all i ∈ K and 1 < n < N where

l i = j∈K a ij E[1 -Q j ] = j∈K N/2 n=1 a ij v j,n , r i = j∈K a ij E[Q j ] = j∈K N n=N/2+1 a ij v j,n . (3)
and n v i,n = 1.

We can easily verify that X i = θ 1 , i.e. v i,1 = 1 for all i is an equilibrium for the above set of equations. When v i,1 = 1 for all i, v i,n = 0 for all n ≥ 2 and as a result, l i = τ i and r i = 0 for all i which gives vi,n = 0 for all i, n. Excluding the extreme solutions θ+ and θ-, the non-linearity of system (2) could give rise to the existence of interior rest points which are locally stable. Such rest points are referred to as metastable states in Physics. Metastability of Markov processes is precisely defined in [START_REF] Huisinga | Phase transitions and metastability in markovian and molecular systems[END_REF], where the exit times from these metastable states are shown to approach infinity when the network size is arbitrarily large.

A. Rest points of the dynamics

For a given r i = E[R i (t)], the equilibrium state v * i,n must satisfy the following conditions

0 = -β 1 ri τi v * i,1 + β 2 ( τi-ri τi )v * i,2 0 = -β n v * i,n + β n+1 ( τi-ri τi )v i,n+1 +β n-1 ri τi v * i,n-1 0 = -β N ( τi-ri τi )v * i,N + β N -1 ri τi v * i,N -1 (4)
We can write any v * i,n based on v * i,1 , by simplification as

v * i,n = β 1 β n r i τ i -r i n-1 v * i,1 . (5)
As the sum of v i,n over n must be 1, we can solve for v * i,1

as

v * i,1 = 1 N n=1 β1 βn ri τi-ri n-1 . (6)
We then can use this relationship to construct a fixed-point algorithm that computes a rest-point of the global opinion dynamics for all users.

Data: Number of agents K, the edge weights a i,j for all i, j ∈ K, initial values v i,n (0), convergence factor << 1, opinion levels N and the jump rates β n for all n ∈ {1, . . . , N }. Result: v(m) at the end of the loop is close to a fixed point of the opinion dynamics do m ← m + 1 ; Set

r i (m) = k N n=N/2+1 a i,k v k,n (m) (7)
for all i ∈ K ; Set

v i,n (m) = β1 βn ri(m) τi-ri(m) n-1 N l=1 β1 β l ri(m) τi-ri(m) l-1 (8)
for all n ∈ {1, . . . , N }, i ∈ K ; while ||v m -v m-1 || ≥ ; Algorithm 1: Algorithm to find a fixed point of the NIMFA.

Additionally, we can obtain some nice properties on the relation between r i and v i,n by studying the following function.

Lemma 1: Consider the function f :

[0, 1] → [0, 1] defined as f (x) := N n=N/2+1 β1 βn x 1-x n-1 N n=1 β1 βn x 1-x n-1 (9)
for all x ∈ [0, 1) and with f (1) = 1. We have that f (x) is a monotonically increasing continuous function and takes the values f (0) = 0, f (0.5) = 0.5 and lim x→1 f (x) = 1.

Proof: Due to space limitation the proof is omitted. We can use f ( ri τi-ri ) to calculate the probability that an agent i will take the action 1, i.e., 6) and ( 5).

N n=N/2+1 v * i,n = f ( ri τi-ri ) from (

IV. OPINION SPREADING

A way to model generic interaction networks is to consider that they are the union of a number of clusters (see for instance [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF] for a cluster detection algorithm). Basically a cluster C is a group of agents in which the opinion of any agent in C is influenced more by the other agents in C, than agents outside C. When the interactions between cluster are deterministic and very weak, we can use a two time scale-modeling as in [START_REF] Martin | Time scale modeling for consensus in sparse directed networks with time-varying topologies[END_REF] to analyze the overall behavior of the network. In the stochastic framework and knowing only a quantized version of the opinions we propose here a development aiming at characterizing the majority actions in clusters. The notion of cluster can be mathematically formalized as follows.

Definition 3 (Cluster): A subset of agents C ⊂ K defines a cluster when, for all i, j ∈ C and some λ > 0.5 the following inequality holds

a ij ≥ λ τ i |C| . ( 10
)
The maximum λ which satisfies this inequality for all i, j ∈ C is called the cluster coefficient.

For any given set of agents C ⊂ K, let us denote that

ν C -= j∈C N/2 n=1 v j,n |C| , and
ν C + = j∈C N n=N/2+1 v j,n |C| .
Those values represent the expected fraction of agents within a set C with action 0 and 1, respectively. We also denote by ν C n , the average probability of agents in a cluster to have opinion θ n , i.e., ν C n = i∈C vi,n |C|

. Now we can use the definition of a cluster given in [START_REF] Fortunato | Vector opinion dynamics in a bounded confidence consensus model[END_REF] to obtain the following proposition.

Proposition 2: The dynamics of the average opinion probabilities in a cluster C ⊂ K can be written as: Proof: Due to space limitation the proof is omitted. The result above shows that instead of looking at individual opinions of agents inside a cluster, we can provide equation [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF] for the dynamics of the expected fraction of agents in a cluster with certain opinions.

νC 1 κ = -β 1 ν C 1 λν C + + (1 -λ)δ +β 2 ν C 2 λν C -+ (1 -λ)(1 -δ) νC n κ = -β n ν C n + β n+1 ν C n+1 λν C -+ (1 -λ)(1 -δ) +β n-1 ν C n-1 λν C + + (1 -λ)δ νC N κ = -β N ν C N λν C -+ (1 -λ)(1 -δ) +β N -1 ν C N -1 λν C + + (1 -λ)δ (

A. Action preservation

One question that can be asked in this context is what are the sufficient conditions for the preservation of actions in a cluster, i.e. regardless of external opinions, agents preserve the majority action inside the cluster C for long time. At the limit, all the agents will have identical opinions corresponding to an absorbing state of the network but, clusters with large enough λ may preserve their action in metastable states (long time).

Proposition 3: If ∃ x ∈ (0.5, 1) such that x = f (λx) than cluster C with coefficient λ preserves its action in a metastable state. If no such x exists, then the only equilibrium when the perturbation term δ = 1 from (11) is at ν C + = 1, and when δ = 0, the equilibrium is at ν C + = 0. Proof: Due to space limitation the proof is omitted.

B. Propagation of actions

In the previous subsection, we have seen that a cluster C can preserve its majority action regardless of external opinion if it has a sufficiently large λ. If there are agents outside C with some connections to agents in C, then this action can be propagated. Let τ C i = j∈C a ij denote the total trust of agent i in the cluster C. Let the cluster C be such that it has λ large enough so that νC + > 0.5 exists where νC + = f (λν C + ). Proposition 4: If the cluster C is preserving an action 1 with at least a fraction νC + of the population in C having action 1, then the probability of any agent i ∈ K \ C to chose action 1 at equilibrium is bounded as follows.

f νC + τ C i τ i ≤ Pr(Q * i = 1) ≤ 1 -f νC - τ C i τ i . ( 12
)
where Q * i is the action taken by i when the system is in a non-absorbing NIMFA equilibrium state.

Proof: Due to space limitation the proof is omitted.

C. Control of opinion spreading

Consider that an external entity, a firm for example, wants to control the actions of the agents in the network. In particular, the external agency wants to ensure that a cluster C preserves its initial action. Practically, a set of consumers in C might prefer the product of the firm, and this firm wants to ensue that other competing firms do not sway their opinions and convert their opinions.

For this purpose, the firm tries to reinforce the opinion spread within C and from C to its followers, by strengthening the influence of agents in C. As an example, the party might pay the social network, such as Facebook or Twitter, to make messages, in the form of wall posts or tweets, to be more visible when the source of these messages are within C. This implies that a ij for any i ∈ K and j ∈ C, is now modified to a ij = a ij (1 + u), where u denotes the control parameter. Here, u = 0 represents the normal state of the network and u > 0 implies that agents in the network will view messages from agents in C more frequently or more easily (with a higher priority).

Thus, the cluster coefficient of C is no longer the initial cluster coefficient λ, but the new coefficient is increased depending on u.

Proposition 5: Let λ be the cluster coefficient of C. Then a control which strengthens the connections from C from a ij to a ij (1 + u) for all j ∈ C and i ∈ K results in a new cluster coefficient λ ≥ λ given by

λ ≥ λ 1 + u 1 + λu (13)
This results in a threshold on the control required for preservation as the smallest u * ≥ 0 satisfying

x = f λ 1 + u * 1 + λu * x ( 14
)
for some x ∈ (0.5, 1]. Additionally, any follower of C has its probability of action 1 modified to

f νC + τ C i (1 + u) τ i + τ C i u ≤ Pr(Q * i = 1) ≤ 1-f νC - τ C i (1 + u) τ i + τ C i u (15)
Proof: Due to space limitation the proof is omitted. As λ ≤ 1, λ ≥ λ always, and we also have lim u→∞ λ = 1. This implies that as long as we apply a sufficiently large control u, any cluster C will be able to preserve its action (as a result of Corollary 1). Additionally, this also means that agents who are followers of C will now be influenced to a greater degree by C.

V. NUMERICAL RESULTS

For all simulations studied, unless otherwise mentioned, we take Θ = {0.2, 0.4, 0.6, 0.8}, β 1 = β 4 = 0.01 per unit of time and β 2 = β 3 = 0.02 per unit of time.

For the first set of simulations, we take another graph structure, but with the same K as indicated in Figure 1. We first randomly make links between any i, j ∈ K with a probability of 0.05. When such a link exists, a ij = 1 and a ij = 0 otherwise. Then we construct a cluster C 1 , with the agents i = 1, 2, . . . , 40, and C 2 with agents i = 81, 82, . . . , 120. We also label agents 40 < i ≤ 60 as set B 1 and 60 < j ≤ 80 as set B 2 . To provide the relevant cluster structure, we made the edge weights a ij = 1 for all τi ≥ 0.444 for all 60 < i ≤ 80.

Cluster C 1 |C 1 | = 40 Cluster C 2 |C 2 | = 40 Set B1 |B1| = 20 Set B2 |B2| = 20
• i, j ∈ C 1 or i, j ∈ C 2 ,

A. Propagation of actions

We find that the largest x satisfying x = f (λ 1 x) is 0.95 and that satisfying x = f (λ 2 x) is 0.94. Therefore, if all agents in C 1 start with opinion 0.2 and all agents in cluster 2 start with opinion 0.8, we predict from proposition 3 that ν C1

Q i (t) for S = C 1 , C 2 , B 1 , B 2 .
We see that C 1 and C 2 preserve their initial actions as given by proposition 3. We also see that as B 1 follows only C 1 , it's action is close to C 1 . As B 2 follows both C 1 and C 2 who have contradicting actions, it has a very mixed opinion which keeps changing randomly in time.

Simulations of the continuous time Markov chain show that our theoretical results are valid even when the cluster size is 40. Figure 2 plots the population fraction of agents with action 1 within a certain set for one simulation. We look for this value in the clusters C 1 and C 2 as well as the sets B 1 and B 2 . C 1 and C 2 are seen to preserve their actions which are opposite to each other. Since B 1 has a significant trust in C 1 alone, the opinion of C 1 is propagated to B 1 . However, as B 2 trusts both C 1 and C 2 , its opinion is influenced by the two contradicting actions resulting in having some agents with action 1 and the rest with action 0.

B. Control of opinion spreading

We consider the same graph structure used in Fig. 2 illustrated in Fig. 1, but with Cluster C 2 having its first 25 agents removed. As a result, the cluster coefficient of this cluster becomes λ 2 = 0.636, which no longer allows for preservation of its action as seen in Figure 3a. From proposition 3, we find that a λ > 0.8 ensures preservation. Therefore, we introduce a control u = 1.5 which enhances the visibility of actions spread by agents in C 2 by a factor of 2.5, resulting in a ij = 2.5a ij for all j ∈ C, i ∈ K. This results in a new λ 2 ≥ 0.8 according to proposition 5 and verified by numerical calculation on the graph to be λ 2 = 0.814. As a result, we observe from Figure 3b that the cluster 2 action is preserved for a long duration. for a finite number of agents. Whereas, when this number becomes large enough, the stochastic system can enter into a quasi-stationary regime in which partial agreements are reached. This type of phenomenon has been observed in allto-all and cluster type topologies. Additionally, we have also studied the impact of an external entity which tries to control the actions of the users in a social network by manipulating the network connections. This can be interpreted as a company paying a social platform to make content from certain groups of agents more visible or frequent. We have shown how such a control can enable a community or cluster of agents to preserve or propagate its opinion better.

  11) where κ = i∈C τi |C| and δ ∈ [0, 1].

Fig. 1 :

 1 Fig. 1: Structure of the graph. Any two agents in K may be connected with a 0.05 probability. All agents within a cluster are connected, and the arrows indicate directed connections.

-

  ≥ 0.95 and ν C2 + ≥ 0.94 in the metastable state. Additionally, applying proposition 4 yields ν B1 -≥ f (0.95 × 0.714) = 0.85, ν B2 -, ≥ f (0.95 × 0.444) = 0.324 and ν B2 + ≥ f (0.94 × 0.444) = 0.315.

Fig. 2 :

 2 Fig. 2: Simulation of i∈SQ i (t) for S = C 1 , C 2 , B 1 , B 2 .We see that C 1 and C 2 preserve their initial actions as given by proposition 3. We also see that as B 1 follows only C 1 , it's action is close to C 1 . As B 2 follows both C 1 and C 2 who have contradicting actions, it has a very mixed opinion which keeps changing randomly in time.

  (a) Simulation with no control implemented. (b) Simulation with u = 1 on cluster 2.

Fig. 3 :

 3 Fig. 3: Average population with action 1 plotted vs time for each set.

  making C 1 and C 2 clusters with coefficients λ 1 = 0.833 and λ 2 = 0.816 (for the particular random graph generated for this simulation).• 40 < i ≤ 60 and 1 ≤ j ≤ 20, making agents in B 1 trust C 1 with 60 < i ≤ 80 and 1 ≤ j ≤ 20 or 80 < j ≤ 120, making agents in B 2 trust both C 1 and C 2 , with

	τ	C 1 i
		τ τi , C 1 i	τ	C 2 i

τi ≥ 0.714 for all 40 < i ≤ 60.

•


Irinel-Constantin Morȃrescu
email: constantin.morarescu@univ-lorraine.fr

Vineeth Satheeskumar Varma

Lucian Bus
email: lucian@busoniu.net

Samson Lasaulce
email: samson.lasaulce@lss.supelec.fr

Space-time budget allocation for marketing over social networks

Keywords: Social networks, hybrid systems, optimal control

We address formally the problem of opinion dynamics when the agents of a social network (e.g., consumers) are not only influenced by their neighbors but also by an external influential entity referred to as a marketer. The influential entity tries to sway the overall opinion to its own side by using a specific influence budget during discrete-time advertising campaigns; consequently, the overall closed-loop dynamics becomes a linear-impulsive (hybrid) one. The main technical issue addressed is finding how the marketer should allocate its budget over time (through marketing campaigns) and over space (among the agents) such that the agents' opinion be as close as possible to a desired opinion; for instance, the marketer may prioritize certain agents over others based on their influence in the social graph. The corresponding space-time allocation problem is formulated and solved for several special cases of practical interest. Valuable insights can be extracted from our analysis. For instance, for most cases we prove that the marketer has an interest in investing most of its budget at the beginning of the process and that budget should be shared among agents according to the famous water-filling allocation rule. Numerical examples illustrate the analysis.

INTRODUCTION

The last decades have witnessed an increasing interest in the study of opinion dynamics in social networks. This is mainly motivated by the fact that people's opinions are increasingly influenced through digital social networks. Therefore, governmental institution but also private companies consider that marketing over social networks becomes a key tool for promoting new products or ideas. However, most of the existing studies focus on the analysis of models without control, i.e., they study the convergence, dynamical patterns or asymptotic configurations of the open-loop dynamics. Various mathematical models [START_REF] Degroot | Reaching a consensus[END_REF]Friedkin and Johnsen., 1990;[START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF][START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF][START_REF] Altafini | Consensus problems on networks with antagonistic interactions[END_REF][START_REF] Chowdhury | Continuous opinions and discrete actions in social networks: a multi-agent system approach[END_REF] have been proposed to capture more features of these complex dynamics. Empirical models based on in vitro and in vivo experiments have also been developed [START_REF] Davis | Understanding group behavior : Consensual action by small groups, volume 1, chapter Group decision making and quantitative judgments : A consensus model[END_REF][START_REF] Ohtsubo | Majority influence process in group judgment : Test of the social judgment scheme model in a group polarization context[END_REF][START_REF] Kerckhove | Modelling influence and opinion evolution in online collective behaviour[END_REF]. The emergence of consensus received a particular attention in opinion dynamics [START_REF] Axelrod | The dissemination of culture: A model with local convergence and global polarization[END_REF][START_REF] Galam | Towards a theory of collective phenomena: Consensus and attitude changes in groups[END_REF]. While some mathematical models naturally lead to consensus [START_REF] Degroot | Reaching a consensus[END_REF]Friedkin and Johnsen., 1990), others lead to network clustering [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF][START_REF] Altafini | Consensus problems on networks with antagonistic interactions[END_REF][START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF]. In order to enforce consensus, some recent studies propose the control of one or a few agents, see [START_REF] Caponigro | Sparse feedback stabilization of multi-agent dynamics[END_REF]; [START_REF] Dietrich | Control via leadership of opinion dynamics with state and timedependent interactions[END_REF]. Beside these methods of controlling opinion dynamics towards consensus, we also find recent attempts to control the discretetime dynamics of opinions such that as many agents as possible reach a certain set after a finite number of influences [START_REF] Hegselmann | Optimal opinion control : The campaign problem[END_REF]. In [START_REF] Masucci | Strategic resource allocation for competitive influence in social networks[END_REF], the authors consider multiple influential entities competing to control the opinion of consumers under a game theoretical setting. However, this work assumes an undirected graph and a voter model for opinion dynamics resulting in strategies that are independent of the node centrality. On the other hand, [START_REF] Varma | Opinion dynamics aware marketing strategies in duopolies[END_REF] considers a similar competition with opinion dynamics over a directed graph and no budget constraints. In this paper, we consider a different problem that requires minimizing the distance between opinions and a desired value using a given control/marketing budget. Moreover, we assume that the maximal marketing influence cannot instantaneously shift the opinion of one individual to the desired value. Basically, we consider a continuous time opinion dynamics and we want to design a marketing strategy that minimizes the distance between opinions and the desired value after a given finite number of discrete-time campaigns under budget constraints. To solve this control design problem we write the overall closed-loop dynamics as a linear-impulsive system and we show that the optimal strategy is to influence as much as possible the most central/popular individuals of the network. (see [START_REF] Bonacich | Eigenvector-like measures of centrality for asymmetric relations[END_REF] for a formal definition of centrality). To the best of our knowledge our work is different from all the existing results on opinion dynamics control. Unlike the few previous works on the control of opinions in social networks, we do not control the state of the influencing entity. Instead, we consider that value as fixed and we control the influence weight that the marketer has on different individuals of the social network. By doing so, we emphasize the advantages of targeted marketing with respect to broadcasting strategies when budget constraints have to be taken into account. Moreover, we show that, although the individual control action u i (t k ) at time t k can be chosen in the interval [0, ū], the optimal choice is discrete: either 0 or ū. The rest of the paper is organized as follows. Section 2 formulates the opinion dynamics control problem under consideration. A useful preliminary result for solving a specific optimization problem with constraints is given in Section 3. To motivate our analysis, we emphasize in Section 4 the improvements that can be obtained by targeted advertising with respect to a uniform/broadcasting control. Section 5 contains the results related to the optimal control strategy. We first analyze the case when the campaign budget is given a priori and must be optimally partitioned among the network agents. Secondly, we look at the case when the campaign budget is unknown but the campaigns are distanced in time. Both cases point out that the optimal control contains only 0 or ū actions. These results motivate us to study in Section 6 the spatio-temporal distribution of the budget under the assumption that all the components of u(t k ) are either 0 or ū. Numerical examples and concluding remarks end the paper.

PROBLEM STATEMENT

We consider an entity (for example, a governmental institution or a company) that is interested in attracting consumers to a certain opinion. Consumers belong to a social network and we refer to any consumer as an agent. For the sake of simplicity, we consider a fixed social network over the set of vertices V = {1, 2, . . . , N } of N agents. In other words, we identify each agent with its index in the set V. To agent n ∈ V we assign a normalized scalar opinion x n (t) ∈ [0, 1] that represents its opinion level and can be interpreted e.g., as the probability for an agent to act as desired. We use x(t) = (x 1 (t), x 2 (t), . . . , x N (t)) to denote the state of the network at any time t, where x(t) ∈ X and X = [0, 1] N .

In order to obtain a larger market share with a minimum investment, the external entity applies an action vector u(t k ) = (u 1 (t k ), . . . , u N (t k )) ∈ U i in marketing campaigns at discrete time instants t k ∈ T , k ∈ N. A given action therefore corresponds to a given marketing campaign aiming at influencing the consumer's opinion. The instants corresponding to the campaigns are known and are collected in the set T = {t 0 , t 1 , . . . , t M }. Between two consecutive campaigns, the consumer's opinion is only influenced by the other consumers of the network. We assume that t k -t k-1 = δ k ∈ [δ m , δ M ] where δ m < δ M are two fixed real numbers. Throughout the paper we refer to d ∈ {0, 1} as the desired opinion that the external entity wants to be adopted. We consider ∀i ∈ V the following dynamics:

       ẋi (t) = N j=1 a ij (x j (t) -x i (t)), t ∈ [t k , t k+1 ) x i (t k ) = u i (t k )d + (1 -u i (t k ))x i (t - k ) , ∀k ∈ N, (1) where u i (t k ) ∈ [0, ū] with ū < 1, ∀i ∈ V and M k=0 N i=1 u i (t k ) ≤ B
where B represents the total budget of the external entity for the marketing campaigns. Dynamics (1) can be rewritten using the collective variable X(t) = (d, x(t)) as:

Ẋ(t) = -LX(t) X(t k ) = PX(t - k ) , (2)
where

L = 0 0 1,N 0 N,1 L , P = 1 0 1,N u(t k ) I N -diag(u(t k ))
with diag(u(t k )) ∈ R N ×N being the diagonal matrix having the components of u(t k ) on the diagonal. Remark 1. It is noteworthy that:

• L is a Laplacian matrix corresponding to a network of N + 1 agents. The first agent represents the external entity and is not connected to any other agent while the rest of the agents represents the consumers and are connected through the social network defined by the influence weights a ij . • P is a row stochastic matrix that can be interpreted as a Perron matrix associated with the tree having the external entity as a parent of all the other nodes. Consequently, without budget constraints, the network reaches, at least asymptotically, the value d.

Several space-time control strategies can be implemented under the budget constraints. For instance, we can spend the same budget for each agent i.e., u i (t k ) = u j (t k ), ∀i, j ∈ V, we can also allocate the entire budget for specific agents of the network. Moreover, the budget can be spent either on few or many campaigns. Our objective is to design a space-time control strategy that minimizes the following cost function

J T = N i=1 |x i (T ) -d| (3)
for some T > t M , and we have the cost associated with the asymptotic opinion given by

J ∞ = N i=1 lim t→∞ |x i (t) -d| (4)
This can be interpreted as follows. If the entity (a governmental institution for example) is interested in convincing the public to buy some product or change their habits (practice sports or quit smoking for instance), it will try to move the asymptotic consensus value of the network as close as possible to the desired value, i.e. minimize J ∞ . In some other cases, like an election campaign which targets to get the opinions close to d within a finite time T , we will minimize J T . It is worth mentioning that between campaigns and after the last campaign the opinions evolve according to consensus dynamics.

PRELIMINARIES

We first state a very useful Lemma which will help us to find the optimal solutions for many sub-cases of our problem. Lemma 1. Given an optimization problem (OP) of the form minimize

y∈R L C(y) subject to 0 ≤ y i ≤ ȳ < 1, L i=1 y i ≤ B.
(5)

where C(y) is a decreasing convex function in y i such that one of the following two conditions hold Case 1: ∀ i ∈ {1, . . . , L}, ∃g(y) ≥ 0 such that ∂C(y) ∂y i = -c i g(y);

Case 2: ∂C(y)

∂y i = 1 1 -y i for all i ∈ {1, . . . , L}.
Then, a solution y * to this OP is given by water-filling as follows

y * R(i) =        ȳ if i ≤ B Lȳ B -ȳL B Lȳ if i = B Lȳ 0 otherwise (6)
where R : {1, . . . , L} → {1, . . . , L} is any bijection for Case 2 and, a bijection satisfying

c R(1) ≥ c R(2) ≥ • • • ≥ c R(L) . for Case 1.

THE BROADCASTING CASE STUDY

To emphasize the relevance of the problem under consideration, we will show that for some particular network topologies we can obtain a significant improvement of the revenue by using targeted marketing instead of broadcasting-based marketing in which the marketer allocates the same amount of resource to all the agents. First, we derive the optimal revenue that can be obtained by implementing a broadcasting strategy i.e., u i (t k ) = u j (t k ) α k , ∀i, j ∈ V. We suppose that the graph representing the social network contains a spanning tree. Let v be the right eigenvector of L associated with the eigenvalue 0 and satisfying v 1 N = 1. Therefore, in the absence of any control action, one has that lim t→∞ x(t) = v x(0)1 N x ∞ 0 . Let us also introduce the following notation:

x

∞ k = lim t→∞ e -L(t-t k ) x(t k ) = v x(t k )1 N , ∀k ∈ N.
Following (2) and using

δ k = t k+1 -t k , D k = diag(u(t k )) one deduces that: x ∞ k+1 = v x(t k+1 )1 N = v u(t k+1 )d + (I N -D k+1 )x(t - k+1 ) 1 N = v u(t k+1 )d + (I N -D k+1 )e -Lδ k x(t k ) 1 N . Since v L = 0 N one has that v e -Lδ k = v and conse- quently one obtains that x ∞ k+1 -x ∞ k = v u(t k+1 )d -D k+1 e -Lδ k x(t k ) 1 N . (7) In the case of broadcasting one has u(t k ) = α k 1 N and D k = α k I N , where α k ∈ [0, ū] for all k ∈ {0, . . . , M }. Therefore, using v 1 N = 1, (7) becomes x ∞ k+1 -x ∞ k = α k+1 (d1 N -x ∞ k
), which can be equivalently rewritten as

(d1 N -x ∞ k+1 ) = (1 -α k+1 )(d1 N -x ∞ k ).
(8) Using (8) recursively one obtains that

J ∞ (α) = (d1 N -x ∞ M ) = M =0 (1 -α )(d1 N -x ∞ 0 ). ( 9
)
where J B (α) denotes the cost associated with a broadcasting strategy using α k at stage t k . Proposition 1. The broadcasting cost J ∞ (α) is minimized by using the maximum possible investments as soon as possible, i.e.

α k =        ū if k ≤ B N ū B -ūN B N ū if k = B N ū 0 otherwise (10)
Proof. Minimizing J ∞ (α) under the broadcasting strategy assumption is equivalent to minimizing k+1 =0 (1 -α ). This is equivalent to minimizing

C(α) = log k+1 =0 (1 -α )
and we have

∂C ∂α = - 1 1 -α (11)
This results in an OP which satisfies the conditions to use Lemma 1 case 2.

It is noteworthy that for u i ∈ [0, 1) one has that

k+1 =0 (1 -α ) ≥ 1 - k+1 =0 α ≥ 1 - B N . (12)
The last inequality in (12) comes from the broadcasting hypothesis u i (t ) = α , ∀i ∈ V which mean that the budget spent in the -th campaign is N • α . Therefore, the total budget for k + 2 campaigns is N k+1 =0 α and has to be smaller than B. Thus

J = 1 N |(d1 N -x ∞ k+1 )| ≥ (1 - B N )1 N |(d1 N -x ∞ 0 )|.
The interpretation of ( 12) is that for the broadcasting strategy the minimal cost J is obtained when the whole budget is spent in one marketing campaign (provided this is possible i.e., B ≤ N ū), otherwise the first inequality in (12) becomes strict meaning that

J > (1 - B N )1 N |(d1 N -x ∞ 0 )|.
Let us now suppose that the graph under consideration is a tree having the first node as root. Then, using a targeted marketing in which the external entity influences only the root, we will show that, under the same budget constraints, the cost J will be smaller. Indeed, for this graph topology one has

v = (1, 0, . . . , 0) yielding x ∞ k = x 1 (t k )1 N .
Moreover, the dynamics of x 1 (•) writes as:

ẋ1 (t) = 0, t ∈ [t k , t k+1 ) x 1 (t k ) = u 1 (t k )d + (1 -u 1 (t k ))x 1 (t - k ) , ∀k ∈ N. (13) Therefore, x 1 (t k ) = u 1 (t k )d + (1 -u 1 (t k ))x 1 (t k-1 ) yielding d -x 1 (t k ) = (1 -u 1 (t k ))(d -x 1 (t k-1 )),
which is equivalent to (8). As we have seen before, in the broadcasting strategy one has k+1 =0 α ≤ B N whereas targeting only the root, the constraint becomes

k+1 =0 u 1 (t ) ≤ B.
Therefore, for any given broadcasting strategy (u 1 , u 2 , . . . , u k ) there exists a strategy targeted on the root that consists of repeating N times (u 1 , u 2 , . . . , u k ). Doing so, one obtains

(d1 N -x ∞ k+1 ) = k+1 =0 (1 -α ) N (d1 N -x ∞ 0 ).
which leads to a much smaller cost J i.e., the strategy is more efficient.

GENERAL OPTIMAL SPACE-TIME CONTROL STRATEGY

First, we rewrite the optimal control problem as an optimization problem by treating the control u(t k ) as an N M dimensional vector to optimize. We denote u i,k = u i (t k ) to represent the control for agent i ∈ V at time t k . Then our problem can be rewritten as Minimize

u∈R N M J T (u) Subject to 0 ≤ u i,k ≤ ū ∀i ∈ V, k ∈ {0, . . . , M }, and
N i=1 M k=1 u i,k ≤ B (14)
Here, J T (u) is a multilinear function in u. Before solving problem ( 14) we want to get further insights on the solution's structure, which will lead to important simplifications. Therefore, instead of solving the general optimization problem ( 14), we consider splitting our problem into time-allocation and spaceallocation. For a given time-allocation, i.e. if we know that for stage k a maximum budget of β k ≤ B has been allocated, we find the optimal control strategy for the k-th stage. Moreover, for long stage durations (i.e., t k+1 -t k large) and given temporal budget allocation (β 0 , . . . , β M ), we characterize the optimal space allocation of the budget. Based on these results, we propose a discrete-action spatio-temporal control strategy.

Minimizing the per-stage cost

In this section we consider that the budget β k for each campaign is a priori given, and optimize the corresponding

|d1 N -x ∞ k |. Denote the budget for stage k by β k such that N i=1 u i (t k ) ≤ β k (15)
The corresponding cost for the stage k is written as

J ∞ k (u(t k )) = (d1 N -x ∞ k ) = |d - N i=1 v i x i (t k )| = |d - N i=1 v i (u i (t k )d + (1 -u i (t k ))x i (t - k ))| (16)
We use

γ i = v i |d -x i (t - k )
| to denote the gain by investing in agent i ∈ V. Define by R : V → V, a bijection which sorts the agents based on decreasing γ

i , i.e. γ R(1) ≥ γ R(2) ≥ • • • ≥ γ R(N ) Proposition 2. The cost J ∞ k (u(t k )) is minimized by the fol- lowing investment profile u * R(i) (k) =        ū if i ≤ β k ū β k -ū β k ū if i = β k ū 0 otherwise (17)
Proof. Due to space limitation the proof is omitted.

Space allocation for long stage duration

In the following we consider that a finite number of marketing campaigns with a priori fixed budget are scheduled such that t k+1 -t k is very large for each k ∈ {0, 1, . . . , M -1}. In this case, we can assume that x i (t - k+1 ) = x ∞ k for all i ∈ V and k ∈ {0, 1, . . . , M -1}. Under this assumption, we write

x i (t - 1 ) = x ∞ 0 (u(t 0 )) = N i=1 v i (du i (t 0 ) + x i (t - 0 )(1 -u i (t k )))
(18) for any i ∈ V. Subsequently, we have

x ∞ k (u(t 0 ), u(t 1 ), . . . , u(t k )) = N i=1 v i [du i (t k ) +x ∞ k-1 (u(t 0 ), . . . , u(t k-1 ))(1 -u i (t k )) (19)
for all k ∈ {1, 2, . . . , M }.

Our objective is to minimize

J ∞ = x ∞ M (u(t 0 ), . . . , u(t M )
) -d and this can be done using the proposition below. First, let us define S k : V → V a bijection such that S 0 = R and for all k ∈ {1, 2, . . . , M }, S k gives the agent index after sorting over

v i , i.e., v S k (1) ≥ v S k (2) ≥ • • • ≥ v S k (N ) Proposition 3.
Let the temporal budget allocation be given by

β = (β 0 , . . . , β M ) such that M k=1 β k ≤ B and β k ≤ N ū. Then,
the optimal allocation per agent minimizing the cost J(u) is given by

u * S k (i) (k) =        ū if i ≤ β k ū β k -ū β k ū if i = β k ū 0 otherwise (20)
Proof. Due to space limitation the proof is omitted.

DISCRETE-ACTION SPACE-TIME CONTROL STRATEGY

Motivated by the results in Propositions 2 and 3, in this section we consider that u i (t k ) ∈ {0, ū}, ∀i ∈ V, k ∈ N and B = K ū with K ∈ N given a priori. The objective is to numerically find the best space-time control strategy for a given initial state x 0 of the network.

Algorithms

Let us consider in turn the cases of short and long stages. In the short-stage case, given a time allocation consisting of the budgets β k = b k ū at each stage, Proposition 2 tells us how to allocate each stage budget optimally across the agents. Denote all possible budgets at one stage by B = {0, . . . , min{N, K}}. A very simple algorithm is then to search in a brute-force manner all possible time allocations b = (b 0 , . . . , b M ) ∈ B M +1 , subject to the constraint k b k ≤ K. For each such vector b, we simulate the system from x 0 with dynamics (1) where the budget b k is allocated with Proposition 2, and we obtain a final state x F (b) = v x(t M )1 N (the infinite-time state of the network after the last campaign). We retain a solution with the best cost:

min b |x 1,F (b) -d|
where subscript 1 denotes the first agent (recall that the agents all have the same opinion at infinite time). Note that this cost is J ∞ /N ; we do not sum it over all the agents because this version is easier to interpret as a deviation of each agent from the target state. Furthermore, the simulation can be done in closed form, using the fact that x -(t k+1 ) = e -Lδ k x(t k ). The complexity of this search is O(N 3 (M +1)(min{N, K}+1) M +1 ), dominated by the exponential term. Therefore, this approach will only be feasible for small values of N or K, and especially of M . Considering now the long-stage case, we could still implement a similar brute-force search, but using dynamics (19) for interstage propagation and Proposition 3 for allocation over agents.

However, now we can do better by taking advantage of the fact that for all k > 1, the opinions of all the agents reach identical values. Using this, we will derive a more efficient, dynamic programming solution to the optimal control problem:

min b |x 1,F (b) -d|
where the long-stage dynamics apply but by a slight abuse we keep it the same as in the previous section.

To obtain the DP algorithm, define for k = 1, . . . , M, M + 1 =: F a new state signal z k = [y k , r k ] ∈ Z := [0, 1] × {0, . . . , K}. In this signal, y k = x ∞ k-1 , the opinion resulting from long-term propagation after the k -1th campaign, and r k is the remaining budget to apply (we will start from r 0 = K).

Here, F is associated with the infinite-time state of the network. We will compute a value function V k (z k ), representing the best cost attainable from stage k, if the agent state is y k and budget r k remains:

V F (z F ) = |x F -d|, ∀r F V k (z k ) = min min{r k ,N } b k =0 V k+1 (g(z k , b k )), k = M, . . . , 1
Here, the dynamics g : Z × B → Z are given by: At stage 0, special dynamics g 0 : X × B → Z apply, because the initial state of the network cannot be represented by a single number: Once V k is available, an optimal solution is found by a forward pass, as follows:

y k+1 = v x(t k ), r k+1 = r k -b k where x i (t k ) = u i (b k )d + (1 -u i (b k ))
y 1 = v x(t 0 ), r 1 = K -b 0 where x i (t 0 ) = u i (b 0 )d + (1 -u i (b 0 ))x i,
b * 0 = arg min min{K,N } b0=0 V 1 (g 0 (x 0 , b 0 )), z * 1 = g 0 (x 0 , b * 0 ) b * k = arg min min{r k ,N } b k =0 V k+1 (g(z * k , b k )), z * k+1 = g(z * k , b * k ) for k = 1, . . . , M
and the optimal cost of the overall solution is simply the minimum value at the first step.

To implement this algorithm in practice, we will discretize the continuous state y into Y points, and interpolate the value function on the grid formed by these points, see [START_REF] Bus ¸oniu | Approximate dynamic programming with a fuzzy parameterization[END_REF] for details. The complexity of the backward pass for value function computation is O(M Y (min{N, K}+1)N ) (we disregard the complexity of the forward pass since it is much smaller). To develop an intuition, take the case N < K; then the algorithm is quadratic in N and linear in M and Y . This allows us to apply the algorithm to much larger problems than the brute-force search above. Finally, note that in principle we could develop such a DP algorithm for the short-stage problem, but there we cannot condense the network state into a single number. Each agent state would have to be discretized instead, leading to a memory and time complexity proportional to Y N , which makes the algorithm unfeasible for more than a few agents.

Numerical results

We begin by evaluating the brute-force algorithm on a smallscale problem with short stages. Then, we move to the longstage case, where for the same network we compare DP and the brute-force method, confirming that they get the same result.

Consider N = 15 agents connected on the graph from Figure 1, where the size of the node corresponds to its centrality. There are 4 stages, corresponding to M = 3, and the budget K = 15 = N . The initial states of the agents are random. For a short stage length δ k = 0.5 ∀k, the brute-force approach gets the results from Figure 2. The final cost (each individual agent's difference from the desired opinion) is 0.2485. Table 1, left shows the agents influenced at each stage. Reexamining Figure 1, we see that most of these agents have a large centrality, which is also the reason for which the algorithm selects them. An exception is agent 6 which has a low centrality, but is still influenced at many stages as x 6 (0) ≈ 0.1. We take now the same problem and make a single change: the stages become long (i.e., t k+1 -t k → ∞). We apply DP, with a discretization of y into 10 points. The results are in Figure 3, with the specific agents being controlled shown on the right side of Table 1. Note the solution is different from the short-stage case, and the final cost is 0.2553, slightly worse, which indicates that giving up the fine-grained control of the agents over time leads to some losses, but they are small. To evaluate the impact of function approximation (interpolation), we also run the brute-force search, since in this problem it is still feasible. It gives the same strategy and cost as DP, so we do not show the result. Note that unlike before, agent 6 is only influenced at k = 0 as the stage durations are long and its opinion value plays a role only at the first stage.

CONCLUSIONS

In its full generality, the problem of space-time budget allocation problem over a social network is seen to be non-trivial. However, it can be solved in several special cases of practical interest. If for every marketing campaign, the budget is allocated uniformly over the agents, the problem becomes a pure time budget control and can be solved. On the other hand, for a given time budget control, the problem becomes a pure space problem and the optimal way of allocating the budget is proved to be a water-filling allocation policy. Thirdly, if one goes for a binary budget allocation i.e., the marketer either allocates a given amount of budget to an agent or nothing, the space-time budget allocation problem can be solved by using dynamic programming-based numerical techniques. Numerical results illustrate how the available budget should be used by the marketer to reach its objective in terms of desired opinion for the network.

  This work was supported by projects PEPS INS2I IODINE and PEPS S2IH INS2I YPSOC funded by the CNRS .

  y k is the network state after campaign k, in which the agent allocations u i (b k ) are computed by distributing budget b k with Proposition 3.

  0 and -differently from the other steps -u i (b 0 ) is found with Proposition 2.

Figure 1 .

 1 Figure 1. Small-scale graph.

Figure 2 .

 2 Figure 2. Results for short stages. The bottom plot shows the budget allocated by the algorithm at each stage. The top plot shows the opinions of the agents, with an additional, long stage converging to the average opinion (so the last stage duration is not to scale). The circles indicate the opinions right before applying the control at each stage; note the discontinuous transitions of the opinions after control.

Figure 3 .

 3 Figure 3. Results for long stages. The continuous opinion dynamics is plotted for t ∈ [t k , t k + 25) per stage k, which is sufficient to observe the long stage behavior, i.e., the convergence of opinions of the agents.

Table 1 .

 1 Agents influenced in each campaign. Left: short stages. Right: long stages.

	Campaign	Agents	Campaign Agents
	0	3,5,6,7,8,14	0	3,6,7,8
	1	3,6,7	1	2,3,7,9
	2	3,6,7,9	2	2,3,7,9
	3	3,9	3	2,3,9