Viral Marketing in Social Networks with Competing Products

There is a credible continuous mirror, but it is strongest for Section 2 of the paper, not for the convergence-time results in Section 3. My lead is the paper’s Product Adoption Maximization problem, with Theorem 2.3 as the strongest positive anchor and Theorem 2.1 as its computational boundary.

The right population regime is a large platform whose users fall into finitely many repeated network roles. A type \(t\) specifies the user’s social role, the distribution of roles among their out-neighbours, initial eligibility for targeting, and seeding price. Thus agents of the same type are genuinely interchangeable for the model. There may be millions of users but only \(\tau\) role types: for example, users in a small number of communities, demographic-interest cohorts, or recommendation-network positions. Let \(\mu_t\) be the fraction of the population of type \(t\), with \(\sum_t\mu_t=1\).

The network is represented by a row-stochastic matrix \(P\), where \(P_{tu}\) is the probability that a type-\(t\) user’s uniformly selected out-neighbour has type \(u\). Let \(\beta_t\) be the initial blue mass of type \(t\), and let \(a_t\) be the mass of initially uncoloured type-\(t\) users bought as red seeds. The budget constraint is \(\sum_t a_t\le \kappa\), with \(0\le a_t\le\mu_t-\beta_t\). The initial masses are \(r_t^0=a_t\), \(b_t^0=\beta_t\), and \(u_t^0=\mu_t-\beta_t-a_t\).

The continuum Random Pick dynamics are the law-of-large-numbers version of the paper’s process. At round \(\ell\), an uncoloured type-\(t\) agent adopts red with probability \(\sum_uP_{tu}r_u^\ell/\mu_u\), blue with probability \(\sum_uP_{tu}b_u^\ell/\mu_u\), and remains uncoloured otherwise. Hence, for every type \(t\),

\(r_t^{\ell+1}=r_t^\ell+u_t^\ell\sum_uP_{tu}\frac{r_u^\ell}{\mu_u}\),

\(b_t^{\ell+1}=b_t^\ell+u_t^\ell\sum_uP_{tu}\frac{b_u^\ell}{\mu_u}\),

and

\(u_t^{\ell+1}=u_t^\ell\sum_uP_{tu}\frac{u_u^\ell}{\mu_u}\).

The objective is the limiting red mass \(R_\infty(a)=\sum_t\lim_{\ell\to\infty}r_t^\ell\). This is not continuity of the outcome space or merely a probabilistic reformulation: the continuous object is the population, and the decision is how much population mass to seed.

The first continuous question is \(\textsf{Continuous Product Adoption Maximization}\). Given rational \((\mu,P,\beta,\kappa)\), compute \(\operatorname{OPT}=\max_a R_\infty(a)\), or solve its gap version: distinguish instances with \(\operatorname{OPT}\ge q\) from those with \(\operatorname{OPT}\le q-\delta\), and output a feasible mass vector \(a\). For finite-precision computation, one can require the output value to be within \(\zeta\) of \(R_\infty(a)\), or use a certified horizon \(H\) after which the remaining uncoloured mass is at most \(\zeta\).

This is a direct mirror of Definition 2 and, in particular, of Theorem 2.1, which is proved by the authors here, with the complete proof deferred to their full version [57]. The theorem states that Product Adoption Maximization has no polynomial-time \((1-1/e+\varepsilon)\)-approximation under the stated complexity assumption. The reduction is from Maximum Coverage.

I expect the exact and better-than-\(1-1/e\) versions of the continuous problem to be Class B: the hard combinatorics live in the incidence pattern between set-types and element-types, not in the number of individual users. One can replicate every role \(M\) times, making the population size \(N\) arbitrarily larger than \(\tau\), while preserving the set-selection structure in \(P\). The genuine proof obligation is handling fractional seeding: the continuum permits \(a_t\) strictly between zero and \(\mu_t-\beta_t\). A transfer proof would need a gap-preserving coverage gadget or an argument using the multilinear extension showing that fractional role seeding does not destroy the relevant gap. I regard that as plausible, but Theorem 2.1 by itself does not prove it.

The second question is \(\textsf{Continuous Product Adoption Approximation}\). Given the same instance and accuracy parameters \(\varepsilon,\delta,\zeta\), output a feasible vector \(a\) such that, with probability at least \(1-\delta\), \(R_\infty(a)\ge(1-1/e-\varepsilon)\operatorname{OPT}-\zeta\). The expected runtime should be polynomial in \(\tau\), the encoding length, \(1/\varepsilon\), \(\log(1/\delta)\), and a certified terminal horizon or conditioning parameter, rather than in the number \(N\) of individual users.

This mirrors Theorem 2.3, proved in the paper. Theorem 2.3 gives a w.h.p. \((1-1/e-\varepsilon)\)-approximation through Monte Carlo greedy, relying on Theorem 2.2. Theorem 2.2 is also proved here and establishes that \(F_S(\cdot)\) is monotone and submodular.

In the role-homogeneous population, the finite-population objective is the limit of the normalized multilinear extension of that submodular set function. Thus the mass objective should be monotone and diminishing-returns submodular in the seed fractions \(a_t/\mu_t\). This creates a natural Class A route: continuous greedy or infinitesimal greedy over the type masses, with the mean-field recursion or sampled type-trajectories providing marginal estimates. The paper’s \(1-1/e\) guarantee is therefore not lost; it becomes the familiar approximation threshold for continuous submodular maximization. The algorithmic question is whether this can be implemented with complexity polynomial in \(\tau\), rather than in \(N\), and whether arbitrary rational transition matrices can be handled without an exponentially long convergence horizon.

The authors should recognise this as their problem. It retains competing red and blue products, irreversible adoption, the Random Pick rule, a marketer choosing red seeds, and the expected final red reach. The only change is that “choose \(k\) users” becomes “buy mass \(\kappa\) of users,” exactly the high-multiplicity relaxation. For a finite population with \(N_t\) users of type \(t\), the discrete seed counts satisfy \(a_t=x_t/N\); as \(N\) grows, the integer granularity disappears. Conversely, a continuous solution can be rounded to nearby integer seed counts, with vanishing mass error when \(N\) is large and \(\tau\) is moderate.

The weakest point is that the paper’s graph model permits every node to have an idiosyncratic neighbourhood, whereas the mirror assumes exchangeable role classes. If local topology is the substance of the application, replacing it by \(P\) may be an unacceptable mean-field approximation. There is also no clean direct mirror of Theorem 3.4: the paper’s convergence time is the time until every individual has settled, while an infinite population generally has a nonzero uncoloured tail for arbitrarily many rounds. I would therefore not claim to cover Theorems 3.1–3.4. The positive case is narrower: the continuous population mirror convincingly covers the paper’s central optimization problem, its submodularity theorem, and its approximation result.

The main follow-up questions are whether the Maximum Coverage inapproximability survives fractional type seeding, whether the mean-field objective is always DR-submodular for arbitrary role matrices \(P\), and whether exact optimization or parameterized algorithms become tractable when \(P\) has bounded rank, sparse support, or only a small number of distinct role-neighbourhood profiles.