Algebraische Vertex-Anordnung eines spärlichen Graphen für Adjazenzzugriffs Lokalität und Graphkompression

In dieser Arbeit stellen wir theoretische und praktische Verbindungen zwischen der Vertex-Indexierung für die Kompression spärlicher Graphen/Netze und der Matrixanordnung für die spärliche Matrix-Vektor-Multiplikation und Variableneliminierung her. Wir präsentieren eine fundamentale Analyse der Adjazenzzugriffs-Lokalität in der Vertex-Anordnung aus der Perspektive der Graphzusammensetzung oder -dekomposition in elementare kompakte Graphen. Wir führen einen algebraischen Indexierungsansatz ein, der die vorteilhaften Merkmale bestehender Methoden beibehält, deren Mängel mildert und sich an die Gradverteilung anpasst. Die neue Methode zeigt überlegene und vielseitige Leistung bei der Graphkompression über verschiedene Grapharten hinweg. Sie führt auch zu proportionalen Verbesserungen der Effizienz von Matrix-Vektor-Multiplikationen für Subraumiterationen als Reaktion auf zufällige Suchanfragen in einem großen Netzwerk.