קטלוג האלגוריתמים של Spanner Graph

Spanner Graph, בשיתוף פעולה הדוק עם צוות המחקר של Google Graph Mining, מציע חבילת אלגוריתמים שמכסה את צורכי ניתוח התרשימים בתרחישי השימוש הבאים:

• מרכזיות
• Clustering
• דמיון
• מציאת נתיב

מרכזיות

אלגוריתמים של מרכזיות מדרגים צמתים לפי החשיבות המבנית שלהם בגרף. הוא יכול לעזור לכם לזהות חשבונות שמקורם בתרמית בפינטק, משפיענים בתרשימים של קשרים חברתיים, נתבים קריטיים ברשתות טלקום ועוד.

PageRank

‫PageRank מדרג את הצמתים לפי חשיבות. צומת נחשב חשוב יותר אם הרבה צמתים חשובים אחרים מקשרים אליו. האלגוריתם מדמה מעבר אקראי בגרף. צמתים שביקרו בהם בתדירות גבוהה יותר במהלך ההליכה נחשבים חשובים יותר. לפרטים על האלגוריתם, ראו דירוג דף.

חתימת הפונקציה

PageRank(input_parameters) YIELD node, score

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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 מודד באיזו תדירות צומת נמצא בנתיבים הקצרים ביותר בין זוגות אחרים של צמתים. צמתים עם מרכזיות גבוהה בין צמתים אחרים משמשים לעיתים קרובות כגשרים קריטיים שמחברים בין חלקים שונים של הגרף. פרטים על האלגוריתם זמינים במאמר מרכזיות הביניים.

חתימת פונקציה

BetweennessCentrality(input_parameters) YIELD node, score

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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 מודד את המרחק של צומת מכל הצמתים האחרים בתרשים. צמתים עם מרכזיות קרבה גבוהה יכולים להגיע לצמתים אחרים דרך נתיבים קצרים יותר. פרטים על האלגוריתם זמינים במאמר בנושא מרכזיות לפי קרבה.

חתימת פונקציה

ClosenessCentrality(input_parameters) YIELD node, score

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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;

סידור באשכולות

אלגוריתמים של אשכולות מקבצים צמתים לאשכולות (שנקראים גם קהילות) כך שהצמתים בכל אשכול מחוברים זה לזה בצפיפות רבה יותר מאשר לצמתים באשכולות אחרים. התכונה הזו שימושית לזיהוי רשתות הונאה פוטנציאליות בפינטק, לזיהוי פילוחים של לקוחות בקמעונאות ועוד.

WeaklyConnectedComponents

‫WeaklyConnectedComponents מוצאת קבוצות נפרדות של צמתים כך שכל צומת בקבוצה נגיש מכל צומת אחר באותה קבוצה, אבל לא מצמתים בקבוצות אחרות. לפרטים על האלגוריתם, ראו רכיבים מחוברים.

חתימת פונקציה

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

פרמטרים של קלט

כל פרמטרי הקלט הנפוצים.

תשובה

הפונקציה מניבה:

דוגמה

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 מחלק את התרשים לאשכולות באמצעות אופטימיזציה למודולריות, מדד איכות של צפיפות החיבורים בתוך האשכולות בהשוואה למה שצפוי ברשת אקראית. פרטים על האלגוריתם זמינים במאמר בנושא אשכולות מודולריים.

חתימת פונקציה

ModularityClustering(input_parameters) YIELD node, cluster

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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 מחלק את הצמתים לפי מידת הדמיון או השוני ביניהם, במטרה לקבץ צמתים דומים ולהפריד בין צמתים שונים. פרטים על האלגוריתם מופיעים במאמר אשכולות מתואמים.

חתימת פונקציה

CorrelationClustering(input_parameters) YIELD node, cluster

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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 מקצה צמתים לאשכולות באמצעות טכניקה של הפצת תוויות, החל מתווית ראשונית שעשויה להשתמש בתוויות ראשוניות שסופקו בקלט. כשהצמתים מאמצים באופן איטרטיבי את התווית שמשותפת לרוב השכנים שלהם, קבוצות עם קשרים צפופים מגיעות להסכמה על תווית, ויוצרות קהילות. לפרטים על האלגוריתם, ראו הפצת תוויות.

חתימת הפונקציה

LabelPropagation(input_parameters) YIELD node, cluster

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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 מזהה קהילות צפופות שעשויות לחפוף ועומדות בסף צפיפות מינימלי, כך שכל קליקה (קבוצת צמתים שבה כל צומת מחובר לכל צומת אחר) נכללת באשכול אחד לפחות. פרטים על האלגוריתם מופיעים במאמר בנושא צבירת קליקים.

חתימת הפונקציה

CliqueFinding(input_parameters) YIELD node, clique

הערה: בניגוד לרוב האלגוריתמים, יכולות להיות כמה שורות לאותו צומת, כי צומת יכול להיות חלק מכמה קליקות.

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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;

דמיון

אלגוריתמים של דמיון מכמתים את מידת הדמיון בין זוגות של צמתים על סמך המבנה של השכונות שלהם. זה שימושי להסקת קצוות חסרים בין צמתים לצורך פתרון ישויות, המלצות ועוד.

ב-Spanner Graph יש תמיכה בחישובים הבאים של דמיון בין זוגות של צמתים, שבהם ציוני הדמיון מחושבים על סמך השכונות של הצמתים.

• ‫JaccardSimilarity: על סמך היחס בין השכנים המשותפים לכלל השכנים
• ‫CosineSimilarity: על סמך משקלי הקצוות של שכנים משותפים
• CommonNeighborsSimilarity: לפי מספר השכנים המשותפים
• ‫TotalNeighborsSimilarity: על סמך מספר השכנים של לפחות אחד משני הצמתים

פרטים על האלגוריתם מופיעים במאמר בנושא דמיון בין צמתי זוגות.

לארבעת האלגוריתמים האלה יש את אותם ארגומנטים ומבנה פלט.

חתימת הפונקציה

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

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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;

חיפוש נתיב

אלגוריתמים למציאת נתיבים מחשבים מסלולים אופטימליים בין צמתים. התכונה הזו שימושית לזיהוי המסלול הזול ביותר בשרשרות אספקה, להערכת נקודות חולשה באבטחת סייבר ועוד.

ShortestPath

‫ShortestPath מחשב את המסלולים הקצרים ביותר בין קבוצה נתונה של צומתי מקור לבין קבוצה נתונה של צומתי יעד. פרטים על האלגוריתם זמינים במאמר המסלולים הקצרים ביותר בין רבים לרבים.

חתימת הפונקציה

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

פרמטרים של קלט

כל הפרמטרים הנפוצים של קלט וגם:

תשובה

הפונקציה מניבה:

דוגמה

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;

המאמרים הבאים

• אלגוריתמים של הפעלת Spanner Graph.
• דרישות הסכימה של אלגוריתם Spanner Graph ותאימות לתכונות.
• שיטות מומלצות לשימוש באלגוריתם של Spanner Graph.