论文标题
PREF：大型网络中扩散源 - 集定问题的基于渗透的进化框架
PrEF: Percolation-based Evolutionary Framework for the diffusion-source-localization problem in large networks
论文作者
论文摘要
我们假设可以在必要时研究网络中许多节点的状态，并研究这些节点的配置可以促进更好的解决方案解决扩散源源 - 元素 - DSL问题（DSL）问题。特别是，我们制定了一个包含扩散源的候选集合，并提出了基于渗透的进化框架（PREF）的方法，以最小化该集合。因此，人们只能对几个节点进行更深入的调查以针对来源。为此，我们首先证明DSL问题与网络免疫问题之间存在一些相似之处。我们发现，如果我们将观察者集视为删除节点集，那么候选集合的最小化等效于订单参数的最小化。因此，根据网络渗透和进化算法开发PERF。在各种情况下，在模型和经验网络上都验证了所提出方法的有效性。我们的结果表明，与几乎所有情况下，开发的方法与最新情况相比，可以实现更小的候选人集合。同时，我们的方法也更加稳定，即，与不同的感染概率，扩散模型和爆发范围无关，它具有相似的性能。更重要的是，我们的方法可能会提供一个新的框架来解决极端大型网络中的DSL问题。
We assume that the state of a number of nodes in a network could be investigated if necessary, and study what configuration of those nodes could facilitate a better solution for the diffusion-source-localization (DSL) problem. In particular, we formulate a candidate set which contains the diffusion source for sure, and propose the method, Percolation-based Evolutionary Framework (PrEF), to minimize such set. Hence one could further conduct more intensive investigation on only a few nodes to target the source. To achieve that, we first demonstrate that there are some similarities between the DSL problem and the network immunization problem. We find that the minimization of the candidate set is equivalent to the minimization of the order parameter if we view the observer set as the removal node set. Hence, PrEF is developed based on the network percolation and evolutionary algorithm. The effectiveness of the proposed method is validated on both model and empirical networks in regard to varied circumstances. Our results show that the developed approach could achieve a much smaller candidate set compared to the state of the art in almost all cases. Meanwhile, our approach is also more stable, i.e., it has similar performance irrespective of varied infection probabilities, diffusion models, and outbreak ranges. More importantly, our approach might provide a new framework to tackle the DSL problem in extreme large networks.
