Guest editorial

Special issue on Parallel Matrix Algorithms and Applications (PMAA'16) This special issue of Parallel Computing contains nine articles, selected after peer reviewing, from invited and contributed presentations made at the 8th International Workshop on Parallel Matrix Algorithms and Applications (PMAA'16), that took place at the Université of Bordeaux, France, from July 6-8, 2016. The workshop attracted around 120 participants from all continents, 25% were PhD students and around 10% from industry.

The workshop was co-chaired by Emmanuel Agullo, Peter Arbenz, Luc Giraud, and Olaf Schenk. The members of the program committee were : P. D'Ambra, H. Avron , M. Bader, W. Bangerth, A. Basermann, C. Bekas, P. Bientinesi, R. Blaheta, M. Bollhoefer, E. Boman, G. Bosilca, A. Buttari, X.-C. Cai, H. Calandra, O. Coulaud, E. Chow, E. Darve, Z. Drmac, N. Emad, M. Faverge, E. Gallopoulos, D. Goeddeke, J. Gondahmed Samehzio, D. Gordon, L. Grigori, A. Guermouche, I. Gutheil, G. Houzeaux, T. Huckle, M. Knepley, R. Krause, J. Langou, H. Ltaief, K. Meerbergen, Y. U. Meier, E. Ng, G. Oksa, S. Petiton, P. Ramet, J. Roman, J. E. Roman, C. Petra, T. Sakurai, D. B. Szyld, D. Trystram, M. Tuma, B. Uçar, M. Vajtersic, W. Vanroose, P. Vasconcelos, R. Wyrzykowski. A total of twelve high quality submissions were received. In this special issue nine eventually accepted papers appear.

The nine papers address diverse aspects of linear algebra and high performance computing 1. Jack Dongarra, Mark Gates, Stanimire Tomov address accelerating the SVD two stage reduction and divide-and-conquer using GPUs. The increasing gap between memory bandwidth and computation speed motivates the choice of algorithms to take full advantage of today's high performance computers. For dense matrices, the classic algorithm for the SVD uses a one-stage reduction to bidiagonal form, which is limited in performance by the memory bandwidth. To overcome this limitation, a two-stage reduction to bidiagonal has been gaining popularity. As accelerators, such as GPUs and co-processors, are becoming increasingly widespread in high-performance computing, the authors present an accelerated SVD employing a two-stage reduction to bidiagonal as well as a parallelized and accelerated divide-and-conquer algorithm to solve the subsequent bidiagonal SVD. The new implementation provides a significant speedup compared to existing multi-core and GPU-based SVD implementations.

1 2. David E. Keyes, George Turkiyyah, Hatem Ltaief, Wajih Halim Boukaram present batched QR and SVD algorithms on GPUs with applications in Hierarchical matrix compression. The paper describes high performance implementations of the QR and the SVD of a batch of small matrices hosted on the GPU with applications in the compression of hierarchical matrices. In particular the authors detail multiple kernels based on the level of the GPU memory hierarchy in which the matrices can reside and show substantial speedups against streamed CUSolver SVDs.

3. Akira Imakura, Tetsuya Sakurai consider a complex moment-based parallel nonlinear eigensolver using the block communication-avoiding Arnoldi procedure. Complex moment-based parallel eigensolvers have been actively studied owing to their high parallel efficiency. In this paper, the authors propose a block SS-CAA method, which is a complex momentbased parallel nonlinear eigensolver that makes use of the block communicationavoiding Arnoldi procedure. Numerical experiments indicate that the proposed method has higher performance compared with traditional complex moment-based nonlinear eigensolvers.

4. Chao Chen, Eric F Darve, Erik G Boman, Hadi Pouransari, Sivasankaran Rajamanickam introduce a distributed-memory hierarchical solver for general sparse linear systems. The proposed fully algebraic algorithm exploits the low-rank structure of fill-in blocks during the Gaussian elimination process. The parallel implementation is based on data decomposition such that only local communication is needed for updating boundary information on every processor. The new hierarchical solver achieves an average speedup of 45 compared to its dense counterpart in factorizing three two-million-sized test problems on 256 cores of a supercomputer.

5. David Keyes, George Turkiyyah, Gustavo Chavez, Hatem Ltaief, Stefano Zampini discuss a distributed-memory fast solver for structured linear systems based on accelerated cyclic reduction. More particularly they describe a fast direct solver for rank-compressible block tridiagonal linear systems arising from the discretization of 3D elliptic operators. They provide a baseline for performance and applicability by comparing with the multifrontal method where hierarchical semi-separable matrices are used for compressing the fronts, and with algebraic multigrid. The proposed algorithm exhibits good strong and weak scaling in a distributed context and, as with any direct solver, is advantageous for problems that require the solution of multiple right-hand sides.

6. Chao Yang, Lin Lin, Mathias Jacquelin discuss a new technique named PSelInv -a distributed memory parallel algorithm for selected inversion for non-symmetric matrices. This paper generalizes the parallel selected inversion algorithm called PSelInv to sparse non-symmetric matrices.

The PSelInv method computes selected elements of A -1 . The selection is confined by the sparsity pattern of the matrix A T . PSelInv involves a large number of collective data communication activities within different processor groups of various sizes. In order to minimize idle time and improve load balancing, tree-based asynchronous communication is used to coordinate all such collective communication. Numerical results demonstrate that PSelInv can scale efficiently to 6'400 cores for a variety of matrices. 7. George Karypis, Jongsoo Park, Shaden Smith present HPC formulations of optimization algorithms for tensor completion. Tensor completion is a powerful tool used to estimate or recover missing values in multi-way data. Tensor completion is most often accomplished via low-rank sparse tensor factorization, a computationally expensive non-convex optimization problem. In this work, the authors study three optimization algorithms that have been successfully applied to tensor completion. They evaluate their parallel formulations on a variety of real datasets on a modern supercomputer and demonstrate speedups through 16'384 cores. These improvements reduce time-to-solution from hours to seconds. 8. Alejandro Lamas Davin Ìa, Jose E. Roman discuss MPI-CUDA parallel linear solvers for block-tridiagonal matrices in the context of SLEPc's eigensolvers for the computation of a few eigenpairs of a generalized eigenvalue problem Au = λBu. In this kind of computation, it is often necessary to solve a linear system of equations in each eigensolver iteration.

The linear solve can be performed through an LU factorization or using preconditioned Krylov methods. In this work, the authors aim at comparing different direct linear solvers that can exploit the block-tridiagonal structure. A parallel implementation based on MPI is developed in the context of the SLEPc library. The use of GPU devices to accelerate local computations shows to be competitive for large block sizes. 9. Cristiano I. Malossi, Alessandro Curioni, Costas Bekas, Efstratios Gallopoulos, Vasileios Kalantzis, Yousef Saad present a scalable iterative dense linear system solver for multiple right-hand sides in data analytics. They describe a Parallel-Projection Block Conjugate-Gradient, a distributed iterative solver for the solution of dense and symmetric positive-definite linear systems with multiple right-hand sides with a particular emphasis on linear systems in uncertainty quantification. Numerical experiments on massively parallel architectures illustrate the performance of the proposed scheme in terms of efficiency and convergence rate on a 4 rack BG/Q with up to 65'536 cores using dense matrices of order as high as half a million unknowns and 800 right-hand sides The editors of this special issue of Parallel Computing would like to thank all authors who submitted papers and the numerous reviewers whose expert advice was essential in the selection process.

Emmanuel

  Agullo, Inria, Bordeaux Sud-Ouest, France Peter Arbenz , ETH Zürich, Computer Science Department, Zürich, Switzerland Luc Giraud, Inria, Bordeaux Sud-Ouest, France Olaf Schenk, Università della Svizzera italiana, Institute of Computational Science, Lugano, Switzerland


Swapnil Dhamal

Walid Ben-Ameur

Tijani Chahed

Eitan Altman

Optimal Multiphase Investment Strategies for Influencing Opinions in a Social Network

Keywords: Social networks, opinion dynamics, multiple phases, Katz centrality, zero-sum games, Nash equilibrium

We study the problem of two competing camps aiming to maximize the adoption of their respective opinions, by optimally investing in nodes of a social network in multiple phases. The final opinion of a node in a phase acts as its biased opinion in the following phase. Using an extension of Friedkin-Johnsen model, we formulate the camps' utility functions, which we show to involve what can be interpreted as multiphase Katz centrality. We hence present optimal investment strategies of the camps, and the loss incurred if myopic strategy is employed. Simulations affirm that nodes attributing higher weightage to bias necessitate higher investment in initial phase. The extended version of this paper analyzes a setting where a camp's influence on a node depends on the node's bias; we show existence and polynomial time computability of Nash equilibrium.

I. INTRODUCTION

We consider two competing camps with positive and negative opinion values (referred to as good and bad camps respectively), aiming to maximize the adoption of their respective opinions in a social network. With the opinion adoption quantified as the sum of opinion values of all nodes [START_REF] Gionis | Opinion maximization in social networks[END_REF], [START_REF] Grabisch | Strategic influence in social networks[END_REF], the good camp aims to maximize this sum while the bad camp aims to minimize it. Since nodes update their opinions based on their neighbors' opinions [START_REF] Easley | Networks, crowds, and markets: Reasoning about a highly connected world[END_REF], [START_REF] Acemoglu | Opinion dynamics and learning in social networks[END_REF], a camp would want to influence the opinions of influential nodes by investing on them. Thus given a budget constraint, the strategy of a camp comprises of: how much to invest and on which nodes, in presence of a competing camp which also invests strategically.

A. Motivation

In Friedkin-Johnsen model of opinion dynamics [START_REF] Friedkin | Social influence and opinions[END_REF], [START_REF]Social positions in influence networks[END_REF], every node holds a bias in opinion. This bias plays a critical role in determining a node's final opinion, and consequently the opinions of its neighbors, and hence that of its neighbors' neighbors, and so on. If nodes give significant weightage to their biases, the camps would want to influence these biases. This could be achieved by campaigning in multiple phases, wherein a node's opinion at the end of a phase acts as its biased opinion in the next phase. With the possibility of multiphase campaigning, a camp could not only decide which nodes to invest on, but also how much to invest in each phase (hence, how to split its budget across phases). opinion value of node i at the conclusion of phase q w 0 ii weightage attributed by node i to its bias in a phase wij weightage attributed by node i to the opinion of node j w (q) ig weightage attributed by node i to good camp in phase q w (q) ib weightage attributed by node i to bad camp in phase q x (q) i investment made by good camp on node i in phase q y (q) i investment made by bad camp on node i in phase q kg budget of the good camp k b budget of the bad camp

B. Related Work

Problems related to maximizing opinion adoption in social networks have been extensively studied in the literature [START_REF] Guille | Information diffusion in online social networks: A survey[END_REF], [START_REF] Easley | Networks, crowds, and markets: Reasoning about a highly connected world[END_REF], [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. A primary task in such problems is to determine influential nodes, which has been an important research area in the multiagent systems community [START_REF] Ghanem | Agents of influence in social networks[END_REF], [START_REF] Li | Agent-based influence maintenance in social networks[END_REF], [START_REF] Pasumarthi | Near optimal strategies for targeted marketing in social networks[END_REF], [START_REF] Dhamal | A multi-phase approach for improving information diffusion in social networks[END_REF]. The competitive setting has resulted in several game theoretic studies [START_REF] Ghaderi | Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate[END_REF], [START_REF] Anagnostopoulos | Competitive influence in social networks: Convergence, submodularity, and competition effects[END_REF], [START_REF] Bharathi | Competitive influence maximization in social networks[END_REF]. Specific to analytically tractable models such as DeGroot and Friedkin-Johnsen, there have been studies to determine optimal investments on influential nodes [START_REF] Dubey | Competing for customers in a social network: The quasi-linear case[END_REF], [START_REF] Bimpikis | Competitive targeted advertising over networks[END_REF], [START_REF] Grabisch | Strategic influence in social networks[END_REF]. Our work extends these studies to multiple phases by determining the influential nodes in different phases, and how much they should be invested on in a given phase.

There have been a few studies on adaptive selection of influential nodes in multiple phases [START_REF] Seeman | Adaptive seeding in social networks[END_REF], [START_REF] Rubinstein | Approximability of adaptive seeding under knapsack constraints[END_REF], [START_REF] Horel | Scalable methods for adaptively seeding a social network[END_REF], [START_REF] Correa | Adaptive rumor spreading[END_REF], [START_REF] Badanidiyuru | Locally adaptive optimization: Adaptive seeding for monotone submodular functions[END_REF], [START_REF] Tong | Adaptive influence maximization in dynamic social networks[END_REF], [START_REF] Yuan | No time to observe: Adaptive influence maximization with partial feedback[END_REF]. A survey of such adaptive methods is presented in [START_REF] Singer | Influence maximization through adaptive seeding[END_REF]. An empirical study on optimal budget splitting between two phases is presented in [START_REF] Dhamal | Information diffusion in social networks in two phases[END_REF], which is extended to multiple phases in [START_REF]Effectiveness of diffusing information through a social network in multiple phases[END_REF]. While the reasoning behind using multiple phases in these studies is to adaptively select nodes based on previous observations, we use them for influencing nodes' biases; this necessitates a very different treatment.

II. OUR MODEL

We represent social network as a weighted directed graph, with set of nodes N . Our model can be viewed as a multiphase extension of [START_REF] Dhamal | Optimal investment strategies for competing camps in a social network: A broad framework[END_REF]. Table I presents the notation. In our setting, the bias of node i in phase q is v (q-1) i , which is the opinion value of node i at the conclusion of phase q-1. Since the influence of good camp on node i in phase q would be an increasing function of its investment x (q) i and weightage w (q) ig , we assume the influence to be +w (q) ig x (q) i so as to maintain linearity of Friedkin-Johnsen model. Similarly, -w

(q) ib y (q) i
is the influence of bad camp (negative opinion) on node i. Considering budget constraints, the camps should invest in the p phases such that

p q=1 i∈N x (q) i ≤ k g and p q=1 i∈N y (q) i ≤ k b .
Let w be the matrix consisting of weights w ij . Let v (0) , v (q) , w 0 , w g , w b , x (q) , y (q) be the vectors consisting of elements v

(0) i , v (q) i , w 0 ii , w ig , w ib , x (q)
i , y

i , respectively. Vectors x (q) , y (q) , v (q-1) are static throughout a phase q, while v (q) gets updated in the dynamics. Let • denote Hadamard product: (a • b) i = a i b i . Hence, generalizing the Friedkin-Johnsen update rule to multiphase setting and accounting for camps' investments, the update rule in phase q is:

∀i ∈ N : v (q) i ← w 0 ii v (q-1) i + j∈N wijv (q) j + wigx (q) i -w ib y (q) i ⇐⇒ v (q) ← w 0 •v (q-1) + wv (q) + wg •x (q) -w b •y (q)
With j∈N |w ij | < 1, dynamics in phase q converges to [START_REF]Optimal multiphase investment strategies for influencing opinions in a social network[END_REF]:

v (q) = (I -w) -1 (w 0 • v (q-1) + wg • x (q) -w b • y (q) ) (1)

III. PROBLEM FORMULATION

We first derive an expression for i∈N v

(p)
i , the sum of opinion values of the nodes at the end of terminal phase p.

Let (I -w) -1 = ∆. Let r (1) i = j∈N ∆ ji and r (t) i = j∈N r (t-1) j w 0 jj ∆ ji . That is, r (1)
= ∆ T 1 and r (t) = ∆ T (r (t-1) • w 0 ). It can be shown that, premultiplying Equation ( 1) by 1 T for q = p, and solving the recursion, we get:

i∈N v (p) i = i∈N r (p) i w 0 ii v (0) i + p q=1 i∈N r (p-q+1) i (wigx (q) i -w ib y (q) i ) (2)
A. Multiphase Katz Centrality r

(1) i = (I -w T ) -1 1 i resembles Katz centrality of node i [START_REF] Katz | A new status index derived from sociometric analysis[END_REF], capturing its influencing power over other nodes in a single phase setting (corresponds to terminal phase in multiphase setting). However, the effectiveness of node i with t phases to go (r (t) j ), depends on its influencing power over those nodes j (∆ ji ), which would give good weightage to their bias in the next phase (w 0 jj ), and also have good effectiveness in the next phase with t -1 phases to go (r

(t-1) j
). This is captured by r (t) i = j∈N r (t-1) j w 0 jj ∆ ji . Since r (t) i quantifies i's influence looking t phases ahead, it can be interpreted as the t-phase Katz centrality.

B. The Problem

Here (x (q) ) p q=1 and (y (q) ) p q=1 are the respective strategies of the good and bad camps. Given an investment strategy profile (x (q) ) p q=1 , (y (q) ) p q=1 , let u g (x (q) ) p q=1 , (y (q) ) p q=1 be the utility of good camp and u b (x (q) ) p q=1 , (y (q) ) p q=1 be the utility of bad camp. The good camp aims to maximize (2), while the bad camp simultaneously aims to minimize it. Hence the problem is:

Find Nash equilibrium, given that ug (x (q) ) p q=1 , (y

(q) ) p q=1 = i∈N v (p) i u b (x (q) ) p q=1 , (y (q) ) p q=1 = - i∈N v (p) i subject to p q=1 i∈N x (q) i ≤ kg , p q=1 i∈N y (q) i ≤ k b ∀q ∈ {1, . . . , p} ∀i ∈ N : x (q) i , y (q) i ≥ 0

C. Optimal Investment Strategies

Since the optimization terms with respect to different variables are decoupled in Equation ( 2), the optimal strategies of camps are mutually independent. For the good camp, we order the terms {w ig r (p-q+1) i } i∈N,q=1,...,p in descending order. If the investment allowed per node is unbounded, its optimal strategy is to invest k g on node i * in phase q * , where (i * , q * ) = arg max (i,p) w ig r (p-q+1) i (no investment if this value is non-positive). If the investment per node is bounded by U, the (i, p) pairs are chosen one-by-one according to the aforementioned descending ordering, and invested on with U each, until budget k g is exhausted. The optimal strategy of the bad camp is analogous.

IV. SIMULATION RESULTS

For 2 phases on NetHEPT dataset (15,233 nodes) [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], [START_REF] Chen | Efficient influence maximization in social networks[END_REF], [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF], Figure 1(a) presents optimal budget allotted for phase 1 as a function of w 0 jj (assuming equal w 0 jj , ∀j ∈ N ) with k g = k b = 100 (U = 1 and v (0) i = 0, ∀i ∈ N ). Detailed simulation setup is provided in [START_REF]Optimal multiphase investment strategies for influencing opinions in a social network[END_REF]. For low w 0 jj , the optimal strategy of camps is to invest almost entirely in phase 2, since the effect of phase 1 would diminish considerably in phase 2. The value r

(2) i = j∈N r (1)
j w 0 jj ∆ ji would be significant only if i influences nodes j with significant values of w 0 jj . So investing in phase 1 would be advantageous only if nodes have significant w 0 jj . The slight non-monotonicity of plots is explained in [START_REF]Optimal multiphase investment strategies for influencing opinions in a social network[END_REF]. General observations indicate that a high range of w 0 jj makes it advantageous for camps to invest in phase 1, so as to effectively influence the biases in phase 2. The reasoning generalizes to more than 2 phases. (2) i ), while the good camp is farsighted (considering no bound on investment per node). A myopic bad camp would invest its entire budget in phase 1, and with the same reasoning as above, it would incur more loss for lower values of w 0 jj (ref. [START_REF]Optimal multiphase investment strategies for influencing opinions in a social network[END_REF] for details).

V. IN EXTENDED VERSION OF THIS PAPER

The extended version of this paper [START_REF]Optimal multiphase investment strategies for influencing opinions in a social network[END_REF] analyzes a setting where a node attributes higher weightage to the camp more aligned with its bias. The camps' strategies are no longer mutually independent; we show existence and polynomial time computability of Nash equilibrium.

Fig. 1 .Figure 1

 11 Fig. 1. Results illustrating the effects of w 0 jj (NetHEPT)

  The original publication appears as short paper in the 2018 International Conference on Autonomous Agents and Multiagent Systems. The full version of this paper is available at https://arxiv.org/pdf/1804.06081 Swapnil Dhamal, Walid Ben-Ameur, and Tijani Chahed are with Samovar, Télécom SudParis, CNRS, Université Paris-Saclay, France. Eitan Altman is with INRIA Sophia Antipolis-Méditerranée, France.

ACKNOWLEDGEMENTS

The original publication appears as short paper in the 2018 International Conference on Autonomous Agents and Multiagent Systems. The work is partly supported by CEFIPRA grant No. IFC/DST-Inria-2016-01/448 "Machine Learning for Network Analytics".


Swapnil Dhamal
email: swapnil.dhamal@gmail.com

Walid Ben-Ameur
email: walid.benameur@telecom-sudparis.eu

Tijani Chahed
email: tijani.chahed@telecom-sudparis.eu

Eitan Altman
email: eitan.altman@inria.fr

Manipulating Opinion Dynamics in Social Networks in Two Phases

We propose a setting for two-phase opinion dynamics in social networks, where the final opinion of a node in the first phase acts as its initial biased opinion in the second phase. In this setting, we study the problem of two camps aiming to maximize adoption of their respective opinions by strategically investing on nodes, where the effectiveness of a camp's investment on a node depends on the node's initial bias. We propose an extension of Friedkin-Johnsen model for our setting, and hence formulate the utility functions of the camps. For the non-competitive case where only one camp invests, we present a polynomial time algorithm for determining an optimal way to split the camp's budget between the two phases. For the case of competing camps, we show the existence of Nash equilibria under reasonable assumptions, and that they can be computed in polynomial time. Our main conclusion is that, if nodes attribute high weightage to their initial biases, it is advantageous to have a high investment in the first phase, so as to exploit the manipulated biases in the second phase.

Introduction

Studying opinion dynamics in a society is important to understand and influence elections, viral marketing, propagation of ideas and behaviors, etc. In this paper, we consider two camps who aim to maximize the adoption of their respective opinions in a social network. We consider a strict competition in the space of real-valued opinions, where one camp aims to drive the overall opinion of the network towards being positive while the other camp aims to drive it towards negative; we refer to them as good and bad camps respectively. We consider a well-accepted quantification of the overall opinion of a network: the average or equivalently, sum of opinion values of nodes [START_REF] Gionis | Opinion maximization in social networks[END_REF][START_REF] Grabisch | Strategic influence in social networks[END_REF]. Hence the good and bad camps simultaneously aim to respectively maximize and minimize this sum.

The average or sum of opinion values is of relevance in several applications, e.g., fund collection where the magnitude of a node's opinion value corresponds to the amount and the sign indicates the camp towards which it is willing to contribute. Another example is when nodes are reporting agents on social media, where a node's opinion corresponds to its reported intensity of an event based on the information it receives; this information could be influenced by the camps. In such scenarios, the opinion value of a node would be a real-valued number, and the sum or average of opinion values would be the overall opinion of the network.

Social networks play a prime role in determining the opinions of constituent nodes, since nodes usually update their opinions based on the opinions of their connections [START_REF] Easley | Networks, crowds, and markets[END_REF][START_REF] Acemoglu | Opinion dynamics and learning in social networks[END_REF]. This fact is exploited by camps; they determine influential nodes to invest on in the form of money, free products, convincing discussions, etc., so as to drive these nodes' opinions in their favor. Thus given a budget constraint, the strategy of a camp comprises of how much to invest on each node, in presence of a competing camp who also would invest strategically.

Motivation

In the popular model by Friedkin andJohnsen [1990, 1997], every node holds an initial bias in opinion. It could have formed owing to the node's fundamental views, experiences, mass media exposure, opinion dynamics in the past, etc. This initial bias plays an important role in determining a node's final opinion, and consequently the opinions of its neighbors and hence that of its neighbors' neighbors and so on. If nodes give significant weightage to their biases, the camps would want to manipulate these biases. This could be achieved by campaigning in multiple phases, wherein the opinion at the conclusion of a phase would act as the initial biased opinion for the next phase. Such campaigning is often used during elections and marketing, to gradually drive nodes' opinions.

The initial bias of a node often impacts the effectiveness of camps' investments on that node. For instance, if the initial bias of a node is positive, the investment made by the good camp is likely to be more effective on it than that made by the bad camp. The reasoning is similar to that of the bounded confidence model [START_REF] Krause | A discrete nonlinear and non-autonomous model of consensus formation[END_REF], where a node pays more attention to opinions that do not differ too much from its own opinion. Since a camp's effectiveness depends on the nodes' biases, its investment in the first phase not only manipulates the biases for getting a head start in the second phase, but also the effectiveness of its investment in the second phase.

With the possibility of campaigning in two phases, a camp could not only decide which nodes to invest on, but also how to split its available budget between the two phases.

Related Work

Several models of opinion dynamics have been proposed in the literature [START_REF] Acemoglu | Opinion dynamics and learning in social networks[END_REF][START_REF] Lorenz | Continuous opinion dynamics under bounded confidence: A survey[END_REF], some noteworthy ones being DeGroot [START_REF] Morris | Reaching a consensus[END_REF], Voter [START_REF] Holley | Ergodic theorems for weakly interacting infinite systems and the voter model[END_REF], Friedkin-Johnsen [Friedkin andJohnsen, 1990, 1997], bounded confidence [START_REF] Krause | A discrete nonlinear and non-autonomous model of consensus formation[END_REF], etc. In Friedkin-Johnsen model, each node updates its opinion using a weighted combination of its initial bias and its neighbors' opinions. We generalize this model to multiple phases, while also accounting for the camps' investments.

Problems related to determining influential nodes in social networks have been extensively studied [START_REF] Guille | Information diffusion in online social networks: A survey[END_REF][START_REF] Easley | Networks, crowds, and markets[END_REF][START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Gionis | Opinion maximization in social networks[END_REF]. For instance, [START_REF] Yildiz | Binary opinion dynamics with stubborn agents[END_REF] study the problem of optimal placement of stubborn nodes (whose opinion values stay unchanged) in the discrete binary opinions setting. There also have been game theoretic studies [START_REF] Ghaderi | Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate[END_REF][START_REF] Anagnostopoulos | Competitive influence in social networks: Convergence, submodularity, and competition effects[END_REF][START_REF] Bharathi | Competitive influence maximization in social networks[END_REF]. Specific to analytically tractable models such as DeGroot, there have been studies in the competitive setting to identify influential nodes and the amounts to be invested on them [START_REF] Dubey | Competing for customers in a social network: The quasi-linear case[END_REF][START_REF] Bimpikis | Competitive targeted advertising over networks[END_REF][START_REF] Grabisch | Strategic influence in social networks[END_REF]. Our work extends these studies to two phases, by identifying influential nodes in the two phases and how much they should be invested on in each phase.

There have been a few studies on adaptive selection of influential nodes for opinion diffusion in multiple phases [START_REF] Seeman | Adaptive seeding in social networks[END_REF][START_REF] Rubinstein | Approximability of adaptive seeding under knapsack constraints[END_REF][START_REF] Horel | Scalable methods for adaptively seeding a social network[END_REF][START_REF] Correa | Adaptive rumor spreading[END_REF][START_REF] Badanidiyuru | Locally adaptive optimization: Adaptive seeding for monotone submodular functions[END_REF][START_REF] Tong | Adaptive influence maximization in dynamic social networks[END_REF][START_REF] Yuan | No time to observe: Adaptive influence maximization with partial feedback[END_REF]. [START_REF] Singer | Influence maximization through adaptive seeding[END_REF] presents a survey of such adaptive methodologies. [START_REF] Dhamal | Information diffusion in social networks in two phases[END_REF] empirically study the problem of optimally splitting the available budget between two phases, which has been extended to multiple phases by [START_REF] Dhamal | Effectiveness of diffusing information through a social network in multiple phases[END_REF]. While the reasoning behind using multiple phases in these studies is adaptation of strategy based on previous observations, we aim to use multiple phases for manipulating the initial biases of nodes, which requires a very different analytical treatment.

To the best of our knowledge, there has not been an analytical study on a rich model such as Friedkin-Johnsen, for opinion dynamics in two phases (not even for single camp). The most relevant to this study is our work in [START_REF] Dhamal | Effectiveness of diffusing information through a social network in multiple phases[END_REF] where, however, a camp's influence on a node is assumed to be independent of the node's bias.

Our Contributions

• We formulate the two-phase objective function under

Friedkin-Johnsen model, where a node's final opinion in the first phase acts as its initial bias for the second phase, and the effectiveness of a camp's influence on the node depends on this initial bias.

• For the non-competitive case, we develop a polynomial time algorithm for determining an optimal way to split a camp's budget between the two phases.

• For the case of two competing camps, we show the existence of Nash equilibria under reasonable assumptions, and that they can be computed in polynomial time.

Our Model

Given a social network, let N be the set of nodes and E be the set of weighted directed edges. Let n = |N |. The weights could hold any sign, since the influences could be positive or negative [START_REF] Altafini | Consensus problems on networks with antagonistic interactions[END_REF]. Our model can be viewed as a multiphase extension of [START_REF] Dhamal | Optimal investment strategies for competing camps in a social network: A broad framework[END_REF].

Parameters

As our opinion dynamics runs in two phases, most parameters have two values, one for each phase. For such parameters, we denote its value corresponding to phase p using superscript (p), where p = 1, 2 for first and second phase, respectively. Initial Bias. Every node i holds an initial bias in opinion prior to the opinion dynamics process; we denote it by v 0 i ∈ R. In the multiphase setting, this acts as the initial bias for the first phase. We denote the opinion value of node i at the conclusion of phase 1 by v

(1) i . This acts as its initial bias for phase 2. So by convention, we have v

(0) i = v 0 i .
We denote the weightage that node i attributes to its initial bias by w 0

ii . Network Effect. Let w ij be the weightage attributed by node i to the opinion of its connection j. Consistent with Friedkin-Johnsen model, we assume the influence on node i owing to node j in phase p, to be w ij v (p) j . So the net influence on node i owing to all of its connections is j∈N w ij v (p) j . Weightage to Campaigning. We denote the weightage that node i attributes to the good and bad campaigning in phase p by w (p) ig and w (p) ib , respectively. Since we consider that the initial bias of a node impacts the effectiveness of camps' investments, v ii would also play a role since it quantifies the weightage given by node i to its initial bias. We hence propose a model on this line, wherein w . Let node i attribute a total of θ i to the influence weights of the camps, that is, w

(p) ig + w (p) ib = θ i .
We propose the following natural model:

w (p) ig = θi 1 + w 0 ii v (p-1) i 2 , w (p) ib = θi 1 -w 0 ii v (p-1) i 2 (1)
Camp Investments. The good and bad camps attempt to directly influence the nodes so that their opinions are pulled towards being positive and negative respectively. We denote the investments made by the good and bad camps on node i in phase p by x (p) i and y

(p) i respectively (x (p) i , y (p) i ≥ 0, ∀i ∈ N for p = 1, 2).
Since the influence of good camp (+ve opinion) on node i in phase p would be an increasing function of both x (p) i and w (p) ig , we assume the influence to be +w

(p) ig x (p) i (maintaining the linearity of Friedkin-Johnsen model). Sim- ilarly, -w (p) ib y (p) i
is the influence of bad camp (-ve opinion) on node i in phase p. Let k g and k b be the respective budgets of the good and bad camps. Hence the camps should invest in the two phases such that i∈N (x

(1) i + x (2) i ) ≤ k g and i∈N (y (1) i + y (2) i ) ≤ k b .
Weight Constraints. Friedkin-Johnsen model has the following condition on influence weights:

∀i ∈ N : |w 0 ii | + j∈N |wij| ≤ 1
Since the model follows an opinion update rule (as we see later), convergence is an important factor. A standard assumption for guaranteeing convergence is

j∈N |wij| < 1
This condition is usually enforced to ensure convergence. In our setting, this condition is natural and well suited, since we would have non-zero weights attributed to bias (w 0 ii ). Matrix Forms. Let W be the matrix consisting of weights w ij for each pair of nodes (i, j). p) be the vectors consisting of elements

Let v 0 , w 0 , Θ, w g (p) , w b (p) , x (p) , y (p) , v (
v 0 i , w 0 ii , θ i , w (p) ig , w (p) ib , x (p) i , y (p) i , v (p)
i , respectively. Let operation • denote Hadamard vector product, i.e., (a

• b) i = a i b i .

Opinion Update Rule

The update rule in Friedkin-Johnsen model is ∀i ∈ N :

v i ← w 0 ii v 0 i + j∈N w ij v j .
Extending to multiple phases, the update rule in the

p th phase is ∀i ∈ N : v (p) i ← w 0 ii v (p-1) i + j∈N w ij v (p) j .
Accounting for camps' investments, we get

∀i ∈ N : v (p) i ← w 0 ii v (p-1) i + j∈N wijv (p) j + w (p) ig x (p) i -w (p) ib y (p) i ⇐⇒ v (p) ← w 0 •v (p-1) +Wv (p) +wg (p) •x (p) -w b (p) •y (p) (2)
In phase p, the vectors x (p) , y (p) , v (p-1) stay unchanged; the weights w g (p) , w b (p) (which depend on v (p-1) ) and w 0 also stay unchanged; while v (p) gets updated. Hence, writing the update rule as recursion (with iterating integer τ ≥ 0):

v (p) τ = Wv (p) τ -1 + w 0 • v (p-1) + wg (p) • x (p) -w b (p) • y (p)
It can be simplified as

v (p) τ = W τ v (p) 0 + τ -1 η=0 W η (w 0 •v (p-1) +wg (p) •x (p) -w b (p) •y (p) )
Now, the initial bias for phase p : v

(p) 0 = v (p-1)
. Also, W is strictly substochastic (sum of each row strictly less than 1); its spectral radius is less than 1. So when τ → ∞, we have

lim τ →∞ W τ = 0 and lim τ →∞ τ -1 η=0 W η = (I -W) -1 [Grabisch et al., 2018]. Hence, lim τ →∞ v (p) τ = (I-W) -1 (w 0 •v (p-1) +wg (p) •x (p) -w b (p) •y (p) )
which is a constant vector. So the dynamics in phase p converges to the steady state

v (p) = (I-W) -1 (w 0 •v (p-1) +wg (p) •x (p) -w b (p) •y (p) ) (3)

Formulation of Two-Phase Objective Function

We now derive i∈N v (p)

i , the sum of nodes' opinions at the end of phase p ∈ {1, 2}. Premultiplying (3) by 1 T gives

1 T v (p) = 1 T (I -W) -1 (w 0 • v (p-1) + wg • x (p) -w b • y (p) ) Let ∆ = (I -W) -1 and r T = 1 T (I -W) -1 , that is, r i = j∈N ∆ ji . Since ∆ = ∞ η=0 W η ,
we have that ∆ ji is the influence that j receives from i through walks of all possible lengths. So r i = j∈N ∆ ji can be viewed as overall influencing power of i. Substituting these in above equation,

i∈N v (p) i = i∈N ri(w 0 ii v (p-1) i + wigx (p) i -w ib y (p) i )
When p = 1, this is the sum of opinions at the end of phase 1:

i∈N v (1) i = i∈N ri(w 0 ii v (0) i + w (1) ig x (1) i -w (1) ib y (1) i ) (4)
Similarly, the sum of opinion values at the end of phase 2

is j∈N v (2) j = j∈N rj(w 0 jj v (1) j + w (2) jg x (2) j -w (2)
jb y

(2)

j ) = j∈N rj w 0 jj v (1) j + θj 2 (1+w 0 jj v (1) j )x (2) j - θj 2 (1-w 0 jj v (1) j )y (2) j = j∈N rjw 0 jj v (1) j 1+ θj 2 x (2) j + θj 2 y (2) j + j∈N rj θj 2 (x (2) j -y (2) j )
The first term j∈N r j w 0 jj v

(1)

j 1 + θj 2 x (2) j + θj 2 y
(2) j can be obtained by premultiplying ( 4) by (r

• w 0 • (1 + Θ 2 • x (2) + Θ 2 • y (2)
)) T and using (1). Hence i∈N v

(2) i equals i∈N j∈N

w 0 ii v 0 i 1+ θi 2 x (1) i + θi 2 y (1) i + θi 2 (x (1)
i -y

(1)

i ) • • rjw 0 jj ∆ji 1+ θj 2 x (2) j + θj 2 y (2) j + j∈N rj θj 2 (x (2) j -y (2) j ) (5)
Here (x (1) , x (2) ) is the strategy of the good camp for the two phases, and (y (1) , y (2) ) is the strategy of the bad camp.

Given an investment strategy profile (x (1) , x (2) ), (y (1) , y (2) ) , let u g (x (1) , x (2) ), (y (1) , y (2) ) be the good camp's utility and u b (x (1) , x (2) ), (y (1) , y (2) ) be the bad camp's utility. The good camp aims to maximize the value of (5), while the bad camp aims to minimize it. So,

ug (x (1) , x (2) ), (y (1) , y (2) ) = i∈N v (2) i and u b (x (1) , x (2) ), (y (1) , y (2) ) = - i∈N v (2) i (6)
with the following constraints on the investment strategies:

i∈N x (1) i + x (2) i ≤ kg , i∈N y (1) i + y (2) i ≤ k b ∀i ∈ N : x (1) i , x (2) i , y (1) i , y (2) i ≥ 0
The game can thus be viewed as a two-player zero-sum game, where the players determine their investment strategies (x (1) , x (2) ) and (y (1) , y (2) ); the good camp invests as per x (1) in the first phase and as per x (2) in the second phase, and the bad camp invests as per y (1) in the first phase and as per y (2) in the second phase. Our objective essentially is to find the Nash equilibrium strategies of the two camps.

First we consider a simplified yet interesting (and not-yetstudied-in-literature) case where budget of one of the camps is 0 (say k b = 0); so effectively we have only the good camp.

The Non-Competitive Case

For notational simplicity, let b ji = r j w 0 jj ∆ ji , c i = w 0 ii v 0 i . We saw that r i = j∈N ∆ ji indicates the influencing power of node i. Now, b ji = ∆ ji w 0 jj r j quantifies the overall influence ∆ ji of i on j, which would give weightage w 0 jj to its initial opinion in the next phase, and have an influencing power of r j in the next phase. Hence b ji can be interpreted as the influence of node i on the network through node j, looking one phase ahead. So j∈N b ji can be viewed as the overall influencing power of node i, looking one phase ahead. We denote s i = j∈N b ji and identify its role in our analysis.

For non-competitive case, we have y

(1)

i = y (2) i = 0, ∀i ∈ N in (5). Using above notation, we get that i∈N v (2) i equals i∈N j∈N ci + θi 2 x (1) i (ci +1) bji 1+ θj 2 x (2) j + j∈N rj θj 2 x (2) j (7) = i∈N x (1) i θi 2 (ci +1) j∈N bji 1+ θj 2 x (2) j + i∈N j∈N cibji 1 + θj 2 x (2) j + j∈N rj θj 2 x (2) j (8) = j∈N x (2) j   θj 2 i∈N bji ci + θi 2 x (1) i (ci + 1) + θj 2 rj   + i∈N j∈N bji ci + θi 2 x (1) i (ci + 1) (9)
Deducing from Equations ( 8) and ( 9) that i∈N v

(2) i is a bilinear function in x (1) and x (2) , we prove our next result.

Let the budget k g be split such that k

(1)

g and k

(2)

g are the first and second phase investments, respectively. Our method of finding optimal k

(1) g and k

(2) g is to first search for them in the search space k

(1) g + k

(2) g ∈ (0, k g ] and then compare the thus obtained value of i∈N v

(2) i with that corresponding to k

(1) g = k (2) g = 0, to get the optimal value of i∈N v (2) i . Proposition 1. In the search space k (1) g + k (2) g ∈ (0, k g ],
it is optimal for good camp to exhaust entire budget (k

(1) g +k (2) g = k g
), and to invest on at most one node in each phase.

Proof. Given any x (2) , Expression (8) can be maximized with respect to x (1) by allocating k g -j∈N x

(2) j to a sin-

gle node i that maximizes θi 2 (c i +1) j∈N b ji 1 + θj 2 x
(2) j , if this value is positive. In case of multiple such nodes, one node can be chosen at random. If this value is non-positive for all nodes, it is optimal to have x (1) = 0. When x (1) = 0, Expression (9) now implies that it is optimal to allocate the entire budget k g in second phase to a single node j that maximizes θj 2 i∈N b ji c i + r j , if this value is positive. If this value is non-positive for all nodes, it is optimal to have x (2) = 0. This is the case where starting with an x (2) , we conclude that it is optimal to either invest k g -j∈N x

(2) j on a single node in first phase, or invest the entire budget k g on a single node in second phase, or invest in neither phase.

Similarly using (9), starting with a given x (1) , we can conclude that it is optimal to either invest k g -j∈N x

(1) j on a single node in the second phase, or invest the entire k g on a single node in the first phase, or invest in neither phase.

So starting from any x (1) or x (2) , we can iteratively improve (need not be strictly) on the value of ( 7) by investing on at most one node in a given phase. Furthermore, it is suboptimal to have k

(1) g + k (2) g < k g unless k (1) g = k (2) g = 0.
So there exist optimal vectors x (1) and x (2) that maximize (7), such that x

(1)

α = k (1) g , x (2) β = k (2) g , x (1) i =α = x (2) j =β = 0.
Now the next step is to find nodes α and β that maximize (7). By incorporating α and β in (7), we have i∈N v

(2) i equals i =α j =β cibji + cα + θα 2 k (1) g (cα +1) b βα 1+ θ β 2 k (2) g +r β θ β 2 k (2) g + j =β bjα cα + θα 2 k (1) g (cα + 1) + i =α ci b βi 1 + θ β 2 k (2) g = i∈N j∈N cibji + θα 2 k (1) g j bjα(cα + 1) + θ β 2 k (2) g i∈N b βi ci + r β + θαθ β 4 k (1) g k (2) g b βα (cα + 1) (10)
Now, for a given pair (α, β), we will find the optimal values of k

(1) g and k

(2) g from ( 10). From Proposition 1, we have k

(2) g = k g -k (1)
g . So the expression to be maximized is

k (1) g θα 2 j∈N bjα(cα +1) + (kg -k (1) g ) θ β 2 i∈N b βi ci +r β +k (1) g (kg -k (1) g ) θαθ β 4 b βα (cα + 1) + i∈N j∈N cibji
Equating its first derivative w.r.t. k

(1)

g to zero, we get

k (1) g = kg 2 + j∈N bjα θ β b βα -i∈N b βi ci + r β θαb βα (cα + 1)
A valid value of k

(1)

g can be obtained only if the denominators in above expression are non-zero. However, a zero denominator would mean that Expression (10) is linear, resulting in only two possibilities of k

(1) g , namely, 0 or k g . Also, if the second derivative with respect to k

(1) g is positive, that is, -θ α θ β r β w 0 ββ ∆ βα (w 0 αα v 0 α +1) > 0, optimal k (1)
g is either 0 or k g . If the second derivative with respect to k

(1)

g is negative: -θ α θ β b βα (c α +1) = -θ α θ β r β w 0 ββ ∆ βα (w 0 αα v 0 α +1) < 0, and since k (1) g is bounded in [0, k g ], optimal k (1) g for pair (α, β) is (since c i = w 0 ii v 0 i , b ji = r j w 0 jj ∆ ji , s i = j∈N b ji ): min max kg 2 + sα θ β r β w 0 ββ ∆ βα - 1 + w 0 ββ i∈N ∆ βi w 0 ii v 0 i θαw 0 ββ ∆ βα (1+w 0 αα v 0 α )
, 0 , kg (11) and the corresponding optimal value of k

(2)

g is min max kg 2 - sα θ β r β w 0 ββ ∆ βα + 1 + w 0 ββ i∈N ∆ βi w 0 ii v 0 i θαw 0 ββ ∆ βα (1+w 0 αα v 0 α ) , 0 , kg (12)
When we assumed k

(1)

g and k

(2)

g to be fixed, we had to iterate through all (α, β) pairs to determine the one that gives the optimal value of Expression (10). Now, whenever we look at an (α, β) pair, we can determine the corresponding optimal values of k (1) g and k

(2) g using ( 11) and ( 12), and hence determine the value of Expression (10) by plugging in the optimal k

(1) g and k

(2) g and that (α, β) pair. The optimal pair (α, β) can thus be obtained as the pair that maximizes (10).

Above analysis holds when k

(1)

g + k (2)
g = k g . From Proposition 1, we need to consider one more possibility that k

(1) g = k

(2) g = 0, which gives a constant value i∈N j∈N c i b ji for Expression (10). Let (0, 0) correspond to this additional possibility. It is hence optimal to invest k

(1) g (obtained using ( 11)) on node α in the first phase and k

(2) g (obtained using ( 12)) on node β in the second phase, subject to it giving a value greater than i∈N j∈N c i b ji to Expression (10).

Since we iterate through (n 2 + 1) possibilities (namely, (α, β) ∈ N × N ∪ {(0, 0)}), the above procedure gives a polynomial time algorithm for determining the optimal budget split and the optimal investments on nodes in two phases. Remark 1. For non-negative values of parameters, (11) indicates that for a given (α, β) pair, the good camp would want to invest more in the first phase for a higher s α . This is intuitive from our understanding of s α being viewed as the influencing power of node α looking one phase ahead. Similarly, (12) indicates that it would want to invest more in second phase for a higher r β , since r β can be viewed as the influencing power of node β in the immediate phase. Also, ( 11) and ( 12) indicate that a higher θ α drives the camp to invest in first phase and a higher θ β drives it to invest in second phase. Since w ig is an increasing function of θ i , this implicitly means that a node with a higher w ig drives the good camp to invest in the phase in which that node is selected. Further, we illustrate the role of w 0 ii using simulations in Section 5.

The Case of Competing Camps

Similar to Proposition 1, we can show that i∈N v

(2) i is a multilinear function in this case also, since it can be written as a linear function in x (1) , y (1) , x (2) , y (2) separately. The following proposition can be hence proved on similar lines.

Proposition 2. In the search space k

(1)

g + k (2) g ∈ (0, k g ],
it is optimal for good camp to have k

(1) g + k (2) g
= k g , and invest on at most one node in each phase. In the search space k

(1) b +k (2) b ∈ (0, k b ], it is optimal for bad camp to have k (1) b + k (2) b = k b ,
and invest on at most one node in each phase.

Denoting

w 0 ii v 0 i = c i , r j w 0 jj ∆ ji = b ji , s i = j∈N b ji as before, from Expression (5), i∈N v (2) i can be expanded as i∈N j∈N cibji + j∈N x (2) j θj 2 i∈N cibji +rj + j∈N y (2) j θj 2 i∈N cibji -rj + i∈N x (1) i θi 2 (1+ci) si + j∈N x (2) j θj 2 bji + j∈N y (2) j θj 2 bji - i∈N y (1) i θi 2 (1-ci) si + j∈N x (2) j θj 2 bji + j∈N y (2) j θj 2 bji (13)
From Proposition 2, there exist optimal vectors x (1) , x (2) for good camp and optimal vectors y (1) , y (2) for bad camp, such that x andx (1)

(1) α = k (1) g , x (2) β = k (2) g , y (1) γ = k (1) b , y (2) δ = k (2) b ,
i =α = x (2) j =β = y (1) i =γ = y
(2) j =δ = 0. Assuming such profile of nodes ((α, β), (γ, δ)), we first find ((x

(1) α , x (2) β ), (y (1) γ , y (2) δ )),
or equivalently, the optimal ((k

(1) g , k (2) g ), (k (1) b , k (2) b )) corre- sponding to such a profile. By incorporating ((α, β), (γ, δ)), Expression (13) for i∈N v (2) i simplifies to i∈N j∈N cibji +k (2) g θ β 2 i∈N cib βi + r β +k (2) b θ δ 2 i∈N cib δi -r δ + k (1) g θα 2 (1 + cα) sα + k (2) g θ β 2 b βα + k (2) b θ δ 2 b δα -k (1) b θγ 2 (1 -cγ) sγ + k (2) g θ β 2 b βγ + k (2) b θ δ 2 b δγ (14)
First, we consider the case when k

(1) g + k (2) g = k g and k (1) b + k (2) b = k b . Now,
for a given profile of nodes ((α, β), (γ, δ)), we will find the optimal values of k

(1) g , k (2) g , k (1) b , k (2)
b . In this case, we have k

(2) g = k g -k (1) g and k (2) b = k b -k (1)
b . Substituting this in ( 14) and simultaneously solving

∂ i∈N v (2) i ∂k (1) g = 0 and ∂ i∈N v (2) i ∂k (1) b = 0, we get k (1) g equal to (letting A = θ γ θ δ (1 -c γ )b δγ and B = 1 2 (θ α θ δ (1 + c α )b δα -θ γ θ β (1 -c γ )b βγ ) ): 1 B 2 +θαθ β (1+cα)b βα A sαθα(1+cα)A-r β θ β A-sγ θγ (1-cγ )B +r δ θ δ B +kg θαθ β 2 (1 + cα)b βα A - θγ θ β 2 (1 -cγ )b βγ B +k b θαθ δ 2 (1 + cα)b δα A - θγ θ δ 2 (1 -cγ )b δγ B -θ β A i∈N cib βi -θ δ B i∈N cib δi
We can similarly obtain k i . So we can effectively write u g ((x (1) , x (2) ), (y (1) , y (2) )) as u g ((α, β), (γ, δ)), where u g ((α, β), (γ, δ)) is the value of i∈N v

(2) i , which corresponds to the strategy profile where good camp invests on nodes (α, β) with optimal budget split (k

(1) g , k (2)
g ), and bad camp invests on nodes (γ, δ) with optimal budget split (k ∈ [0, k b ], we make a practically reasonable assumption so as to determine u g ((α, β), (γ, δ)). It is easy to show that if w ij ≥ 0, ∀(i, j), then ∆ ij ≥ 0, ∀(i, j) and r i ≥ 1, ∀i ∈ N . So if we assume w ij ≥ 0, ∀(i, j) and w 0 ii ≥ 0,

θ i ≥ 0, v 0 i ∈ [-1, 1], ∀i ∈ N , we would have that -θ α θ β r β w 0 ββ ∆ βα (1 + w 0 αα v 0 α ) ≤ 0 and θ γ θ δ r δ w 0 δδ ∆ δγ (1 -w 0 γγ v 0 γ ) ≥ 0.
That is, we would have i∈N v

(2) i to be a convex-concave function, which is concave w.r.t. k (2) i [START_REF] Boyd | Convex optimization[END_REF][START_REF] Joseph Arrow | Studies in linear and nonlinear programming[END_REF]. So we can assign this value i∈N v

(2) i to u g ((α, β), (γ, δ)). Thus using above technique, we obtain u g ((α, β), (γ, δ)) for all profiles of nodes ((α, β), (γ, δ)) when k

g = k (2) g = 0. Let the profile ((α, β), (0, 0)) correspond to k (1) b = k (2) b = 0. Note that when k (1) b = k (2)
b = 0, it reduces to non-competitive case with only good camp (Section 3); the value of i∈N v

(2) i for an (α, β) pair can hence be assigned to u g ((α, β), (0, 0)). Thus we can obtain u g ((α, β), (γ, δ)) for all profiles of nodes ((α, β), (0, 0)). Similarly, we can obtain u g ((α, β), (γ, δ)) for all profiles of nodes ((0, 0), (γ, δ)). And from Equation ( 14), u g ((0, 0), (0, 0)) = i∈N j∈N c i b ji .

So we have that the good camp has (n 2 + 1) possible pure strategies to choose from, namely, (α, β) ∈ N ×N ∪{(0, 0)}. Similarly, the bad camp has (n 2 + 1) possible pure strategies to choose from, namely, (γ, δ) ∈ N × N ∪ {(0, 0)}. We thus have a two-player zero-sum game, for which the utilities of the players can be computed for each strategy profile ((α, β), (γ, δ)) as explained above. Though we cannot ensure the existence of a pure strategy Nash equilibrium, the finiteness of the number of strategies ensures the existence of a mixed strategy Nash equilibrium. Further, owing to it being a two-player zero-sum game, the Nash equilibria can be found efficiently by solving a linear program [START_REF] Osborne | An introduction to game theory[END_REF].

Summarizing, under practically reasonable assumptions (w ij ≥ 0, ∀(i, j) and w 0 ii ≥ 0, θ i ≥ 0, v 0 i ∈ [-1, 1], ∀i ∈ N ), we transformed the problem into a two-player zero-sum game with each player having (n 2 + 1) pure strategies, and showed how the players' utilities can be computed for each strategy profile. We thus deduced the existence of Nash equilibria and that they can be found efficiently using linear programming.

Simulations and Results

For determining implications of our analytical results on real-world networks, we conducted simulations on NetHEPT (15,233 nodes, 31,376 edges): a dataset widely used for experimental justifications in the literature on opinion diffusion [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Chen | Efficient influence maximization in social networks[END_REF][START_REF] Chen | Scalable influence maximization for prevalent viral marketing in largescale social networks[END_REF]. We present our results for the non-competitive case. We point that though we presented a polynomial time algorithm for two camps, which is of theoretical interest, it is computationally expensive to run on networks larger than a few hundred nodes. It is hence worth exploring the possibility of a more efficient algorithm. Setup. We assume the value of w 0

ii to be same for all nodes, in order to study the effect of this value. The range of values we consider for w 0

ii is {0, 0.05, . . . , 0.95}. Let N (i) be the set of i's neighbors. We model the influence weights as follows. For a given w 0 ii , we consider θ i > 0 and w ij ≥ 0, ∀j ∈ N (i) such that the weights for any node i sum to 1, i.e., θ i + j∈N (i) w ij = 1-w 0

ii . For different values of w 0 ii , the values of θ i and w ij are scaled proportional to (1-w 0 ii ). We consider v 0 i = 0, ∀i ∈ N to start with a neutral network, for reliably studying the effects of critical parameters r i , w 0

ii , and hence also s j . So, w

(1) ig = θi 2 and w

(2) ig = θi 2 (1+w 0 ii v

(1) i ). Results. Figure 1 presents the optimal budget that should be allotted for first phase as a function of w 0

ii . In our simulations, the optimal values obtained are such that k

(2)

g = k g -k (1) g .
For low values of w 0

ii , the optimal strategy is to invest almost entirely in second phase. This is because the effect of first phase diminishes in second phase when w 0 ii is low. Remark 1 states that high s j value (influencing power of j looking one phase ahead) would attract more investment in first phase. The value s j = i∈N r i w 0

ii ∆ ij would be significant only if j influences nodes i with significant values of w 0

ii . With low w 0

ii , we are less likely to have node j with high value of s j since it requires it to be influential towards significant number of nodes i with significant values of w 0

ii . Hence allotting a significant budget for first phase would be advantageous only if we have nodes with significant value of w 0

ii . We considered v 0 i = 0, ∀i ∈ N in above simulations, however, we also observed the effects of v 0 i = 0 (initially biased network); the nature of plot remains similar to Figure 1 with subtle differences. If v 0 i 's are mostly positive, the good camp invests less in first phase, mainly because v 0 i 's already give a good head start to have a healthy value at the end of first phase (which is bias for second phase), and the budget could rather be invested in second phase. If v 0 i 's are mostly negative, it invests more in first phase to nullify the initial disadvantage.

Conclusion

Using Friedkin-Johnsen model, we proposed a framework for two-phase investment on nodes in a social network, where a node's opinion in first phase acts as its bias in second phase, and the effectiveness of a camp's investment depends on this bias. For one investing camp, we derived polynomial time algorithm for determining optimal budget split between two phases. Our simulations quantified the impact of the weightage that nodes attribute to their biases; a high weightage necessitated high investment in first phase, so that the manipulated biases could be harnessed in second phase. For competing camps, we showed existence of Nash equilibria under reasonable assumptions (w ij ≥ 0, ∀(i, j) and w 0 ii ≥ 0, θ i ≥ 0, v 0 i ∈ [-1,1], ∀i ∈ N ) and their polynomial time computability.

  g , i.e., -θ α θ β r β w 0 ββ ∆ βα (1 + w 0 αα v 0 α ) < 0 and that w.r.t. k(1) b , i.e., θ γ θ δ r δ w 0 δδ ∆ δγ (1 -w 0 γγ v 0 γ ) > 0, and the obtained solution is such that k (1) g ∈ [0, k g ] and k (1) b ∈ [0, k b ], then neither the good camp can change k

  in the domain ([0, k g ], [0, k b ]), we can find a (k

Figure 1 :

 1 Figure 1: Illustration of the effect of w 0 ii (NetHEPT) with kg = 100

Acknowledgement

The work is partly supported by CEFIPRA grant No. IFC/DST-Inria-2016-01/448 "Machine Learning for Network Analytics".