×

Mathematical programming approaches for classes of random network problems. (English) Zbl 1346.90209

Summary: 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.

MSC:

90B10 Deterministic network models in operations research
05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
90C35 Programming involving graphs or networks
90C10 Integer programming
90C51 Interior-point methods

Software:

IPM
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abraham, R.; Robbin, J., Transversal mappings and flows (1967), W. A. Benjamin, Inc: W. A. Benjamin, Inc New York-Amsterdam · Zbl 0171.44404
[2] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows: Theory, algorithms, and applications (1991), Prentice-Hall, Inc: Prentice-Hall, Inc Englewood Cliffs
[3] Berghammer, R.; Rusinowska, A.; de Swart, H., Applying relation algebra and review to measures in a social network, European Journal of Operational Research, 202, 182-195 (2010) · Zbl 1173.91446
[4] Bollobas, B., Random graphs (1985), Cambridge University Press · Zbl 0567.05042
[5] Castro, J., A specialized interior-point algorithm for multicommodity network flows, SIAM Journal on Optimization, 10, 852-877 (2000) · Zbl 0955.90087
[6] Castro, J., An interior-point approach for primal block-angular problems, Computational Optimization and Applications, 36, 195-219 (2007) · Zbl 1148.90351
[7] Castro, J.; Cuesta, J., Quadratic regularizations in an interior-point method for primal block-angular problems, Mathematical Programming, 130, 415-445 (2011) · Zbl 1229.90086
[8] Charon, I.; Germa, A.; Hudry, O., Random generation of tournaments and asymmetric graphs with given out-degrees, European Journal of Operational Research, 95, 411-419 (1996) · Zbl 0974.05502
[9] Conejo, A. J.; Castillo, E.; Minguez, R.; Garcia-Bertrand, R., Decomposition techniques in mathematical programming. Engineering and science applications (2006), Springer · Zbl 1186.90002
[10] Erdös, P.; Rainyi, A., On random graphs, Publicationes Mathematicae, 6, 290-297 (1959) · Zbl 0092.15705
[11] Fremlin, D. H., Measure theory, vol. 2 (2010), Torres Fremlin · Zbl 1225.28012
[12] Gómez, D.; Figueira, J. R.; Eusébio, A., Modeling centrality measures in social network analysis using bi-criteria network flow optimization problems, European Journal of Operational Research, 95, 354-365 (2013) · Zbl 1292.91149
[13] Granovetter, M., Economic action and social structure: The problem of embeddedness, American Journal of Sociology, 91, 481-510 (1985)
[14] Heller, I.; Tompkins, C. B., An extension of a theorem of Dantzig’s, (Kuhn, K.; Tucker, A., Linear inequalities and related systems (1956), Princeton University Press: Princeton University Press Princeton), 247-252 · Zbl 0072.37804
[15] Kapferer, B., Strategy and transaction in an African factory (1972), Manchester University Press
[16] Lusseau, D., The emergent properties of a dolphin social network, Proceedings of the Royal Society of London Series B: Biological Sciences, 270, 186-188 (2003)
[17] Lusseau, D., Identifying the role that individual animals play in their social network, Proceedings of the Royal Society of London Series B: Biological Sciences, 271, 477-481 (2004)
[18] Newman, M. E.J., Random graphs as models of networks, Working Papers 02-04-020 (2002), Santa Fe Institute · Zbl 1001.68931
[19] Newman, M. E.J., Detecting community structure in networks, The European Physical Journal B, 38, 321-330 (2004)
[20] Newman, M. E.J.; Park, J., Why social networks are different from other types of networks, Physical Review E, 68, 036122 (2003)
[21] Newman, M. E.J.; Strogatz, S. H.; Watts, D. J., Random graphs with arbitrary degree distributions and their applications, Physical Review E, 64, 026118 (2001)
[22] Padberg, M., Linear optimization and extensions (1999), Springer: Springer New York · Zbl 0926.90068
[23] Pevzner, A., DNA physical mapping and alternating Eulerian cycles in colored graphs, Algorithmica, 13, 77-105 (1995) · Zbl 0840.92011
[24] Rao, A.; Jana, R.; Bandyopadhyay, S., A Markov chain Monte Carlo method for generating random (0,1) matrices with given marginals, Sankhya, Series A, 58, 225-242 (1996) · Zbl 0901.60047
[25] Robert, C.; Casella, G., Monte Carlo statistical methods (2004), Springer · Zbl 1096.62003
[26] Roberts, J. M., Simple methods for simulating sociomatrices with given marginal totals, Social Networks, 22, 273-283 (2000)
[27] Ryser, H. J., Combinatorial properties of matrices of zeros and ones, Canadian Journal of Mathematics, 9, 371-377 (1957) · Zbl 0079.01102
[28] Schrijver, A., Theory of linear and integer programming (1998), Wiley · Zbl 0970.90052
[29] Snijders, T. A.B., Enumeration and simulation methods for 0-1 matrices with given marginals, Psychometrika, 56, 397-417 (1991) · Zbl 0850.05002
[30] Sternberg, S., Lectures on differential geometry (1964), Englewood Cliffs, NJ: Englewood Cliffs, NJ Prentice-Hall · Zbl 0129.13102
[31] Verhelst, N. D., An efficient MCMC algorithm to sample binary matrices with fixed marginals, Psychometrika, 73, 4, 705-728 (2008) · Zbl 1284.62757
[32] Wasserman, S.; Faust, K., Social network analysis: Methods and applications (1994), Cambridge University Press
[33] Wright, S. J., Primal-dual interior-point methods (1996), SIAM
[34] Ye, Y., Interior point algorithms. Theory and analysis (1997), Wiley · Zbl 0943.90070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.