Optimization Online


Exploiting total unimodularity for classes of random network problems

Jordi Castro(jordi.castro***at***upc.edu)
Stefano Nasini(stefano.nasini***at***upc.edu)

Abstract: Network analysis is of great interest for the study of social, biological and technological networks, with applications, among others, in business, marketing, epidemiology and telecommunications. Researchers are often interested in assessing whether an observed feature in some particular network 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 polynomial time 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.

Keywords: Integer Programming ; Linear Programming ; Total unimodularity ; Interior-Point Methods ; Complex Networks ; Social networks analysis

Category 1: Integer Programming

Category 2: Network Optimization

Category 3: Applications -- Science and Engineering

Citation: J. Castro, S. Nasini, Exploiting total unimodularity for classes of random network problems, Research Report DR 2013/01, Dept. of Statistics and Operations Research, Universitat Polit├Ęcnica de Catalunya, 2013.

Download: [PDF]

Entry Submitted: 07/19/2013
Entry Accepted: 07/19/2013
Entry Last Modified: 07/19/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society