Designing networks: A mixed-integer linear optimization approach

Chrysanthos E. Gounaris, Karthikeyan Rajendran, Ioannis G. Kevrekidis, Christodoulos A. Floudas

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

Designing networks with specified collective properties is useful in a variety of application areas, enabling the study of how given properties affect the behavior of network models, the downscaling of empirical networks to workable sizes, and the analysis of network temporal evolution. Despite the importance of the task, there currently exists a gap in our ability to systematically generate networks that adhere to theoretical guarantees for the given property specifications. In thisarticle, we propose the use of Mixed-Integer Linear Optimization modeling and solution methodologies to address this Network Generation Problem. We present useful modeling techniques and apply them to mathematically express and constrain a broad class of network properties in the context of an optimization formulation. We derive complete formulations for the generation of networks that attain specified levels of connectivity, spread, assortativity and robustness, and we illustrate these via a number of computational case studies.

Original languageEnglish (US)
Pages (from-to)283-301
Number of pages19
JournalNetworks
Volume68
Issue number4
DOIs
StatePublished - Dec 1 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • assortativity
  • clustering coefficient
  • graph theory
  • mathematical optimization
  • network diameter
  • network generation
  • network robustness

Fingerprint Dive into the research topics of 'Designing networks: A mixed-integer linear optimization approach'. Together they form a unique fingerprint.

  • Cite this

    Gounaris, C. E., Rajendran, K., Kevrekidis, I. G., & Floudas, C. A. (2016). Designing networks: A mixed-integer linear optimization approach. Networks, 68(4), 283-301. https://doi.org/10.1002/net.21699