Katalog algoritma Spanner Graph

Spanner Graph, berkolaborasi erat dengan Google Research Graph Mining, menawarkan serangkaian algoritma yang mencakup kebutuhan analisis grafik untuk kasus penggunaan berikut:

Sentralitas

Algoritma sentralitas memberi peringkat pada node berdasarkan kepentingan strukturalnya dalam grafik. Hal ini dapat membantu Anda mengidentifikasi akun penipuan di fintech, influencer dalam grafik sosial, router penting dalam jaringan telekomunikasi, dan banyak lagi.

PageRank

PageRank memberi skor pada node berdasarkan tingkat kepentingannya. Sebuah node dianggap lebih penting jika banyak node penting lainnya menautkannya. Algoritma ini menyimulasikan langkah acak melalui grafik. Node yang lebih sering dikunjungi dalam penelusuran ini dianggap lebih penting. Lihat peringkat halaman untuk mengetahui detail algoritma.

Tanda tangan fungsi

PageRank(input_parameters) YIELD node, score

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
source_nodes Array node grafik Tidak (tidak ada) Jika ada, sumber untuk PageRank yang dipersonalisasi.
damping_factor double Tidak 0,85 Probabilitas bahwa, pada iterasi tertentu, algoritma memilih untuk melakukan penelusuran salah satu tepi keluar dari node saat ini. Harus dalam rentang [0, 1).
max_iterations int Tidak 10 Jumlah maksimum iterasi algoritma. Harus positif. Jumlah iterasi yang lebih tinggi cenderung menghasilkan hasil yang lebih presisi dengan biaya waktu proses yang lebih lama.
approx_precision double Tidak 1e-2 Batas presisi perkiraan untuk algoritma. Harus non-negatif. Nilai yang lebih kecil cenderung menghasilkan hasil yang lebih presisi dengan biaya waktu proses yang lebih lama.

Output

Hasil fungsi:

Nama Jenis Deskripsi
node GRAPH_ELEMENT (node) Node dalam grafik.
skor FLOAT64 Skor PageRank node.

Contoh

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 mengukur seberapa sering sebuah node berada di jalur terpendek antara pasangan node lainnya. Node dengan sentralitas antara yang tinggi sering kali bertindak sebagai jembatan penting yang menghubungkan berbagai bagian grafik. Lihat sentralitas keantaraan untuk mengetahui detail algoritma.

Tanda tangan fungsi

BetweennessCentrality(input_parameters) YIELD node, centrality

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
num_source_nodes INT64 Tidak (tidak ada) Jika ditetapkan, harus positif, dan menentukan jumlah node sumber yang harus dipilih algoritma untuk menghitung sentralitas keantaraan perkiraan. Jika tidak disetel, atau disetel ke angka yang lebih besar dari jumlah node dalam grafik, semua node akan digunakan sebagai node sumber, yaitu algoritma menghitung sentralitas keantaraan yang tepat. Nilai yang lebih tinggi menghasilkan perkiraan yang lebih baik, tetapi juga waktu berjalan yang lebih lama.

Output

Hasil fungsi:

Nama Jenis Deskripsi
node GRAPH_ELEMENT (node) Node dalam grafik.
sentralitas FLOAT64 Skor sentralitas node.

Contoh

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 mengukur seberapa dekat sebuah node dengan semua node lain dalam grafik. Node dengan sentralitas kedekatan yang tinggi dapat menjangkau node lain melalui jalur yang lebih pendek. Lihat closeness centrality untuk mengetahui detail algoritma.

Tanda tangan fungsi

ClosenessCentrality(input_parameters) YIELD node, centrality

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
mode STRING Tidak EXACT Mode algoritma. Nilai yang didukung adalah EXACT dan HYBRID.
use_wasserman_faust BOOL Tidak FALSE Jika `false`, hitung sentralitas kedekatan standar. Jika `true`, hitung sentralitas kedekatan Wasserman-Faust.
epsilon FLOAT64 Tidak 0,1 Hanya digunakan untuk algoritma `HYBRID`. Harus dalam rentang (0.0, 1.0). Nilai yang lebih kecil umumnya berarti presisi yang lebih tinggi. Nilai yang lebih besar umumnya memungkinkan algoritma dieksekusi lebih cepat.
sample_size INT64 Tidak 0 Hanya digunakan untuk algoritma `HYBRID`. Jumlah node pivot yang akan digunakan untuk menghitung nilai sentralitas secara perkiraan. Tidak boleh negatif. Jika tidak disetel atau nol, nilai default min(100 * ln(N), N) akan digunakan, dengan N adalah jumlah node grafik input.

Output

Hasil fungsi:

Nama Jenis Deskripsi
node GRAPH_ELEMENT (node) Node dalam grafik.
sentralitas FLOAT64 Skor sentralitas kedekatan node.

Contoh

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

Algoritma pengelompokan mengelompokkan node ke dalam cluster (juga dikenal sebagai komunitas) sehingga node dalam setiap cluster terhubung lebih erat satu sama lain daripada ke node di cluster lain. Teknik ini berguna untuk mendeteksi potensi sindikat penipuan di fintech, mengidentifikasi segmentasi pelanggan di retail, dan lainnya.

WeaklyConnectedComponents

WeaklyConnectedComponents menemukan kumpulan node yang terpisah sehingga setiap node dalam kumpulan dapat dijangkau dari node lain dalam kumpulan yang sama, tetapi tidak dari node dalam kumpulan lain. Lihat komponen yang terhubung untuk mengetahui detail algoritma.

Tanda tangan fungsi

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

Parameter input

Semua parameter input umum.

Output

Hasil fungsi:

Nama Jenis Deskripsi
node GRAPH_ELEMENT (node) Node dalam grafik.
cluster INT64 ID komponen/cluster terhubung tempat node berada. Dalam rentang [0, N), dengan N adalah jumlah node dalam grafik.

Contoh

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

ModularityClustering membagi grafik menjadi beberapa cluster dengan mengoptimalkan modularitas, yaitu ukuran kualitas kepadatan koneksi dalam cluster dibandingkan dengan yang diharapkan dalam jaringan acak. Lihat pengelompokan modularitas untuk mengetahui detail algoritma.

Tanda tangan fungsi

ModularityClustering(input_parameters) YIELD node, cluster

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
resolution double Tidak 1.0 Mengontrol perincian pengelompokan. Harus berhingga dan non-negatif. Nilai resolusi yang lebih kecil cenderung menghasilkan kelompok yang lebih besar. Nilai umum berada dalam rentang [0,5, 5]. Jika resolusinya nol, algoritma (dengan jumlah iterasi yang memadai) akan menemukan komponen grafik yang terhubung (dengan mengabaikan tepi yang bobotnya nol).
max_iterations int Tidak 10 Jumlah maksimum iterasi luar algoritma. Harus positif. Nilai yang lebih besar cenderung menghasilkan pengelompokan berkualitas lebih tinggi dengan mengorbankan waktu runtime yang lebih lama.
max_inner_iterations int Tidak 10 Jumlah maksimum iterasi dalam algoritma. Harus positif. Nilai yang lebih besar cenderung menghasilkan pengelompokan berkualitas lebih tinggi dengan mengorbankan waktu runtime yang lebih lama.

Output

Hasil fungsi:

Nama Jenis Deskripsi
node GRAPH_ELEMENT (node) Node dalam grafik.
cluster INT64 ID komunitas/cluster tempat node berada. Dalam rentang [0, N), dengan N adalah jumlah node dalam grafik.

Contoh

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 memartisi node berdasarkan kesamaan atau perbedaan berpasangan, yang bertujuan untuk mengelompokkan node serupa dan memisahkan node yang tidak serupa. Lihat pengelompokan korelasi untuk mengetahui detail algoritma.

Tanda tangan fungsi

CorrelationClustering(input_parameters) YIELD node, cluster

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
resolution double Ya (tidak ada) Mengontrol perincian pengelompokan. Harus ditentukan secara eksplisit oleh klien. Harus berhingga dan non-negatif. Nilai yang lebih kecil cenderung menghasilkan kelompok yang lebih besar. Jika resolusinya nol dan semua bobot tepi positif, algoritma (dengan jumlah iterasi yang memadai) akan menemukan komponen terhubung dari grafik.
max_iterations int Tidak 10 Jumlah maksimum iterasi luar algoritma. Harus positif. Nilai yang lebih besar cenderung menghasilkan pengelompokan berkualitas lebih tinggi dengan mengorbankan waktu runtime yang lebih lama.
max_inner_iterations int Tidak 10 Jumlah maksimum iterasi dalam algoritma. Harus positif. Nilai yang lebih besar cenderung menghasilkan pengelompokan berkualitas lebih tinggi dengan mengorbankan waktu runtime yang lebih lama.

Output

Hasil fungsi:

Nama Jenis Deskripsi
node GRAPH_ELEMENT (node) Node dalam grafik.
cluster INT64 ID komunitas/cluster tempat node berada. Dalam rentang [0, N), dengan N adalah jumlah node dalam grafik.

Contoh

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 menetapkan node ke cluster menggunakan teknik propagasi label, dimulai dari pelabelan awal yang dapat menggunakan label awal yang disediakan dalam input. Saat node secara berulang mengadopsi label yang dibagikan oleh sebagian besar tetangganya, grup yang terhubung secara padat akan menyatu ke label konsensus, membentuk komunitas. Lihat propagasi label untuk mengetahui detail algoritma.

Tanda tangan fungsi

LabelPropagation(input_parameters) YIELD node, cluster

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
seed_label_property string Tidak (tidak ada) Nama properti node untuk label awal.
max_iterations int Tidak 10 Jumlah maksimum iterasi propagasi label yang dilakukan algoritma. Harus berhingga dan positif.

Output

Hasil fungsi:

Nama Jenis Deskripsi
node GRAPH_ELEMENT (node) Node dalam grafik.
cluster INT64 ID cluster/label yang disebarkan dari node.

Contoh

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 mengidentifikasi komunitas padat yang berpotensi tumpang-tindih yang memenuhi nilai minimum kepadatan, sedemikian rupa sehingga setiap klik (grup node di mana setiap node terhubung ke setiap node lainnya) terdapat dalam setidaknya satu cluster. Lihat penggabung klik untuk mengetahui detail algoritma.

Tanda tangan fungsi

CliqueFinding(input_parameters) YIELD node, clique

Catatan: Tidak seperti kebanyakan algoritma, ada beberapa baris untuk node yang sama karena node dapat menjadi bagian dari banyak klik.

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
min_density double Tidak 0,9 Kepadatan minimum cluster yang akan ditampilkan. Harus dalam [0, 1].

Output

Hasil fungsi:

Nama Jenis Deskripsi
node GRAPH_ELEMENT (node) Node dalam grafik.
klik INT64 ID klik tempat node berada.

Contoh

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;

Kemiripan

Algoritma kemiripan mengukur seberapa mirip pasangan node berdasarkan struktur lingkungan sekitarnya. Hal ini berguna untuk menyimpulkan tepi yang hilang antar-node untuk penyelesaian entitas, rekomendasi, dan lainnya.

Spanner Graph mendukung kesamaan node berpasangan berikut dengan skor kesamaan dihitung berdasarkan lingkungan node.

  • JaccardSimilarity: Berdasarkan rasio tetangga umum terhadap total tetangga
  • CosineSimilarity: Berdasarkan bobot tepi tetangga umum
  • CommonNeighborsSimilarity: Berdasarkan jumlah tetangga yang dibagikan
  • TotalNeighborsSimilarity: Berdasarkan jumlah tetangga dari setidaknya salah satu dari dua node

Lihat kesamaan node berpasangan untuk mengetahui detail algoritma.

Keempat algoritma ini memiliki argumen dan struktur output yang sama.

Tanda tangan fungsi

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

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
source_nodes Array node Ya T/A
target_nodes Array node Ya T/A

Output

Hasil fungsi:

Nama Jenis Deskripsi
source_node GRAPH_ELEMENT (node) Node sumber yang digunakan dalam penghitungan kemiripan.
target_node GRAPH_ELEMENT (node) Node target yang digunakan dalam penghitungan kemiripan.
kemiripan FLOAT64 Skor kemiripan yang dihitung antara node sumber dan target.

Contoh

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;

Penemuan Jalur

Algoritma pencarian jalur menghitung rute optimal antar-node. Hal ini berguna untuk mengidentifikasi rute termurah dalam rantai pasokan, menilai kerentanan dalam keamanan siber, dan banyak lagi.

ShortestPath

ShortestPath menghitung jalur terpendek antara sekumpulan node sumber tertentu dan sekumpulan node target tertentu. Lihat jalur terpendek banyak-ke-banyak untuk mengetahui detail algoritma.

Tanda tangan fungsi

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

Parameter input

Semua parameter input umum dan:

Nama Jenis Wajib Default Deskripsi
source_nodes Array node Ya T/A
target_nodes Array node Ya T/A

Output

Hasil fungsi:

Nama Jenis Deskripsi
source_node GRAPH_ELEMENT (node) Node sumber jalur.
target_node GRAPH_ELEMENT (node) Target node jalur.
jalur GRAPH_PATH Jalur terpendek ditemukan.
cost FLOAT64 Biaya jalur terpendek.

Contoh

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;

Langkah berikutnya