...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Knowledge and Data Engineering >Bump Hunting in the Dark: Local Discrepancy Maximization on Graphs
【24h】

Bump Hunting in the Dark: Local Discrepancy Maximization on Graphs

机译：在黑暗中寻找凹凸：图形上的局部差异最大化

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the problem of discrepancy maximization on graphs: given a set of nodes Q of an underlying graph G , we aim to identify a connected subgraph of G that contains many more nodes from Q than other nodes. This variant of the discrepancy-maximization problem extends the well-known notion of “bump hunting” in the Euclidean space [1] . We consider the problem under two access models. In the unrestricted-access model, the whole graph G is given as input, while in the local-access model we can only retrieve the neighbors of a given node in G using a possibly slow and costly interface. We prove that the basic problem of discrepancy maximization on graphs is NP -hard, and empirically evaluate the performance of four heuristics for solving it. For the local-access model, we consider three different algorithms that aim to recover a part of G large enough to contain an optimal solution, while using only a small number of calls to the neighbor-function interface. We perform a thorough experimental evaluation in order to understand the trade offs between the proposed methods and their dependencies on characteristics of the input graph.
机译：我们研究图上差异最大化的问题：给定基础图G的一组节点Q，我们的目标是确定G的连通子图，该子图包含来自Q的节点多于其他节点。差异最大化问题的这种变体扩展了欧几里德空间[1]中众所周知的“凹凸搜索”概念。我们考虑两种访问模型下的问题。在无限制访问模型中，整个图G作为输入给出，而在本地访问模型中，我们只能使用可能缓慢且昂贵的接口来检索G中给定节点的邻居。我们证明了图上差异最大化的基本问题是NP-hard，并通过经验评估了四种启发式算法的性能。对于本地访问模型，我们考虑了三种不同的算法，这些算法旨在恢复G的足够大的部分，以包含最佳解决方案，同时仅使用对邻居函数接口的少量调用。我们进行了全面的实验评估，以了解建议的方法及其对输入图特征的依赖性之间的权衡。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号