Tractable structure learning in radial physical flow networks

Deepjyoti Deka, Scott Backhaus, Michael Chertkov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)


Physical Flow Networks are different infrastructure networks that allow the flow of physical commodities through edges between its constituent nodes. These include power grid, natural gas transmission network, water pipelines etc. In such networks, the flow on each edge is characterized by a function of the nodal potentials on either side of the edge. Further the net flow in and out of each node is conserved. Learning the structure and state of physical networks is necessary for optimal control as well as to quantify its privacy needs. We consider radial flow networks and study the problem of learning the operational network from a loopy graph of candidate edges using statistics of nodal potentials. Based on the monotonic properties of the flow functions, the key result in this paper shows that if variance of the difference of nodal potentials is used to weight candidate edges, the operational edges form the minimum spanning tree in the loopy graph. Under realistic conditions on the statistics of nodal injection (consumption or production), we provide a greedy structure learning algorithm with quasilinear computational complexity in the number of candidate edges in the network. Our learning framework is very general due to two significant attributes. First it is independent of the specific marginal distributions of nodal potentials and only uses order properties in their second moments. Second, the learning algorithm is agnostic to exact flow functions that relate edge flows to corresponding potential differences and is applicable for a broad class of networks with monotonic flow functions. We demonstrate the efficacy of our work through realistic simulations on diverse physical flow networks and discuss possible extensions of our work to other regimes.

Original languageEnglish
Title of host publication2016 IEEE 55th Conference on Decision and Control, CDC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781509018376
Publication statusPublished - 27 Dec 2016
Externally publishedYes
Event55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States
Duration: 12 Dec 201614 Dec 2016

Publication series

Name2016 IEEE 55th Conference on Decision and Control, CDC 2016


Conference55th IEEE Conference on Decision and Control, CDC 2016
Country/TerritoryUnited States
CityLas Vegas


  • Computational Complexity
  • Graphical Models
  • Missing data
  • monotonic flow
  • Physical flow networks
  • positive quadrant dependence
  • Spanning Tree


Dive into the research topics of 'Tractable structure learning in radial physical flow networks'. Together they form a unique fingerprint.

Cite this