Bump Hunting in the Dark: Local Discrepancy Maximization on Graphs

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Tutkijat

Organisaatiot

  • Finnish Institute of Occupational Health

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
Artikkeli7476870
Sivut529-542
Sivumäärä14
JulkaisuIEEE Transactions on Knowledge and Data Engineering
Vuosikerta29
Numero3
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