מודל בלוקים סטוכסטי

מודל בלוקים סטוכסטי (Stochastic block model) הוא שם כולל למשפחת מודלים סטוכסטיים שפותחה לראשונה בשנת 1983 על ידי פול ו. הולנד ועמיתיו . מודלים אלו משמשים לניתוח רשתות ולתיאור מבנה רשתות על ידי חלוקתן לבלוקים או קהילות, בהם בדרך כלל ההסתברות להימצאות קשתות בין צמתים בתוך אותה קהילה גבוהה יותר בהשוואה לקשתות בין צמתים מקהילות שונות.

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

הגדרה

מודל בלוקים סטוכסטי $SBM(n,p,W)$ עבור גרפים מקריים לא מכוונים מוגדר על ידי הפרמטרים הבאים:

• $n\in \mathbb {N}$ מציין את מספר הצמתים בגרף.
• $p=(p_{1},p_{2},...,p_{k})$ הוא ווקטור הסתברויות מעל הקבוצות $[k]:=\{1,...,k\}$ כאשר $k\in \mathbb {N}$ הוא מספר הקהילות בגרף.
• מטריצת הסתברויות הקהילות $W\in [0,1]^{k\times k}$ מתארת את ההסתברויות לקיומה של קשת בין כל שתי קהילות. במילים אחרות, ההסתברות לקיומה של קשת בין צומת מקהילה $i$ לקהילה $j$ היא $W_{ij}$ .

המודל הסטטיסטי

בהינתן זוג $(X,G)$, שבו $G=(V,E)$ הוא גרף ו-$X$ הוא ווקטור. נאמר שהזוג נדגם מתוך $SBM(n,p,W)$, אם מתקיימים התנאים הבאים:

• $X$ הינו ווקטור $n$ ממדי, כאשר כל אחת מהכניסות שלו מכילה ערכים מעל $\{1,...,k\}$, ומתפלגת באופן זהה ובלתי תלוי (i.i.d) בשאר הכניסות, בהתאם לווקטור ההסתברויות $p$.
• הגרף $G=(V,E)$ מכיל $n$ צמתים, כאשר ההסתברות לקיומה של קשת בין הצומת ה-$i$ לצומת ה-$j$ היא $W_{X_{i}X_{j}}$, וההסתברויות עבור כל זוג צמתים הן בלתי תלויות.

הקהילות בגרף

קהילות בגרף יוגדרו באופן הבא: $C_{i}=\{v\in V:X_{v}=i\}$ עבור כל $i\in [n]$.

התפלגויות

עבור $x\in [k]^{n},e\in \{0,1\}^{n \choose 2}$, מתקיים

התפלגות הקהילות

$\mathbb {P} (X=x):=\prod _{i=1}^{n}p_{x_{i}}=\prod _{i=1}^{k}p_{i}^{|C_{i}|}$

התפלגות הקשתות בהינתן הקהילות

$\mathbb {P} (E=e|X=x):=\prod _{1\leq u<v\leq n}W_{x_{u},x_{v}}^{e_{uv}}(1-W_{x_{u},x_{v}})^{1-e_{uv}}=\prod _{1\leq i\leq j\leq k}W_{i,j}^{N_{ij}(x,e)}(1-W_{i,j})^{N_{ij}^{c}(x,e)}$

כאשר:

• $N_{ij}(x,e):=\sum _{u<v,x_{u}=i,x_{v}=j}\mathbb {I} \{e_{uv}=1\}$
• $N_{ij}^{c}(x,e):=\sum _{u<v,x_{u}=i,x_{v}=j}\mathbb {I} \{e_{uv}=0\}=|C_{i}||C_{j}|-N_{ij}(x,e),\quad i\neq j$
• $N_{ii}^{c}(x,e):=\sum _{u<v,x_{u}=i,x_{v}=i}\mathbb {I} \ \{e_{uv}=0\}={\frac {|C_{i}|(|C_{i}|-1)}{2}}-N_{ii}(x,e)$

מקרים מיוחדים

• כאשר מטריצת ההסתברויות $W$ היא קבועה, כלומר $W_{ij}=p$ לכל זוג $i,j$, מדובר במקרה פרטי של מודל הבלוקים הסטוכסטי הידוע כמודל ארדש-רני (Erdős–Rényi Model). במודל זה, קיומן של קהילות אינו משמעותי, שכן ההסתברות שכל צומת יתחבר לכל צומת אחר היא תמיד זהה.

• כאשר במטריצת ההסתברויות $W$ ערכי האלכסון קבועים ושווים ל- $p$ והערכים מחוץ לאלכסון קבועים שווים ל- $q$, אזי ההסתברות לקיומה של קשת בין צמתים בתוך אותה קהילה שווה ל-$p$, ואילו ההסתברות לקיומה של קשת בין קהילות שונות שווה ל-$q$. במקרה שבו $p>q$, המודל מכונה מודל אסורטטיבי (Assortativity); במקרה ההפוך, שבו $p<q$, המודל נקרא מודל דיסאסורטטיבי. שם נוסף למודל זה בספרות הינו The Planted Partition Model.
• מודל שבו $W_{ii}>W_{jk}$ עבור כל $j\neq k$ מכונה מודל אסורטטיבי חזק, כלומר כל ערכי האלכסון גדולים יותר מכל הערכים שמחוץ לאלכסון.
• מודל שבו $W_{ii}>W_{ij}$ עבור כל $i\neq j$ מכונה מודל אסורטטיבי חלש, שבו כל ערך באלכסון דומיננטי יותר מכל הערכים באותה השורה והעמודה שלו בלבד.

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

בעיות סטטיסטיות נפוצות

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

זיהוי (Detection)

הבעיה הראשונה היא זיהוי, שבו המטרה היא לקבוע האם לגרף נתון יש מבנה סמוי של קהילות (latent community structure), או באופן שקול, האם הגרף נדגם מאיזשהי התפלגות פריורית מעל מודל בלוקים סטוכסטי (Stochastic Block Model), או האם הוא נדגם מעל מודל ארדש-רני (Erdős–Rényi Model) .

שיחזור חלקי (Partial Recovery)

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

שחזור מלא (Exact Recovery)

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

שימושים נפוצים

מספר אלגוריתמים פותחו כדי לזהות קהילות במודלים של בלוקים סטוכסטיים (SBMs), או הותאמו כדי לפתור בעיות כאלו, כאשר כל אחד מנצל טכניקות מתמטיות שונות. סיווג ספקטרלי משתמש בווקטורים העצמיים של מטריצת השכנויות או ה-Laplacian של הגרף כדי לזהות קהילות. מקסום מודולריות, שמיושם לרוב באמצעות אלגוריתם Louvain, ממקסם פונקציית מודולריות שמשווה את הצפיפות של קצוות הקהילות לגרפים אקראיים. Belief Propagation מעדכנת באופן איטרטיבי את הסבירות של צמתים להשתייך לקהילות ספציפיות על ידי העברת הודעות בין צמתים שכנים. Expectation-Maximization (EM) היא גישה הסתברותית מתחפלת, בה נעריך את הקשר של הצמתים לקהילות על פי המידע הנתון (מידע חלקי), לבין מקסום הסבירות של הגרף הנצפה תחת ה-SBM. שיטות מבוססות Likelihood, כגון נראות מקסימלית ומיקסום ההסתברות הפוסטריורית , מעריכות את שיוך הקהילות על ידי אופטימיזציה של הסבירות או ההסתברות הבייסיאנית של ה-SBM. לבסוף, שיטות מבוססות למידת עמוקה (Deep Learning-Based Methods), כגון רשתות (Graph Neural Networks - GNNs), הלומדות embeddings של צמתים דרך ארכיטקטורות המותאמות לנתוני גרפים, מה שמאפשר גילוי קהילות גמיש וניתן להרחבה במודלים מורכבים ורועשים. אלגוריתמים אלו מהווים את הבסיס לטכניקות המודרניות לגילוי קהילות ב-SBMs .

דוגמה לשימוש בקוד

ניתוח רשתות ניתן לבצע במגוון שפות תכנות, כאשר אחת הפופולריות ביותר היא פייתון. בדוגמה הבאה נעשה שימוש בשלוש חבילות מרכזיות לניתוח רשתות ומחקר: NetworkX, scikit-learn ו-NumPy. בנוסף, ויזואליזציה של הנתונים תתבצע באמצעות החבילה המוכרת Matplotlib.

import networkx as nx
import matplotlib.pyplot as plt
from sklearn.cluster import SpectralClustering
import numpy as np

def spectral_clustering_on_graph(G, num_clusters):
    # יצירת מטריצת שכנויות
    adjacency_matrix = nx.to_numpy_array(G)

    # אתחול אלגוריתם Spectral Clustering
    sc = SpectralClustering(
        n_clusters=num_clusters,
        affinity='precomputed',
        assign_labels='kmeans',
        random_state=42
    )

    # התאמת הנתונים וחיזוי תוויות הקהילות
    labels = sc.fit_predict(adjacency_matrix)
    return labels

תחילה, ניצור גרף מקרי, המכיל 30 צמתים, תוך שימוש במטריצת הסתברויות הבאה: $W={\begin{pmatrix}0.9&0.2&0.2\\0.2&0.9&0.2\\0.2&0.2&0.9\\\end{pmatrix}}$.

המשמעות היא שההסתברות לקשת בין צמתים בתוך אותה קהילה היא $0.9$, ואילו ההסתברות לקשת בין צמתים מקהילות שונות היא $0.2$.

# שלב 1: יצירת גרף SBM
sizes = [10, 10, 10] # מספר הצמתים בכל בלוק
# הסתברויות לקיום קשתות בתוך ובין הבלוקים
probs = [[0.9, 0.2, 0.2], 
         [0.2, 0.9, 0.2],
         [0.2, 0.2, 0.9]]

G = nx.stochastic_block_model(sizes, probs, seed=42)
spectral_clustering_on_graph(G, 3)

להלן תוצאת האלגוריתם המיושמת על הגרף שנוצר:

תוצאת אלגוריתם Spectral Analysis על גרף אקראי שנוצר באמצעות מודל בלוקים סטוכסטי בעל שלוש קהילות

ראו גם

• תורת הרשתות
• ניתוח רשתות חברתיות
• ניתוח אשכולות ספקטרלי

קישורים חיצוניים

• ספר הנקרא High-Dimensional Probability ונכתב על ידי רומן ורשין [1].
• תיעוד של stochastic_block_model בסיפרייה Networkx כולל דוגמאות [2].
• תיעוד של Spectral Clustering בחבילה scikit-learn.