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.
Rewiring. The meta-graph for a degree sequence, with a vertex for each connected simple graph with that degree sequence and an edge connecting graphs related by rewiring a pair of edges, was studied by Taylor @cite_17 ; in particular, he showed this meta-graph to be connected (Thm. 3.3) extending an earlier result by Rysler for simple graphs @cite_9 . This fact is used in rewiring .
@cite_9 @cite_17
2021903957 155825010
This paper is concerned with a matrix A of m rows and n columns, all of whose entries are 0’s and 1’s. Let the sum of row i of A be denoted by r i (i = 1, ... , m) and let the sum of column i of A be denoted by S i (i = 1, ... ,n). This paper investigates realizations of a given degree sequence, and the way in which they are related by switchings. The results are given in the context of simple graphs, multigraphs and pseudographs. We show that we can transform any connected graph to any other connected graph of the same degree sequence, by switchings wich are constrained to connected graphs. This is done for certain labelled graphs, the result for unlabelled graphs following as a corollary. The results are then extended to infinite degree sequences.