Waldorp, Lourens J.; Schmittmann, Verena D. Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming. (English) Zbl 1343.05143 J. Appl. Math. 2015, Article ID 580361, 9 p. (2015). Summary: Calculation of assortative mixing by degree in networks indicates whether nodes with similar degree are connected to each other. In networks with scale-free distribution high values of assortative mixing by degree can be an indication of a hub-like core in networks. Degree correlation has generally been used to measure assortative mixing of a network. But it has been shown that degree correlation cannot always distinguish properly between different networks with nodes that have the same degrees. The so-called \(s\)-metric has been shown to be a better choice to calculate assortative mixing. The \(s\)-metric is normalized with respect to the class of networks without self-loops, multiple edges, and multiple components, while degree correlation is always normalized with respect to unrestricted networks, where self-loops, multiple edges, and multiple components are allowed. The challenge in computing the normalized \(s\)-metric is in obtaining the minimum and maximum value within a specific class of networks. We show that this can be solved by using linear programming. We use Lagrangian relaxation and the subgradient algorithm to obtain a solution to the \(s\)-metric problem. Several examples are given to illustrate the principles and some simulations indicate that the solutions are generally accurate. MSC: 05C82 Small world graphs, complex networks (graph-theoretic aspects) 05C07 Vertex degrees 90C05 Linear programming 90B10 Deterministic network models in operations research Keywords:Lagrangian relaxation; subgradient algorithm Software:R; lpSolve PDFBibTeX XMLCite \textit{L. J. Waldorp} and \textit{V. D. Schmittmann}, J. Appl. Math. 2015, Article ID 580361, 9 p. (2015; Zbl 1343.05143) Full Text: DOI References: [1] Newman, M. E. J., Assortative mixing in networks, Physical Review Letters, 89, 20 (2002) [2] van Mieghem, P.; Wang, H.; Ge, X.; Tang, S.; Kuipers, F. A., Influence of assortativity and degree-preserving rewiring on the spectra of networks, The European Physical Journal B, 76, 4, 643-652 (2010) · Zbl 1202.05131 [3] Piraveenan, M.; Prokopenko, M.; Zomaya, A. Y., Classifying complex networks using unbiased local assortativity, Proceedings of the Alife 12th Conference [4] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223 [5] Barrat, A.; Barthelemy, M.; Vespignani, A., Dynamical Processes on Complex Networks (2008), Cambridge University Press · Zbl 1198.90005 [6] Borsboom, D.; Cramer, A. O. J.; Schmittmann, V. D.; Epskamp, S.; Waldorp, L. J., The small world of psychopathology, PLoS ONE, 6, 11 (2011) [7] Li, L.; Alderson, D.; Doyle, J. C.; Willinger, W., Towards a theory of scale-free graphs: definition, properties, and implications, Internet Mathematics, 2, 4, 431-523 (2005) · Zbl 1103.05082 [8] Alderson, D. L.; Li, L., Diversity of graphs with highly variable connectivity, Physical Review E, 75, 4 (2007) [9] Li, L.; Alderson, D.; Willinger, W.; Doyle, J., A first-principles approach to understanding the internet’s router-level topology, Proceedings of the 2004 Conference On Applications, Technologies, Architectures, And Protocols For Computer Communications (SIGCOMM ’04), ACM [10] Schrijver, A., Theory of Linear and Integer Programming. Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics (1986), Chichester, UK: John Wiley & Sons, Chichester, UK · Zbl 0665.90063 [11] Nemhauser, G.; Wolsey, L., Integer and Combinatorial Optimization (1999), John Wiley & Sons · Zbl 0944.90001 [12] Boyd, S., The subtour polytope of the travelling salesman problem [Ph.D. thesis] (1986), University of Waterloo · Zbl 0726.90086 [13] Held, M.; Karp, R. M., The traveling-salesman problem and minimum spanning trees, Operations Research, 18, 6, 1138-1162 (1970) · Zbl 0226.90047 [14] Piraveenan, M.; Prokopenko, M.; Zomaya, A. Y., Local assortativity and growth of Internet, European Physical Journal B—Condensed Matter and Complex Systems, 70, 2, 275-285 (2009) [15] Bertsimas, D.; Tsitsklis, J., Introduction to Linear Optimization (1997), Belmont, Mass, USA: Athena Scientific and Dynamic Ideas, Belmont, Mass, USA [16] Krumke, S. [17] Schrijver, A., Polyhedral proof methods in combinatorial optimization, Discrete Applied Mathematics, 14, 2, 111-133 (1986) · Zbl 0602.90111 [18] Fisher, M. L., The lagrangian relaxation method for solving integer programming problems, Management Science, 50, 12, 1861-1874 (2004) [19] Boyd, S.; Elliott-Magwood, P.; Iwata, S., Structure of the extreme points of the subtour elimination problem of the stsp, Combinatorial Optimization and Discrete Algorithms, 33-47 (2010) · Zbl 1223.90050 [20] Magnus, J. R.; Neudecker, H., Matrix Differential Calculus with Applications in Statistics and Econometrics. Matrix Differential Calculus with Applications in Statistics and Econometrics, Wiley Series in Probability and Statistics (1999), Chichester, UK: John Wiley & Sons, Chichester, UK · Zbl 0912.15003 [21] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Mathematical Programming, 6, 62-88 (1974) · Zbl 0284.90057 [22] Held, M.; Karp, R. M., The traveling-salesman problem and minimum spanning trees. Part II, Mathematical Programming, 1, 1, 6-25 (1971) · Zbl 0232.90038 [23] R Development Core Team, R: A Language and Environment for Statistical Computing (2012), Vienna, Austria: R Foundation for Statistical Computing, Vienna, Austria [24] Berkelaar, M.; Eikland, K.; Notebaert, P., lpsolve: Open Source (Mixedinteger) Linear Programming System (2004), GNU Lesser General Public License [25] Cramer, A. O. J.; Waldorp, L. J.; van der Maas, H. L. J.; Borsboom, D., Comorbidity: a network perspective, Behavioral and Brain Sciences, 33, 2-3, 137-150 (2010) 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.