Designing Networks: A Mixed-Integer Linear Optimization Approach
arXiv:1502.00362 · doi:10.1002/net.21699
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 (21)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Assortative mixing in networks
- Mixing patterns in networks
- Characterization of complex networks: A survey of measurements
- Hierarchical Organization in Complex Networks
- Dynamical and correlation properties of the Internet
- Growing Scale-Free Networks with Tunable Clustering
- Community structure and scale-free collections of Erdös-Rényi graphs
- Factors that predict better synchronizability on complex networks
- Construction and properties of assortative random networks
- A Scalable Generative Graph Model with Community Structure
- Tuning clustering in random networks with arbitrary degree distributions
- Performance of networks of artificial neurons: The role of clustering
- Evolving Clustered Random Networks
- Random Networks with Tunable Degree Distribution and 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