论文标题
影响社会物理网络中最大化的算法
Algorithms for Influence Maximization in Socio-Physical Networks
论文作者
论文摘要
鉴于有向图（代表社交网络），影响最大化的问题是找到k节点，当受影响（或激活）时，它将最大程度地提高被激活的剩余节点的数量。在本文中，我们考虑了一个更通用的问题，该版本包括一组其他节点，称为物理节点，因此社交网络中的节点被一个或多个物理节点介绍。物理节点在两个状态之一中存在，打开或封闭，并且可以打开的最大物理节点数量有限制。在这种情况下，如果社交网络中有足够的活跃邻居，并且至少有一个打开的物理节点涵盖了一个社交网络中的不活动节点，则它会变得活跃。这个问题出现在灾难恢复中，一个流离失所的社会群体决定仅在其社交网络返回和附近的某些基础设施组成部分进行修复之后才能在灾难之后返回。一般的问题是在任何恒定因子内近似近似值，因此我们表征了问题的特殊实例的最佳和近似算法。
Given a directed graph (representing a social network), the influence maximization problem is to find k nodes which, when influenced (or activated), would maximize the number of remaining nodes that get activated. In this paper, we consider a more general version of the problem that includes an additional set of nodes, termed as physical nodes, such that a node in the social network is covered by one or more physical nodes. A physical node exists in one of two states at any time, opened or closed, and there is a constraint on the maximum number of physical nodes that can be opened. In this setting, an inactive node in the social network becomes active if it has enough active neighbors in the social network and if it is covered by at least one of the opened physical nodes. This problem arises in disaster recovery, where a displaced social group decides to return after a disaster only after enough groups in its social network return and some infrastructure components in its neighborhood are repaired. The general problem is NP-hard to approximate within any constant factor and thus we characterize optimal and approximation algorithms for special instances of the problem.
