Complex Contagion Influence Maximization: A Reinforcement Learning Approach

The strongest positive case is a single, carefully delimited anchor: Theorem 2, which states that “the \(K\)-complex contagion influence maximization problem is NP-hard.” This theorem is proved in the paper, although its proof invokes the earlier NP-hardness of Independent Cascade influence maximization by Kempe, Kleinberg, and Tardos (2003), using the paper’s \(K=1\) reduction. Thus it is an anchor for the computational problem, but not evidence that genuinely complex contagion with \(K\ge2\) is itself hard.

My proposed mirror is Finite-Horizon \(K\)-Complex Contagion Influence Maximization over a Continuous Population, or \(K\)-CCIM\(_\infty\).

An instance consists of a finite set of population types \(R=\{1,\ldots,\tau\}\), rational masses \(\mu_i>0\) with \(\sum_i\mu_i=1\), a rational contact matrix \(P\), a contact degree \(d\), complex-contagion parameters \(K,p_0,p_1\), a seed-mass budget \(\beta\), and a cascade horizon \(H\). Type \(i\) is a complete network-role description: agents of that type have the same contact profile \(P_{i,\cdot}\), the same number \(d\) of contacts, and the same adoption parameters. \(P_{ij}\) is the fraction of contacts of type \(i\) leading to type \(j\). One may restrict \(P\) to symmetric or reversible kernels if an undirected network is required.

The decision variable is a seed-mass vector \(x\), where \(0\le x_i\le\mu_i\) and \(\sum_i x_i\le\beta\). Thus \(x_i\) is the fraction of the entire population of type \(i\) receiving the intervention initially. If \(y_i\) is the active mass of type \(i\), write \(z_i=y_i/\mu_i\) and \(q_i(y)=\sum_jP_{ij}z_j\). A type-\(i\) agent then has a binomially distributed number of active contacts, so its mean adoption probability is \( \rho(q_i)=p_1+(p_0-p_1)\sum_{\ell=K}^{d}\binom{d}{\ell}q_i^\ell(1-q_i)^{d-\ell} \). Starting with \(y_i^{(0)}=x_i\), the mean-field cascade evolves by \(y_i^{(r+1)}=y_i^{(r)}+(\mu_i-y_i^{(r)})\rho(q_i(y^{(r)}))\). The objective is to output a feasible \(x\) maximizing \( \Phi_H(x)=\sum_i y_i^{(H)} \). Equivalently, the decision version asks whether some feasible \(x\) satisfies \(\Phi_H(x)\ge Q\), for a rational target \(Q\).

This is not merely making the outcome fractional. The continuous object is the population of agents and the intervention is a mass of seed agents. A finite society with \(n\) agents is recovered by taking approximately \(n\mu_i\) agents of type \(i\), with seed masses restricted to multiples of \(1/n\). The continuous model is therefore the high-multiplicity limit of a stochastic block-network family. The number of people may be millions while \(\tau\) records only a few dozen or few hundred recurring network roles.

A plausible regime is a national health or agricultural campaign operating across many repeated communities. There may be millions of households, farmers, or young people, but only a moderate number of relevant roles: community-health workers, highly connected households, peripheral households, age or occupation classes, and so on. Agents sharing a role have indistinguishable contact statistics and adoption behaviour. The paper’s own motivating domains—HIV prevention and agricultural innovation—make this more than an artificial reinterpretation. The original graph is replaced by a finite-type contact kernel, but the threshold-complementarity mechanism remains exactly the paper’s: isolated seeds have little value, while enough active neighbours can cause a surge in adoption.

The authors should recognise this as their problem. Their original decision is to choose a seed set \(S\) under a budget and maximize \(\sigma(G,S)\). The mirror replaces \(S\) by a seed-mass allocation \(x\), \(|S|=T\) by \(\sum_i x_i\le\beta\), and total influence by influenced population mass. It preserves the complex-contagion rule, the network-mediated cascade, and the non-submodular complementarities. It does not attempt to continuize the paper’s RL architecture; the RL algorithm is a proposed solver, not the computational object being mirrored.

My expectation is that the general exact problem is Class B: hardness should remain when \(\tau\), \(P\), and \(K\) are part of the input, because the combinatorics live in the interaction structure and the choice of network roles, not in the number of named agents. A finite base network can be represented by a type-interaction kernel and then blown up into many exchangeable agents. The resulting optimization is a nonconvex polynomial optimization problem over the seed masses, since the binomial-tail cascade map is polynomial in the active fractions.

The important qualification is that Theorem 2 does not itself prove this transfer. Fractional seeding creates a genuine loophole: a tiny mass assigned to a type may have a very different effect from selecting one discrete node, especially when \(K=1\). A proper Class B theorem would need a gap-preserving reduction showing that optimal mass allocations cannot exploit such infinitesimal seeds, perhaps using \(K\ge2\), carefully chosen thresholds, or a campaign model with realistic minimum intervention masses. If that cannot be done, the mirror may instead reveal a continuum-specific complexity boundary—or tractability in restricted block models.

This is also the weakest point of the positive case. The model deliberately restricts arbitrary networks to a finite-type, high-multiplicity regime, and fractionalization may destroy the exact hardness argument used in the paper. But that is a limitation of the expected complexity result, not of the mirror itself. The question remains a faithful and technically substantial continuous version of the paper’s central problem, with immediate follow-ups: whether exact hardness survives fractional seeding, whether approximation is possible, whether fixed \(\tau\) gives tractability, and whether the discrete and continuous variants admit rounding guarantees.

I would therefore cover only Theorem 2. Theorem 3 and the empirical claims about RL4CCIM are useful supporting material, but they are not independent computational anchors.