  A typical way in which network data is recorded is to measure all the
interactions among a specified set of core nodes; this produces a graph
containing this core together with a potentially larger set of fringe nodes
that have links to the core. Interactions between pairs of nodes in the fringe,
however, are not recorded by this process, and hence not present in the
resulting graph data. For example, a phone service provider may only have
records of calls in which at least one of the participants is a customer; this
can include calls between a customer and a non-customer, but not between pairs
of non-customers.
  Knowledge of which nodes belong to the core is an important piece of metadata
that is crucial for interpreting the network dataset. But in many cases, this
metadata is not available, either because it has been lost due to difficulties
in data provenance, or because the network consists of found data obtained in
settings such as counter-surveillance. This leads to a natural algorithmic
problem, namely the recovery of the core set. Since the core set forms a vertex
cover of the graph, we essentially have a planted vertex cover problem, but
with an arbitrary underlying graph. We develop a theoretical framework for
analyzing this planted vertex cover problem, based on results in the theory of
fixed-parameter tractability, together with algorithms for recovering the core.
Our algorithms are fast, simple to implement, and out-perform several methods
based on network core-periphery structure on various real-world datasets.
