Was ist der effizienteste Weg, um eine sehr spärliche Netzwerkmatrix in Julia zu definieren?

Question

Ich habe die Daten für ein sehr großes Netzwerk, das ziemlich spärlich ist. Ich habe mich gefragt, was die speicherfreundlichste Möglichkeit wäre, um zu speichern und am einfachsten zu erreichen, ob zwei Knoten verbunden sind.

Offensichtlich mit N Knoten, ist in Bezug auf Raum nicht so effizient eine N * N Matrix hält I speichern. Also dachte ich vielleicht wie unten die Adjazenzliste halten:

Array(Vector{Int64}, N_tmp) 

Wo N_tmp < = N, wie viele Knoten keine Verbindungen aufweisen.

Können Sie mir helfen, ob es bessere Möglichkeiten gibt, oder vielleicht Pakete, die in Bezug auf Speicher und Zugriff besser sind?

Answer 1

In LightGraphs.jl verwenden wir Adjazenzlisten (im Grunde ein Vektor von Vektoren), um Nachbarn für jeden Knoten zu speichern. Dies bietet eine sehr gute Speichernutzung für große, spärliche Graphen, was uns ermöglicht, auf Hunderte von Millionen von Knoten auf Standardhardware zu skalieren, während ein schneller Zugriff bereitgestellt wird, der die native Matrixstruktur für die meisten Graphenoperationen übertrifft.

Man könnte überlegen, ob LightGraphs direkt Ihren Bedürfnissen gerecht wird.

Bearbeiten mit zusätzlichen Informationen: speichern wir eine sortierte Liste von Nachbarn - das gibt uns eine Performance-Einbußen auf der Kante Schöpfung, sondern macht es viel schneller nachfolgende Lookups zu tun.