Mon, 27.10.2014
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.
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.
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.
Aristides Gionis, Michael Mathioudakis, Antti Ukkonen, 'Bump Hunting in the
Dark - Local Discrepancy Maximization on Graphs', ICDE 2015, Seoul, Korea
Dark - Local Discrepancy Maximization on Graphs', ICDE 2015, Seoul, Korea
Last updated on 27 Oct 2014 by Michael Mathioudakis - Page created on 27 Oct 2014 by Michael Mathioudakis