Eur. Phys. J. B (2012) 85: 151
https://doi.org/10.1140/epjb/e2012-20899-2

Regular Article

Do greedy assortativity optimization algorithms produce good results?^*

¹ Network Architecture and Services, Delft University of Technology, Faculty of EEMCS, 2628 CD Delft, Netherlands
² The Delft Bioinformatics Lab, Delft University of Technology, Faculty of EEMCS, 2628 CD Delft, Netherlands

^a e-mail: w.winterbach@tudelft.nl

Received: 3 November 2011
Received in final form: 27 February 2012
Published online: 16 May 2012

Abstract

We consider algorithms for generating networks that are extremal with respect to degree assortativity. Networks with maximized and minimized assortativities have been studied by other authors. In these cases, networks are rewired whilst maintaining their degree vectors. Although rewiring can be used to create networks with high or low assortativities, it is not known how close the results are to the true maximum or minimum assortativities achievable by networks with the same degree vectors. We introduce the first algorithm for computing a network with maximal or minimal assortativity on a given vector of valid node degrees. We compare the assortativity metrics of networks obtained by this algorithm to assortativity metrics of networks obtained by a greedy assortativity-maximization algorithm. The algorithms are applied to Erdős-Rényi networks, Barabàsi-Albert and a sample of real-world networks. We find that the number of rewirings considered by the greedy approach must scale with the number of links in order to ensure a good approximation.