Title: Core Discovery in Hidden Graphs,
Abstract: Massive network exploration is an important research direction with many
applications. In such a setting, the network is, usually, modeled as a graph
$G$, whereas any structural information of interest is extracted by inspecting
the way nodes are connected together. In the case where the adjacency matrix or
the adjacency list of $G$ is available, one can directly apply graph mining
algorithms to extract useful knowledge. However, there are cases where this is
not possible because the graph is \textit{hidden} or \textit{implicit}, meaning
that the edges are not recorded explicitly in the form of an adjacency
representation. In such a case, the only alternative is to pose a sequence of
\textit{edge probing queries} asking for the existence or not of a particular
graph edge. However, checking all possible node pairs is costly (quadratic on
the number of nodes). Thus, our objective is to pose as few edge probing
queries as possible, since each such query is expected to be costly. In this
work, we center our focus on the \textit{core decomposition} of a hidden graph.
In particular, we provide an efficient algorithm to detect the maximal subgraph
of $S_k$ of $G$ where the induced degree of every node $u \in S_k$ is at least
$k$. Performance evaluation results demonstrate that significant performance
improvements are achieved in comparison to baseline approaches.