Networks Inference

**We are often interested in infering the topology of a network**.
Specifically, we want to know which
nodes form part of a subnetwork. We can think of a network as a collection of nodes
(computers) that connect to some monitors (servers)
through some routers.

When a node pings a monitor (e.g., google), we
can measure the distance (measured in hop counts)
between such node and such monitor. We can construct
a distance matrix where each row represents a
monitor, and each column represents a node. The
*ith*
column gives the distances between the *ith* node and
all the monitors. But since not every node
pings every monitor, we have incomplete data.

In a simplified model, if node *i* forms part of
subnet *k*, then the *ith* column is given by the
sum of (a) the distance between node *i* and router
*k*, and (b) the distance between router *k*and each of
the monitors:

Hence, these measurements lie in a **union of subspaces**.
If we cluster the columns according to their subspaces, we can
determine the subnets.

© Daniel Pimentel-Alarcón