מבוא לעיבוד גרפי ניצוצות עם GraphFrames

1. הקדמה

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

במדריך זה נטען ונחקור אפשרויות גרפים באמצעות Apache Spark ב- Java. כדי להימנע ממבנים מורכבים, נשתמש בממשק API של Apache Spark גרף קל ורמה גבוהה: ה- API של GraphFrames.

2. גרפים

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

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

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

3. הגדרת Maven

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

בואו נוסיף spark-graphx 2.11,מסגרות גרף, ו ניצוץ-מ"ר 2.11:

 org.apache.spark spark-graphx_2.11 2.4.4 graphframes graphframes 0.7.0-spark2.4-s_2.11 org.apache.spark spark-sql_2.11 2.4.4 

גרסאות חפץ אלה תומכות בסקאלה 2.11.

כמו כן, כל כך קורה ש- GraphFrames אינו נמצא במרכז Maven. אז בואו נוסיף גם את מאגר Maven הדרוש:

  SparkPackagesRepo //dl.bintray.com/spark-packages/maven 

4. תצורת ניצוץ

על מנת לעבוד עם GraphFrames, נצטרך להוריד את Hadoop ולהגדיר את ה- HADOOP_HOME משתנה הסביבה.

במקרה של Windows כמערכת ההפעלה, אנו גם נוריד את המתאים winutils.exe אל ה HADOOP_HOME / bin תיקיה.

לאחר מכן, נתחיל בקוד שלנו ביצירת התצורה הבסיסית:

SparkConf sparkConf = SparkConf חדש () .setAppName ("SparkGraphFrames") .setMaster ("מקומי [*]"); JavaSparkContext javaSparkContext = JavaSparkContext חדש (sparkConf);

נצטרך גם ליצור SparkSession:

הפעלת SparkSession = SparkSession.builder () .appName ("SparkGraphFrameSample") .config ("spark.sql.warehouse.dir", "/ file: C: / temp") .sparkContext (javaSparkContext.sc ()). Master ( "מקומי [*]") .getOrCreate ();

5. בניית גרפים

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

נעבוד על מערכות היחסים בין משתמשים מרשת חברתית היפותטית.

5.1. נתונים

ראשית, לדוגמא זו, בואו נגדיר את שתי הישויות כ- מִשׁתַמֵשׁ ו מערכת יחסים:

משתמש בכיתה ציבורית {פרטי מזהה ארוך; שם מחרוזת פרטי; // constructor, getters and seters} יישומים ציבוריים בכיתת היחסים ניתן לסידור {פרטי סוג מחרוזת; פרטי מחרוזת src; פרטי מחרוזת dst; מזהה UUID פרטי; יחסי ציבור (סוג מחרוזת, מחרוזת src, מחרוזת dst) {this.type = type; this.src = src; this.dst = dst; this.id = UUID.randomUUID (); } // גטרים וקובעים}

לאחר מכן, בואו נגדיר כמה מִשׁתַמֵשׁ ו מערכת יחסים מקרים:

משתמשים ברשימה = ArrayList חדש (); users.add (משתמש חדש (1L, "ג'ון")); users.add (משתמש חדש (2L, "מרטין")); users.add (משתמש חדש (3L, "פיטר")); users.add (משתמש חדש (4L, "אלישיה")); רשימת יחסים = ArrayList חדש (); relationss.add (קשר חדש ("חבר", "1", "2")); relationss.add (קשר חדש ("עוקב", "1", "4")); relationss.add (קשר חדש ("חבר", "2", "4")); relationss.add (קשר חדש ("יחסי", "3", "1")); relationss.add (קשר חדש ("יחסי", "3", "4"));

5.2. GraphFrame למשל

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

מערך נתונים UserDataset = session.createDataFrame (משתמשים, User.class); Dataset relationshipDataset = session.createDataFrame (קשרים, Relation.class); GraphFrame גרף = GraphFrame חדש (userDataframe, relationshipDataframe);

סוף סוף נרשום את הקודקודים והקצוות שלנו במסוף כדי לראות איך זה נראה:

graph.vertices (). show (); graph.edges (). show ();
+ --- + ------ + | מזהה | שם | + --- + ------ + | 1 | ג'ון | | 2 | מרטין | | 3 | פיטר | | 4 | אלישיה | + --- + ------ + + --- + -------------------- + --- + -------- - + | dst | id | src | סוג | + --- + -------------------- + --- + --------- + | 2 | 622da83f-fb18-484 ... | 1 | חבר | | 4 | c6dde409-c89d-490 ... | 1 | בעקבות | | 4 | 360d06e1-4e9b-4ec ... | 2 | חבר | | 1 | de5e738e-c958-4e0 ... | 3 | יחסית | | 4 | d96b045a-6320-4a6 ... | 3 | יחסית | + --- + -------------------- + --- + --------- +

6. מפעילי גרפים

עכשיו שיש לנו GraphFrame למשל, בואו נראה מה אנחנו יכולים לעשות עם זה.

6.1. לְסַנֵן

GraphFrames מאפשר לנו לסנן קצוות וקודקודים לפי שאילתה.

לאחר מכן, לאחר מכן, נסנן את הקודקודים לפי שֵׁם נכס ב מִשׁתַמֵשׁ:

graph.vertices (). filter ("name = 'Martin'"). show ();

בקונסולה אנו יכולים לראות את התוצאה:

+ --- + ------ + | מזהה | שם | + --- + ------ + | 2 | מרטין | + --- + ------ +

כמו כן, אנו יכולים לסנן ישירות על הגרף על ידי התקשרות filterEdges אוֹ filterVertices:

graph.filterEdges ("type = 'Friend'") .dropIsolatedVertices (). קודקודים (). show ();

כעת, מכיוון שסיננו את הקצוות, ייתכן שעדיין יהיו לנו כמה קודקודים מבודדים. אז נתקשר dropIsolatedVertices ().

כתוצאה מכך יש לנו תצלום, עדיין א GraphFrame למשל, רק עם מערכות היחסים שיש להן מעמד "חבר":

+ --- + ------ + | מזהה | שם | + --- + ------ + | 1 | ג'ון | | 2 | מרטין | | 4 | אלישיה | + --- + ------ +

6.2. תארים

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

ה מעלות הפעולה רק מחזירה את ספירת כל הקצוות של כל קודקוד. מצד שני, inDegrees סופר רק קצוות נכנסים, ו outDegrees סופר רק קצוות יוצאים.

בואו ונמנה את המעלות הנכנסות של כל הקודקודים בתרשים שלנו:

graph.inDegrees (). show ();

כתוצאה מכך, יש לנו GraphFrame המציג את מספר הקצוות הנכנסים לכל קודקוד, למעט אלה ללא:

+ --- + -------- + | id | inDegree | + --- + -------- + | 1 | 1 | | 4 | 3 | | 2 | 1 | + --- + -------- +

7. אלגוריתמים גרפיים

GraphFrames מספק גם אלגוריתמים פופולריים מוכנים לשימוש - בואו נסתכל על כמה מהם.

7.1. דירוג דף

אלגוריתם Page Rank שוקל את הקצוות הנכנסים לקודקוד והופך אותו לניקוד.

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

לדוגמא, ברשת חברתית, אם אחריו אנשים שונים אנשים שונים, הוא או היא ידורגו גבוה.

הפעלת אלגוריתם דירוג העמודים היא פשוטה למדי:

graph.pageRank () .maxIter (20) .resetProbability (0.15) .run () .vertices () .show ();

כדי להגדיר את האלגוריתם הזה, עלינו לספק:

  • maxIter - מספר האיטרציות של דירוג העמודים להפעלה - מומלץ 20, מעטים מדי יפחיתו את האיכות, ורבים מדי יפחיתו את הביצועים
  • resetProbability - ההסתברות לאיפוס אקראי (אלפא) - ככל שהיא נמוכה יותר, כך יתפשט התוצאה בין המנצחים והמפסידים - טווחים תקפים הם בין 0 ל -1. בדרך כלל, 0.15 הוא ציון טוב

התגובה דומה GraphFrame, אם כי הפעם אנו רואים טור נוסף המעניק את דירוג העמוד של כל קודקוד:

+ --- + ------ + ------------------ + | מזהה | שם | דירוג דף + --- + ------ + ------------------ + | 4 | אלישיה | 1.9393230468864597 | | 3 | פיטר | 0.4848822786454427 | | 1 | ג'ון | 0.7272991738542318 | | 2 | מרטין | 0.848495500613866 | + --- + ------ + ------------------ +

בגרף שלנו, אלישיה היא קודקוד הרלוונטי ביותר, ואחריה מרטין וג'ון.

7.2. רכיבים מחוברים

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

אנו יכולים להתקשר לאלגוריתם ללא פרמטרים באמצעות ה- connectedComponents () שיטה:

graph.connectedComponents (). run (). show ();

האלגוריתם מחזיר א GraphFrame המכיל כל קודקוד ואת הרכיב אליו כל אחד מחובר:

+ --- + ------ + ------------ + | מזהה | שם | רכיב | + --- + ------ + ------------ + | 1 | ג'ון | 154618822656 | | 2 | מרטין | 154618822656 | | 3 | פיטר | 154618822656 | | 4 | אלישיה | 154618822656 | + --- + ------ + ------------ +

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

למרות שיש לנו כאן טור נוסף - מזהה הרכיב - הגרף שלנו עדיין זהה.

7.3. ספירת משולשים

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

בקהילת רשתות חברתיות קל למצוא מספר לא מבוטל של משולשים המחוברים זה לזה.

אנו יכולים לבצע בקלות משולש ספירה ישירות משלנו GraphFrame למשל:

graph.triangleCount (). run (). show ();

האלגוריתם מחזיר גם א GraphFrame עם מספר המשולשים שעוברים בכל קודקוד.

+ ----- + --- + ------ + | ספירה | מזהה | שם | + ----- + --- + ------ + | 1 | 3 | פיטר | | 2 | 1 | ג'ון | | 2 | 4 | אלישיה | | 1 | 2 | מרטין | + ----- + --- + ------ +

8. מסקנה

Apache Spark הוא כלי נהדר לחישוב כמות נתונים רלוונטית בצורה אופטימלית ומופצת. וספריית GraphFrames מאפשרת לנו להפיץ פעולות גרף בקלות על ניצוץ.

כמו תמיד, קוד המקור המלא של הדוגמה זמין ב- GitHub.


$config[zx-auto] not found$config[zx-overlay] not found