/ / Graph Giant Connected Component - Python, Netzwerk, Grafik, verbundene Komponenten

Graph Giant Connected Component - Python, Netzwerk, Grafik, verbundene Komponenten

Ich habe eine Matrix der Form

a b 8.0
a d 0.1
......

Die erste Spalte ist Knoten A, der zweite Knoten B und der dritteKorrelationskoeffizient Ich muss ein Programm machen, das eine Schwelle findet, also hat das angeschlossene Netzwerk eine Riesenverbindungskomponente, die aus 50-60% der gesamten Netzwerkknoten besteht. Ich habe ein Programm geschrieben, das eine binäre Suche nach dem Schwellenwert verwendet

if Giant Connected Component > 60% new threshold=oldthreshold + oldthreshold/2
if Giant Connected Component < 50% new threshold=oldthreshold - oldthreshold/2

Das Problem ist, dass Algorithmus auch nach Schwellenwerten> 1 und / oder <0 sucht. Wie kann ich damit umgehen? Oder gibt es eine bessere Idee, wie man es berechnet?

Antworten:

0 für die Antwort № 1

Der von Ihnen beschriebene Algorithmus ist keine binäre Suche.

Um die binäre Suche korrekt zu implementieren, sollten Sie zwei Werte verfolgen, min_threshold und max_threshold. Stellen Sie diese zunächst auf die minimal und maximal möglichen Schwellwerte ein. Dann bei jedem Schritt:

threshold = (min_threshold + max_threshold)/2
if GCC(threshold) > 60%:  # threshold is too low, update minimum
min_threshold = threshold
else if GCC(threshold) < 50%:  # threshold is too high, update maximum
max_threshold = threshold