מדידת פופולריות ברשת חברתית מכוונת (הירארכית)

05/07/2014

תגובה אחת

רשתות חברתיות כדוגמת פייסבוק או לינקדאין מאופיינות ברשת של חברויות בה לכל משתתף יש חברים, לכל אחד מהם חברים משלו וכך הלאה.
מדובר ברשת ולא בעץ מכיוון שיתכנו בה מעגלים סגורים בהם ראובן, שמעון ולוי חברים זה של זה (אחת מתכונותיו היסודיות של העץ – שאין בו מעגלים), ובוודאי שאין מדובר בעץ היררכי בו מתקיימים יחסי אב-בן מכיוון שכל חברות באתרים הנ”ל היא סימטרית: אם ראובן חבר של שמעון, אזי שמעון גם חבר של ראובן; מה שלא יכול לקרות בעץ היררכי (אם ראובן המנהל של שמעון אזי ברור ששמעון אינו יכול להיות המנהל של ראובן).
מהכתוב ניתן להבין שיתכן עץ שאינו היררכי, אך זה אינו נושא הדיון.

אני עובד כיום בחברת הייטק בשם EToro שגם לה יש רשת חברתית. מדובר בחברה שמספקת מערכת “חברתית” לניהול השקעות בניירות ערך, ובה כל משקיע יכול לראות את התיקים של המשקיעים האחרים ואת ביצועיהם, ו”להעתיק” ממי שביצועיו בתחום נראים מבטיחים. אם תרצו – במקום להיעזר בשירותי מנהלי תיקים או להשקיע בקרנות נאמנות שיש מי שמנהל את תיק ההשקעות שלהן, כאשר בשני המקרים איננו יודעים מה האינטרסים של מנהלי התיקים ולמה הם מסוגלים, אנחנו יכולים לבחור בעצמנו מישהו שיהפוך ליועץ לעת מצוא, הוא משקיע גם את כספו במישרין (ואת כספנו בעקיפין) וכך אנחנו יכולים להסתמך על ביצועיו בעבר ועל היעדר ניגודי אינטרסים בעתיד..
כאן כבר מדובר ברשת הירארכית: קודם כל – אם שמעון מעתיק מראובן, אזי כנראה שראובן אינו מעתיק משמעון; ובנוסף – טבע הדברים הוא שיש מספר מומחים שיודעים כיצד להשקיע, מספר מומחי משנה שיודעים אחרי מי לעקוב, וכך הלאה. לא מדובר בעץ הירארכי מכיוון שכל משקיע “זוטר” יכול להעתיק ממספר מומחים, ולכל מומחה יש מספר מעתיקים. יתכנו איפוא מעגלים (ניתן להגיע מקודקוד אחד לאחר במספר דרכים), אך ניתן להניח שאין לולאות (מצב בו ניתן לחזור לנקודת המוצא); כלומר לא יתכן מצב בו שמעון מעתיק מראובן, לוי מעתיק משמעון, ולבסוף ראובן מעתיק מלוי (ובעקיפין מעצמו): מטבע הדברים לא סביר שזה יקרה, ולצרכינו נניח שזה לא קורה (בסוף אראה כיצד ניתן להתגבר על בעיות כאלו).

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

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

ניקח דוגמה פשוטה וננסה את כוחנו:

image

Use tempdb;

Go

 

Create Table T_Members(Member Char(1) Primary Key);

 

Create Table T_Tree(Followed Char(1),

                Follower Char(1),

                Constraint FK_T_1 Foreign Key(Followed) References T_Members(Member),

                Constraint FK_T_2 Foreign Key(Follower) References T_Members(Member));

 

Create Unique Clustered Index Idx_T_Tree On T_Tree(Followed,Follower);

Go

 

Truncate Table T_Tree;

Delete From T_Members;

Insert

Into    T_Members

Values    ('A'),

        ('B'),

        ('C'),

        ('D'),

        ('E'),

        ('F');

 

Insert

Into    T_Tree

Values    ('A','B'),

        ('A','C'),

        ('B','D'),

        ('C','B'),

        ('E','C');

 

Select    * From T_Members;

Select    * From T_Tree;

image

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

Select    M.Member,

        Count(T.Follower)+1 DirectFollowers

From    T_Members M

Left Join T_Tree T

        On M.Member=T.Followed

Group By M.Member;

image

אני משתמש בטבלת T_Members וב-Left Join כדי להגיע גם לכאלה שלא עוקבים אחריהם (D,F),
ואני מוסיף 1 לתוצאה כדי שהיא תכלול גם את הנעקב עצמו (אני רוצה לשמור על אחידות כי בהמשך, כשאספור גם את העוקבים הלא ישירים, אספור למעשה את מספר הקודקודים בתת-הרשת שמתחילה בקודקוד מסויים וכוללת גם אותו).

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

With    T As

(Select Member Ancestor,

        Member Father,

        Member Son,

        1 Level,

        Cast(Member As Varchar(Max)) Path

From    T_Members

Union All

Select    T.Ancestor,

        T.Son,

        Tr.Follower,

        T.Level+1 Level,

        Cast(T.Path+','+Tr.Follower As Varchar(Max))

From    T

Inner Join T_Tree Tr

        On T.Son=Tr.Followed)

Select    *

From    T

Order By Ancestor,

        Father,

        Son;

image

אפשר לראות שהצירוף Father=B, Son=D מופיע 5 פעמים:

  1. פעם מתחת ל-Ancestor A (דרך C)- שורה 4
  2. פעם מתחת ל-Ancestor A (דרך B)- שורה 5
  3. פעם מתחת ל-Ancestor B- שורה 8
  4. פעם מתחת ל-Ancestor C- שורה 9
  5. פעם מתחת ל-Ancestor E- שורה 13

כמו כן – כל קודקוד מופיע פעם אחת בתור Ancestor & Father & Son ב-Level=1, כתוצאה מה”עוגן” – החלק הראשון של ה-CTE.
כל זה יוצר בעייה כשנרצה לספור את מספר הבנים הישירים של כל אב (Father), ואת מספר הבנים העקיפים של כל אב קדום (Ancestor), ולשם כך נכניס את השליפה הקודמת לחישוב ה-Direct Followers ל”עוגן” (Ancle) של ה-CTE ואת ה-IndirectFollowers נחשב בעזרת Count Distinct:

With    T As

(Select    M.Member Ancestor,

        M.Member Father,

        M.Member Son,

        1 Level,

        Cast(Member As Varchar(Max)) Path,

        Count(T.Follower)+1 DirectFollowers

From    T_Members M

Left Join T_Tree T

        On M.Member=T.Followed

Group By M.Member

Union All

Select    T.Ancestor,

        T.Son,

        Tr.Follower,

        T.Level+1 Level,

        Cast(T.Path+','+Tr.Follower As Varchar(Max)),

        Cast(Null As Int)

From    T

Inner Join T_Tree Tr

        On T.Son=Tr.Followed)

Select    Ancestor,

        Max(DirectFollowers) DirectFollowers,

        Count(Distinct Son) IndirectFollowers

From    T

Group By Ancestor

Order By Ancestor;

image

שימו לב שהתוצאות של כל קודקוד כוללות אותו עצמו.

מה קורה אם יש חלילה לולאה אין סופית?
ניצור בזדון לולאה על ידי כך שנקשר את D ל-A ואזי ABDA וגם ACBDA יהיו כאלו:

Insert

Into    T_Tree

Values    ('D','A');

image

ננסה שוב לפרוש את הרשת באופן רקורסיבי:

With    T As

(Select Member Ancestor,

        Member Father,

        Member Son,

        1 Level,

        Cast(Member As Varchar(Max)) Path

From    T_Members

Union All

Select    T.Ancestor,

        T.Son,

        Tr.Follower,

        T.Level+1 Level,

        Cast(T.Path+','+Tr.Follower As Varchar(Max))

From    T

Inner Join T_Tree Tr

        On T.Son=Tr.Followed)

Select    *

From    T

Order By Ancestor,

        Father,

        Son;

image

הודעת השגיאה מלמדת שה-Level גדול מ-100, “קצת מוזר” שזה קורה ברשת כזו קטנה (אנחנו כבר מבינים שהמערכת נכנסה ללולאה אין סופית, אך מעמידים פני תם), ולכן נצרף את ה-Hint שמסיר את המגבלה הזו (MaxRecursion):

With    T As

(Select Member Ancestor,

        Member Father,

        Member Son,

        1 Level,

        Cast(Member As Varchar(Max)) Path

From    T_Members

Union All

Select    T.Ancestor,

        T.Son,

        Tr.Follower,

        T.Level+1 Level,

        Cast(T.Path+','+Tr.Follower As Varchar(Max))

From    T

Inner Join T_Tree Tr

        On T.Son=Tr.Followed)

Select    *

From    T

Order By Ancestor,

        Father,

        Son

Option (MaxRecursion 0);

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

With    T As

(Select Member Ancestor,

        Member Father,

        Member Son,

        1 Level,

        Cast(Member As Varchar(Max)) Path

From    T_Members

Union All

Select    T.Ancestor,

        T.Son,

        Tr.Follower,

        T.Level+1 Level,

        Cast(T.Path+','+Tr.Follower As Varchar(Max))

From    T

Inner Join T_Tree Tr

        On T.Son=Tr.Followed

        And ','+T.Path+',' Not Like '%,'+Tr.Follower+',%')

Select    *

From    T

Option (MaxRecursion 0);

image

אפשר לראות שהתוצאות השתנו ונוספו שורות חדשות, כמו למשל שורה 10 ECBDA, וצריך להיות ברור שיש כאן בעייה.

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

הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

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

תגובה אחת

  1. יהונתן23/03/2015 ב 22:16

    אחלה פוסט על CTE רקורסיבי. יפה מאוד!

    הגב