Network Topology Identification using PCA and its Graph Theoretic
  Interpretations
  We solve the problem of identifying (reconstructing) network topology from
steady state network measurements. Concretely, given only a data matrix
$\mathbf{X}$ where the $X_{ij}$ entry corresponds to flow in edge $i$ in
configuration (steady-state) $j$, we wish to find a network structure for which
flow conservation is obeyed at all the nodes. This models many network problems
involving conserved quantities like water, power, and metabolic networks. We
show that identification is equivalent to learning a model $\mathbf{A_n}$ which
captures the approximate linear relationships between the different variables
comprising $\mathbf{X}$ (i.e. of the form $\mathbf{A_n X \approx 0}$) such that
$\mathbf{A_n}$ is full rank (highest possible) and consistent with a network
node-edge incidence structure. The problem is solved through a sequence of
steps like estimating approximate linear relationships using Principal
Component Analysis, obtaining f-cut-sets from these approximate relationships,
and graph realization from f-cut-sets (or equivalently f-circuits). Each step
and the overall process is polynomial time. The method is illustrated by
identifying topology of a water distribution network. We also study the extent
of identifiability from steady-state data.
