Katalog der Spanner Graph-Algorithmen

Vorschau – 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 der Grafikanalyse für die folgenden Anwendungsfälle abdecken:

• Zentralität
• Clustering
• Ähnlichkeit
• Pfadsuche

Zentralität

Mit Zentralitätsalgorithmen werden Knoten nach ihrer strukturellen Bedeutung in einem Diagramm eingestuft. So lassen sich beispielsweise betrügerische Konten im Fintech-Bereich, Influencer in sozialen Netzwerken oder kritische Router in Telekommunikationsnetzwerken 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 Durchlauf häufiger besucht werden, gelten als wichtiger. Weitere Informationen zum Algorithmus finden Sie unter PageRank.

Funktionssignatur

PageRank(input_parameters) YIELD node, score

Eingabeparameter

Alle gemeinsamen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
source_nodes	Array von Knoten im Diagramm	Nein	(keine)	Sofern vorhanden, Quelle für personalisierten PageRank.
damping_factor	double	Nein	0,85	Die Wahrscheinlichkeit, dass der Algorithmus in einer bestimmten Iteration eine der ausgehenden Kanten des aktuellen Knotens durchläuft. Der Wert muss im Bereich [0, 1) liegen.
max_iterations	int	Nein	10	Die maximale Anzahl an 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	double	Nein	1e-2	Schwellenwert für die Approximationsgenauigkeit für den Algorithmus. Muss nicht negativ sein. Kleinere Werte führen in der Regel zu genaueren Ergebnissen, allerdings auf Kosten einer längeren Laufzeit.

Ausgabe

Funktionsergebnis:

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 gibt an, wie oft ein Knoten auf den kürzesten Pfaden zwischen anderen Knotenpaaren liegt. Knoten mit hoher Betweenness-Zentralität fungieren oft als wichtige Brücken, die verschiedene Teile des Diagramms verbinden. Weitere Informationen zum Algorithmus

Funktionssignatur

BetweennessCentrality(input_parameters) YIELD node, centrality

Eingabeparameter

Alle gemeinsamen 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 gesetzt, die größer als die Anzahl der Knoten im Diagramm ist, werden alle Knoten als Quellknoten verwendet. Das bedeutet, dass der Algorithmus genaue Betweenness-Zentralitäten berechnet. Höhere Werte führen zu besseren Schätzungen, aber auch zu längeren Laufzeiten.

Ausgabe

Funktionsergebnis:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Diagramm.
Zentralität	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, centrality
RETURN node.id, centrality;

ClosenessCentrality

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

Funktionssignatur

ClosenessCentrality(input_parameters) YIELD node, centrality

Eingabeparameter

Alle gemeinsamen 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	Bei „false“ werden Standard-Closeness-Zentralitäten berechnet. Wenn „true“, werden Wasserman-Faust-Closeness-Zentralitä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 in der Regel eine höhere Genauigkeit. Bei größeren Werten kann der Algorithmus in der Regel schneller ausgeführt werden.
sample_size	INT64	Nein	0	Wird nur für den HYBRID-Algorithmus verwendet. Die Anzahl der Pivot-Knoten, die zum ungefähren Berechnen der Zentralitätswerte verwendet werden sollen. Muss nicht negativ sein. Wenn der Wert nicht festgelegt oder null ist, wird der Standardwert min(100 * ln(N), N) verwendet, wobei N die Anzahl der Knoten des Eingabediagramms ist.

Ausgabe

Funktionsergebnis:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Diagramm.
Zentralität	FLOAT64	Der Wert für die Nähezentralität 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, centrality
RETURN node.id, centrality;

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 in Fintech-Unternehmen zu erkennen, Kundensegmentierungen im Einzelhandel zu identifizieren und vieles mehr.

WeaklyConnectedComponents

Mit WeaklyConnectedComponents werden disjunkte Knotensätze gefunden, sodass jeder Knoten in einem Satz von jedem anderen Knoten im selben Satz, aber nicht von Knoten in anderen Sätzen aus erreichbar ist. Weitere Informationen zum Algorithmus finden Sie unter Verbundene Komponenten.

Funktionssignatur

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

Eingabeparameter

Alle gemeinsamen Eingabeparameter.

Ausgabe

Funktionsergebnis:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Diagramm.
Cluster	INT64	Die ID der verbundenen Komponente oder des verbundenen 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. Die Modularität 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 gemeinsamen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
Auflösung	double	Nein	1,0	Steuert den Detaillierungsgrad des Clusterings. Muss endlich und nicht negativ sein. Bei kleineren Auflösungswerten entstehen in der Regel größere Cluster. 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	int	Nein	10	Maximale Anzahl der äußeren Iterationen des Algorithmus. Muss positiv sein. Größere Werte führen in der Regel zu hochwertigeren Clustern, allerdings auf Kosten einer längeren Laufzeit.
max_inner_iterations	int	Nein	10	Maximale Anzahl an inneren Iterationen des Algorithmus. Muss positiv sein. Größere Werte führen in der Regel zu hochwertigeren Clustern, allerdings auf Kosten einer längeren Laufzeit.

Ausgabe

Funktionsergebnis:

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/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

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

Funktionssignatur

CorrelationClustering(input_parameters) YIELD node, cluster

Eingabeparameter

Alle gemeinsamen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
Auflösung	double	Ja	(keine)	Steuert den Detaillierungsgrad des Clusterings. Muss vom Client explizit 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 Kantengewichte positiv sind, findet der Algorithmus (mit einer ausreichenden Anzahl von Iterationen) die verbundenen Komponenten des Graphen.
max_iterations	int	Nein	10	Maximale Anzahl der äußeren Iterationen des Algorithmus. Muss positiv sein. Größere Werte führen in der Regel zu hochwertigeren Clustern, allerdings auf Kosten einer längeren Laufzeit.
max_inner_iterations	int	Nein	10	Maximale Anzahl an inneren Iterationen des Algorithmus. Muss positiv sein. Größere Werte führen in der Regel zu hochwertigeren Clustern, allerdings auf Kosten einer längeren Laufzeit.

Ausgabe

Funktionsergebnis:

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

Mit LabelPropagation werden Knoten mithilfe einer Label-Propagation-Technik Clustern zugewiesen. Dabei wird von einer anfänglichen Kennzeichnung ausgegangen, für die möglicherweise Seed-Labels aus der Eingabe verwendet werden. 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 Label Propagation.

Funktionssignatur

LabelPropagation(input_parameters) YIELD node, cluster

Eingabeparameter

Alle gemeinsamen Eingabeparameter und:

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

Ausgabe

Funktionsergebnis:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Diagramm.
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 sich überschneidende dichte Communities, die einen Mindestdichteschwellenwert erfüllen, sodass jede Clique (eine Gruppe von Knoten, in 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 mehrere Zeilen für denselben Knoten geben, da ein Knoten Teil vieler Cliquen sein kann.

Eingabeparameter

Alle gemeinsamen Eingabeparameter und:

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

Ausgabe

Funktionsergebnis:

Name	Typ	Beschreibung
Knoten	GRAPH_ELEMENT (Knoten)	Ein Knoten im Diagramm.
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. Das 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, wobei Ähnlichkeitswerte auf der Grundlage der Nachbarschaften der Knoten berechnet werden.

• JaccardSimilarity: Basierend auf dem Verhältnis von gemeinsamen Nachbarn zu allen Nachbarn
• CosineSimilarity: Basierend auf Kantengewichtungen 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 gemeinsamen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
source_nodes	Array von Knoten	Ja	–
target_nodes	Array von Knoten	Ja	–

Ausgabe

Funktionsergebnis:

Name	Typ	Beschreibung
source_node	GRAPH_ELEMENT (Knoten)	Der Quellknoten, der bei der Ähnlichkeitsberechnung verwendet wird.
target_node	GRAPH_ELEMENT (Knoten)	Der Zielknoten, der bei der Ä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. Das ist nützlich, um die kostengünstigste Route in Lieferketten zu ermitteln, die Anfälligkeit in der Cybersicherheit zu bewerten und vieles mehr.

ShortestPath

Mit ShortestPath werden die kürzesten Pfade zwischen einer bestimmten Gruppe von Quellknoten und einer bestimmten Gruppe von Zielknoten berechnet. Weitere Informationen zum Algorithmus finden Sie unter Kürzeste Pfade zwischen vielen Start- und Zielorten.

Funktionssignatur

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

Eingabeparameter

Alle gemeinsamen Eingabeparameter und:

Name	Typ	Erforderlich	Standard	Beschreibung
source_nodes	Array von Knoten	Ja	–
target_nodes	Array von Knoten	Ja	–

Ausgabe

Funktionsergebnis:

Name	Typ	Beschreibung
source_node	GRAPH_ELEMENT (Knoten)	Der Quellknoten des Pfads.
target_node	GRAPH_ELEMENT (Knoten)	Der Zielknoten des Pfads.
Pfad	GRAPH_PATH	Der kürzeste gefundene Pfad.
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

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