| paper | Why Rumors Spread Fast in Social Networks, and How to Stop It |
| authors | Ahad N. Zehmakan, Charlotte Out, Sajjad Hesamipour Khelejan |
| venue | IJCAI 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper has no numbered theorem, lemma, corollary, or proposition asserting a computational complexity or algorithmic result. Theorem 4 fixes CM6 and proves non-spreading on a graph family; it does not study choosing or optimizing interventions. The proposed shield-allocation problem is therefore a new mean-field control problem rather than a computational mirror of a result in the paper.
fails bit a — no named computational result to mirror
The proposed finite-type recurrence replaces individual adjacency, common-neighbour structure, and two-distinct-neighbour exposure by aggregate kernels and Poisson closures, while also replacing two vanishing seed supernodes with a macroscopic seed cohort.
fatal: True
The candidate covers only the CM6 intervention and Theorem 4's non-spreading phenomenon; it leaves Theorems 1–3, the graph-expansion proofs, and the experiments without a qualifying computational mirror.
The strict answer is that this paper has no qualifying named computational result. Theorem 1, Theorem 2, Theorem 3, and Theorem 4, together with Lemmas 1–3, are asymptotic probability and dynamics statements. None asserts NP-hardness, membership in \(P\), FPT, or even gives an algorithmic optimization problem. The unnumbered observation that influence maximization is NP-hard is cited from Kempe et al., not proved or named here. Thus, under the programme’s literal anchor rule, a fully compliant positive case is unavailable.
The strongest conditional case is nevertheless a plausible mirror of the paper’s countermeasure result, Theorem 4, proved by the authors here with the proof deferred to the full version. It states that on an \((n,d)\)-moderate expander with \(d\le n^{1/2-\epsilon}\), if two uniformly chosen supernodes initially contain red nodes and CM6 is used—requiring a node to hear the rumor from at least two neighbors—then the rumor does not spread with high probability.
I would formulate the following computational problem.
Double-Hearing Shield Allocation\(_\infty\). A society consists of finitely many network-role types \(T=\{1,\ldots,\tau\}\), with rational masses \(\mu_t\). A type completely specifies a user’s community role, contact intensity \(\lambda_{tu}\) toward every type \(u\), limiting Jaccard-trust coefficient \(\sigma_{tu}\), forgetting parameter \(k\), and intervention price \(b_t\). The matrices \(\lambda\) and \(\sigma\) are required to be realizable as the limiting contact and Jaccard profiles of a typed block-network family; they are not arbitrary unrelated trust numbers.
The input also contains rational initial red masses \(\rho_t\), a finite horizon \(H\), and a target \(\theta\), such as \(\theta=0.1\). The decision variable is \(z_t\in[0,\mu_t-\rho_t]\), the mass of type \(t\) educated to use CM6. The objective is to minimize intervention cost,
\[ \min \sum_{t\in T} b_tz_t, \]
subject to the final orange mass after \(H\) rounds being at most \(\theta\).
For precision, let \(r_{t,a,h}(j)\) be the mass of type \(t\), protection status \(h\in\{1,2\}\), and red age \(a\in\{1,\ldots,k\}\) at round \(j\). The exposure intensity faced by type \(t\) is
\[ q_t(j)= \sum_{u\in T}\sum_{a=1}^{k}\sum_{h\in\{1,2\}} \lambda_{tu}\sigma_{tu}2^{-a}r_{u,a,h}(j). \]
An unprotected user accepts with probability
\[ p_1(q)=1-e^{-q}, \]
while a CM6-protected user accepts only after two successful contacts, with probability
\[ p_2(q)=1-e^{-q}(1+q). \]
The recurrence sends uncolored mass to red according to \(p_h(q_t(j))\), advances red ages, and turns age-\(k\) red mass orange. The constraint is therefore
\[ \Omega_H(z)\le \theta, \]
where \(\Omega_H(z)\) is the orange mass generated by this explicitly specified recurrence. Because the recurrence contains exponentials, the computational version should ask for an \(\varepsilon\)-optimal solution, or use a promised-gap decision formulation.
The regime is a social-media platform with millions of users but only a modest number of recurring network roles: community membership, degree/contact profile, homophily pattern, and trust response. Thus \(N\gg\tau\), and \(\mu_t\) is the fraction of users in role \(t\). Mass represents users, not probability over outcomes. A protected fraction of a type is legitimate because protection creates two complete subtypes—ordinary and double-hearing—rather than distinguishing named individuals.
This would be recognizable to the authors as their model at a typed high-multiplicity level: it retains randomized transmission, forgetting, Jaccard-based trust, orange terminal states, and the decentralized CM6 intervention. It is not merely a generic mean-field epidemic model. The natural bridge is that a rational mass vector can be realized by many exchangeable users of each role, while the recurrence is the law-of-large-numbers limit of their contact process.
I would expect fixed-policy evaluation to be Class A: for fixed \(H\) and \(k\), one can evaluate the recurrence to prescribed accuracy in time polynomial in \(\tau\), \(H\), and the precision. The shield-allocation problem itself is more plausibly Class C: the nested threshold effects make the optimization nonconvex, and the difficulty comes from interactions among type masses rather than from the number of named users. Whether it admits a convex reformulation, approximation scheme, or FPT algorithm in \(\tau\) would be a genuine computational question.
The paper’s Theorem 3 provides supporting motivation—the unprotected analogue spreads in \(O(\log_d n)\) rounds on a moderate expander—but I would not use it as a second anchor. It is another dynamical theorem, not an independent computational result, and its single-red-node premise becomes problematic in an atomless model.
The weakest point is substantial: Theorem 4 starts from two individual supernodes, whose mass vanishes as \(n\to\infty\). A deterministic continuum with zero initial red mass cannot start a rumor at all. The proposed mirror must therefore use a positive-mass seed cohort, or a more sophisticated two-scale limit retaining a stochastic branching phase. Moreover, actual Jaccard similarity depends on individual adjacency, so replacing the graph by a finite contact kernel is an extension from graph instances to typed block-network instances, not a literal clone of every graph in the paper.
So the positive case is: the paper inspires a coherent, computationally meaningful continuous control problem, narrowly covering CM6 and Theorem 4 in a realistic repeated-role regime. But strictly under the ChoCo rubric, it remains a new problem inspired by a named dynamical theorem, not a mirror anchored by a named computational result.
I would vote red. Under the programme’s literal anchor rule, this paper has no qualifying anchor at all. Theorems 1–4 and Lemmas 1–3 are asymptotic probability and dynamics statements: none asserts a complexity classification, an optimization algorithm, or even a computational decision problem. Theorem 4 says that CM6 prevents spreading from two random supernodes on a particular graph family; it does not formulate the choice or optimization of CM6. The proposed Shield Allocation problem therefore is not a continuous mirror of a computational result in the paper. It is a new intervention problem inspired by one of its dynamical theorems.
Even granting that relaxed standard, the proposed mirror does not preserve the paper’s essential object. The process is not determined by the population masses of behavioural roles. It depends on individual adjacency, common-neighbour sets, the location of red nodes, and the number of distinct red neighbours from which an uncolored node hears the rumor. The quantities driving the proofs are graph expansion, supernode boundaries, spectral structure, clique size, and the fact that there is at most one edge between two supernodes.
A pair of typed graphs can have the same masses, contact intensities \(\lambda_{tu}\), and average Jaccard coefficients \(\sigma_{tu}\), while having different boundaries and completely different spreading behaviour. Requiring those matrices to be realizable does not close the aggregate dynamics: it only says that some graph realizes the pairwise statistics. To make a type complete in the programme’s sense, it would have to encode enough of an agent’s neighbourhood and its surrounding topology to determine future exposure. For the graph families in the paper, that effectively makes types rooted graph positions or local graph environments, with the number of types growing with \(n\). The high-multiplicity gain then disappears.
The proposed recurrence makes the change explicit. The original acceptance probability is a product over particular neighbours, whereas \(1-e^{-q}\) and \(1-e^{-q}(1+q)\) are Poisson exposure closures. In particular, CM6 concerns two distinct successful neighbours, not merely an aggregate exposure intensity. Such a closure may define a sensible mean-field model, but it is not derived from the paper’s process on moderate expanders, whose proof relies precisely on local cliques and correlated boundary growth.
The seed problem reinforces the mismatch. Theorem 4 starts with two supernodes, whose mass is
\[ \frac{2}{n/\log^2 n}=\frac{2\log^2 n}{n}\longrightarrow 0. \]
A deterministic finite-type continuum therefore starts with zero red mass, making “the rumor does not spread” vacuous. Replacing this by a positive-mass seed cohort is a legitimate new model, but it changes the theorem from a rare-seed statement about two randomly located supernodes to a macroscopic initial-condition problem. Retaining the two exceptional seeds requires a separate stochastic, two-scale limit, precisely preserving the individual-level feature that continuization was meant to remove.
The better possible construction would use a graphon, sparse kernel, or rooted-network limit with a positive-mass role structure and a positive-mass seed cohort. That could be worthwhile as a mean-field control paper. But its computational object would be policy optimization over a relational network kernel and a distribution of local configurations, not an LP-like problem over a continuous society of finitely many complete types. It would be a new continuous network model, not a mirror of Theorem 4.
Finally, the intervention objective itself—prices \(b_t\), protected masses \(z_t\), horizon \(H\), and an \(\varepsilon\)-optimal shield allocation—is supplied entirely by the proponent. The paper fixes CM6 and compares it experimentally; it never studies optimal allocation. This is not a criticism that the resulting problem might be easy or hard. It is the more basic point that the proposed computational question is not present in the paper.
Mean-field and sociophysical work should not be counted as prior continuous computational treatment; it is relevant machinery. But that machinery cannot supply the missing computational anchor. A typed graphon version might be an interesting independent project, and that is the negative case’s genuine weakness. Under the stated ChoCo test, however, the paper offers no named computational result to mirror, and its only plausible dynamical anchor requires replacing the population problem by a substantially richer network-limit problem.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.