שְׁאֵלָה:
כיצד לבצע איתור קהילה ברשת חברתית / גרף משוקלל?
laramichaels
2010-09-21 20:50:46 UTC
view on stackexchange narkive permalink

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

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

האם יש אלגוריתמים ספציפיים שאני צריך להסתכל עליהם?

שמונה תשובות:
#1
+20
Petr
2010-09-21 22:20:48 UTC
view on stackexchange narkive permalink

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

תודה רבה על שציינת לי את זה, החמצתי לחלוטין את ההתייחסות למשקולות בתיעוד.
#2
+10
chl
2010-09-21 22:45:49 UTC
view on stackexchange narkive permalink

אני יודע ש Gephi יכול לעבד גרף משוקלל לא מכוון, אבל נראה לי שאני זוכר שיש לאחסן אותו ב GDF, שהוא די קרוב ל- CSV או ל- Ucinet DL. שים לב שזה עדיין שחרור אלפא. כעת, לגבי אשכול הגרף שלך, נראה שלגפי חסרים צינורות אשכולות, למעט האלגוריתם MCL הזמין כעת בגרסה האחרונה. היה פרויקט קוד גוגל בשנת 2009, סטטיסטיקה של רשת גפי (הכוללת למשל את מדד המודולריות של ניומן), אבל אני לא יודע אם משהו פורסם בכיוון הזה. בכל מקרה, נראה שזה מאפשר חישובי מודולריות / אשכולות כלשהם, אך ראו גם ניתוח רשתות חברתיות באמצעות R ו- Gephi ו הכנת נתונים לניתוח רשתות חברתיות באמצעות R ו- Gephi ( תודה רבה ל- @ Tal).

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

כדאי גם להסתכל על INSNA - תוכנת ניתוח רשתות חברתיות או על דף האינטרנט של טים אוונס על רשתות מורכבות ומורכבות א>.

שלום לך, רק כדי ליידע אותך שגפי לא יכול להתמודד עם גרף לא מכוון משוקלל כדי לזהות קהילה באמצעות מודולריות. תודה. גאוטם
@Gautam טוב לדעת, תודה. אני לא ממש מכיר את גפי, אבל חשבתי שהוא נמצא בהתפתחות פעילה.
#3
+8
Seb
2010-10-14 12:15:50 UTC
view on stackexchange narkive permalink

ג'פי מיישם את שיטת Louvain Modularity: http://wiki.gephi.org/index.php/Modularity

תרועות

@Seb יש יישומים ב- R שאתה מכיר?
#4
+5
Seb
2012-02-25 22:01:11 UTC
view on stackexchange narkive permalink

אלגוריתם המודולריות של Louvain זמין ב- C ++: https://sites.google.com/site/findcommunities/

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

אלגוריתם המודולריות של Louvain הוא מהיר ויציב , אני תוהה אם יש גרסה להפחתת מפה שלו.
#5
+4
kingledion
2018-01-15 18:14:55 UTC
view on stackexchange narkive permalink

אם אתה משתמש בפייתון ויצרת גרף משוקלל באמצעות NetworkX, תוכל להשתמש ב פיתון-לובין לצורך אשכולות.כאשר G הוא גרף משוקלל:

  קהילת ייבוא
מחיצה = community.best_partition (G, weight = 'weight')
 
#6
+2
Jacques Wainer
2010-09-27 06:33:46 UTC
view on stackexchange narkive permalink

בדיוק נתקלתי בחבילת ה- tnet עבור R. נראה כי היוצר חוקר גילוי קהילה בגרפים משוקללים ודו-צדדיים (דו-מצביים).

http://opsahl.co .uk / tnet / content / view / 15/27 /

עדיין לא השתמשתי בו.

#7
+2
Reihaneh
2010-10-09 02:42:44 UTC
view on stackexchange narkive permalink

יש לי יישום של java עבור רשת שאינה חופפת, משוקללת / לא משוקללת, שיכולה כנראה להתמודד עם 3 מיליון צמתים (בדקתי אותה עבור מערך מיליון צומת). עם זאת, זה עובד כמו k- פירוש, וצריך לזהות את מספר המחיצות כקלט (k ב kmeans). תוכלו למצוא מידע נוסף כאן, והנה הקוד, ב- github

לחיים,

#8
+2
Jerry
2013-01-24 11:05:59 UTC
view on stackexchange narkive permalink

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

https://sites.google.com/site/communitydetectionslpa/

ראה סקירה נחמדה arxiv.org/abs/1110.5813 למידע נוסף



שאלה ותשובה זו תורגמה אוטומטית מהשפה האנגלית.התוכן המקורי זמין ב- stackexchange, ואנו מודים לו על רישיון cc by-sa 2.0 עליו הוא מופץ.
Loading...