AI、机器学习、深度学习、数据挖掘或数学研究人员：以下是一篇论文的题目和摘要：题目：成为一名影响者很难：在固定源点的时间图中最大化影响力的复杂性摘要：我们考虑了在时间图上的影响最大化问题，其中有一个单一的固定源点。我们偏离了标准的影响最大化模型，该模型的目标是选择最具有影响力的顶点集。相反，在我们的模型中，我们给出了一个固定的顶点或源点，并且目标是找到最佳的时间步来传播，以使这个顶点的影响最大化。我们将这个问题框架化为一种传播过程，它遵循一种易感-感染-易感（SIS）模型的变体，并且我们关注四个目标函数。在最大扩散（MaxSpread）目标函数中，目标是最大化至少被感染一次的顶点总数。在最大病毒（MaxViral）目标函数中，目标是最大化同一时间步被感染的顶点数。在最大病毒时间步（MaxViralTstep）目标函数中，目标是最大化在给定时间步长内被感染的顶点数。最后，在最小非病毒时间（MinNonViralTime）目标函数中，目标是最大化每$d$个时间步长内被感染的总顶点数。我们对这四个目标函数在三个不同情况下进行了彻底的复杂度理论分析：（1）非限制设定，源点可以在任何时候传输；（2）限制时间窗口设定，源点必须在预定或移动的时间窗口内传输；（3）周期性设定，时间图具有一个小周期。我们证明了所有这些问题，除了周期图的最大扩散问题，即使在非常简单的底层图上也是不可解的。 (Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source)

翻译：AI、机器学习、深度学习、数据挖掘或数学研究人员：以下是一篇论文的题目和摘要：题目：成为一名影响者很难：在固定源点的时间图中最大化影响力的复杂性摘要：我们考虑了在时间图上的影响最大化问题，其中有一个单一的固定源点。我们偏离了标准的影响最大化模型，该模型的目标是选择最具有影响力的顶点集。相反，在我们的模型中，我们给出了一个固定的顶点或源点，并且目标是找到最佳的时间步来传播，以使这个顶点的影响最大化。我们将这个问题框架化为一种传播过程，它遵循一种易感-感染-易感（SIS）模型的变体，并且我们关注四个目标函数。在最大扩散（MaxSpread）目标函数中，目标是最大化至少被感染一次的顶点总数。在最大病毒（MaxViral）目标函数中，目标是最大化同一时间步被感染的顶点数。在最大病毒时间步（MaxViralTstep）目标函数中，目标是最大化在给定时间步长内被感染的顶点数。最后，在最小非病毒时间（MinNonViralTime）目标函数中，目标是最大化每$d$个时间步长内被感染的总顶点数。我们对这四个目标函数在三个不同情况下进行了彻底的复杂度理论分析：（1）非限制设定，源点可以在任何时候传输；（2）限制时间窗口设定，源点必须在预定或移动的时间窗口内传输；（3）周期性设定，时间图具有一个小周期。我们证明了所有这些问题，除了周期图的最大扩散问题，即使在非常简单的底层图上也是不可解的。

Argyrios Deligkas,Michelle Döring,Eduard Eiben,Tiger-Lily Goldsmith,George Skretas

from arxiv, 21 pages, 6 figures

We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and we focus on four objective functions. In the MaxSpread objective, the goal is to maximize the total number of vertices that get infected at least once. In the MaxViral objective, the goal is to maximize the number of vertices that are infected at the same time step. In the MaxViralTstep objective, the goal is to maximize the number of vertices that are infected at a given time step. Finally, in MinNonViralTime, the goal is to maximize the total number of vertices that get infected every $d$ time steps. We perform a thorough complexity theoretic analysis for these four objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph has a small period. We prove that all of these problems, with the exception of MaxSpread for periodic graphs, are intractable even for very simple underlying graphs.

翻译：成为一名影响者很难：在固定源点的时间图中最大化影响力的复杂性摘要：本文考虑了在时间图上的影响最大化问题，其中有一个单一的固定源点。我们偏离了标准的影响最大化模型，该模型的目标是选择最具有影响力的顶点集。相反，在我们的模型中，我们给出了一个固定的顶点或源点，并且目标是找到最佳的时间步来传播，以使这个顶点的影响最大化。我们将这个问题框架化为一种传播过程，它遵循一种易感-感染-易感（SIS）模型的变体，并且我们关注四个目标函数。在最大扩散（MaxSpread）目标函数中，目标是最大化至少被感染一次的顶点总数。在最大病毒（MaxViral）目标函数中，目标是最大化同一时间步被感染的顶点数。在最大病毒时间步（MaxViralTstep）目标函数中，目标是最大化在给定时间步长内被感染的顶点数。最后，在最小非病毒时间（MinNonViralTime）目标函数中，目标是最大化每$d$个时间步长内被感染的总顶点数。我们对这四个目标函数在三个不同情况下进行了彻底的复杂度理论分析：（1）非限制设定，源点可以在任何时候传输；（2）限制时间窗口设定，源点必须在预定或移动的时间窗口内传输；（3）周期性设定，时间图具有一个小周期。我们证明了所有这些问题，除了周期图的最大扩散问题，即使在非常简单的底层图上也是不可解的。