Mathematical programming approaches for classes of random network problems

作者：Castro Jordi^*; Nasini Stefano

来源：European Journal of Operational Research, 2015, 245(2): 402-414.

DOI：10.1016/j.ejor.2015.03.021

• Interior-point methods
• Integer programming
• Complex networks
• Total unimodularity
• Central path

Random simulations from complicated combinatorial sets are often needed in many classes of stochastic problems. This is particularly true in the analysis of complex networks, where researchers are usually interested in assessing whether an observed network feature is expected to be found within families of networks under some hypothesis (named conditional random networks, i.e., networks satisfying some linear constraints). This work presents procedures to generate networks with specified structural properties which rely on the Solution of classes of integer optimization problems. We show that, for many of them, the constraints matrices are totally unimodular, allowing the efficient generation of conditional random networks by specialized interior-point methods. The computational results suggest that the proposed methods can represent a general framework for the efficient generation of random networks even beyond the models analyzed in this paper. This work also opens the posSibility for other applications of mathematical programming in the analysis of complex networks.

• 出版日期2015-9-1