Short and Wide Network Paths

Lavanya Marla, Lav R. Varshney, Devavrat Shah, Nirmal A. Prakash, Michael E. Gale

Research output: Contribution to journalArticlepeer-review


Network flow is a powerful mathematicalframework to systematically explore the relationship between structure and function in biological, social, and technological networks. We introduce a new pipelining model of flow through networks where commodities must be transported over single paths rather than split over several paths and recombined. We show this notion of pipelined network flow is optimized using network paths that are both short and wide, and develop efficient algorithms to compute such paths for given pairs of nodes and for all-pairs. Short and wide paths are characterized for many real-world networks. Using this framework, we further develop novel information-theoretic lower bounds on computation speed in nervous systems due to limitations from anatomical connectivity and physical noise. This provides predictions on the structural organization and behavior of the nematode Caenorhabditis elegans.

Original languageEnglish (US)
Pages (from-to)524-537
Number of pages14
JournalIEEE Transactions on Network Science and Engineering
Issue number2
StatePublished - 2022


  • Biological system modeling
  • Network flow
  • Neurons
  • Optimization
  • Pipeline processing
  • shortest paths
  • Signal processing algorithms
  • Standards
  • Switching circuits
  • widest paths
  • Widest paths
  • Shortest paths

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Networks and Communications
  • Computer Science Applications


Dive into the research topics of 'Short and Wide Network Paths'. Together they form a unique fingerprint.

Cite this