Efficient Information Flow Maximization in Probabilistic Graphs
Efficient Information Flow Maximization in Probabilistic Graphs
复制标题
DOI：
10.1109/tkde.2017.2780123
复制
发表时间：
2018-05-01
影响因子：
8.9
通讯作者：
Renz, Matthias
中科院分区：
文献类型：
--
作者：
Frey, Christian;Zufle, Andreas;Renz, Matthias
通过大型网络可靠地传播信息，例如，通信网络、社交网络或传感器网络在涉及营销、社交网络和无线传感器网络的许多应用中非常重要。然而，友谊的社会关系可能已经过时，通信联系可能会失败，从而导致这种网络中的不确定性概念。在本文中，我们解决的问题，优化信息传播的不确定网络给定的约束预算的边缘。我们发现，这个问题需要解决两个NP-难的子问题：预期的信息流的计算，和边缘的最佳选择。为了计算到源顶点的预期信息流，我们提出了F-树作为一种专门的数据结构，它识别图的独立组件，对于这些组件，可以分析和有效地计算信息流，或者可以独立于其余网络应用传统的蒙特-卡罗采样。对于寻找最佳边缘的问题，我们提出了一系列的算法，利用这种数据结构的属性。我们的评估表明，这些算法导致高质量的解决方案，从而产生高的信息流，同时保持低运行时间。
Reliable propagation of information through large networks, e.g., communication networks, social networks, or sensor networks is very important in many applications concerning marketing, social networks, and wireless sensor networks. However, social ties of friendship may be obsolete, and communication links may fail, inducing the notion of uncertainty in such networks. In this paper, we address the problem of optimizing information propagation in uncertain networks given a constrained budget of edges. We show that this problem requires to solve two NP-hard subproblems: the computation of expected information flow, and the optimal choice of edges. To compute the expected information flow to a source vertex, we propose the F-tree as a specialized data structure, that identifies independent components of the graph for which the information flow can either be computed analytically and efficiently, or for which traditional Monte-Carlo sampling can be applied independently of the remaining network. For the problem of finding the optimal edges, we propose a series of heuristics that exploit properties of this data structure. Our evaluation shows that these heuristics lead to high quality solutions, thus yielding high information flow, while maintaining low running time.