| paper | Majority Opinion Diffusion in Social Networks: An Adversarial Approach |
| authors | Ahad N. Zehmakan |
| venue | AAAI 2021 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 6.1
statement extracted from the paper’s text layer
Given a finite typed base graph \(H=(T,E_H)\), rational type masses \(\mu_i\) summing to \(1\), rational black and white seed masses \(b,w\), and horizon \(t\), form the atomless complete blow-up in which type \(i\) has mass \(\mu_i\) and each base edge induces all-to-all interaction between its two type masses. Choose \(x_i^B,x_i^W\ge0\) with \(x_i^B+x_i^W\le\mu_i\), \(\sum_i x_i^B=b\), and \(\sum_i x_i^W=w\); run majority diffusion for \(t\) rounds with aggregate half-splitting on ties, and minimize the resulting white mass \(\Phi_t\), or approximate its optimum.
An atomless high-multiplicity population of clone classes \(i\in T\), with mass \(\mu_i\), exact typed-blow-up interactions, divisible black and white seed allocations \(x_i^B,x_i^W\), and objective \(\Phi_t\), the white population mass after \(t\) diffusion rounds.
The proponent's original \(a_{ij}\)-only recurrence discards the local incidence and neighborhood-overlap information on which the diffusion process depends.
fatal: False
The mirror covers Theorem 6.1 and leaves the resilience theorems, stabilization-time bounds, and other hardness discussion untreated.
The strongest honest case is a qualified yes, with Theorem 6.1 as the sole anchor. I would not use the paper’s informal statement that the fixed-size stabilization problem is NP-hard: it is not attached to a numbered theorem. Theorem 6.1 is different: it is a named approximation-hardness result proved in this paper, with the reduction supplied in Appendix I.
The paper defines Minimum Influence (MI) as follows. Given a graph \(G=(V,E)\), integers \(b,w,t\), choose \(b\) initially black seed nodes and \(w\) initially white seed nodes; all other nodes are uncolored. Run the paper’s majority diffusion for \(t\) rounds, breaking ties randomly, and minimize the expected number \(\mathbb{E}[\hat w_t]\) of white nodes present by round \(t\). Theorem 6.1 states:
If \(\mathcal A\) is a polynomial-time \(\beta\)-approximation algorithm for MI, then \(\beta>n^{1-\zeta}\) for every \(\zeta>0\), unless \(\mathrm{P}=\mathrm{NP}\).
This is proved here, not cited. The reduction is from CLIQUE. For a graph \(G'\) and target clique size \(k\), the construction replaces vertices and edges by large clique gadgets, sets \(b=k\), \(w=\binom{k}{2}\), and \(t=2\). If \(G'\) has a \(k\)-clique, the optimum is \(\binom{k}{2}\); if it has no such clique, every solution has value greater than \(n^{1-\zeta}\binom{k}{2}\). The large gadgets amplify the gap, while the combinatorial choice is whether the black seed positions encode a clique.
My proposed mirror is Typed Continuous Minimum Influence, or \(\mathrm{CMI}_t\). An instance contains a finite set of structural population types \(T=\{1,\ldots,\tau\}\), rational masses \(\mu_i>0\) with \(\sum_i\mu_i=1\), a rational interaction matrix \(a_{ij}\), seed masses \(b,w\), and a number of rounds \(t\). Type \(i\) is a complete network role: its agents have the same exposure profile, degree parameters, targeting price, and every other attribute used by the diffusion process. The mass \(\mu_i\) is the fraction of the population having that role.
Here \(a_{ij}\) is the number, or weight, of type-\(j\) neighbours seen by one type-\(i\) agent. If \(B_j^{(r)}\) and \(W_j^{(r)}\) are the cumulative black and white masses of type \(j\) after round \(r\), then type \(i\)'s black and white exposure is \(P_i^B(r)=\sum_j a_{ij}B_j^{(r)}/\mu_j\) and \(P_i^W(r)=\sum_j a_{ij}W_j^{(r)}/\mu_j\). The division by \(\mu_j\) converts coloured mass into the fraction of type \(j\) that is coloured. For an undirected typed network, the parameters can satisfy the usual consistency condition \(\mu_i a_{ij}=\mu_j a_{ji}\).
The decision variable is a pair of mass allocations \(x_i^B,x_i^W\), satisfying \(x_i^B,x_i^W\ge 0\), \(x_i^B+x_i^W\le\mu_i\), \(\sum_i x_i^B=b\), and \(\sum_i x_i^W=w\). The remaining mass is initially uncoloured. In each round, every uncoloured unit of type \(i\) becomes black if \(P_i^B>P_i^W\), white if \(P_i^W>P_i^B\), and is split equally in expectation if the exposures tie. If both exposures are zero, it remains uncoloured. The objective is to minimize \(\Phi_t=\sum_i W_i^{(t)}\).
Thus the continuous question is:
Given \((T,\mu,a,b,w,t)\), find a feasible black/white seed-mass allocation minimizing the expected white population mass after \(t\) majority-diffusion rounds; or, for approximation, output an allocation whose value is at most \(\beta\) times the optimum.
This is a population continuization, not a fractionalization of opinions or outcomes. Every unit of population still has an integral state—black, white, or uncoloured. Only the population of each structural type and the amount targeted are divisible. The tie rule is the natural atomless limit of the paper’s independent tie-breaking: an infinitesimal population splits into half black and half white in aggregate.
The intended regime is a large platform, product-adoption market, or collection of repeated local communities. There may be millions of users but only \(\tau\) repeated exposure roles: for example, residents of many copies of the same neighbourhood template, employees occupying repeated positions in a corporate communication network, or accounts belonging to recurring community and degree classes. The relevant comparison is \(N\gg\tau\), where \(N\) is the finite population represented by the masses. Agents of one type are interchangeable for this problem, not merely similar in their opinions.
The bridge is concrete. A rational mass vector can be multiplied by a common denominator \(N\) to obtain a finite population with \(N\mu_i\) agents of type \(i\). Conversely, a finite regular blow-up of a typed interaction template aggregates to \((\mu,a)\). The continuous instance therefore compresses repeated graph roles instead of simply renaming \(n\) individual vertices as fractional mass. The approximation ratio is unchanged by normalization: multiplying all masses by \(N\) multiplies both the optimum and the algorithm’s value by \(N\).
I expect this mirror to be Class B—hardness should transfer—although this is a conjectured direction, not something Theorem 6.1 already proves. The reduction’s meaningful combinatorics is the selection of vertex and edge roles encoding a clique. The large clique gadgets mainly amplify a gap. That is evidence that the difficulty is not fundamentally the number of named agents, and hence should survive repeated agents.
The necessary technical work is nontrivial. Fractional targeting may allow mass to be spread across several vertex types, so the discrete clique gap does not automatically carry over. A continuous reduction would need to show that every sufficiently good mass allocation can be rounded, or that the gadget dynamics itself forces near-integral mass on the relevant types. If that fails, the problem could instead become tractable, or could exhibit Class C hardness caused by the nonconvex majority-threshold regions. Either outcome would be a meaningful continuization result.
The authors should recognise \(\mathrm{CMI}_t\) as their problem: it preserves the same graph-mediated majority rule, the same black/white seed budget, the same uncoloured state, the same finite horizon, the same tie randomness in aggregate, and exactly the same objective. What changes is only the population representation and the admissible targeting granularity. It also asks a genuinely new computational question: whether the spectacular discrete approximation barrier in Theorem 6.1 is caused by individual population multiplicity or by the underlying network-role combinatorics.
The mirror covers only Theorem 6.1. The resilience theorems, random stabilization bounds, and the unnamed NP-hardness discussion on exact stabilization time are outside its anchor scope. Natural follow-up questions are the complexity as a function of \(\tau\), \(t\), and input length; approximation thresholds; restrictions to regular or expander-type kernels; and quantitative rounding theorems relating \(\mathrm{CMI}_t\) to finite repeated-agent instances.
The weakest point is that the paper’s graph model is fully individualised, whereas my mirror introduces a typed interaction kernel and therefore a co-modification of the network representation. Moreover, the exact reduction in Appendix I may rely on discrete seed positions that fractional mass can smooth away. I would concede both points. They do not make the mirror artificial: repeated network roles are a legitimate high-multiplicity regime, and the question of whether the hardness survives fractional targeting is precisely the computational content of the mirror.
The only serious anchor is Theorem 6.1, so the negative case cannot rely on the absence of a computational result. The theorem is a genuine, named approximation-hardness result. The objection must instead be that the proposed continuous problem is not actually a continuization of the paper’s diffusion process.
The difficulty is that this process is relational, not type-separable. A node’s future colour depends on the exact identities and overlaps of its neighbours, and on which of those neighbours became coloured in earlier rounds. The matrix \(a_{ij}\) does not contain that information. Two \(d\)-regular graphs can have the same single “degree type” and the same value of \(a_{11}=d\), while having completely different diffusion behaviour: one might be a union of small cliques and the other a connected expander. The aggregate mass \(\mu_1\) and exposure parameter \(a_{11}\) cannot distinguish them. The proposed recurrence using \(B_j/\mu_j\) therefore silently replaces the paper’s local majority process by a mean-field process.
One can repair this by making types much more detailed. But then a type must encode an agent’s complete incidence pattern, including which edge gadgets it reaches and how those neighbours are themselves connected. In Appendix I, the important \(v_i\)- and \(u_j\)-vertices are distinct precisely because their incidences encode the instance of CLIQUE. Merging them destroys the reduction’s meaning. Retaining those distinctions requires at least one type for essentially every vertex and edge role of \(G'\), so \(\tau\) grows with the original hard instance. The repeated mass then sits mainly in the large clique padding, which is an amplification device rather than the source of the computational choice. This is fractionalizing a graph construction, not finding a small high-multiplicity population model of the paper’s problem.
The alternative is to use an exact blow-up: replace every vertex of \(G\) by many clones and every edge by complete bipartite connections between the corresponding clone classes. That is a legitimate model, but it exposes a second problem. The proof of Theorem 6.1 depends on integer placement of exactly \(k\) black seeds and \(\binom{k}{2}\) white seeds. Its no-clique argument uses inequalities such as \(w(A)\le b(A)-1\) and \(w(A)\le b(A)+1\). Under divisible masses those unit gaps disappear. A fractional allocation can spread black mass across many vertex classes and white mass across many edge gadgets; the paper’s counting argument gives no reason that such an allocation must encode a clique or trigger the same gadget cascade. Thus the proposed mirror is not supported by the theorem’s reduction. Establishing a continuous gap would require new gadgets and a new soundness proof.
The strongest repair would be to retain the entire graph as a graphon or as a continuum of rooted network positions, with a state function over that object. But then the network itself—not merely the population—is the principal continuous object. The result would be a continuum-network or mean-field diffusion problem, not a population continuization of the paper’s finite graph problem. It may be interesting, but it no longer tests whether Theorem 6.1’s approximation barrier survives high multiplicity of agents.
This leaves a sharp dichotomy. With a small number of structural types, the interaction data are too coarse to represent the local process. With sufficiently rich types, the types reproduce the original graph and the “continuous society” is only a fractional blow-up of its vertices. There is no evident regime in which the named theorem becomes a population-distribution problem while preserving the information on which the theorem is built.
That is the strongest negative case, but it is not airtight. The blow-up version is a sensible new computational question, and the graphon version may also be worth studying if the authors explicitly accept the co-modified network model. The honest conclusion is therefore not that no conceivable mirror exists. It is that the proponent has not supplied a mirror of Theorem 6.1: their finite type kernel changes the diffusion rule, while the exact repair either retains the whole graph or changes the object of continuization.
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.