Big Graph im Speicher

Question

Ich möchte alle verwendeten Ports in großen Pcaps aufzeichnen. Es sind 65535 Ports verfügbar und jeder Port kann jeden Port miteinander kommunizieren: 65535 x 65535 Links insgesamt

Die Matrix wird sehr spärlich sein (viele 0 Einträge). Außerdem denke ich, dass die Kanten nicht gerichtet werden müssen, daher kann Port1-> Port2 zu Port2-> Port1 hinzugefügt werden (was unsere Anzahl der Werte auf 65535 * 65536/2 reduziert). Wie würden Sie dies mit Python speichern? In numpiger? Wie hoch ist der geschätzte Speicherbedarf?

Danach möchte ich die größte Summe für einen Port finden und pop() es (die ganze Zeile und Spalte während). Das heißt, ich möchte z.B. Port1 wurde 500 Mal verwendet (100 Mal von Port2 nach Port1, 300 Mal von Port3 nach Port1, Port4 nach Port1 100 Mal) ...

Grafisch gesprochen möchte ich 65535 Knoten haben, die miteinander verbunden werden können. Dann möchte ich den Knoten finden, der an verbundenen Kanten die höchste Summe von Werten hat. Danach möchte ich den Knoten knacken (und die entsprechenden Kanten löschen, was die Summe der anderen Knoten verringert).

Danke!

Answer 1

In Python, und je nachdem, wie spärlich spärlich ist, wird ein dict-of-dicts recht gut damit umgehen.

connections = { ..., 8080: { 4545:17, 20151:3, ...}, ...} 

Wenn ich verstanden habe, was Sie richtig machen, dann ist die Anzahl der Verbindungen zu Port p

count = sum(connections[8080].values()) 

Entfernen Port p

del connections[p] 
for conn in connections.values(): # edit, bug fixed. 
    if p in conn: 
     del conn[p] 

Wenn Sie versuchen wollen Speicher sparen, indem nur die Hälfte der Paare gespeichert wird, dann leidet die Einfachheit stark.

Answer 2

Schauen Sie in die Adjazenzliste-Darstellung von Graph, es wird höchstwahrscheinlich Ihren Bedürfnissen entsprechen.

Allerdings ist ein Graph mit 65535 Vertices nicht so groß. Auch wenn Sie es nicht mit einer einfachen Matrix darstellen können.

Der Speicherverbrauch ist O (E + V) mit V Anzahl der Scheitelpunkte (65535) und E Anzahl der Kanten (auf einem dünnen Graphen hat es die gleiche Größenordnung als V).