Katalog der Spanner Graph-Algorithmen

Vorabversion – Spanner Graph-Algorithmen

Diese Funktion unterliegt den „Bedingungen für Pre-GA-Angebote“ im Abschnitt „Allgemeine Dienstbedingungen“ der dienstspezifischen Nutzungsbedingungen. Pre-GA‑Funktionen stehen in der vorliegenden Form zur Verfügung und bieten möglicherweise nur eingeschränkten Support. Weitere Informationen finden Sie unter den Beschreibungen der Startphase.

Hinweis: Diese Funktion ist in der Spanner Enterprise-Version und Enterprise Plus-Version verfügbar. Weitere Informationen finden Sie in der Übersicht über Spanner-Versionen.

Spanner Graph bietet in enger Zusammenarbeit mit Google Research Graph Mining eine Reihe von Algorithmen, die die Anforderungen an die Graphenanalyse für die folgenden Anwendungsfälle abdecken:

• Zentralität
• Clustering
• Ähnlichkeit
• Pfadsuche

Zentralität

Zentralitätsalgorithmen ordnen Knoten nach ihrer strukturellen Bedeutung innerhalb eines Graphen ein. Sie können damit betrügerische Konten im Fintech-Bereich, Influencer in sozialen Netzwerken, kritische Router in Telekommunikationsnetzwerken und mehr identifizieren.

PageRank

PageRank bewertet Knoten nach Wichtigkeit. Ein Knoten gilt als wichtiger, wenn viele andere wichtige Knoten darauf verweisen. Der Algorithmus simuliert einen Random Walk durch den Graphen. Knoten, die bei diesem Walk häufiger besucht werden, gelten als wichtiger. Weitere Informationen zum Algorithmus finden Sie unter PageRank.

Funktionssignatur

PageRank(input_parameters) YIELD node, score

Eingabeparameter

Alle häufig verwendeten Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
source_nodes	Array von Graphknoten	Nein	(keine)	Falls vorhanden, Quelle für personalisierten PageRank.
damping_factor	FLOAT64	Nein	0,85	Die Wahrscheinlichkeit, dass der Algorithmus bei einer bestimmten Iteration eine der ausgehenden Kanten des aktuellen Knotens durchläuft. Der Wert muss im Bereich von [0, 1) liegen.
max_iterations	INT64	Nein	10	Die maximale Anzahl von Iterationen des Algorithmus. Muss positiv sein. Eine höhere Anzahl von Iterationen führt in der Regel zu genaueren Ergebnissen, allerdings auf Kosten einer längeren Laufzeit.
approx_precision	FLOAT64	Nein	1e-2	Schwellenwert für die Approximationsgenauigkeit für den Algorithmus. Darf nicht negativ sein. Kleinere Werte führen in der Regel zu genaueren Ergebnissen, allerdings auf Kosten einer längeren Laufzeit.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Diagramm.
Punktzahl	FLOAT64	Der PageRank-Wert des Knotens.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/my-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL PageRank(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    source_nodes => ARRAY {
                      MATCH (n:Account {id:7})
                      RETURN n
                    }
  ) YIELD node, score
RETURN node.id, score;

BetweennessCentrality

BetweennessCentrality misst, wie oft ein Knoten auf den kürzesten Pfaden zwischen anderen Knotenpaaren liegt. Knoten mit hoher Zwischenzentralität fungieren oft als wichtige Brücken, die verschiedene Teile des Graphen verbinden. Weitere Informationen zum Algorithmus finden Sie unter Betweenness Centrality.

Funktionssignatur

BetweennessCentrality(input_parameters) YIELD node, score

Eingabeparameter

Alle häufig verwendeten Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
num_source_nodes	INT64	Nein	(keine)	Wenn festgelegt, muss der Wert positiv sein. Er gibt an, wie viele Quellknoten der Algorithmus für die Berechnung der ungefähren Betweenness-Zentralität auswählen soll. Wenn nicht festgelegt oder auf eine Zahl festgelegt, die größer als die Anzahl der Knoten im Graphen ist, werden alle Knoten als Quellknoten verwendet. Das bedeutet, dass der Algorithmus die genauen Betweenness-Zentralitäten berechnet. Höhere Werte führen zu besseren Schätzungen, aber auch zu längeren Laufzeiten.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Graphen.
Punktzahl	FLOAT64	Der Zentralitätswert des Knotens.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/my-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL BetweennessCentrality(
    node_labels => ['Account'], edge_labels => ['Transfers'], num_source_nodes => 5
  ) YIELD node, score
RETURN node.id, score;

ClosenessCentrality

ClosenessCentrality misst, wie nah ein Knoten an allen anderen Knoten im Diagramm ist. Knoten mit hoher Closeness-Zentralität können andere Knoten über kürzere Pfade erreichen. Weitere Informationen zum Algorithmus finden Sie unter Closeness Centrality.

Funktionssignatur

ClosenessCentrality(input_parameters) YIELD node, score

Eingabeparameter

Alle allgemeinen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
Modus	STRING	Nein	EXACT	Der Algorithmusmodus. Unterstützte Werte sind EXACT und HYBRID.
use_wasserman_faust	BOOL	Nein	FALSE	Wenn false, werden Standard-Nähe-Zentralitäten berechnet. Wenn true, werden die Wasserman-Faust-Nähezentralitäten berechnet.
Epsilon	FLOAT64	Nein	0,1	Wird nur für den HYBRID-Algorithmus verwendet. Muss im Bereich (0,0, 1,0) liegen. Kleinere Werte bedeuten im Allgemeinen eine höhere Genauigkeit. Größere Werte ermöglichen in der Regel eine schnellere Ausführung des Algorithmus.
sample_size	INT64	Nein	0	Wird nur für den HYBRID-Algorithmus verwendet. Die Anzahl der Pivot-Knoten, die für die ungefähre Berechnung der Zentralitätswerte verwendet werden sollen. Muss nicht negativ sein. Wenn nicht festgelegt oder null, wird der Standardwert min(100 * ln(N), N) verwendet, wobei N die Knotenzahl des Eingabegraphen ist.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Diagramm.
Punktzahl	FLOAT64	Der Closeness-Zentralitätswert des Knotens.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/my-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL ClosenessCentrality(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    mode => 'EXACT'
  ) YIELD node, score
RETURN node.id, score;

Clustering

Clustering-Algorithmen gruppieren Knoten in Clustern (auch als Communities bezeichnet), sodass Knoten innerhalb jedes Clusters dichter miteinander verbunden sind als mit Knoten in anderen Clustern. Das ist nützlich, um potenzielle Betrugsringe im Fintech-Bereich zu erkennen, Kundensegmentierungen im Einzelhandel zu identifizieren und vieles mehr.

WeaklyConnectedComponents

WeaklyConnectedComponents findet disjunkte Knotengruppen, sodass jeder Knoten in einer Gruppe von jedem anderen Knoten in derselben Gruppe erreichbar ist, aber nicht von Knoten in anderen Gruppen. Weitere Informationen zum Algorithmus finden Sie unter Verbundene Komponenten.

Funktionssignatur

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

Eingabeparameter

Alle häufig verwendeten Eingabeparameter.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Graphen.
Cluster	INT64	Die ID der verbundenen Komponente/des Clusters, zu dem der Knoten gehört. Im Bereich [0, N), wobei N die Anzahl der Knoten im Diagramm ist.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/wcc-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL WeaklyConnectedComponents(
    node_labels => ['Account'], edge_labels => ['Transfers']
  ) YIELD node, cluster
RETURN node.id, cluster;

ModularityClustering

Mit ModularityClustering wird der Graph in Cluster unterteilt, indem die Modularität optimiert wird. Das ist ein Qualitätsmaß für die Dichte der Verbindungen innerhalb von Clustern im Vergleich zu einem zufälligen Netzwerk. Weitere Informationen zum Algorithmus finden Sie unter Modularity Clustering.

Funktionssignatur

ModularityClustering(input_parameters) YIELD node, cluster

Eingabeparameter

Alle allgemeinen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
resolution	FLOAT64	Nein	1,0	Steuert den Detaillierungsgrad des Clusterings. Muss endlich und nicht negativ sein. Kleinere Auflösungswerte führen in der Regel zu größeren Clustern. Typische Werte liegen im Bereich [0,5, 5]. Wenn die Auflösung null ist, findet der Algorithmus (mit einer ausreichenden Anzahl von Iterationen) die verbundenen Komponenten des Graphen (Kanten mit dem Gewicht null werden ignoriert).
max_iterations	INT64	Nein	10	Maximale Anzahl der äußeren Iterationen des Algorithmus. Muss positiv sein. Größere Werte führen in der Regel zu qualitativ hochwertigeren Clustern, allerdings auf Kosten einer längeren Laufzeit.
max_inner_iterations	INT64	Nein	10	Maximale Anzahl der inneren Iterationen des Algorithmus. Muss positiv sein. Größere Werte führen in der Regel zu einer höheren Qualität der Clusterung, allerdings auf Kosten einer längeren Laufzeit.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Graphen.
Cluster	INT64	Die ID der Community/des Clusters, zu dem der Knoten gehört. Im Bereich [0, N), wobei N die Anzahl der Knoten im Diagramm ist.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/modularity-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL ModularityClustering(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    resolution => 1.0, max_iterations => 10
  ) YIELD node, cluster
RETURN node.id, cluster;

CorrelationClustering

Bei CorrelationClustering werden Knoten basierend auf ihrer paarweisen Ähnlichkeit oder Unähnlichkeit partitioniert. Ziel ist es, ähnliche Knoten zu gruppieren und unähnliche Knoten zu trennen. Weitere Informationen zum Algorithmus finden Sie unter Korrelations-Clustering.

Funktionssignatur

CorrelationClustering(input_parameters) YIELD node, cluster

Eingabeparameter

Alle allgemeinen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
resolution	FLOAT64	Ja	(keine)	Steuert den Detaillierungsgrad des Clusterings. Muss explizit vom Kunden definiert werden. Muss endlich und nicht negativ sein. Kleinere Werte führen in der Regel zu größeren Clustern. Wenn die Auflösung null ist und alle Kantengewichtungen positiv sind, findet der Algorithmus (mit einer ausreichenden Anzahl von Iterationen) die verbundenen Komponenten des Graphen.
max_iterations	INT64	Nein	10	Maximale Anzahl der äußeren Iterationen des Algorithmus. Muss positiv sein. Größere Werte führen in der Regel zu qualitativ hochwertigeren Clustern, allerdings auf Kosten einer längeren Laufzeit.
max_inner_iterations	INT64	Nein	10	Maximale Anzahl der inneren Iterationen des Algorithmus. Muss positiv sein. Größere Werte führen in der Regel zu einer höheren Qualität der Clusterung, allerdings auf Kosten einer längeren Laufzeit.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Diagramm.
Cluster	INT64	Die ID der Community/des Clusters, zu dem der Knoten gehört. Im Bereich [0, N), wobei N die Anzahl der Knoten im Diagramm ist.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/correlation-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL CorrelationClustering(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    resolution => 0.5
  ) YIELD node, cluster
RETURN node.id, cluster;

LabelPropagation

LabelPropagation weist Knoten mithilfe einer Labelweitergabe-Technik Clustern zu. Dabei wird von einer anfänglichen Labelerstellung ausgegangen, die möglicherweise Seed-Labels aus der Eingabe verwendet. Da Knoten das Label, das von der Mehrheit ihrer Nachbarn geteilt wird, iterativ übernehmen, konvergieren dicht vernetzte Gruppen zu einem Konsenslabel und bilden Communities. Weitere Informationen zum Algorithmus finden Sie unter Labelweitergabe.

Funktionssignatur

LabelPropagation(input_parameters) YIELD node, cluster

Eingabeparameter

Alle allgemeinen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
seed_label_property	STRING	Nein	(keine)	Der Name des Knotenattributs für das Seed-Label.
max_iterations	INT64	Nein	10	Die maximale Anzahl von Iterationen der Label-Weitergabe, die der Algorithmus ausführt. Muss endlich und positiv sein.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Graphen.
Cluster	INT64	Die weitergegebene Cluster-/Label-ID des Knotens.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/lp-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL LabelPropagation(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    max_iterations => 10
  ) YIELD node, cluster
RETURN node.id, cluster;

CliqueFinding

CliqueFinding identifiziert potenziell überlappende dichte Communities, die einen Mindestdichteschwellenwert erfüllen, sodass jede Clique (eine Gruppe von Knoten, bei der jeder Knoten mit jedem anderen Knoten verbunden ist) in mindestens einem Cluster enthalten ist. Weitere Informationen zum Algorithmus finden Sie unter Clique-Aggregator.

Funktionssignatur

CliqueFinding(input_parameters) YIELD node, clique

Hinweis: Im Gegensatz zu den meisten Algorithmen kann es für denselben Knoten mehrere Zeilen geben, da ein Knoten Teil mehrerer Cliquen sein kann.

Eingabeparameter

Alle allgemeinen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
min_density	FLOAT64	Nein	0,9	Die Mindestdichte der zurückzugebenden Cluster. Muss im Bereich [0, 1] liegen.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Graphen.
Clique	INT64	Die ID der Clique, zu der der Knoten gehört.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/clique-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL CliqueFinding(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    min_density => 0.9
  ) YIELD node, clique
RETURN node.id, clique;

Ähnlichkeit

Ähnlichkeitsalgorithmen quantifizieren, wie ähnlich sich Knotenpaare auf Grundlage der Struktur ihrer Nachbarschaften sind. Dies ist nützlich, um fehlende Kanten zwischen Knoten für die Entitätsauflösung, Empfehlungen und mehr abzuleiten.

Spanner Graph unterstützt die folgenden paarweisen Knotenähnlichkeiten, bei denen Ähnlichkeitswerte basierend auf den Nachbarschaften der Knoten berechnet werden.

• JaccardSimilarity: Basierend auf dem Verhältnis der gemeinsamen Nachbarn zu den Gesamtnachbarn
• CosineSimilarity: Basierend auf Kantengewichten gemeinsamer Nachbarn
• CommonNeighborsSimilarity: Basierend auf der Anzahl der gemeinsamen Nachbarn
• TotalNeighborsSimilarity: Basierend auf der Anzahl der Nachbarn von mindestens einem der beiden Knoten

Weitere Informationen zum Algorithmus finden Sie unter Paarweise Knotenähnlichkeit.

Diese vier Algorithmen haben dieselben Argumente und dieselbe Ausgabestruktur.

Funktionssignatur

[JaccardSimilarity|CosineSimilarity|CommonNeighborsSimilarity|TotalNeighborsSimilarity](input_parameters) YIELD source_node, target_node, similarity

Eingabeparameter

Alle häufig verwendeten Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
source_nodes	Array von Graphknoten	Ja	–	Die Quellknoten für die paarweise Ähnlichkeitsberechnung.
target_nodes	Array von Graphknoten	Ja	–	Die Zielknoten für die paarweise Ähnlichkeitsberechnung.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
source_node	GRAPH_ELEMENT (Knoten)	Der Quellknoten, der in der Ähnlichkeitsberechnung verwendet wird.
target_node	GRAPH_ELEMENT (Knoten)	Der Zielknoten, der für die Ähnlichkeitsberechnung verwendet wird.
Ähnlichkeit	FLOAT64	Der berechnete Ähnlichkeitswert zwischen Quell- und Zielknoten.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/jaccard-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL JaccardSimilarity(
    source_nodes => ARRAY {
                      MATCH (n:Account {id: 7})
                      RETURN n
                    },
    target_nodes => ARRAY {
                      MATCH (n:Account)
                      WHERE n.id != 7
                      RETURN n
                    }
  ) YIELD source_node, target_node, similarity
RETURN source_node.id AS source_id, target_node.id AS target_id, similarity;

Pfadsuche

Pfadfindungsalgorithmen berechnen optimale Routen zwischen Knoten. Dies ist nützlich, um die günstigste Route in Lieferketten zu ermitteln, die Anfälligkeit in der Cybersicherheit zu bewerten und vieles mehr.

ShortestPath

ShortestPath berechnet die kürzesten Pfade zwischen einer bestimmten Gruppe von Quellknoten und einer bestimmten Gruppe von Zielknoten. Weitere Informationen zum Algorithmus finden Sie unter Kürzeste Pfade zwischen mehreren Punkten.

Funktionssignatur

ShortestPath(input_parameters) YIELD source_node, target_node, path, cost

Eingabeparameter

Alle allgemeinen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
source_nodes	Array von Graphknoten	Ja	–	Die Quellknoten für die Berechnung des kürzesten Pfads.
target_nodes	Array von Graphknoten	Ja	–	Die Zielknoten für die Berechnung des kürzesten Pfads.

Ausgabe

Funktionsergebnisse:

Name	Typ	Beschreibung
source_node	GRAPH_ELEMENT (Knoten)	Der Quellknoten des Pfads.
target_node	GRAPH_ELEMENT (Knoten)	Der Zielknoten des Pfads.
Pfad	GRAPH_PATH	Die kürzeste gefundene Route.
Kosten	FLOAT64	Die Kosten des kürzesten Pfads.

Beispiel

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/shortest-path-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL ShortestPath(
    source_nodes => ARRAY {
                      MATCH (n:Account {id: 7})
                      RETURN n
                    },
    target_nodes => ARRAY {
                      MATCH (n:Account {id: 16})
                      RETURN n
                    }
  ) YIELD source_node, target_node, path, cost
RETURN source_node.id AS source_id, target_node.id AS target_id, PATH_LENGTH(path) AS length, cost;

Nächste Schritte

• Spanner Graph-Algorithmen ausführen
• Anforderungen an das Schema für Spanner Graph-Algorithmen und Kompatibilität von Funktionen.
• Best Practices für Spanner Graph-Algorithmen