| paper | Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source |
| authors | — |
| venue | AAMAS 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given a finite type set \(Q\) with rational masses \(\mu_q\), \(\sum_{q\in Q}\mu_q=1\), a distinguished source \(s\), period \(p\), repeated type relations \(E_1,\ldots,E_p\), influence duration \(\delta\), and posting budget \(b\), where each relation is lifted to complete cohort-to-cohort contacts, choose \(T\subseteq\mathbb{N}\) with \(|T|\le b\) to maximize \(\sum_{q\in Q}\mu_q\mathbf{1}[q\text{ is active at some time under }T]\) under the paper's renewal dynamics.
A high-multiplicity temporal-contact network with synchronized role types \(Q\), mass \(\mu_q\) per type, complete bipartite temporal contacts specified by \(E_t\), integer posting schedule \(T\), and objective equal to the total mass of types ever activated.
The type-level relations \(E_t\) do not by themselves specify the lift from cohorts to individual contacts, so the \(2^p\operatorname{poly}(\tau,p,\delta,L)\) transfer is conditional on complete-blow-up semantics rather than valid for arbitrary temporal graphs.
fatal: False
The mirror covers Theorem 5.1's periodic MaxSpread algorithm, Theorem 3.10's weighted MaxSpread approximation, and Theorem 5.2's periodic viral hardness; it leaves the fixed-window and shifting-window results, the periodic SIS MaxSpread open problem, and other open questions untreated.
There is a credible mirror, with \(\textsc{Periodic-MaxSpread}_\infty\) as the lead. It preserves the paper’s fixed source, temporal contacts, SIS-style renewal, discrete posting schedule, and “when-to-post” objective; only the audience becomes a high-multiplicity population.
Take a platform audience partitioned into finitely many complete temporal-contact types \(Q=\{q_1,\ldots,q_\tau\}\). A type includes everything relevant to the diffusion process: its temporal neighbourhood, relay role, and common influence duration \(\delta\). Let \(\mu_q\in\mathbb{Q}_{\ge 0}\) be the fraction of the audience of type \(q\), with \(\sum_q\mu_q=1\). The source \(s\) is a distinguished influencer, not a mass-bearing audience type. At every time \(t\), the type-level temporal graph has edges \(E_t\subseteq Q^2\), and the paper’s counter dynamics run on types: a type becomes active when an adjacent type is active, its counter resets to \(\delta\), and otherwise its counter decreases.
Thus all agents in a type are clones: they have the same temporal contacts and evolve identically. If \(\mu_q=N_q/N\), this is exactly the quotient of a finite audience containing \(N_q\) clones of type \(q\). The objective is not expected influence or fractional activation inside a type. It is the mass of types ever activated:
\[ F_{\mathrm{spread}}(T) = \sum_{q\in Q}\mu_q \mathbf{1}\!\left[q\text{ is active at some time under schedule }T\right]. \]
This is a genuine high-multiplicity regime: a social-media campaign may address millions of users but only hundreds or thousands of recurring temporal-contact cohorts—say, users in the same broadcast channel, time zone, engagement window, and relay position. The source still chooses individual integer time slots. We are continuizing the population, not time, outcomes, or uncertainty.
My lead anchor is Theorem 5.1, proved in this paper: MaxSpread on a periodic temporal graph of period \(t_{\max}\) can be solved in time \(2^{t_{\max}}\operatorname{poly}(|V(G)|)\). Its continuous counterpart is:
\[ \textsc{Periodic-MaxSpread}_\infty \]
An instance consists of a finite type set \(Q\), rational masses \(\mu\), a distinguished source \(s\), a period \(p\), temporal type-relations \(E_1,\ldots,E_p\) repeated forever, an influence duration \(\delta\), and a posting budget \(b\). A feasible solution is a finite schedule \(T\subseteq\mathbb{N}\) with \(|T|\le b\). The task is to find a schedule maximizing \(F_{\mathrm{spread}}(T)\).
I expect this problem to be Class A. The proof of Theorem 5.1 depends only on the finite type-level state space and on the fact that, for MaxSpread, it suffices to examine transmissions in the first period and simulate until no new type is activated. Replacing vertices by types changes the simulation cost from \(\operatorname{poly}(|V(G)|)\) to \(\operatorname{poly}(\tau)\); accumulating rational masses adds only polynomial bit complexity. The resulting exact algorithm is therefore
\[ 2^p\operatorname{poly}(\tau,p,\delta,L), \]
where \(L\) is the encoding length of the masses and thresholds. For fixed period, this is polynomial-time.
The rational-clone bridge is exact. Clearing denominators produces \(N_q\) identical agents of each type. Since every clone in a type has the same state at every time, the continuous objective equals the finite objective divided by \(N\). No winner convention, certificate, or feasible schedule changes. This makes the mirror more than a weighted analogy: it is the exact high-multiplicity version of a type-regular temporal graph.
A useful second anchor is Theorem 3.10, also proved here: all three finite-horizon objectives admit a polynomial-time \((1-1/e)\)-approximation. For MaxSpread, define
\[ R_j=\{q\in Q:q\text{ becomes active at some time if the source transmits only at time }j\}. \]
By the paper’s Lemma 3.9, for every schedule \(T\),
\[ F_{\mathrm{spread}}(T) = \sum_{q\in \bigcup_{j\in T}R_j}\mu_q. \]
This gives the precise problem
\[ \textsc{Weighted-Finite-MaxSpread}_\infty \]
with the same finite temporal type graph, rational masses, duration \(\delta\), horizon \(H\), and budget \(b\). A solution is a schedule \(T\subseteq[H]\), \(|T|\le b\), and its value is the displayed weighted union. The task is to output a schedule whose value is at least \((1-1/e)\) times optimum.
This is weighted MaximumCoverage over the single-post reach sets \(R_j\), so the greedy algorithm gives the same \((1-1/e)\) guarantee in polynomial time. I would classify this approximation problem as Class A, while expecting its exact optimization companion to retain inherited hardness. The paper’s central insight—that several transmissions produce the union of their individual influence sets—survives perfectly under population masses.
The third anchor marks the boundary rather than supplying filler. Theorem 5.2, proved in this paper, states that periodic MaxViral and MaxViralTstep are NP-hard and W[2]-hard parameterized by the transmission budget \(b\), for every \(p\ge2\) and \(1\le\delta<p\). A continuous version is:
\[ \textsc{Periodic-MaxViralTstep}_\infty \]
An instance consists of \(Q,\mu,s,p,E_1,\ldots,E_p,\delta,b\), a target time \(t^\star\), and a rational threshold \(\kappa\). The question is whether there exists a schedule \(T\) with \(|T|\le b\) such that
\[ F_{\mathrm{viral}}(T;t^\star) = \sum_{q\in Q}\mu_q \mathbf{1}[q\text{ is active at }t^\star] \ge \kappa. \]
I expect hardness to transfer, hence Class B. Give every role equal mass, clear denominators, and replace each role by an arbitrary large clone cohort. The SetCover construction in Theorem 5.2 is then reproduced at the type level, with the threshold normalized by the total population. The combinatorics live in the temporal posting phases and the budget, not in the fact that individual audience members are separately named. Continuization does not remove that hardness; it only changes the objective from a count to a mass.
The scope is deliberately limited. These mirrors cover periodic MaxSpread exactly, the finite-horizon MaxSpread approximation, and periodic MaxViralTstep. They do not claim continuous analogues of every fixed-window or shifting-window theorem, nor of the paper’s SIS variant under which the authors leave periodic MaxSpread open. They also do not rely on the continuous-time diffusion papers cited in Section 1.2: those continuize time or diffusion laws, whereas this mirror continuizes the population.
The weakest point is topology. In an arbitrary social network, two users with the same demographic description may occupy different graph positions, and preserving their entire temporal neighbourhood can make every user its own type. The mirror therefore needs a real regime assumption: repeated cohort roles with synchronized temporal contacts, represented by a type-level temporal graph or its clone expansion. If the authors insist that individual topology is essential and never repeats, the population gain disappears. That is a genuine limitation, not something to conceal.
But the proposed regime is recognizable as their problem: a fixed influencer, a temporal graph, a discrete posting schedule, the same SIS-style spreading process, and the same influence objectives. It is a faithful high-multiplicity extension for audiences whose network interaction is organized through repeated temporal roles. The positive case is strongest for Theorem 5.1: the paper’s exact periodic algorithm survives almost unchanged, with \(\tau\) replacing the number of named users and rational mass replacing vertex count.
The paper clears the “named computational result” gate, so the negative case cannot rest on the absence of an algorithmic anchor. Its only serious route is semantic: all three proposed mirrors assume that temporal-network vertices can be aggregated into population types without losing the network.
That assumption is not automatic here. In this paper, a vertex’s relevant identity is its time-dependent adjacency pattern and its position in the relay structure. A distribution over types does not determine those relations. Suppose types \(A\) and \(B\) are adjacent. Replacing them by cohorts could mean a complete bipartite lift, in which one active \(A\)-agent activates every \(B\)-agent, or a matching lift, in which only one \(B\)-agent activates. The same \((\mu,E_t)\) gives different influence masses. If “type” includes exact neighbours, repeated types generally disappear; if it includes only neighbour types, the quotient has forgotten information the diffusion process uses.
This defeats Theorem 5.1 as a direct mirror. Its \(2^{t_{\max}}\operatorname{poly}(|V|)\) algorithm applies to a named temporal graph. The proposed \(2^p\operatorname{poly}(\tau)\) algorithm applies only after imposing a new complete-blow-up semantics in which every member of a role has the same cohort-level contacts and synchronizes with the whole neighbouring cohort. That is a structured network re-modelling, not merely replacing population counts by masses. It may be a legitimate extension, but the paper itself does not establish that such cohort/channel networks are its high-multiplicity regime.
The same objection applies to Theorem 3.10. The weighted-union identity is mathematically correct once the quotient dynamics have been accepted. But the sets \(R_j\) are precomputed behavioural signatures of a type-level network; they are not determined by a population measure. Defining types by identical single-post reach sets makes the problem exactly weighted MaximumCoverage, but it compiles away the temporal network and its interactions. That is an objective-specific re-encoding, not a continuous population model of the diffusion process. It also cannot serve as a common type semantics for MaxViral or MaxViralTstep, where simultaneous activation and temporal correlation matter.
Theorem 5.2 is the hardest anchor to reject. The proponent is right that, under the complete-blow-up interpretation, the SetCover reduction can be cloned: scale all masses equally, clone each path and terminal role, and scale the threshold. The periodic path roles remain distinct types, but each can have high multiplicity. The hardness then survives.
Consequently, the topology objection defeats the proposed mirrors only under a strict direct-mirror standard. If the programme is willing to recognise complete-blow-up temporal networks, the proponent has a credible extension, especially for Periodic-MaxSpread and the weighted MaxSpread approximation. Calling it “already continuous” because of the cited continuous-time diffusion literature would be wrong, and calling it invalid merely because the answer may remain easy or hard would also be wrong.
So the honest negative case is weak. I would reject the mirrors as faithful continuizations of the paper’s original graph model, because the population quotient does not preserve contact semantics without adding a strong new lift assumption. But I could not responsibly claim that no worthwhile scenario exists: the cohort/blow-up model is author-recognizable and its rational-clone bridge is substantially sound.
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.