• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Discovery Science >An Algorithm for Influence Maximization in a Two-Terminal Series Parallel Graph and its Application to a Real Network
【24h】

An Algorithm for Influence Maximization in a Two-Terminal Series Parallel Graph and its Application to a Real Network

机译：一种影响双终端串行图中最大化的算法及其在真实网络中的应用

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We developed an algorithm to exactly solve an influence maximization problem (MAXINF) for a two-terminal series parallel graph (TTSPG) in the independent cascade model. The class of TTSPGs can be considered as a class wider than that of trees, only for which an efficient exact solver of this problem has been developed so far. Our algorithm calculates candidate node sets in the divide-and-conquer manner keeping the number of them as small as possible by efficiently eliminating unnecessary ones in merge of subproblems' solutions. Furthermore, we propose a way of converting an arbitrary network to a TTSPG with edges important for propagation to apply our method to real networks. According to our empirical results, our method is significantly faster than the greedy approximation algorithm for MAXINF of a TTSPG. We also demonstrate improvement of solutions by converting to TTSPGs instead of trees using real networks made from DBLP datasets.
机译：我们开发了一种算法，精确地解决了独立级联模型中的双端串联平行图（TTSPG）的影响最大化问题（MAXINF）。 TTSPG的类可以被认为是宽的级别，而不是树木的阶级，只有到了到目前为止已经开发了这个问题的有效精确的求解器。我们的算法以剥离和征服方式计算候选节点集，通过有效地消除子问题的解决方案的合并中的不必要，保持它们的数量尽可能小。此外，我们提出了一种方法，可以将任意网络转换为TTSPG，其边缘对于传播来应用于实际网络的方法。根据我们的经验结果，我们的方法比TTSPG的MAXINF贪婪近似算法明显更快。我们还通过使用由DBLP数据集的真实网络转换为TTSPGS而不是树木来展示解决方案的改进。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号