d4-conf-ijcai-2015-0439

The strongest anchor is Theorem 1, proved in this paper by a reduction from Set Cover. It says that, given an IC information-propagation network and a budget \(k\), choosing exactly \(k\) seed nodes to maximize the expected number of active nodes plus informed inactive nodes is NP-hard. The reduction’s useful clue is that it sets propagation probabilities to zero: the selected seeds remain active, while their contacts can still contribute informed nodes. That gives a concrete hard case to carry into a population limit.

Consider a large messaging platform launching a public-health alert. Its \(N\) users fall into \(\tau\) large, statistically exchangeable cohorts—for example, language and engagement groups—with \(\tau\ll N\). Members of a cohort share the modeled contact rates and activation probabilities; those profiles, including any differences in seeding cost, define their type. The platform chooses ambassadors from the population, and wants to maximize the share who either adopt the alert or become aware of it. A seed is still an agent, awareness is still the paper’s informed state, and the objective remains information coverage.

Here is a precise mirror, Typed Mean-Field Information-Coverage Maximization. An instance has rational type masses \(\mu_t\) summing to \(1\), a seed budget \(\kappa\), contact intensities \(q_{tu}\geq 0\), and activation probabilities \(p_{tu}\in[0,1]\). Interpret it as the limit of \(N\)-person IC networks with \(N\mu_t\) members of type \(t\), where each possible directed contact from type \(t\) to type \(u\) occurs with probability \(q_{tu}/N\), and an attempted activation succeeds with probability \(p_{tu}\). A solution is a seed-mass vector \(x\) with \(0\leq x_t\leq\mu_t\) and \(\sum_t x_t=\kappa\).

The limiting diffusion and coverage are defined by a recurrence. Start with newly active mass \(z^0=x\), cumulative active mass \(a^0=x\), and covered mass \(v^0=x\). In each round, for every type \(u\), set
\[ z_u^{r+1}=(\mu_u-a_u^r)\left(1-\exp\left[-\sum_t q_{tu}p_{tu}z_t^r\right]\right),\qquad a_u^{r+1}=a_u^r+z_u^{r+1}, \]
and
\[ v_u^{r+1}=v_u^r+(\mu_u-v_u^r)\left(1-\exp\left[-\sum_t q_{tu}z_t^r\right]\right). \]
The success rate determines newly active mass; the contact rate determines newly covered mass, including people who were contacted but did not activate. The objective is \(C(x)=\sum_u v_u^\infty\). The computational question is whether, for rational input and \(\epsilon>0\), one can return a feasible \(x\) with \(C(x)\geq (1-1/e-\epsilon)\max_y C(y)\) in time polynomial in \(\tau\), input bit length, and \(1/\epsilon\). This asks about seed-mass optimization for the paper’s underlying active-plus-informed objective, not about an encoding.

My expectation is Class A for approximation, though that is a conjecture for the full cascade model. There is a direct foothold in the paper’s own hardness mechanism. When \(p_{tu}=0\), only seeds are active, and the objective becomes
\[ C_0(x)=\sum_u\left[\mu_u-(\mu_u-x_u)\exp\left(-\sum_t q_{tu}x_t\right)\right]. \]
This function is monotone and has diminishing returns in its mass coordinates, making continuous submodular maximization a plausible route to an approximation algorithm. In that regime, the discrete Set Cover choice of whether to seed a named node has become an allocation of seed mass across types. For \(p_{tu}>0\), activation waves feed back into later coverage; extending the diminishing-returns structure through those waves is the central proof obligation. Exact optimization may remain hard.

This is a plausible mirror because the population is the object being continuized, while the seed decision, IC-style propagation, and coverage measure stay recognizable. It covers Theorem 1’s seed-selection hardness, especially its Set Cover mechanism; it does not claim to mirror the paper’s #P-hard evaluation result or its experimental algorithms. The weakest point is also the main modeling choice: replacing a fixed graph’s individual neighborhood pattern with type-level contact rates loses local incidence and overlap structure. The mirror is persuasive in a large, cohort-based network regime where those rates are the intended model; it is much weaker when individual network positions matter and the number of distinct profiles grows with the population.