Journal article
Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree
Information processing letters, v 139, pp 53-59
01 Nov 2018
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. (C) 2018 Elsevier B.V. All rights reserved.
Metrics
15 Record Views
Details
- Title
- Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree
- Creators
- Jonathan Stokes - Drexel UniversitySteven Weber - Drexel University
- Publication Details
- Information processing letters, v 139, pp 53-59
- Publisher
- Elsevier
- Number of pages
- 7
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:000445992000011
- Scopus ID
- 2-s2.0-85050495839
- Other Identifier
- 991019167427804721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Information Systems