Abstract We examine two greedy heuristics — wiring and rewiring — for constructing maximum assortative graphs over all simple connected graphs with a target degree sequence. Counterexamples show that natural greedy rewiring heuristics do not necessarily return a maximum assortative graph, even though it is known that the meta-graph of all simple connected graphs with given degree is connected under rewiring. Counterexamples show an elegant greedy graph wiring heuristic from the literature may fail to achieve the target degree sequence or may fail to wire a maximally assortative graph.
Wiring. Li and Alderson @cite_15 introduced a greedy wiring heuristic for constructing a graph with maximum assortativity over the set of simple connected graphs with a target degree sequence. Kincaid @cite_12 argues wiring a minimally or maximally assortative connected simple graph is NP-hard and proposes a heuristic which is shown numerically to perform near optimally in minimizing graph assortativity. Winterbach @cite_4 , Zhou @cite_8 , and Meghanathan @cite_7 have also proposed methods unconstrained by graph connectivity of wiring maximally assortative graphs. This paper examines Li's heuristic further in wiring .
@cite_4 @cite_7 @cite_8 @cite_15 @cite_12
2140214099 2184540354 2000092045 1987236914 2338515455
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-Renyi networks, Barabasi-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. We define the problem of maximal assortativity matching (MAM) for a complex network graph as the problem of maximizing the similarity of the end vertices (with respect to some measure of node weight) constituting the matching. In this pursuit, we introduce a metric called the assortativity weight of an edge, defined as the product of the number of uncovered adjacent edges and the absolute value of the difference in the weights of the end vertices. The MAM algorithm prefers to include edges that have the smallest assortativity weight in each iteration (one edge per iteration) until all edges are covered. The MAM algorithm can also be adapted to determine a maximal dissortative matching (MDM) to maximize the dissimilarity between the end vertices that are part of a matching as well as to determine a maximal node matching (MNM) that simply maximizes the number of vertices that are part of the matching. We run the MAM, MNM and MDM algorithms on real-world network graphs as well as on the theoretical model-based random network graphs and scale-free network graphs and analyze the tradeoffs between the of node matches and assortativity index (targeted optimal values: 1 for MAM and -1 for MDM). Recently, the assortative mixing of complex networks has received much attention partly because of its significance in various social networks. In this paper, a new scheme to generate an assortative growth network with given degree distribution is presented using a Monte Carlo sampling method. Since the degrees of a great number of real-life networks obey either power-law or Poisson distribution, we employ these two distributions to grow our models. The models generated by this method exhibit interesting characteristics such as high average path length, high clustering coefficient and strong rich-club effects. There is a large, popular, and growing literature on "scale-free" networks with the Internet along with metabolic networks representing perhaps the canonical examples. While this has in many ways reinvigorated graph theory, there is unfortunately no consistent, precise definition of scale-free graphs and few rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and that the most celebrated claims regarding the Internet and biology are verifiably false. In this paper, we introduce a structural metric that allows us to differentiate between all simple, connected graphs having an identical degree sequence, which is of particular interest when that sequence satisfies a power law relationship. We demonstrate that the proposed structural metric yields considerable insight into the claimed properties of SF graphs and provides one possible measure of the extent to which a graph is scale-free. This structural view can be related t...