Designing Networks: A Mixed-Integer Linear Optimization Approach

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 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 this paper, we propose the use of Mixed-Integer Linear Optimization modeling and solution methodologies to address this Network Generation Problem. We present a number of useful modeling techniques and apply them to mathematically express and constrain network properties in the context of an optimization formulation. We then develop 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.

References in corpus (7)

• Community structure and scale-free collections of Erdös-Rényi graphs
• A Scalable Generative Graph Model with Community Structure
• Performance of networks of artificial neurons: The role of clustering
• Generation of arbitrarily two-point correlated random networks
• Growing Scale-free Small-world Networks with Tunable Assortative Coefficient
• Generating random networks with given degree-degree correlations and degree-dependent clustering
• Tuning the average path length of complex networks and its influence to the emergent dynamics of the majority-rule model