| paper | d4-conf-aaai-2007-0075 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper has no numbered theorem, lemma, corollary, or proposition with a computational claim: its approximation guarantee is attributed to prior work, and its proposed estimator is evaluated experimentally. That fails the named-result requirement even if the proposed type-mass influence-maximization question is plausible.
fails bit a — no named computational result to mirror
No qualifying paper-owned computational result is covered; the proposed question addresses the underlying influence-maximization objective, while the paper's SCC-based estimator, experiments, and LT analysis are left alone.
This paper has no qualifying anchor under your rule. It contains no numbered theorem, lemma, corollary, or proposition asserting a complexity result. Its main contribution is an empirically evaluated method for estimating influence in a fixed finite graph. The paper does quote the guarantee \(\sigma(A_k)\ge (1-1/e)\sigma(A_k^\star)\), but attributes it to Kempe, Kleinberg, and Tardos (2003); it is neither numbered nor proved here. So I cannot honestly give an anchor-backed case from this paper.
The strongest candidate mirror I can offer is a continuous version of its underlying IC influence maximization problem. Imagine a very large platform or organization with millions of people but only tens or hundreds of stable behavioral or organizational types. People of type \(t\) share the same seeding cost and the same contact rates with every other type. The population is represented by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\).
Call the candidate Type-Mass IC Influence Maximization. An instance consists of the type masses \(\mu_t\), rational contact intensities \(\lambda_{st}\), rational transmission probabilities \(q_{st}\), a seed-mass budget \(\kappa\), and an accuracy parameter \(\varepsilon>0\). Its network interpretation is a sparse stochastic block model: in a population of size \(N\), an ordered pair from type \(s\) to type \(t\) has an edge with probability \(\lambda_{st}/N\), and transmission along that edge succeeds with probability \(q_{st}\). The decision is a seed fraction \(x_t\in[0,1]\) for each type, subject to \(\sum_t\mu_t x_t\le\kappa\). Starting from \(a_t^{(0)}=x_t\), define
\[ a_t^{(r+1)} = 1-(1-x_t)\exp\!\left(-\sum_s\mu_s\lambda_{st}q_{st}a_s^{(r)}\right). \]
The question is to output a feasible seed vector whose limiting activated mass \(\sum_t\mu_t a_t^{(\infty)}\) is within \(\varepsilon\) of the maximum. This keeps the paper’s central decision—where to spend a seed budget to maximize IC spread—while making the population itself continuous.
I think the authors would recognize the influence-maximization objective and IC process in this question. The scenario also has a plausible high-multiplicity regime: many people per type, with far fewer types than people. My tentative expectation is that the variable-type problem may be continuum-specifically hard because the seed allocation interacts with a nonlinear cascade fixed point; fixed numbers of types may admit tractable optimization. That is a hypothesis for a prover, not a result of this paper. Natural follow-ups are whether the objective has a useful continuous diminishing-returns property, and when the finite stochastic-block problem converges to this mass formulation.
The weakest point is that this replaces the paper’s given, realized social graph with a type-based random network model. The proposed algorithm exploits detailed reachability and strongly connected components in that realized graph, so this mirror does not capture the paper’s algorithmic contribution or its experiments. It is a plausible mirror of the underlying optimization problem, but the paper provides no named result to anchor it.
The paper offers no paper-owned complexity result to continuize. Its central contribution is an estimator for marginal influence on a given finite graph, evaluated experimentally. The \((1-1/e)\) guarantee is attributed to Kempe, Kleinberg, and Tardos; the paper neither proves it nor claims a new complexity classification. The proponent raises no named theorem or other computational result as an anchor. The unnumbered influence-maximization problem is the strongest candidate, but it is a problem definition, not a result of this paper.
There is also a substantive gap between the paper’s computation and the proposed mirror. On a realized graph, a node’s influence depends on its particular paths and overlap with the other seeds’ reachable sets. The estimator exploits that topology, including strongly connected components. A faithful type would have to include enough of each node’s network position to preserve those facts; in a realistic graph, that could leave nearly every node in its own type, with no useful aggregation. The proposed stochastic block model avoids that by replacing the realized graph with type-to-type contact rates. Its fixed-point equations pose a coherent seed-allocation problem, but answer it for a random network ensemble rather than the observed network this paper studies. A graph-kernel version makes the same trade: it keeps a continuous population description by changing the object whose influence is being optimized.
That is the strongest case against a mirror of this paper’s contribution: a faithful continuization has no evident population compression, while the compressed model is a new formulation with no result here to anchor it. But it does not establish the universal claim. A large population with a small number of stable interaction types is plausible, and optimizing seed mass for its limiting influence is a computational question the authors could recognize. Under the programme’s rules, changing the network model does not by itself defeat that mirror. So the negative case is strong against mirroring the paper’s *algorithmic contribution*, but weak against the claim that no worthwhile continuous mirror exists in any scenario.
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.