Decentralized Online Influence Maximization
Decentralized Online Influence Maximization
复制标题
DOI：
10.1109/allerton49937.2022.9929315
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Yigit E. Bayiz;U. Topcu
中科院分区：
文献类型：
--
作者：
Yigit E. Bayiz;U. Topcu
我们考虑在随机网络中寻找最大影响力节点的问题，其中每个节点以恒定但未知的概率影响其他节点。我们开发了一个在线算法，学习节点的相对影响。它放宽了现有文献中的假设，即一个中心观察者可以监控全球的影响力传播。所提出的算法将在线更新委托给网络上的节点，因此只需要在节点上进行局部观测。我们表明，使用探索然后提交的学习策略，该算法在时域$T$上积累的累积遗憾接近$O（T^{2/3}）$的网络具有大量的节点。此外，我们表明，对于固定的$T$，最坏的情况下，遗憾的增长与图中的节点数$n$的线性。数值实验表明，这种线性相关的Chung-Lu模型。实验还表明，$\vareps $ -贪婪的学习策略可以达到类似的性能，探索然后提交策略的Chung-Lu模型。
We consider the problem of finding the maximally influential node in random networks where each node influences every other node with constant yet unknown probability. We develop an online algorithm that learns the relative influences of the nodes. It relaxes the assumption in the existing literature that a central observer can monitor the influence spread globally. The proposed algorithm delegates the online updates to the nodes on the network; hence requires only local observations at the nodes. We show that using an explore-then-commit learning strategy, the cumulative regret accumulated by the algorithm over horizon $T$ approaches $O(T^{2/3})$ for a network with a large number of nodes. Additionally, we show that, for fixed $T$, the worst case-regret grows linearly with the number $n$ of nodes in the graph. Numerical experiments illustrate this linear dependence for Chung-Lu models. The experiments also demonstrate that $\varepsilon$ -greedy learning strategies can achieve similar performance to the explore-then-commit strategy on Chung-Lu models.