Bump Hunting in the Dark: Local Discrepancy Maximization on Graphs

Tutkimustuotos: Lehtiartikkelivertaisarvioitu



  • Finnish Institute of Occupational Health


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 \mathbf {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.


JulkaisuIEEE Transactions on Knowledge and Data Engineering
TilaJulkaistu - 1 maaliskuuta 2017
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu
TapahtumaInternational Conference on Data Engineering - Seoul, Etelä-Korea
Kesto: 13 huhtikuuta 201517 huhtikuuta 2015
Konferenssinumero: 31

ID: 10994574