# Keeping Up With the Winner!
Targeted Advertisement to Communities in Social Networks

Shailaja Mallick1, Vishwaraj Doshi2, Do Young Eun1

###### Abstract

When a new product enters a market already dominated by an existing product,
will it survive along with this dominant product? Most of the existing works
have shown the coexistence of two competing products spreading/being adopted
on overlaid graphs with same set of users. However, when it comes to the
survival of a weaker product on the same graph, it has been established that
the stronger one dominates the market and wipes out the other. This paper
makes a step towards narrowing this gap so that a new/weaker product can also
survive along with its competitor with a positive market share. Specifically,
we identify a locally optimal set of users to induce a community that is
targeted with advertisement by the product launching company under a given
budget constraint. To this end, we model the system as competing Susceptible-
Infected-Susceptible (SIS) epidemics and employ perturbation techniques to
quantify and attain a positive market share in a cost-efficient manner. Our
extensive simulation results with real-world graph dataset show that with our
choice of target users, a new product can establish itself with positive
market share, which otherwise would be dominated and eventually wiped out of
the competitive market under the same budget constraint.

##  1 Introduction

Motivation: In this competitive world of rapid technological advancements, one
of the key strategic decisions that a company launching a new product has to
make is how to market itself (Cooper and Kleinschmidt 1987; Montoya-Weiss and
Calantone 1994). It can carve out a niche by differentiating itself from its
competitors, either by its product design or brand image (Fuchs and
Diamantopoulos 2010; Jalkala and Keränen 2014), and highlighting them through
marketing techniques such as advertisements. In such situations,
advertisements serve as a medium of communication and play a key role for the
firm to achieve this differentiation. There has been evidence that products
with no mass advertisements have gained popularity over time as the companies
have focused on targeting advertisements to niche communities (Dalgic and
Leeuw 1994). The effectiveness of targeting a small portion of users
(communities) who can further spread and influence their neighborhood network
via the word-of-mouth, rather than focusing on the whole population, has
proven beneficial and also recognized by businesses in the market (Armstrong
and Kotler 2003; Yang et al. 2006).

For example, Nintendo dominated the video game consoles market in the US for
almost a decade until the introduction of the PlayStation (PS) (Gallagher and
Park 2002). Over the next few years, PS was able to establish and eventually
dominate the video game console market, forcing Nintendo to focus on hand-held
consoles. Subsequently, Xbox initially entered a PS-dominated video game
consoles market, and was able to sustain itself in the market (Nic Healey
2013). Similarly, in the aviation industry, Airbus entered and managed to
sustain in a Boeing dominated market (Irwin and Pavcnik 2004). Figure 1 shows
how before the introduction of Xbox 360, PS 2 already dominated the US market
and since the emergence of Xbox, it took some time to mark its presence in the
market against its competitor (similar for iPhone 4S and Galaxy S4)111Real-
data collected from Google Trends for the United States region which provides
“insights into search pattern”(https://trends.google.com/trends/?geo=US)..

Figure 1: Real web-search percentage over a time period showing the
introduction of a new product (Galaxy S4 & Xbox 360) alongside an existing
product (iPhone 4S & PlayStation 2).

Note that, in the above examples, the new product always enters a monopoly,
i.e., market dominated by a single competitor, and manages to survive. Hence,
given these motivating examples, we focus on the following scenario: any given
market is dominated by a single product and a competing product strategizes
(i.e., advertising to niche communities) to survive in that market.
Specifically, our mathematical model captures the early phase of market
scenario when there is only one product in the market and a ‘new’ product
tries to enter this monopoly.

When it comes to modeling product competition where individuals are the
adopters, the interactions between them can be modeled as edges of a graph,
which are linked via socially meaningful relationships like friendship or
information exchange. Such social networks have become the paradigm for
studying the spread of competing products and their adoption among individuals
(Kalish 1985). Although here we stress on ‘product’ adoption and its influence
among neighbors, we can draw a similar analogy within different contexts, for
example, having an opinion (or preference) towards a political
party/idea/information spreading in a network and how targeted advertisement
plays an influential role in opinion formation/spreading mechanism. Given
these motivating scenarios, we focus on settings where a new product enters a
market dominated by a competitor.

Choice of Modeling Approach - bi-SIS: When two products compete with each
other on a network, the eventual outcomes can be one of the following:
absolute dominance, where one of the products dominates by wiping out its
competitor and is adopted widely; die-out, where none of the products are
adopted; or coexistence, where both of the products are adopted within the
network (Prakash et al. 2012; Beutel et al. 2012; Sahneh and Scoglio 2014; Wei
et al. 2016). Various mathematical models, such opinion dynamics-based models
(i.e., analysis of how opinions form/spread in a population) such as De-Groot,
Hegselmann-Krause, Friedkin-Johnsen, variants of epidemic models (Omic and Van
Mieghem 2009; Liu et al. 2019), and others (Proskurnikov and Tempo 2017,
2018), have been proposed to capture the dynamics of competing products. Most
of the works around classical opinion dynamics-based models focus on showing
eventual consensus (everyone agrees to one of the opinions/rumors eventually),
which has also been extended to capture the scenario of coexistence of two
opinions (or clusters of opposing opinions). These works have shown
coexistence by either relying on external factors in the form of stubborn
agents (initially or currently forming bias towards an opinion), zealots (who
never alter their initial stance) or via the inclusion of confidence bounds
beyond which individuals do not interact (Gargiulo, Lottini, and Mazzoni 2008;
Yang et al. 2012; Dandekar, Goel, and Lee 2013; Mobilia 2015; Amelkin, Bullo,
and Singh 2017; Mukhopadhyay, Mazumdar, and Roy 2020; Anagnostopoulos et al.
2022; Nguyen et al. 2020). The addition of stubborn agents already guarantees
that at least one of the opinions (the one followed by the stubborn agents) is
always adopted and hence results in clusters of opinions. With the inclusion
of these additional factors in the model setups, eventual consensus, or
complete wipe-out is infeasible.

The propagation of information, influence maximization, idea, or opinion/rumor
diffusion in a network has also been extensively studied via Linear Threshold
(LT)/ Information Cascade (IC) model (Kempe, Kleinberg, and Tardos 2003; Chen,
Yuan, and Zhang 2010). In these models, individuals can be either in an active
(i.e., influenced) or an inactive (i.e., free of influence) state. Here, the
overarching assumption is that individuals either never change states or can
only switch between active or inactive states randomly (Granovetter 1978;
Pathak, Banerjee, and Srivastava 2010), with all nodes (users) becoming
activated eventually. This is not always true in the context of
products/opinions, as people tend to change their preferences/opinions/views
from time to time.

The Susceptible-Infected-Susceptible (SIS) epidemic model has been used to
study the spread of viruses in a network of populations (Lajmanovich and Yorke
1976; Van Mieghem, Omic, and Kooij 2008). However, the bi-SIS model, a variant
of the SIS model (single virus), has been used to characterize the spreading
dynamics of two competing products/opinions in a network (Prakash et al. 2012;
Sahneh and Scoglio 2014). In such a model, via word-of-mouth or by being
influenced by their neighbors, users adopt one of the two competing products
(get infected) and gradually recover to become susceptible to infection again.
Unlike the opinion dynamics-based model or LT/IC model, the bi-SIS model does
not necessitate that the individuals have an opinion, positive or negative,
ex-ante; in contrast, it allows individuals to switch states from being
susceptible (inactive) to an infected (active) state and vice-versa. It has
proved to be effective in capturing eventual consensus or coexistence in any
general arbitrary graph, including special graphs such as complete or random
graphs (Wang et al. 2003; Li, van de Bovenkamp, and Van Mieghem 2012; Prakash
et al. 2012; Santos, Moura, and Xavier 2015; Yang, Yang, and Tang 2017). It
can be seen that the bi-SIS model aptly captures competitiveness without the
need to have any prior assumptions or dependence on a specific network
structure. Thus, the bi-SIS model captures all the three possible state spaces
along with providing conditions for each of the outcomes i.e., die-out,
absolute dominance, and coexistence.

Although the bi-SIS model is effective in capturing all the possible outcomes,
most of the existing works only focus on the stability analysis of the
equilibrium points or identifying which of the three possible outcomes the
system converges to (Van Mieghem, Omic, and Kooij 2008; Li, van de Bovenkamp,
and Van Mieghem 2012; Prakash et al. 2012; Sahneh and Scoglio 2014; Doshi,
Mallick, and Eun 2021). Furthermore, none of these works explicitly quantify
the magnitude of existence; for example, the market share of either one or
both of the competing products, especially in a general graph setting. Note
that with respect to opinion dynamics, for example, the simple linear French-
De-Groot model with stubborn agents (French Jr 1956; Proskurnikov and Tempo
2017) has shown quantifying results on a general graph. However, as mentioned
earlier, unlike the bi-SIS model, the opinion dynamics-based models do not
capture all the three possible state space and thus pose a limitation when it
comes to the analysis of the market share of competing products.

Our Contributions: In this paper, we take a step forward and propose
techniques to quantify and improve the market share of the new/weaker product
when it competes with an existing dominant product in the market via bi-SIS
epidemic model. Under limited budget constraints, this new company launching
its product would aim for survival, and the best strategy in this situation is
to target certain users via advertisement/promotional offers to form a small
support users’ group (community) who, with their positive reviews, can spread
about this new product. The motivation behind promoting such communities
(additional edges among the users of the graph) is to increase the rate of
influence so as to maximize the chance of its survival. Specifically, a
resource-constrained company would want to identify an optimal set of
individuals to form such communities to maximize its (positive) market share
as much as possible.

When it comes to quantifying the resulting market share on a general graph,
there is no known closed-form for the positive fixed point (market share) even
for a single-SIS model. The situation is further compounded when the
competition comes into play (bi-SIS). To tackle this challenge, we employ the
perturbation approach to optimally assign the resources under a specific
budget structure based on model parameters and approximate the resulting
market share of this original losing/weaker product. Our proposed budget
structure also accounts for a minimum budget below which the company, despite
spending positive amount of budget on advertisement expecting a non-zero
return on investment, still gets zero market share and thus cannot compete
with its competitor. By leveraging our theoretical findings, we develop a
heuristic approach which returns a locally optimal choice of users, under a
total budget constraint with heterogeneous costs for different users. We also
demonstrate the efficacy of our approach by comparing against different
benchmarks such as different standard centrality measures, over real network
topology with various cost constraints for the users in the community.

##  2 System Model and Problem Setup

In this section, we take an initial look at the problem of optimally targeting
individual users and recruiting them to participate in community, with the
goal of maximizing the long term market share of the new product. It has been
shown that when two products compete on a ‘same’ graph222Same graph is
analogous to one social network platform, for example, Facebook. with same set
of users, at steady state, the stronger one dominates and wipes-out the weaker
one (Prakash et al. 2012). WLOG, in our setting, on a ‘same’ graph, Product 1
is the dominant product in the market and Product 2 is the new/weaker product
(with zero market share) trying to compete against Product 1 for a positive
market share. In our context, a community or online discussion forum provides
a platform where a group of interacting users actively exchange information
about common interests. Few pertinent examples can be a subreddit – a
community in Reddit (Reddit 2009) or influencer pods in social media
platforms. In a subreddit, members can post information which is accessible to
all members of the group, irrespective of whether members follow each other or
not. In the case of influencer pods, groups of influencers work together to
boost each other’s engagement (e.g., product’s marketing) (Contributor 2024).
We focus on the problem of creating one such community. We assume that any
interactions or discussions between users in this newly formed community are
solely about the new company’s product, and the influence among the users of
the community is uniform/homogeneous.

Figure 2: Illustration of users forming community (Nodes 1,3,6-8 in layer
$\mathcal{F}$). The blue (red) nodes denote users adopting Product 1 (Product
2) at any given instance, and gray nodes are the users who do not own any of
the products.

Suppose that any user whom the company has targeted in the form of
advertisement/content-marketing chooses to engage in the community-based
discussions with a certain probability. We can safely assume that the more
aggressive the company is with its advertising efforts targeted towards the
user, the higher is the probability of the user participating in this created
community. In real life, these targeted advertisement efforts take various
forms, such as product placement, early-bird discounts, or promotional offers,
and cost a certain amount of resources. Later in this section, we give a more
detailed discussion on the modelling aspects of the cost structure for our
problem.

### The System Model

Let $u_{i}$ denote the probability with which any user $i\in\mathcal{N}$
actively engages in such a community. We assume that all users participating
in the community are able to communicate with one another, and Product 2’s
influence spreads across this community with rate $\gamma\beta_{2}$ (where
$\gamma$ is a factor capturing the rate of influence relative to $\beta_{2}$).
To clearly visualize this creation of a community, we draw it as a separate
layer, as shown in Figure 2. The top layer $\mathcal{G}$ denotes the original
graph where the mutual follower relationships are according to adjacency
matrix $\mathbf{A}$, and layer $\mathcal{F}$ denotes the created community, in
which a user $i\in\mathcal{N}$ participates with probability $u_{i}$. The
spread of influence within this community, is akin to adding an edge of weight
$\gamma$ for any two users $i$ and $j$ known to be actively participating in
the community. Specifically, the parameter $\gamma$ denotes the amount the
company is willing to spend on the members of the community to improve their
communication efficiency (user’s interaction). If the two users were already
connected prior to being a part of the community, that is, $a_{ij}=1$
($a_{12}$ in Figure 2), then $\gamma$ is simply an additional reinforcement of
their connection as a consequence of them interacting through multiple media.
The thick ‘red’ lines in Figure 2 highlight this reinforcement whereas the
‘black’ lines indicate the original interaction links. Specifically, the
introduction of additional edge weight (as shown in layer $\mathcal{F}$ in
Figure 2) is to induce an artificial community-like structure (clique) where
the edge weight denotes how much the users are influenced from other users
through their posts/shared information. The probability with which both $i$
and $j$ engage in the forum thus becomes $u_{i}u_{j}$ ($u_{7}u_{8}$ in Figure
2), and the total weight of edges connecting them is, on average, given by
$a_{ij}+\gamma u_{i}u_{j}$. Table 1 explains the terminology we have used in
this paper. We denote vectors ($\mathbf{v}\\!\in\\!\mathbb{R}^{N}$) and
matrices ($\mathbf{H}\in\mathbb{R}^{N\times N}$) as bold lowercase and
uppercase letters, respectively. Note that in our model we assume that the
Product 1 does not advertise to counter this ‘incursion’ by Product 2 and a
user cannot adopt both products at the same time. We also assume that the
complete network structure information is available to the company before
launching the new product.

Symbol | Definition/Description
---|---
$\mathcal{G(N,E)}$ | Undirected, connected graph
$\mathcal{N}=\\{1,2,\dots,N\\}$ | Set of nodes
$\mathbf{A}\triangleq[a_{ij}]$ | Adjacency matrix of graph $\mathcal{G}$
$\beta_{1}$ ($\beta_{2}$) | Adoption rate of product 1 (or product 2)
$\delta_{1}$ ($\delta_{2}$) | Disown rate of product 1 (or product 2)
$\tau_{1}=\beta_{1}/\delta_{1}$ ($\tau_{2}$) | Effective adoption rate of product 1 (or product 2)
$u_{i}$ | Probability with which any user $I$ actively engages in community
$w_{i}$ | Cost of recruiting user $i$ in community
$\gamma$ | Influence rate among community users (uniform)
$C$ | Budget allocated by company launching new product (product 2)
$\lambda=\lambda(\mathbf{H})>0$ | Largest eigenvalue of matrix $\mathbf{H}$
$\mathbf{x}^{*}(\mathbf{y}^{*})\gg\mathbf{0}$ | Positive fixed points corresponding to single-SIS
$\mathbf{S}_{\mathbf{v}}\triangleq diag(\mathbf{1}-\mathbf{v})$ | Diagonal matrix with elements $(1-v_{i})$

Table 1: Symbols

As mentioned earlier in Section 1, we use the bi-SIS ODE system to model our
system dynamics, which yields the following

$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\beta_{1}(1\\!-\\!x_{i}(t)\\!-\\!y_{i}(t))\sum_{j\in\mathcal{N}}a_{ij}x_{j}(t)-\delta_{1}x_{i}(t)$
(1) $\displaystyle\dot{y}_{i}(t)$
$\displaystyle=\beta_{2}(1\\!-\\!x_{i}(t)\\!-\\!y_{i}(t))\sum_{j\in\mathcal{N}}[a_{ij}+\gamma
u_{i}u_{j}]y_{j}(t)$ $\displaystyle-\delta_{2}y_{i}(t),$

where $x_{i}(t)$ ( $y_{i}(t)$ ) is the probability with which user $i$ owns
Product 1 (Product 2) at time $t\geq 0$. Also, $\beta_{2}(a_{ij}+\gamma
u_{i}u_{j})$ is the overall expected rate at which the user $j$, say who
already owns Product 2, causes the susceptible (owns neither products) user
$i$ to adopt Product 2. Note that (1) is an extension of the original bi-SIS
model (Prakash et al. 2012) whose system dynamics for any two competing
products propagating on a graph with adjacency matrix $\mathbf{A}$ is given by

$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\beta_{1}\big{(}1-x_{i}(t)-y_{i}(t)\big{)}\sum_{j\in\mathcal{N}}a_{ij}x_{j}(t)-\delta_{1}x_{i}(t)$
$\displaystyle\dot{y}_{i}(t)$
$\displaystyle=\beta_{2}\big{(}1-x_{i}(t)-y_{i}(t)\big{)}\sum_{j\in\mathcal{N}}a_{ij}y_{j}(t)-\delta_{2}y_{i}(t).$

It has been established that the above system dynamics results in only the
stronger product to dominate the market and wipe out the weaker one. We, in
this paper, try to bridge this gap by inducing a community ($\gamma
u_{i}u_{j}$ in (1)) within the original graph so that the weaker product can
survive (i.e., a positive market share) in the market.

Using $\mathbf{u}=[u_{i}]_{i\in\mathcal{N}}$ to denote the vector of
probabilities with which users participate in the community, we can write (1)
in a matrix-vector form as follows:

$\displaystyle\dot{\mathbf{x}}(t)$
$\displaystyle=\beta_{1}\text{diag}(\mathbf{1}\\!-\\!\mathbf{x}(t)\\!-\\!\mathbf{y}(t))\mathbf{A}\mathbf{x}(t)-\delta_{1}\mathbf{x}(t)$
(2) $\displaystyle\dot{\mathbf{y}}(t)$
$\displaystyle=\beta_{2}\text{diag}(\mathbf{1}\\!-\\!\mathbf{x}(t)\\!-\\!\mathbf{y}(t))\left[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}\right]\mathbf{y}(t)$
$\displaystyle-\delta_{2}\mathbf{y}(t).$

As can be seen in (2), the extra edge weights added to the original adjacency
matrix $\mathbf{A}$, as a result of creating community in the manner as
described earlier, are in the form of a rank one update given by
$\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}$.333$\gamma\mathbf{u}\mathbf{u}^{T}$
leads to a clique with homogeneous influence rate among the users. Note that
heterogeneous influence rate (while ensuring more generality) introduces
further complications in the analysis, which we leave as a future work. Later
in Section 3, we use this special form of the update to aid our analysis. Our
propagation model (2) yields the equilibrium equations

$\displaystyle\mathbf{x}$
$\displaystyle=\tau_{1}\text{diag}(\mathbf{1}-\mathbf{x}-\mathbf{y})\mathbf{A}\mathbf{x}$
(3) $\displaystyle\mathbf{y}$
$\displaystyle=\tau_{2}\text{diag}(\mathbf{1}-\mathbf{x}-\mathbf{y})\left[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}\right]\mathbf{y},$
(4)

where $\mathbf{x}$ and $\mathbf{y}$ are the fixed points of (2) for Product 1
and Product 2, respectively.

### Problem Setup

We present the problem of maximizing the market share
$\bar{y}=1/N\sum_{i\in\mathcal{N}}y_{i}$ (where $\mathbf{y}=[y_{i}]$ is the
fixed point for Product 2 from (4)) under a limited budget constraint, say
$C$, by the optimization problem given by

$\displaystyle\hskip 20.00003pt\underset{\gamma,\mathbf{u}}{\text{maximize}}\
\ \ \ $
$\displaystyle\bar{y}=\frac{1}{N}\\!\sum\limits_{i\in\mathcal{N}}y_{i}$
subject to
$\displaystyle\sqrt{\gamma}\sum\limits_{i\in\mathcal{N}}w_{i}u_{i}\leq C$
$\displaystyle u_{i}\in[0,1]\ \ \ \ \forall i\in\mathcal{N}.$

We structure the cost constraint in this optimization problem in a
heterogeneous manner. Under this setting, $w_{i}$ is the cost of recruiting
user $i$ in a newly created community. This user $i$ will be included in the
forum with probability $u_{i}$ such that the ‘average cost’ of having user $i$
in the forum would be $w_{i}u_{i}$ ($w_{6}u_{6}$ in Figure 2). This setting is
very general and can capture various scenarios such as $w_{i}$ being larger
(more expensive to recruit) for more popular users/influencers as would be the
case in reality. The company also allocates a portion of its budget towards
$\gamma$, which captures the overall communication efficiency across the
channels established for user interaction, as part of creating the discussion
group444The parameters $\gamma$ and $w_{i}$ set in this model are part of the
budget, which in a practical situation would be determined as a function of
the total budget allocated by the company launching the new product.. We
reflect this in the budget constraint in our optimization problem 2, with the
presence of the $\sqrt{\gamma}$ term. This ensures that the scaling between
$\gamma$ and $\mathbf{u}$ is the same as $\gamma\mathbf{u}\mathbf{u}^{T}$ as
in (4). To be more specific, for any choice of $\mathbf{u}$ up to a
multiplicative constant, we can allocate $C$ between $\gamma$ and $\mathbf{u}$
without affecting the fixed point $\mathbf{y}$. Our scaling ensures that
$\hat{\mathbf{u}}=c\mathbf{u}$ and $\hat{\gamma}=\gamma/c^{2}$ for any
constant $c$ renders the terms $\gamma\mathbf{u}\mathbf{u}^{T}$ unchanged. Any
other scaling would force us to consider every possible value of $\mathbf{u}$
and $\gamma$ _separately_ and thus obfuscate the meaning of the budget
constraint for our optimization problem and subsequently our analysis on the
optimal choice of $(\gamma,\mathbf{u})$ on the maximal market share $\bar{y}$.
This completes our problem set up, and we are now ready to address its
analysis in the next section.

##  3 Analysis of Product 2’s Market share $\bar{y}$

In this section, we begin by first analyzing the budget constraint in 2 and
the minimum amount of budget needed to ensure positive market share of Product
2, $\bar{y}>0$. We also establish a key result on the behavior of $\bar{y}$ as
the entries $u_{i}$ of the vector of probabilities $\mathbf{u}$ (probability
with which any user $i\in\mathcal{N}$ actively engages in the community) are
perturbed. We then define an optimization problem that helps in updating
$\mathbf{u}$, consequently helping towards obtaining an improved market share
of Product 2 under the same budget constraint. We defer to the Appendix all
the technical proofs of the results presented in this section.

### Minimum Budget for $\bar{y}>0$

To begin with, we provide the following proposition regarding the budget
constraint in 2.

######  Proposition 3.1.

Any solution $(\gamma^{*},\mathbf{u}^{*})$ to the optimization problem 2
always satisfies the budget constraint with equality, that is,

$\sqrt{\gamma^{*}}\sum\limits_{i\in\mathcal{N}}w_{i}u_{i}^{*}=C.$

Proposition 3.1 tells us that the optimal market share of Product 2 is always
obtained by spending all the available budget. This follows from the
monotonicity property555Arising from the fact that the bi-SIS system is a
monotone dynamical system (Doshi, Mallick, and Eun 2021). of the ODE system
(2) in that $\bar{y}$ turns out to be an increasing function of $\gamma$ and
$\mathbf{u}$, albeit being nonlinear. See Appendix A for details.

For general bi-SIS models, Product 2 needs to satisfy a threshold type
survival condition
$\tau_{2}\lambda(\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}])>1$,
in order to secure a positive market share in the long run666Both products
survive (coexistence equilibria) when
$\tau_{1}\lambda(\mathbf{S}_{\mathbf{y}^{*}}\mathbf{A})\\!>\\!1$ and
$\tau_{2}\lambda(\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}])\\!>\\!1$,
and the system globally converges to
$(\mathbf{x},\mathbf{y})\\!\gg\\!(\boldsymbol{\mathbf{0}},\boldsymbol{\mathbf{0}})$.
Here, $\mathbf{x},\mathbf{y}$ correspond to coexistence fixed points (Sahneh
and Scoglio 2014; Doshi, Mallick, and Eun 2021).. This condition captures the
relationship between the initial market share of Product 1, given by
$\bar{x}^{*}=1/N\sum_{i\in\mathcal{N}}x^{*}_{i}$, and the budget $C$, which is
a function of the pair $(\gamma,\mathbf{u})$. Specifically, for a given
$\tau_{2}$ and any $\mathbf{u}$ fixed up to a multiplicative constant, the
survival condition indicates that when $\bar{x}^{*}$ is large, the term
$\gamma\mathbf{u}\mathbf{u}^{T}$ also needs to be large (to ensure a large
enough eigenvalue)777This follows from the fact that the spectral radius of a
non-negative matrix is a non-decreasing function of its elements (Meyer 2000)
and the terms in
$\mathbf{S}_{\mathbf{x}^{*}}=\text{diag}(\mathbf{1}-\mathbf{x}^{*})$ is
decreasing in $\mathbf{x}^{*}$. in order for Product 2 to survive in the long
term, subsequently needing a large budget to do so. This implies that as the
market share of Product 1 increases, the minimum budget required for Product 2
to survive also increases, which can also be seen from the heat-map as
depicted888We numerically simulate the ODE system (2) for a small graph of
dolphins’ population (62 nodes, 159 edges) (Lusseau et al. 2003). in Figure 3.
For an arbitrarily chosen $\mathbf{u}$, fixed up to a multiplicative constant,
Figure 3 illustrates how the steady-state market share of Product 2 varies
with $C$ and $\mathbf{x}^{*}$. The ‘red’ curve in Figure 3 indicates the
minimum budget required to attain $\bar{y}>0$, and any amount spent below the
minimum budget leads to a zero market share. In other words, a positive budget
spent by the company towards its product placement does not necessarily
guarantee even a small non-zero return; the company launching a new product
must account for the existing competitor’s market share to decide the minimum
budget to ensure its non-zero long-term market share.

Figure 3: Heat map illustration of the market share as a function of budget
$C$ and $\bar{x}^{*}$.

### Main Result

We now turn our attention towards establishing a key result on the sensitivity
of $\bar{y}$, with respect to entries $u_{i}$ of $\mathbf{u}$. For a general
graph with adjacency matrix $\mathbf{A}$, it is impossible to obtain the
optimal solution to 2 in a closed form; the main issue being the absence of a
closed-form expression of $\bar{y}$. Even for the single-SIS model in a
general graph setting, there is no known closed-form for the positive fixed
point. The situation is further compounded when competition comes into play in
the bi-SIS model. Therefore, to gain better insight into $\bar{y}$ and how it
would change with model parameters, we begin by applying small perturbation to
$u_{i}$ for each $i\in\mathcal{N}$. As previously mentioned, change in
$\gamma$ does not affect the fixed point in (3), (4) when the budget is kept
constant, since the term $\gamma\mathbf{u}\mathbf{u}^{T}$ remains the same
under the aforementioned scaling for $\gamma$ and $\mathbf{u}$ with the same
budget $C$. The only way to obtain an increase in $\bar{y}$ is by
_heterogeneously_ changing the entries $u_{i}$, and thereby obtaining an
updated version which is no longer a multiplicative constant of the initial
$\mathbf{u}$.

To proceed, we first define the terms critical curve and critical parameters,
which we use throughout the rest of this section. The ‘critical curve’ is the
set of parameters at which the aforementioned survival condition is satisfied
with equality, and we call any such set of parameters ‘critical’ if they are
on the critical curve. Let $(\gamma^{c},\mathbf{u}^{c})$ denote a pair of such
critical parameters for which
$\tau_{2}\lambda(\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma^{c}\mathbf{u}^{c}{\mathbf{u}^{c}}^{T}])=1$.
Lemma 3.2 provides a feasible ‘initial’ pair of critical parameters.

######  Lemma 3.2.

Let $\mathbf{v}\in\mathbb{R}^{N}$ be the PF eigenvector of
$\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A}$ associated with
$\lambda(\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A})$. Then, for the choice of
$\mathbf{u}^{c}$ and $\gamma^{c}$ such that

$\mathbf{u}^{c}\propto\mathbf{S}_{\mathbf{x}^{*}}^{-1}\mathbf{v},~{}~{}\text{
and
}~{}~{}\gamma^{c}=\frac{1/\tau_{2}-\lambda(\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A})}{{{\mathbf{u}^{c}}^{T}}\mathbf{S}_{\mathbf{x}^{*}}\mathbf{u}^{c}},$

we have
$\tau_{2}\lambda(\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma^{c}\mathbf{u}^{c}\mathbf{u}^{cT}])=1$.

For any given such pair, let $\boldsymbol{\nu}^{c}=[\nu^{c}_{i}]$ be the
PF999The Perron-Frobenius (PF) eigenvector is the eigenvector corresponding to
the largest eigenvalue of a non-negative, irreducible matrix (Meyer 2000).
eigenvector of
$\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma^{c}\mathbf{u}^{c}{\mathbf{u}^{c}}^{T}]$.
From the threshold condition we know that $\bar{y}=0$ when
$\tau_{2}\lambda(\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma^{c}\mathbf{u}^{c}{\mathbf{u}^{c}}^{T}])=1$.
As a first step towards obtaining a positive $\bar{y}$, we apply perturbation
$\alpha_{i}>0$ ($\boldsymbol{\alpha}=[\alpha_{i}]$) to any $i$’th entry
$u_{i}^{c}$ of $\mathbf{u}^{c}$. The updated entry is then given by
$u^{c}_{i}+\alpha_{i}$, and we have the following result.

######  Theorem 3.3.

The market share of Product 2 as a function of the perturbation $\alpha_{i}>0$
to $u_{i}^{c}$, can be written as

$\bar{y}(\alpha_{i})=\zeta\nu_{i}^{c}\alpha_{i}+O(\alpha_{i}^{2}),$ (5)

where $\zeta>0$ is a constant independent of $i$.

Theorem 3.3 tells us that the magnitude of increase in $\bar{y}$ due to
increase in $u^{c}_{i}$ (that is, $\alpha_{i}$) is roughly proportional to
$\nu^{c}_{i}$ with an error term101010Note that Theorem 3.3 shows the
sensitivity of $\bar{y}$ with respect to ‘one’ particular $\alpha_{i}>0$ for
which we expect to see the best possible increase in the market share. Any
$\alpha_{i}<0$ results in a zero market share $\bar{y}=0$ since
$\tau_{2}\lambda(\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma^{c}\mathbf{u}^{c}{\mathbf{u}^{c}}^{T}])\leq
1$.. This implies that there is a greater reward in terms of market share to
invest in nodes with larger $\nu_{i}^{c}$. The result from Theorem 3.3 helps
in obtaining a direction leading to an increase in $\bar{y}$.

Suppose we have an initial pair of model parameters which satisfy the
threshold condition, and thus form a critical pair
$(\gamma^{c},\mathbf{u}^{c})$. These chosen parameters would then satisfy the
budget $C=\sqrt{\gamma^{c}}\sum_{i\in\mathcal{N}}w_{i}u_{i}^{c}$. By keeping
the budget constant, we intend to move in a direction that obtains the best
possible increase in $\bar{y}$ from its initial value of $\bar{y}=0$ at the
critical point. We do so by applying a perturbation to $u_{i}^{c}$, which
needs to have both positive and negative components to ensure that the budget
constraint remains binding. Also, Theorem 3.3 indicates that the increase in
$\bar{y}$ is roughly proportional to $\nu_{i}^{c}$.

We leverage this result and the perturbation approach to formulate another
optimization problem 3. Since Theorem 3.3 holds in a small region around the
critical curve, we limit the maximum size of perturbation to $\epsilon>0$.
Specifically, for a given initial $\mathbf{u}^{c}$, we define
$\tilde{u}_{i}\triangleq u_{i}^{c}+\alpha_{i}$, for all $i\in\mathcal{N}$
where $\alpha_{i}\in[-\epsilon,\epsilon]$ and the step size $\epsilon$ is a
small constant that controls the maximal size of perturbation in $\mathbf{u}$.
We then consider the following optimization problem:

$\displaystyle\hskip
50.00008pt\underset{\alpha_{1},\cdots,\alpha_{N}}{\text{maximize}}\ \ \ \ $
$\displaystyle\underset{i\in\mathcal{N}}{\sum}\alpha_{i}\nu_{i}$ subject to
$\displaystyle\sum_{i\in\mathcal{N}}w_{i}\alpha_{i}=0,$
$\displaystyle\alpha_{i}\in[-\epsilon,\epsilon].$

The solution $\boldsymbol{\alpha}$ to 3 is based on the decreasing order of
$(\nu_{i}/w_{i})$ such that it satisfies the given constraints. This solution
is essentially a relaxation of the well-known 0-1 Knap-sack problem (Garey and
Johnson 1979), which for a given initial critical parameters
$(\gamma^{c},\mathbf{u}^{c})$ leads to a direction resulting in the best
possible increase in $\bar{y}$. The perturbed $\mathbf{u}$ is the optimal
number of users who can be targeted with advertisements of Product 2, and thus
results in a positive market share.

##  4 Experimental Setup & Results

In this section, we present simulation results on real-world graphs under a
cost constraint for a given initial ($\gamma,\mathbf{u}$) pair according to
Lemma 3.2. We first briefly describe the simulation setup for our experiments,
which includes the budget structure and then describe the baseline methods
that we use to compare its performance against our approach.

### Simulation Setup

We use the following two real-world social network based graph datasets for
the simulations, which are undirected, connected graphs from SNAP (Leskovec
and Krevl 2014) and Network (Rossi and Ahmed 2015) repositories.

  1. 1.

Social circles- Facebook: Friends list of users using Facebook App, which
contains 4,039 nodes and 88,234 edges (McAuley and Leskovec 2012).

  2. 2.

Facebook pages of public figures: Nodes which are blue-verified public
figures’ facebook pages and edges are mutual likes among them. It contains
11,565 nodes and 67,000 edges (Rozemberczki and Sarkar 2020).

As Product 1 already exists in the network and being stronger than Product 2,
the effective adoption rates are such that initially
$\tau_{1}\lambda(\mathbf{S}_{\mathbf{y}^{*}}\mathbf{A})\\!>\\!1$ and
$\tau_{2}\lambda(\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A})\\!\leq\\!1$ (zero
market share). Here, $\tau_{1}=0.8,\tau_{2}=0.05$ for Facebook dataset with
4039 nodes and $\tau_{1}=0.4,\tau_{2}=0.03$ for Facebook dataset with $\approx
12k$ nodes. In the simulation results, we are interested in the immediate
increment of $\lambda(\mathbf{S}_{\mathbf{x}^{*}}\mathbf{B})$ (where
$\mathbf{B}=\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}$) from its initial value
$\tau_{2}\lambda(\mathbf{S}_{\mathbf{x}^{*}}\mathbf{B})=1$ for a given initial
pair $(\gamma^{c},\mathbf{u}^{c})$.

We set the budget as per Proposition 3.1 and run our simulation for different
values of $\epsilon$ (parameter that controls the perturbation of
$\mathbf{u}$) under two scenarios: (i) when the cost of resource allocation is
homogeneous across all nodes, for example, $w_{i}=1$ for all $i\in\mathcal{N}$
and, (ii) when the cost of resource allocation is heterogeneous, for example,
one instance of $\mathbf{w}$ sampled uniformly at random. The proposed
algorithm for obtaining the locally optimal set of users is given in Algorithm
1.

### Comparison with Baseline Methodologies

Input: $\mathbf{A},\tau_{1},\tau_{2},\mathbf{w},\epsilon$

Output: $\mathbf{u}$

1

2Initialize  __:

$\mathbf{v}(0)=\boldsymbol{\nu}^{c}$

/* $\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A}$’s eigenvector */

$\mathbf{u}(0)=\mathbf{u}_{0}$

/* as in Lemma 3.2 */

$\gamma(0)=\gamma_{0}$

/* as in Lemma 3.2 */

3 $\epsilon(0)=\epsilon$

4

5

6

7$\epsilon(1)\leftarrow\min\\{\epsilon(0),\min\\{\mathbf{u}(0)\\}\\}$

$\boldsymbol{\alpha}\leftarrow\mathcal{P}(\mathbf{v}(0),$
$\epsilon(1),\mathbf{u}(0))$

/* Solution to optimization problem */

8 $\mathbf{u}(1)\leftarrow\mathbf{u}(0)+\boldsymbol{\alpha}$

9

Algorithm 1 Local Search for bi-SIS

To evaluate the performance, we compare our proposed approach of selecting a
community against two methodologies: (i) standard centrality measures such as
degree-based centrality and eigenvector-based centrality, and (ii) NetShield
algorithm (Chen et al. 2015), as baseline algorithms. In this section, we
describe each of the methodologies along with the reasoning for selecting
these as baseline algorithms.

Degree-based centrality is a measure of node connectivity based on the number
of links (degree) each node has with others which is useful in identifying
popular nodes in a network who can further connect to a wider network (Newman
2018). Similar to this, eigenvector-based centrality (EVC) measures a node’s
influence that it has on other nodes in the network. This is done by assigning
an importance score based on the fact that a node is important when it is
linked to another important node. EVC identifies not only the influence of a
node on a direct connection, but also the impact on the entire network
(Wasserman and Faust 1994). We chose to compare against these measures to gain
a holistic analysis against such well-known centrality methods which are
generally used to understand the relationship structure in a social network
(Freeman 1978; Friedkin 1991). Also, one of the reasons to choose these
centrality measures is because one would assume that spending resources on
influential users (users with higher degree or evc score) would return higher
market share, which we show otherwise in our simulation results.

From the methodological perspective, Chen et. al. (Chen et al. 2015) uses a
very similar epidemic modeling approach and have proposed an algorithm
‘NetShield’ that helps in determining the number of users/nodes who can be
immunized to contain the epidemic. Within our context, we utilize this
algorithm as one of the baselines to determine the number of users who can be
selected to form the community. In (Chen et al. 2015), NetShield algorithm
aims to minimize the influence spread by first selecting and then deleting
those nodes who are more likely to further spread the influence in the graph.
For baseline comparison, we utilize this algorithm to determine those highly
influential users who can be recruited to form a community who can then
increase the influence spread of the new product in the graph.

Input: $\mathbf{A},\tau_{1},\tau_{2},\gamma^{c},N,C,\mathbf{w},\mu$

/* $\mathbf{\mu}$ = chosen centrality measure */

Output: $\mathbf{u}$

1 $u_{i}=\frac{C\mu_{i}w_{i}}{\sum\limits_{j\in T}\mu_{j}w_{j}}$ for all $i\in
N$

2

Algorithm 2 Centrality Measure Methodology

In each of these baseline methodologies, while the total budget remains the
same, that is, $C=\sum_{i}\sqrt{\gamma}w_{i}u_{i}$, we assign the cost $w_{i}$
(either homogeneous or heterogeneous) based on the ratio of its degree and
importance score for degree and eigenvector centrality measure, respectively
as outlined in Algorithm 2. Similarly, the cost $w_{i}$ is assigned to the
users obtained from the NetShield algorithm. The obtained $\mathbf{u}$ is then
similarly fed to (4) to obtain the market share of Product 2.

### Simulation Results

Here, we present the comparison results for both the homogeneous and
heterogeneous cost distribution for the above mentioned real-world graphs
dataset. To visualize our system in the two dimensions, we represent Product
2’s (Product 1) market share on the y-axis as
AvgY$=(1/N)\sum_{i\in\mathcal{N}}y_{i}$
(AvgX$=(1/N)\sum_{i\in\mathcal{N}}x_{i}$).

As mentioned in Section 3, the step size $\epsilon$ is a small constant that
controls the maximal size of perturbation in $\mathbf{u}$. The obtained
$\mathbf{u}$ is then fed into the bi-SIS ODE (4) along with other associated
parameters which is then simulated over 1000 time steps to obtain the market
share of Product 2 (Similarly for Product 1 using (3)). Figures 4 – 7 show how
the market shares of Product 1 and Product 2 change based on different
$\epsilon$ values when the cost is homogeneously and heterogeneously
distributed. The results indicate that as the $\epsilon$ value increases, the
market share of Product 2 also increases while the market share of Product 1
decreases, under both homogeneous and heterogeneous cost distribution. This
demonstrates that the users’ probability of willingness to participate in the
community also increases as the $\epsilon$ value increases, thereby resulting
in a higher market share.

Figure 4: Facebook ($\approx 4k$ nodes): Change in $\bar{\mathbf{y}}$ (AvgY)
and $\bar{\mathbf{x}}$ (AvgX) for Homogeneously distributed cost and different
values of $\epsilon$. Figure 5: Facebook ($\approx 4k$ nodes): Change in
$\bar{\mathbf{y}}$ (AvgY) and $\bar{\mathbf{x}}$ (AvgX) for Heterogeneously
distributed cost and different values of $\epsilon$. Figure 6: Facebook
($\approx 12k$ nodes): Change in $\bar{\mathbf{y}}$ (AvgY) and
$\bar{\mathbf{x}}$ (AvgX) for Homogeneously distributed cost and different
values of $\epsilon$. Figure 7: Facebook ($\approx 12k$ nodes): Change in
$\bar{\mathbf{y}}$ (AvgY) and $\bar{\mathbf{x}}$ (AvgX) for Heterogeneously
distributed cost and different values of $\epsilon$.

Figure 8 shows that for the locally optimal choice of users returned by our
approach for different values of $\epsilon$, under both heterogeneous and
homogeneous cost distribution, the initial weaker/new product has a higher
market share than the baseline centrality measures and NetShield algorithm,
thus validating our theoretical results. Although it is usually assumed that
spending resources on users with the highest number of followers (influential
users) will result in a higher market share, our simulation results show
otherwise, i.e., any set of users selected by our algorithm, irrespective of
the number of followers, can result in a higher market share. This result has
profound implications on the budget constraint, i.e., maximum amount that can
be spent on recruiting users, as users with more followers are usually very
expensive. Note that similar numerical results can indeed be obtained for even
larger graphs than shown here, for any choice of budget, $C$, as long as the
cost assigned to each $u_{i}$ is not too large and is thus, omitted here to
avoid repetition.

Figure 8: Facebook ($\approx 4k$ nodes): Change in $\bar{\mathbf{y}}$ (AvgY)
for Homogeneously & Heterogeneously distributed cost against Degree-based,
Eigenvector-based centrality measure, & NetShield Algorithm.

##  5 Conclusion & Future Work

We have developed an algorithm that returns an optimal set of users that form
a community, that is, the best possible pair of $(\gamma,\mathbf{u})$ and
these set of users when targeted with advertisement under a given budget
constraint results in a positive market share of the new product, Product 2.
Through perturbation approach we identify the set of users that can be
influenced through advertisement so that Product 2 can enter into the network
with a positive market share. We also compare our proposed approach against
standard centrality measures and NetShield algorithm (used in finding nodes in
SIS epidemic model) using two different datasets. The results indicate that
our approach of targeting the chosen users outperforms in both the cases when
the budget is assigned either homogeneously or heterogeneously to users that
are part of the community. We believe that our work is the first step towards
finding an optimal size of community for a new firm (launching a product) to
compete against a dominant product in a market. By basing our theoretical
analysis using the bi-SIS epidemic model and extensive simulation on different
real-world graphs demonstrate the efficacy of our approach, including its
exceeding performance over the standard centrality measures.

While this paper focuses on finding an optimal set of users to maximize the
market share of a new product competing against an existing dominant product,
we abstract away from analyzing multiple products’ (more than two)
competition. As an avenue of future research, utilizing a multi-layer graph
structure and incorporating multiple products’ competition would greatly
contribute to a better understanding of how a new product strives to improve
its market share in the presence of multiple products.

##  Appendix A Appendix

### Proof of Proposition 3.1

###### Proof.

Let $(\gamma,\mathbf{u})$ and $(\hat{\gamma},\hat{\mathbf{u}})$ be such that
we have $\gamma u_{i}u_{j}\leq\hat{\gamma}\hat{u}_{i}\hat{u}_{j}$, with strict
inequality for at least one pair of $i,j$. Let $\mathbf{y}$, $\mathbf{z}$ be
the resulting fixed point for Product 2 under parameters
$(\gamma,\mathbf{u})$, $(\hat{\gamma},\hat{\mathbf{u}})$), respectively. We
show that $\bar{y}<\bar{z}$, that is, it is always better to spend more if the
budget allows for it. Let $(\mathbf{x},\mathbf{y})$ and
$(\hat{\mathbf{x}}(t),\hat{\mathbf{y}}(t))$ denote the fixed points of the ODE
system (2) with parameters $(\gamma,\mathbf{u})$ and
$(\hat{\gamma},\hat{\mathbf{u}})$, respectively, where the initial point
$(\hat{\mathbf{x}}(0),\hat{\mathbf{y}}(0))=(\mathbf{x},\mathbf{y})$. Then, we
have111111For any two vectors $\mathbf{p}=[p_{i}]$ and $\mathbf{q}=[q_{i}]$,
the inequality $\mathbf{p}>\mathbf{q}$ implies $p_{i}\geq q_{i}$, with strict
inequality for at least one entry.

$\left.\frac{d\hat{\mathbf{x}}(t)}{dt}\right|_{t=0}=\beta_{1}\text{diag}(\mathbf{1}\\!-\\!\mathbf{x}\\!-\\!\mathbf{y}(t))\mathbf{A}\mathbf{x}-\delta_{1}\mathbf{x}=0$

$\left.\frac{d\hat{\mathbf{y}}(t)}{dt}\right|_{t=0}=\beta_{2}\text{diag}(\mathbf{1}\\!-\\!\mathbf{x}\\!-\\!\mathbf{y})\left[\mathbf{A}+\hat{\gamma}\hat{\mathbf{u}}\hat{\mathbf{u}}^{T}\right]\mathbf{y}-\delta_{2}\mathbf{y}$

$\hskip
50.00008pt>\beta_{2}\text{diag}(\mathbf{1}\\!-\\!\mathbf{x}\\!-\\!\mathbf{y})\left[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}\right]\mathbf{y}-\delta_{2}\mathbf{y}=0.$

Therefore, there exists an $\epsilon>0$ for which we have
$\mathbf{x}\geq\hat{\mathbf{x}}(\epsilon)$ and
$\mathbf{y}\leq\hat{\mathbf{y}}(\epsilon)$. From (Doshi, Mallick, and Eun
2021), we know that the bi-SIS system is strongly monotone (Smith 1995) for
$\mathbf{x},\mathbf{y}\in(0,1)^{N}$. Hence,
$\mathbf{y}<\hat{\mathbf{y}}(\epsilon)\ll\mathbf{y}(t+\epsilon)$ for all
$t>0$, and since $\mathbf{z}=\lim_{t\to\infty}\mathbf{y}(t+\epsilon)$, we have
$\mathbf{y}\ll\mathbf{z}$. ∎

### Proof of Lemma 3.2

###### Proof.

Consider the matrix
$\mathbf{M}=\mathbf{S}_{\mathbf{x}^{*}}(\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T})$.
By substituting
$\mathbf{u}=\mathbf{S}_{\mathbf{x}^{*}}^{-1}\mathbf{v}$,121212The vector
$\mathbf{u}$ can actually be taken as any scalar multiple of
$\mathbf{S}_{\mathbf{x}^{*}}^{-1}\mathbf{v}$, that is
$\mathbf{u}=c\mathbf{S}_{\mathbf{x}^{*}}^{-1}\mathbf{v}$ for any
$c\in\mathbb{R}$. We drop the ‘$c$’ notation for clarity. it can be written as

$\mathbf{M}=\mathbf{S}_{\mathbf{x}^{*}}(\mathbf{A}+\gamma\mathbf{S}_{\mathbf{x}^{*}}^{-1}\mathbf{v}\mathbf{u}^{T})=\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A}+\gamma\mathbf{v}\mathbf{u}^{T},$

which is now in the form of a rank-one perturbation to the matrix
$\hat{\mathbf{M}}=\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A}$, and is in the same
form as in Proposition 1.1 in (Bru et al. 2012) with $\mathbf{v}$ as the first
eigenvector of $\hat{\mathbf{M}}$, and $\gamma\mathbf{u}$ being the additional
$N-$dimensional vector. Then, from Proposition 1.1 in (Bru et al. 2012),
$\mathbf{v}$ is also the first eigenvector of
$\mathbf{M}=\mathbf{S}_{\mathbf{x}^{*}}(\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T})$
associated with eigenvalue
$\lambda(\mathbf{M})=\lambda(\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A})+\gamma\mathbf{u}^{T}\mathbf{v}=\lambda(\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A})+\gamma\mathbf{u}^{T}\mathbf{S}_{\mathbf{x}^{*}}\mathbf{u}$.
Finally, by rearranging the above terms, we can check that the value of
$\gamma$ for which $\lambda(\mathbf{M})=1/\tau_{2}$ is given by
$\gamma=\frac{1/\tau_{2}-\lambda(\mathbf{S}_{\mathbf{x}^{*}}\mathbf{A})}{\mathbf{u}^{T}\mathbf{S}_{\mathbf{x}^{*}}\mathbf{u}}$.
∎

### Proof of Theorem 3.3

We begin by taking the derivative of (4) with respect to $\gamma$ and $u_{r}$
evaluated at $(\gamma^{c},\mathbf{u}^{c})$ which yields131313We define c.p. to
refer to the point at which we take derivative of (4), i.e.,
$c.p.\triangleq(\gamma,\mathbf{u})=(\gamma^{c},\mathbf{u}^{c})$.

$\left.\frac{\partial
y_{i}}{\partial\gamma}\right|_{c.p.}=\tau_{2}(1-x^{*}_{i})\sum_{j\in\mathcal{N}}(a_{ij}+\gamma^{c}u_{i}{{}^{c}}u_{j}{{}^{c}})\left.\frac{\partial
y_{i}}{\partial\gamma}\right|_{c.p.}$ (6) $\left.\frac{\partial
y_{i}}{\partial
u_{r}}\right|_{c.p.}=\tau_{2}(1-x^{*}_{i})\sum_{j\in\mathcal{N}}(a_{ij}+\gamma
u_{i}^{c}u_{j}^{c})\left.\frac{\partial y_{i}}{\partial u_{r}}\right|_{c.p.},$
(7)

where $\partial\mathbf{y}/\partial\gamma=[\partial y/\partial\gamma]_{i}$ and
$\partial\mathbf{y}/\partial u_{r}=[\partial y/\partial u_{r}]_{i}$ are
eigenvectors of
$\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}]$ up to
some multiplicative constants (PF theorem (Meyer 2000)) corresponding to
eigenvalue $\tau_{2}$. We first give the following result, to help us derive
Lemma A.2, which in turn helps in determining the multiplicative constants.

######  Lemma A.1.

Let $\epsilon_{1},\epsilon_{2}>0$ be any small constants such that
$\gamma(\epsilon_{1})$ and $\mathbf{u}(\epsilon_{2})$ are perturbations around
$\gamma,\mathbf{u}$. Then, for all $\epsilon_{3}\\!>\\!0$ such that
$\lambda(\gamma,\mathbf{u})=\lambda(\gamma^{c},\mathbf{u}^{c})+\epsilon_{3}$,
there exists $\epsilon_{4}\\!>\\!0$ such that
$\mathbf{y}=\epsilon_{4}\mathbf{v}(\gamma,\mathbf{u})$.

###### Proof.

Since (6) is an eigenvalue problem of the form
$\mathbf{A}\nu=\lambda\mathbf{\nu}$, it allows for
$\left.\frac{dy_{i}}{d\gamma}\right|_{\gamma=\gamma^{c}}\\!>\\!0$ as
$\left.\lambda(\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}])\right|_{\gamma=\gamma^{c}}=1/\tau_{2}$.
Similarly, it can be shown that
$\left.\frac{dy_{i}}{du_{i}}\right|_{u_{i}=u_{i}^{c}}\\!>\\!0$.

From (6), we have that $1/\tau_{2}=\lambda(\gamma^{c},\mathbf{u}^{c})>0$ and
$\frac{dy_{i}}{d\gamma}\triangleq[v]_{i}$, i.e.,
$\mathbf{y}=\epsilon\mathbf{v}(\gamma,\mathbf{u})$ is the eigenvector of
$\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}]$. For
$\lambda(\gamma^{c},\mathbf{u}^{c})>\lambda(\gamma,\mathbf{u})$, $1/\tau_{2}$
cannot be the eigenvalue and only possible solution is $[v]_{i}=0$. Hence, for
$\lambda(\gamma,\mathbf{u})>\lambda(\gamma^{c},\mathbf{u}^{c})$, i.e., for any
small arbitrary constant
$\epsilon,~{}\lambda(\gamma,\mathbf{u})\\!=\\!\lambda(\gamma^{c},\mathbf{u}^{c})+\epsilon$,
$1/\tau_{2}$ is the eigenvalue with
$\mathbf{y}=\epsilon\mathbf{v}(\gamma,\mathbf{u})$. ∎

Now, the following lemma helps in determining the constants.

######  Lemma A.2.

Let
$\lambda(\gamma,\mathbf{u})\triangleq\lambda(\mathbf{S}_{\mathbf{x}^{*}}[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}])$,
and $(\gamma^{c},\mathbf{u}^{c})$ be any pair of critical parameters, and let
$\bar{\mathbf{y}}(\gamma,\mathbf{u})\triangleq\mathbf{1}^{T}\mathbf{y}(\gamma\mathbf{u})/N$
denote the market share as a function of any feasible $(\gamma,\mathbf{u})$.
Then, $\bar{\mathbf{y}}(\gamma,\mathbf{u})$ can be written as,

$\displaystyle\bar{\mathbf{y}}(\gamma,\mathbf{u})$
$\displaystyle=\frac{\tau_{2}\mathbf{1}^{T}\mathbf{v}(\gamma^{c},\mathbf{u}^{c})}{N\sum\limits_{i=1}^{N}\frac{v_{i}(\gamma^{c},u_{i}^{c})^{3}}{(1-x_{i}^{*})^{2}}}\left(\lambda(\gamma,\mathbf{u})-1/\tau_{2}\right)$
(8)
$\displaystyle+O\left(\left(\lambda(\gamma,\mathbf{u})-1/\tau_{2}\right)^{2}\right).$

###### Proof.

From (3) and (4), we have the following expressions and then Proposition A.3
regarding orthogonality of right eigenvectors.

$\frac{\mathbf{1}^{T}\mathbf{y}}{\tau_{2}}=(\mathbf{1}-\mathbf{x})^{T}\\!\left[\mathbf{A}\\!+\\!\gamma\mathbf{u}\mathbf{u}^{T}\right]\\!\mathbf{y}-\mathbf{y}^{T}\\!\left[\mathbf{A}\\!+\\!\gamma\mathbf{u}\mathbf{u}^{T}\right]\\!\mathbf{y}$
(9)

$\displaystyle\frac{\mathbf{y}^{T}\mathbf{S}_{\mathbf{x}}^{-1}\mathbf{y}}{\tau_{2}}$
$\displaystyle=\mathbf{y}^{T}\\!\left[\mathbf{A}\\!+\\!\gamma\mathbf{u}\mathbf{u}^{T}\right]\\!\mathbf{y}$
(10)
$\displaystyle-\mathbf{y}^{T}\mathbf{S}_{\mathbf{x}}^{-1}\text{diag}(\mathbf{y})\\!\left[\mathbf{A}\\!+\\!\gamma\mathbf{u}\mathbf{u}^{T}\right]\\!\mathbf{y}$

######  Proposition A.3.

For all $k\neq j$, the right eigenvectors $\mathbf{v}_{k}$ of
$\mathbf{M}=\mathbf{S}_{\mathbf{x}^{*}}[A+\gamma\mathbf{u}\mathbf{u}^{T}]$
satisfy $\mathbf{v}_{k}^{T}\mathbf{S}_{\mathbf{x}}^{-1}\mathbf{v}_{j}=0$.

###### Proof.

Let,
$\mathbf{S}_{\mathbf{x}}^{-1/2}\mathbf{M}\mathbf{S}_{\mathbf{x}^{*}}^{1/2}=\mathbf{S}_{\mathbf{x}^{*}}^{1/2}[\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}]\mathbf{S}_{\mathbf{x}^{*}}^{1/2}\triangleq\hat{\mathbf{M}}$
hence, $\mathbf{M}$ and $\hat{\mathbf{M}}$ are similar matrices with same set
of eigenvalues (Meyer 2000), with right eigenvector of $\hat{\mathbf{M}}$
corresponding to eigenvalue $\lambda_{k}$ given by
$\mathbf{S}_{\mathbf{x}^{*}}^{-1/2}\mathbf{v}_{k}$. $\hat{\mathbf{M}}$ is a
symmetric matrix as $\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T}$ is symmetric,
and its eigenvectors are orthogonal to each other. Hence, for all $k\neq j$,
we have
$\mathbf{v}_{k}^{T}\mathbf{S}_{\mathbf{x}^{*}}^{-1/2}\mathbf{S}_{\mathbf{x}^{*}}^{1/2}\mathbf{v}_{j}=\mathbf{v}_{k}^{T}\mathbf{S}_{\mathbf{x}^{*}}^{-1}\mathbf{v}_{j}=0$.
∎

From $\mathbf{y}$ as a linear combination of eigenvectors, we have

$\mathbf{y}=\sum\limits_{k=1}^{N}c_{k}\mathbf{v}_{k}.$ (11)

From the above equation, we have

$\frac{\mathbf{1}^{T}\mathbf{y}}{\tau_{2}}=\sum\limits_{k=1}^{N}\tau_{2}^{-1}c_{k}\mathbf{1}\mathbf{v}_{k},\\\
$ (12)
$\frac{\mathbf{y}^{T}\mathbf{S}_{\mathbf{x}}^{-1}\mathbf{y}}{\tau_{2}}=\sum\limits_{k=1}^{N}\tau_{2}^{-1}c_{k}^{2}.$
(13)

Substituting (11) in (9) and in (10) gives

$\displaystyle\frac{\mathbf{1}^{T}\mathbf{y}}{\tau_{2}}$
$\displaystyle=\sum\limits_{k=1}^{N}c_{k}\lambda_{k}\mathbf{1}^{T}\mathbf{v}_{k}-c_{k}^{2}\lambda_{k}.$
(14)
$\displaystyle\begin{split}\frac{\mathbf{y}^{T}\mathbf{S}_{\mathbf{x}}^{-1}\mathbf{y}}{\tau_{2}}&=\sum\limits_{j=1}^{N}c_{j}^{2}\lambda_{j}\\\
&-\sum\limits_{j=1}^{N}\sum\limits_{k=1}^{N}\sum\limits_{l=1}^{N}c_{j}c_{k}c_{l}\lambda_{l}\sum\limits_{i=1}^{N}\frac{[\mathbf{v}_{j}]_{i}[\mathbf{v}_{k}]_{i}[\mathbf{v}_{k}]_{i}}{(1-x_{i})^{2}}\end{split}$
(15)

By equating (12) with (14), (13) with (15) yields

$\sum\limits_{k=1}^{N}(\lambda_{k}-\tau_{2}^{-1})c_{k}\mathbf{1}^{T}\mathbf{v}_{k}=\sum\limits_{k=1}^{N}c_{k}^{2}\lambda_{k}$
(16)
$\sum\limits_{j=1}^{N}(\lambda_{j}-\tau_{2}^{-1})c_{j}^{2}=\sum\limits_{j=1}^{N}\sum\limits_{k=1}^{N}\sum\limits_{l=1}^{N}c_{j}c_{k}c_{l}\lambda_{l}\sum\limits_{i=1}^{N}\frac{[\mathbf{v}_{j}]_{i}[\mathbf{v}_{k}]_{i}[\mathbf{v}_{k}]_{i}}{(1-x_{i})^{2}}$
(17)

From Lemma A.1, we know
$\lambda(\gamma,\mathbf{u})=\lambda(\gamma^{c},\mathbf{u}^{c})+\epsilon_{1}$
for some $\epsilon_{1}>0$, there exists an $\epsilon_{2}>0$ such that
$\mathbf{y}=\epsilon_{2}\mathbf{v}(\gamma^{c},\mathbf{u}^{c})$. Also,
$\mathbf{y}=\alpha\mathbf{v}(\gamma^{c},\mathbf{u}^{c})+\beta\mathbf{w}$,
where $\mathbf{w}$ is a vector orthogonal to $\mathbf{v}(\gamma,\mathbf{u})$,
and $\beta$ goes down to zero faster than $\alpha$ as
$(\gamma,\mathbf{u})\to(\gamma^{c},\mathbf{u}^{c})$, or
$\lambda(\gamma,\mathbf{u})\to\lambda(\gamma^{c},\mathbf{u}^{c})\tau_{2}^{-1}$.
Let
$\alpha=\alpha_{0}(\lambda_{1}-\lambda_{1}^{c})^{p}+o((\lambda_{1}-\lambda_{1}^{c})^{p})$
and
$\beta=\beta_{0}(\lambda_{1}-\lambda_{1}^{c})^{q}+o((\lambda_{1}-\lambda_{1}^{c})^{q})$,
where $q>p>0$. From (11), $\mathbf{y}$’s component $c_{1}$ and $c_{k}$ (for
all $k>1$) is associated with $\mathbf{v}$ and vectors orthogonal to
$\mathbf{v}$, respectively. Then, we have
$c_{1}=r_{1}(\lambda_{1}-\lambda_{1}^{c})^{p}+o((\lambda_{1}-\lambda_{1}^{c})^{p})$,
and
$c_{k}=r_{k}(\lambda_{1}-\lambda_{1}^{c})^{q}+o((\lambda_{1}-\lambda_{1}^{c})^{q})$.
Substituting these in (16) when $\lambda_{1}\to\lambda_{1}^{c}$ shows that it
is of the order,
$\sum\limits_{k=2}^{N}r_{k}\mathbf{1}^{T}\mathbf{v}_{k}(\lambda_{k}-\tau_{2}^{-1})(\lambda_{1}-\lambda_{1}^{c})^{q}+r_{1}\mathbf{1}^{T}\mathbf{v}_{1}(\lambda_{1}-\lambda_{1}^{c})^{p+1}\\\
+o\left((\lambda_{1}-\lambda_{1}^{c})^{\min(q,p+1)}\right)$, and
$\sum\limits_{k=2}^{N}r_{k}^{2}\lambda_{k}(\lambda_{1}-\lambda_{1}^{c})^{2q}+r_{1}^{2}\lambda_{1}(\lambda_{1}-\lambda_{1}^{c})^{2p}+o\left((\lambda_{1}-\lambda_{1}^{c})^{2p}\right)$.

Similarly (17) gives,

$\displaystyle
r_{1}^{2}(\lambda_{1}-\lambda_{1}^{c})^{2p+1}+\sum\limits_{k=2}^{N}r_{k}^{2}(\lambda_{k}-\tau_{2}^{-1})(\lambda_{1}-\lambda_{1}^{c})^{2q}$
$\displaystyle+$ $\displaystyle
o\left((\lambda_{1}-\lambda_{1}^{c})^{\min(2q,2p+1)}\right),$ $\displaystyle
r_{1}^{3}\lambda_{1}(\lambda_{1}-\lambda_{1}^{c})^{3p}\sum\limits_{i=1}^{N}\frac{v_{1i}}{(1-x_{i})^{2}}+o((\lambda_{1}-\lambda_{1}^{c})^{3p})$
$\displaystyle+O((\lambda_{1}-\lambda_{1}^{c})^{2p+q}).$

From these we have the following cases: Case A: $q\geq p+1$, which means that
$p+q=2p$ implying $p=1$; Case B: $q<p+1$, implying $q=2p$; Case C: $2q\geq
2p+1$, in which case $2p+1=3p$ and $2q=2p+q$, implying $p=1$ and $q=2$; Case
D: $2q<2p+1$, which gives us $2q=3p$ and $2p+1=2p+q$. Observe that Cases A and
C are the only ones complementing each other, while the others pairs are
contradictory. Hence, it’s true that $p=1$ and $q=2$. By equating the
corresponding powers allows us to rewrite (11) as

$\displaystyle\mathbf{y}=\frac{\mathbf{v}(\gamma,\mathbf{u})}{\lambda_{1}(\gamma,\mathbf{u})\sum\limits_{i=1}^{N}\frac{v_{i}(\gamma,\mathbf{u})}{(1-x_{i}(\gamma,\mathbf{u}))^{2}}}\left(\lambda_{1}(\gamma,\mathbf{u})-\lambda_{1}(\gamma^{c},\mathbf{u}^{c})\right)$
$\displaystyle+O\left((\lambda_{1}(\gamma,\mathbf{u})-\lambda_{1}(\gamma^{c},\mathbf{u}^{c}))^{2}\right).$

A Taylor series expansion with respect to $\lambda_{1}(\gamma,\mathbf{u})$ and
centred around $\lambda_{1}(\gamma^{c},\mathbf{u}^{c})=\tau_{2}^{-1}$, gives
us141414$\lambda_{1}(\gamma,\mathbf{u})$ corresponds to the first eigenvalue
from PF Theorem and is equivalent to $\lambda(\gamma,\mathbf{u})$.

$\displaystyle\begin{split}\mathbf{y}&=\frac{\tau_{2}\mathbf{v}(\gamma^{c},\mathbf{u}^{c})}{\sum\limits_{i=1}^{N}\frac{v_{i}(\gamma^{c},\mathbf{u}^{c})}{(1-x^{*}_{i})^{2}}}\left(\lambda_{1}(\gamma,\mathbf{u})-\tau_{2}^{-1}\right)\\\
&+O\left((\lambda_{1}(\gamma,\mathbf{u})-\tau_{2}^{-1})^{2}\right).\end{split}$

∎

Now, we use the results from Lemma A.2 towards the proof of Theorem 3.3, which
is as follows. Note that $\lambda(\gamma,\mathbf{u})-1/\tau_{2}$ on the RHS in
Lemma A.2 is actually based on given $(\gamma^{c},\mathbf{u}^{c})$ at the
critical point, i.e., $\mathbf{x}=\mathbf{x}^{*},\mathbf{y}=\boldsymbol{0}$.

###### Proof.

From first-order approximation, we know that $f(x)\approx
f(a)+f^{\prime}(a)(x-a)$. Utilizing this, $\lambda(\gamma^{c},\mathbf{u})$
with respect to change in $u_{i}$ based on given
$\lambda(\gamma^{c},\mathbf{u}^{c})$ at critical point, we have

$\lambda(\gamma,\mathbf{u})\approx\lambda(\gamma^{c},\mathbf{u}^{c})+\lambda^{\prime}(\gamma^{c},\mathbf{u}^{c})\Delta\mathbf{u}.$
(18)

Utilizing Theorem 1 from (Greenbaum, Li, and Overton 2020), we know that at
$u_{i}=u_{i}^{c}$,
$\lambda^{\prime}(\gamma^{c},\mathbf{u}^{c})=\mathbf{q}^{*}\mathbf{M}^{\prime}\mathbf{p}$
where $\lambda^{\prime}(\gamma^{c},\mathbf{u}^{c})$ and $\mathbf{M}^{\prime}$
are, respectively, the derivatives of $\lambda(\gamma,\mathbf{u})$ and
$\mathbf{M}$ at $u_{i}=u_{i}^{c}$. Also,
$\mathbf{M}=\mathbf{S}_{\mathbf{x}^{*}}(\mathbf{A}+\gamma\mathbf{u}\mathbf{u}^{T})$
with largest eigenvalue $\lambda(\gamma^{c},\mathbf{u}^{c})$ corresponding to
right eigenvector $\mathbf{p}=\mathbf{v}$ and left eigenvector
$\mathbf{q}=\mathbf{v}^{T}\mathbf{S}_{\mathbf{x}^{*}}^{-1}$. Substituting this
in (18) and from Lemma 3.2, we have

$\lambda(\gamma^{c},\mathbf{u})-\frac{1}{\tau_{2}}=\mathbf{q}^{*}\mathbf{M}^{\prime}\mathbf{p}\Delta\mathbf{u},$
(19)

where $\Delta\mathbf{u}=u_{i}-u_{i}^{c}$. The derivative of $\mathbf{M}$ with
respect to $u_{i}$ gives $\frac{\partial\mathbf{M}}{\partial
u_{i}}=\gamma^{c}\mathbf{S}_{\mathbf{x}^{*}}\big{[}e_{i}\mathbf{u}^{T}+\mathbf{u}e_{i}^{T}\big{]}$.

This gives us
$\mathbf{M}^{\prime}=\gamma\mathbf{S}_{\mathbf{x}^{*}}\big{[}e_{i}\mathbf{u}^{T}+\mathbf{u}e_{i}^{T}\big{]}$
at $u_{i}$. Substituting this on the RHS of (19) gives
$\mathbf{q}^{*}\mathbf{M}^{\prime}\mathbf{p}\Delta\mathbf{u}=2\gamma^{c}\mathbf{u}^{T}\mathbf{v}(u_{i}-u^{c}_{i})v_{i}$,
where the term $2\gamma^{c}\mathbf{u}^{T}$ always remains constant.
Substituting this again in (19) gives

$\lambda(\gamma^{c},\mathbf{u})-\frac{1}{\tau_{2}}=2\gamma^{c}\mathbf{u}^{T}\mathbf{v}(u_{i}-u^{c}_{i})v_{i},$
(20)

which implies that the change is in the direction of $\mathbf{v}=[v_{i}]$ for
all $i\in\mathcal{N}$. ∎

## Broader Impact

Our goal is to develop a heuristic approach through which a new/weaker product
can survive (with a positive market share) along with an existing dominant
product. This has wider managerial implications for brand managers running new
product introduction campaigns. Specifically, such campaigns involve targeting
niche communities through advertisements or promotional offers. For example,
brand managers utilize social media platforms such as Instagram, where they
perform brand advertisements through influencers/niche groups, while operating
within a limited advertisement budget. Our model captures this exact dynamics
by identifying an optimal set of users under a budget constraint to form a
community who can be similarly targeted.

We use real-world social network data of Facebook users and compare it against
standard centrality measures. The comparison results indicate that it is not
always necessary to spend all resources on more famous influencers/public
figures for product promotion, but the community identified by our approach
provides a much better market share. Again, this has wider implications and
provides insights on how best to spend the limited advertisement budget.
Finally, we assume that companies have the complete network information, which
might not be always true. However, even with incomplete network information
and through our approach, companies can identify niche set of users and ensure
survival. Further, more information regarding the network will only result in
improving the market share.

## Ethical Considerations

The data (graph structure) for simulation results is accessed from publicly
available repositories. There is no other ethical issue associated with our
work.

## Acknowledgements

This work was done when Shailaja Mallick and Vishwaraj Doshi were PhD students
at North Carolina State University. This work was supported in part by
National Science Foundation under Grant Nos. CNS-2007423 and IIS-1910749.

## References

  * Amelkin, Bullo, and Singh (2017) Amelkin, V.; Bullo, F.; and Singh, A. K. 2017.  Polar opinion dynamics in social networks.  _IEEE Transactions on Automatic Control_ , 62(11): 5650–5665.
  * Anagnostopoulos et al. (2022) Anagnostopoulos, A.; Becchetti, L.; Cruciani, E.; Pasquale, F.; and Rizzo, S. 2022.  Biased opinion dynamics: when the devil is in the details.  _Information Sciences_ , 593: 49–63.
  * Armstrong and Kotler (2003) Armstrong, G.; and Kotler, P. 2003.  _Marketing: an introduction_.  Pearson Educación.
  * Beutel et al. (2012) Beutel, A.; Prakash, B. A.; Rosenfeld, R.; and Faloutsos, C. 2012.  Interacting viruses in networks: can both survive?  In _ACM SIGKDD_.
  * Bru et al. (2012) Bru, R.; Canto, R.; Soto, R. L.; and Urbano, A. M. 2012.  A Brauer’s theorem and related results.  _Central European Journal of Mathematics_ , 10: 312–321.
  * Chen et al. (2015) Chen, C.; Tong, H.; Prakash, B. A.; Tsourakakis, C. E.; Eliassi-Rad, T.; Faloutsos, C.; and Chau, D. H. 2015.  Node immunization on large graphs: Theory and algorithms.  _IEEE Transactions on Knowledge and Data Engineering_ , 28(1): 113–126.
  * Chen, Yuan, and Zhang (2010) Chen, W.; Yuan, Y.; and Zhang, L. 2010.  Scalable influence maximization in social networks under the linear threshold model.  In _IEEE international conference on data mining_ , 88–97.
  * Contributor (2024) Contributor, G. 2024.  What Are Influencer Pods? – Everything You Need to Know.  https://grin.co/blog/influencer-pods/.  Accessed: 2024-03-22.
  * Cooper and Kleinschmidt (1987) Cooper, R. G.; and Kleinschmidt, E. J. 1987.  New products: what separates winners from losers?  _Journal of Product Innovation Management_ , 4(3): 169–184.
  * Dalgic and Leeuw (1994) Dalgic, T.; and Leeuw, M. 1994.  Niche marketing revisited: concept, applications and some European cases.  _European journal of marketing_ , 28(4): 39–55.
  * Dandekar, Goel, and Lee (2013) Dandekar, P.; Goel, A.; and Lee, D. T. 2013.  Biased assimilation, homophily, and the dynamics of polarization.  _Proceedings of the National Academy of Sciences_ , 110(15): 5791–5796.
  * Doshi, Mallick, and Eun (2021) Doshi, V.; Mallick, S.; and Eun, D. Y. 2021.  Competing Epidemics on Graphs–Global Convergence and Coexistence.  In _IEEE INFOCOM_.
  * Freeman (1978) Freeman, L. C. 1978.  Centrality in social networks conceptual clarification.  _Social networks_ , 1(3): 215–239.
  * French Jr (1956) French Jr, J. R. 1956.  A formal theory of social power.  _Psychological review_ , 63(3): 181.
  * Friedkin (1991) Friedkin, N. E. 1991.  Theoretical foundations for centrality measures.  _American journal of Sociology_ , 96(6): 1478–1504.
  * Fuchs and Diamantopoulos (2010) Fuchs, C.; and Diamantopoulos, A. 2010.  Evaluating the effectiveness of brand-positioning strategies from a consumer perspective.  _European Journal of Marketing_ , 44(11/12): 1763–1786.
  * Gallagher and Park (2002) Gallagher, S.; and Park, S. H. 2002.  Innovation and competition in standard-based industries: A historical analysis of the US home video game market.  _IEEE transactions on engineering management_ , 49(1): 67–82.
  * Garey and Johnson (1979) Garey, M. R.; and Johnson, D. S. 1979.  _Computers and intractability_ , volume 174.  Freeman San Francisco.
  * Gargiulo, Lottini, and Mazzoni (2008) Gargiulo, F.; Lottini, S.; and Mazzoni, A. 2008.  The saturation threshold of public opinion: are aggressive media campaigns always eective?  In _Proceedings of ESSA 2008 Conference_.
  * Granovetter (1978) Granovetter, M. 1978.  Threshold models of collective behavior.  _American journal of sociology_ , 83(6): 1420–1443.
  * Greenbaum, Li, and Overton (2020) Greenbaum, A.; Li, R.-c.; and Overton, M. L. 2020.  First-order perturbation theory for eigenvalues and eigenvectors.  _SIAM review_ , 62(2): 463–482.
  * Irwin and Pavcnik (2004) Irwin, D. A.; and Pavcnik, N. 2004.  Airbus versus Boeing revisited: international competition in the aircraft market.  _Journal of international economics_ , 64(2): 223–245.
  * Jalkala and Keränen (2014) Jalkala, A. M.; and Keränen, J. 2014.  Brand positioning strategies for industrial firms providing customer solutions.  _Journal of Business & Industrial Marketing_, 29(3): 253–264.
  * Kalish (1985) Kalish, S. 1985.  A new product adoption model with price, advertising, and uncertainty.  _Management science_ , 31(12): 1569–1585.
  * Kempe, Kleinberg, and Tardos (2003) Kempe, D.; Kleinberg, J.; and Tardos, É. 2003.  Maximizing the spread of influence through a social network.  In _Proceedings of the ninth ACM SIGKDD_ , 137–146.
  * Lajmanovich and Yorke (1976) Lajmanovich, A.; and Yorke, J. A. 1976.  A deterministic model for gonorrhea in a nonhomogeneous population.  _Mathematical Biosciences_ , 28(3-4): 221–236.
  * Leskovec and Krevl (2014) Leskovec, J.; and Krevl, A. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.  Accessed: 2022-02-20.
  * Li, van de Bovenkamp, and Van Mieghem (2012) Li, C.; van de Bovenkamp, R.; and Van Mieghem, P. 2012.  Susceptible-infected-susceptible model: A comparison of N-intertwined and heterogeneous mean-field approximations.  _Physical Review E_ , 86(2): 026116.
  * Liu et al. (2019) Liu, J.; Paré, P. E.; Nedić, A.; Tang, C. Y.; Beck, C. L.; and Başar, T. 2019.  Analysis and control of a continuous-time bi-virus model.  _IEEE Transactions on Automatic Control_ , 64(12): 4891–4906.
  * Lusseau et al. (2003) Lusseau, D.; Schneider, K.; Boisseau, O. J.; Haase, P.; Slooten, E.; and Dawson, S. M. 2003.  The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations.  _Behavioral Ecology and Sociobiology_ , 54(4): 396–405.
  * McAuley and Leskovec (2012) McAuley, J. J.; and Leskovec, J. 2012.  Learning to discover social circles in ego networks.  In _NIPS_ , volume 2012, 548–56.
  * Meyer (2000) Meyer, C. D. 2000.  _Matrix Analysis and Applied Linear Algebra_ , volume 71.  SIAM.
  * Mobilia (2015) Mobilia, M. 2015.  Nonlinear q-voter model with inflexible zealots.  _Physical Review E_ , 92(1): 012803.
  * Montoya-Weiss and Calantone (1994) Montoya-Weiss, M. M.; and Calantone, R. 1994.  Determinants of new product performance: A review and meta-analysis.  _Journal of product innovation management_ , 11(5): 397–417.
  * Mukhopadhyay, Mazumdar, and Roy (2020) Mukhopadhyay, A.; Mazumdar, R. R.; and Roy, R. 2020.  Voter and majority dynamics with biased and stubborn agents.  _Journal of Statistical Physics_ , 181: 1239–1265.
  * Newman (2018) Newman, M. 2018.  _Networks_.  Oxford university press.
  * Nguyen et al. (2020) Nguyen, V. X.; Xiao, G.; Xu, X.-J.; Wu, Q.; and Xia, C.-Y. 2020.  Dynamics of opinion formation under majority rules on complex social networks.  _Scientific reports_ , 10(1): 456.
  * Nic Healey (2013) Nic Healey. 2013.  Battle of the ad campaign: PS4 vs Xbox One.  https://www.cnet.com/tech/gaming/battle-of-the-ad-campaign-ps4-vs-xbox-one/.  Accessed: 2023-01-12.
  * Omic and Van Mieghem (2009) Omic, J.; and Van Mieghem, P. 2009.  Epidemic spreading in networks—variance of the number of infected nodes.  _Delft University of Technology, report20090707. http://www. nas. ewi. tudelft. nl/people/Piet/TUDelftReports_.
  * Pathak, Banerjee, and Srivastava (2010) Pathak, N.; Banerjee, A.; and Srivastava, J. 2010.  A generalized linear threshold model for multiple cascades.  In _IEEE International Conference on Data Mining_ , 965–970.
  * Prakash et al. (2012) Prakash, B. A.; Beutel, A.; Rosenfeld, R.; and Faloutsos, C. 2012.  Winner takes all: competing viruses or ideas on fair-play networks.  In _ACM World Wide Web_.
  * Proskurnikov and Tempo (2017) Proskurnikov, A. V.; and Tempo, R. 2017.  A tutorial on modeling and analysis of dynamic social networks. Part I.  _Annual Reviews in Control_ , 43: 65–79.
  * Proskurnikov and Tempo (2018) Proskurnikov, A. V.; and Tempo, R. 2018.  A tutorial on modeling and analysis of dynamic social networks. Part II.  _Annual Reviews in Control_ , 45: 166–190.
  * Reddit (2009) Reddit. 2009.  Reddit.  https://www.reddit.com.  Accessed: 2022-10-10.
  * Rossi and Ahmed (2015) Rossi, R. A.; and Ahmed, N. K. 2015.  The Network Data Repository with Interactive Graph Analytics and Visualization.  In _AAAI_.
  * Rozemberczki and Sarkar (2020) Rozemberczki, B.; and Sarkar, R. 2020.  Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models.  In _Proceedings of the 29th ACM International Conference on Information and Knowledge Management_ , 1325–1334.
  * Sahneh and Scoglio (2014) Sahneh, F. D.; and Scoglio, C. 2014.  Competitive epidemic spreading over arbitrary multilayer networks.  _Physical Review E_ , 89(6): 062817.
  * Santos, Moura, and Xavier (2015) Santos, A.; Moura, J. M.; and Xavier, J. M. 2015.  Bi-virus SIS epidemics over networks: Qualitative analysis.  _IEEE Transactions on Network Science and Engineering_ , 2(1): 17–29.
  * Smith (1995) Smith, H. L. 1995.  _Monotone dynamical systems: an introduction to the theory of competitive and cooperative systems_.  41\. American Mathematical Soc.
  * Van Mieghem, Omic, and Kooij (2008) Van Mieghem, P.; Omic, J.; and Kooij, R. 2008.  Virus spread in networks.  _IEEE/ACM Transactions On Networking_ , 17(1): 1–14.
  * Wang et al. (2003) Wang, Y.; Chakrabarti, D.; Wang, C.; and Faloutsos, C. 2003.  Epidemic spreading in real networks: An eigenvalue viewpoint.  In _IEEE Reliable Distributed Systems_.
  * Wasserman and Faust (1994) Wasserman, S.; and Faust, K. 1994.  Social network analysis: Methods and applications.  _(No Title)_.
  * Wei et al. (2016) Wei, X.; Chen, S.; Wu, X.; Ning, D.; and Lu, J.-a. 2016.  Cooperative spreading processes in multiplex networks.  _Chaos: An Interdisciplinary Journal of Nonlinear Science_ , 26(6).
  * Yang et al. (2012) Yang, H.-X.; Wang, W.-X.; Lai, Y.-C.; and Wang, B.-H. 2012.  Convergence to global consensus in opinion dynamics under a nonlinear voter model.  _Physics Letters A_ , 376(4): 282–285.
  * Yang, Yang, and Tang (2017) Yang, L.-X.; Yang, X.; and Tang, Y. Y. 2017.  A bi-virus competing spreading model with generic infection rates.  _IEEE Transactions on Network Science and Engineering_ , 5(1): 2–13.
  * Yang et al. (2006) Yang, W.-S.; Dia, J.-B.; Cheng, H.-C.; and Lin, H.-T. 2006.  Mining social networks for targeted advertising.  In _Proceedings of the 39th Annual Hawaii International Conference on System Sciences_ , volume 6, 137a–137a.