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

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

מרכזיות

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

PageRank

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

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

PageRank(input_parameters) YIELD node, score

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

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

שם סוג חובה ברירת מחדל תיאור
source_nodes מערך של צמתי גרף לא (ללא) אם קיים, המקור ל-PageRank בהתאמה אישית.
damping_factor double לא 0.85 ההסתברות שבכל איטרציה נתונה, האלגוריתם יבחר לעבור לאחד מהקצוות היוצאים של הצומת הנוכחי. הערך חייב להיות בטווח [0, 1).
max_iterations int לא 10 המספר המקסימלי של איטרציות של האלגוריתם. חייב להיות חיובי. מספר גבוה יותר של איטרציות נוטה להניב תוצאות מדויקות יותר, אבל זמן הריצה ארוך יותר.
approx_precision double לא ‫1e-2 סף הדיוק של הקירוב לאלגוריתם. הערך לא יכול להיות שלילי. ערכים קטנים יותר נוטים להניב תוצאות מדויקות יותר, אבל זמן הריצה ארוך יותר.

תשובה

הפונקציה מחזירה:

שם סוג תיאור
צומת ‫GRAPH_ELEMENT (צומת) צומת בתרשים.
score FLOAT64 ציון PageRank של הצומת.

דוגמה

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, centrality

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

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

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

תשובה

הפונקציה מחזירה:

שם סוג תיאור
צומת ‫GRAPH_ELEMENT (צומת) צומת בתרשים.
מרכזיות FLOAT64 ציון המרכזיות של הצומת.

דוגמה

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

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

ClosenessCentrality(input_parameters) YIELD node, centrality

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

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

שם סוג חובה ברירת מחדל תיאור
מצב מחרוזת לא EXACT מצב האלגוריתם. הערכים הנתמכים הם EXACT ו-HYBRID.
use_wasserman_faust BOOL לא לא נכון אם הערך הוא false, מחשבים את מרכזי הקרבה הסטנדרטיים. אם הערך הוא true, המערכת מחשבת את מרכזיות הקרבה של Wasserman-Faust.
epsilon FLOAT64 לא 0.1 הפרמטר הזה משמש רק לאלגוריתם 'HYBRID'. הערך חייב להיות בטווח (0.0, 1.0). ערכים קטנים יותר בדרך כלל מצביעים על דיוק גבוה יותר. ערכים גדולים יותר בדרך כלל מאפשרים לאלגוריתם לפעול מהר יותר.
sample_size INT64 לא 0 הפרמטר הזה משמש רק לאלגוריתם 'HYBRID'. מספר צמתי הציר שבהם יש להשתמש כדי לחשב בקירוב את ערכי המרכזיות. הערך לא יכול להיות שלילי. אם לא מגדירים ערך או מגדירים אפס, נעשה שימוש בערך ברירת המחדל min(100 * ln(N), N), כאשר N הוא מספר הצמתים של גרף הקלט.

תשובה

הפונקציה מחזירה:

שם סוג תיאור
צומת ‫GRAPH_ELEMENT (צומת) צומת בתרשים.
מרכזיות FLOAT64 הניקוד של מרכזיות הקרבה של הצומת.

דוגמה

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;

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

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

WeaklyConnectedComponents

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

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

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

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

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

תשובה

הפונקציה מחזירה:

שם סוג תיאור
צומת ‫GRAPH_ELEMENT (צומת) צומת בתרשים.
אשכול INT64 המזהה של הרכיב או האשכול המחוברים שהצומת שייך אליהם. בטווח [0, N), כאשר N הוא מספר הצמתים בגרף.

דוגמה

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

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

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

שם סוג חובה ברירת מחדל תיאור
רזולוציה double לא 1.0 הפרמטר הזה קובע את רמת הפירוט של האשכולות. הערך חייב להיות סופי ולא שלילי. ערכים קטנים יותר של רזולוציה בדרך כלל מובילים לאשכולות גדולים יותר. הערכים האופייניים הם בטווח [0.5, 5]. כשהרזולוציה היא אפס, האלגוריתם (עם מספר מספיק של איטרציות) מוצא את הרכיבים המחוברים של הגרף (תוך התעלמות מקצוות שהמשקל שלהם הוא אפס).
max_iterations int לא 10 המספר המקסימלי של איטרציות חיצוניות של האלגוריתם. חייב להיות חיובי. ערכים גדולים יותר בדרך כלל מובילים לאשכולות איכותיים יותר, אבל על חשבון זמן ריצה ארוך יותר.
max_inner_iterations int לא 10 מספר החזרות המרבי של האלגוריתם. חייב להיות חיובי. ערכים גדולים יותר מובילים בדרך כלל לאשכולות איכותיים יותר, אבל זמן הריצה ארוך יותר.

תשובה

הפונקציה מחזירה:

שם סוג תיאור
צומת ‫GRAPH_ELEMENT (צומת) צומת בתרשים.
אשכול INT64 המזהה של הקהילה או האשכול שהצומת שייך אליהם. בטווח [0, N), כאשר N הוא מספר הצמתים בגרף.

דוגמה

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

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

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

שם סוג חובה ברירת מחדל תיאור
רזולוציה double כן (ללא) הפרמטר הזה קובע את רמת הפירוט של האשכולות. חובה להגדיר באופן מפורש על ידי הלקוח. הערך חייב להיות סופי ולא שלילי. ערכים קטנים יותר נוטים להוביל לאשכולות גדולים יותר. כשהרזולוציה היא אפס וכל משקלי הקשתות חיוביים, האלגוריתם (עם מספר מספיק של איטרציות) מוצא את הרכיבים המחוברים של הגרף.
max_iterations int לא 10 המספר המקסימלי של איטרציות חיצוניות של האלגוריתם. חייב להיות חיובי. ערכים גדולים יותר בדרך כלל מובילים לאשכולות איכותיים יותר, אבל על חשבון זמן ריצה ארוך יותר.
max_inner_iterations int לא 10 מספר החזרות המרבי של האלגוריתם. חייב להיות חיובי. ערכים גדולים יותר מובילים בדרך כלל לאשכולות איכותיים יותר, אבל זמן הריצה ארוך יותר.

תשובה

הפונקציה מחזירה:

שם סוג תיאור
צומת ‫GRAPH_ELEMENT (צומת) צומת בתרשים.
אשכול INT64 המזהה של הקהילה או האשכול שהצומת שייך אליהם. בטווח [0, N), כאשר N הוא מספר הצמתים בגרף.

דוגמה

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

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

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

שם סוג חובה ברירת מחדל תיאור
seed_label_property מחרוזת לא (ללא) שם מאפיין הצומת של תווית הזרע.
max_iterations int לא 10 המספר המקסימלי של איטרציות של הפצת תוויות שהאלגוריתם מבצע. חייב להיות סופי וחיובי.

תשובה

הפונקציה מחזירה:

שם סוג תיאור
צומת ‫GRAPH_ELEMENT (צומת) צומת בתרשים.
אשכול INT64 המזהה של האשכול או התווית שהועברו מהצומת.

דוגמה

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

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

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

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

שם סוג חובה ברירת מחדל תיאור
min_density double לא 0.9 הצפיפות המינימלית של האשכולות שיוחזרו. הערך חייב להיות בין 0 ל-1.

תשובה

הפונקציה מחזירה:

שם סוג תיאור
צומת ‫GRAPH_ELEMENT (צומת) צומת בתרשים.
קליקה INT64 המזהה של הקליקה שאליה שייך הצומת.

דוגמה

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

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

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

שם סוג חובה ברירת מחדל תיאור
source_nodes מערך של צמתים כן לא רלוונטי
target_nodes מערך של צמתים כן לא רלוונטי

תשובה

הפונקציה מחזירה:

שם סוג תיאור
source_node ‫GRAPH_ELEMENT (צומת) צומת המקור שמשמש לחישוב הדמיון.
target_node ‫GRAPH_ELEMENT (צומת) צומת היעד שמשמש לחישוב הדמיון.
דמיון FLOAT64 ציון הדמיון המחושב בין צומת המקור לצומת היעד.

דוגמה

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

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

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

שם סוג חובה ברירת מחדל תיאור
source_nodes מערך של צמתים כן לא רלוונטי
target_nodes מערך של צמתים כן לא רלוונטי

תשובה

הפונקציה מחזירה:

שם סוג תיאור
source_node ‫GRAPH_ELEMENT (צומת) צומת המקור של הנתיב.
target_node ‫GRAPH_ELEMENT (צומת) צומת היעד של הנתיב.
נתיב GRAPH_PATH הנתיב הקצר ביותר שנמצא.
cost FLOAT64 העלות של הנתיב הקצר ביותר.

דוגמה

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;

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