论文标题
通过结合学习自动机对动态社交网络的影响最大化
Influence Maximization on Dynamic Social Networks with Conjugate Learning Automata
论文作者
论文摘要
从所有顶点中选择最佳子集作为种子来最大程度地发挥社交网络的影响，这是一项兴趣的任务。已经提出了各种方法来选择静态网络中的最佳顶点，但是，它们受到动态的挑战，即社交网络结构的时间相关变化。这种动力学阻碍了静态网络的范式，并在影响静态网络的影响最大化和动态网络的算法之间留下了看似不可思议的差距。在本文中，我们扩展了以前的工作，并证明已成功应用以最大程度地应用了对静态网络影响的共轭学习自动机（增强学习的基本变体）也可以应用于动态网络。网络动力学是通过影响范围的变化来衡量的，并吸收到学习过程中。我们的提议细致地制定了网络动态的效果：影响范围的变化越多，从头开始学习种子的可能性就越大。在此假设下，完全利用网络变化的连续性。合成和现实世界网络的实验结果验证了我们提案的特权，以替代方法。
Selecting the optimal subset from all vertices as seeds to maximize the influence in a social network has been a task of interest. Various methods have been proposed to select the optimal vertices in a static network, however, they are challenged by the dynamics, i.e. the time-dependent variation of the social network structure. Such dynamics hinder the paradigm for static networks and leaves a seemingly unbridgeable gap between algorithms of influence maximization on static networks and those on dynamic ones. In this paper, we extend our previous work and demonstrate that conjugate learning automata (an elementary variant of reinforcement learning) that have been successfully applied to maximize influence on static networks can be applied to dynamic networks as well. The network dynamics is measured by the variation of the influence range and absorbed into the learning procedure. Our proposal delicately formulates the effect of network dynamics: the more the influence range varies, the more likely the seeds are to be learned from scratch. Under this assumption, the continuity of the network variation is fully taken advantage of. Experimental results on both synthetic and real-world networks verify the privileges of our proposal against alternative methods.
