Adjazenzmatrix / Bipartite Graphen

[Evora]

Guten Tag,

ich beschäftige mich seit einigen Tagen mit dem gleichen Problem, eventuell hat ja jemand von euch einen Tipp wie ich vorgehen kann.

Ich habe zwei Datenreihen (liste, array, ..) die ich miteinander "Matchen" möchte. Ziel ist es, dass der Mögliche zusammenhang dargestellt wird, also im Grunde die Geringsten Distanzen als Kante dargestellt werden. Mein ansatz war die ungarische Methode, welche ich in drei Datenbanken gefunden habe (scipy_optimize, hungarian_algorithm und munkres). Ich hatte eine Distanzmatrix der beiden normalisierten Datensätze erstellt, damit lässt sich das Matching jedoch nicht durchfürehn. Scipy_optimize und hungarian_algorithm fordern einen bipartiten Graphen oder eine entsprechende Matrix im Dateiformat Dict oder Array.

Ich habe festgestellt, dass NetworkX die Adjazenzmatrix und Bipartite Graphen abbildet und ebenfalls Matchings anbietet. Allerdings stellt sich mir die Frage, wie erzeuge ich denn eine Adjazenzmatrix ohne vorheriges Matching. Es macht für mich wenig Sinn, dass diese bereits als Eingangswert benötigt wird wenn ich doch genau diese Verknüpfungen mithilfe des Matchings ermitteln möchte. Man kann in NetworkX zwar das eine in das andere überführen, wie man die Adjazenzmatrix oder den Graphen erstellt habe ich jedoch bislang nicht herausgefunden.

Anbei ein Beispiel der Distanzmatrix wie ich sie aufgestellt hatte:

import pandas as pd
import numpy as np
from scipy.spatial import distance_matrix

list1 = [0.2, 0.3, 0.7, 0.9, 1.0]
list2 = [0.1, 0.3, 0.6, 0.8, 1.0]
df_list1 = pd.DataFrame(list1, columns = ['Number'])
df_list2 = pd.DataFrame(list2, columns = ['Number'])
Matrix= pd.DataFrame(distance_matrix(df_list1.values, df_list2.values), index=df_list1.index, columns=df_list2.index)
display(Matrix)



In der Adjazenzmatrix müsste ja jetzt theoretisch (vereinfacht) überall dort wo eine 0 oder 0,1 steht eine 1 eingetragen werden und sonst eine null. Das ist natürlich bei den Realdaten nicht ganz so offensichtlich.

[einfachTobi]

Hast du dir die entsprechende Stelle in der Doku über bipartite Graphen mal angesehen? https://networkx.org/documentation/stab ... rtite.html.

[Evora]

Ja das habe ich mir schon relativ oft angeschaut, leider werd ich nicht sonderlich klüger.

Ich hatte jetzt überlegt, da ein Matching die geringste entfernung suchen soll und ich mit der Distanzmatrix bereits geringe entfernungen habe einfach die min() Funktion darauf anzuwenden und die gefunden werte mit 1 zu ersetzen und entsprechend alle anderen werte mit 0. Somit hätte ich mir händisch eine art Adjazenzmatrix gebastelt.

Problem das ich jetzt wieder habe, die .min() Funktion lässt sich nur einmal auf die Matrix anwenden, danach gibt sie keine werte mehr aus. Weiß jemand woran das liegt? Gibt es dafür eine Lösung? Das war mein Ansatz:

liste_min1 = Matrix.min().to_frame() # Minimum aller Spalten als Dataframe

#Schleife um die in den 227 Spalten gefundenen Minimalwerte mit eins zu ersetzen
for i in range(0, 227):
Matrix = Matrix.replace([liste_min2['first']], '1')

Jetzt hab ich auhc meine Matrix mit je einer 1 pro Spalte, allerdings kann ich auf diese neue Matrix kein min() mehr anwenden, die Ausgabe bleibt immer leer