劉應興的部落格

隨機圖形 (Random graph)，或隨機網絡圖，這裡指的是有固定 n 個節點 (nodes)，節點之間是否有連線 (edges 或 arcs) 具有隨機性的圖形。有些時候節點間的連線可以多條，也可以是連回自身的，但這裡只考慮不同節點間的無向或對稱連線連線，而且不考慮重複連線。因此，n 個節點的圖，最多 n(n-1)/2 條連線。節點 i, j 之間是否有連線以 X(i,j) 表示。兩相異節點之間可通過其他節點而相連，稱之為兩節點之間的一條路徑 (path), 也就是：存在 k_1,...,k_m 使 X(i,k_1),X(k_m,j) 及 X(k_i,k_(i+1)) 都是 1。如果任兩相異節點之間都有一條路徑，這樣的圖形是連通的 (connected)。這樣的隨機圖形可以說是靜態的隨機圖形，所有可能的 n(n-1)/2 條節點連線確定其值為 0 或 1 之後，圖形就確定不變了，也就是說：這裡考慮的一個隨機圖形是

頂點集 V = {1, 2, ..., n} 和隨機變數群 A = {X(i,j); i, j = 1,..., n, i < j}

組成的 (V, A) 組合，而其實現值或觀測值是一個確定的網絡圖。另有一種隨機圖形是動態的產生節點連線，除非這個過程停止，這個隨機圖都只是一個中間產物而不能確定其形狀，這可以說是一個動態的隨機圖。例如，由一個節點，例如 1 開始，以 1/n 機率決定下一個節點  X(1)（允許連到自身），然後再決定下一個節點 X(2) = X(X(1))，以此類推, X(k) = X(X(k-1))，序列 (1, X(1), ..., X(k), ...) 構成一個動態的隨機圖。無論靜態或動態的隨機圖形都可能有許多不同的隨機方式，例如有一種 ER 模型是考慮 M 個邊（M 條節點間連線）的各種圖出現的機率都相同；這樣的圖也可用動態的描述

前面文章提過友誼詭論  (friendship paradox)，說一個人的平均朋友數，平均來說，少於其朋友的平均朋友數。Wiki 有數學解釋，不過這裡可以用隨機圖形簡單的理解：假設所有 X(i,j)（i, j 是朋友）都是 i.i.d. Bernoulli(p), 則第 i 個人（節點 i）的平均朋友人數是

f(i) = E[Σ_{j≠i} X(i,j)] = (n-1)p

假設 j 是他的一個朋友，則在 i, j 是朋友的條件下，j 的平均朋友數是

f(j|i) = E[Σ_{k≠j} X(k,j) | X(i,j) = 1] = 1 + E[Σ_{k: j≠k≠i} X(k,j)] = 1 + (n-2)p

顯然 (n-1)p < 1 + (n-2)p，不是因為有些人特別有人緣或特別長袖善舞造成的假象，也不是真假友誼的問題。當然，假設 X(i,j) i.i.d. 可能與現實不符，那只是簡化假設以便於理解；較符現實地，假設 X(i,j) = 1 的機率是 p(i,j)，則

f(i) = Σ_{j≠i} p(i,j)

而其朋友 j 的平均朋友數是

f(j|i) = 1 + Σ_{k: j≠k≠i} p(k,j) = 1-p(i,j) + Σ_{k: j≠k} p(k,j)

即 f(j) 加上 1-p(i,j)。如果

Σ_{k: j≠k} p(k,j) =  Σ_{j: j≠i} p(i,j)

也就是 f(j) = f(i)，那麼 f(j|i) 比 f(i) 平均高了 1-p(i,j)。當然，在允許 p(i,j) 不是常數 p 時，也意謂對特定 i, j, 上列等式一般是不成立的，因為在真實世界，總有些人比較容易交到朋友，有些人則不善於交往。但以上結果表明：即使你的朋友沒有比你會交朋友，但在你們已經是朋友的情況下，你的朋友的期望朋友數理當比你多；如果你的朋友人緣更好些，那他的朋友多於你就更理所當然了。

以上是假設所有 X(i,j) 是相互獨立的，如果相互並不獨立，則

　　f(j|i) = 1 + Σ_{k: j≠k≠i} E[X(k,j) | X(i,j)=1] = 1 + Σ_{k: j≠k≠i} p'(k,j)

其中 p'(k,j) = P[X(k,j) = 1 | X(i,j)=1] 可能比無條件機率 p(k,j) = P[X(k,j) = 1] 高也可能低，當全部或部分 p'(k,j) 低於 p(k,j) 時，就很難說 f(j|i) 比 f(j) 高或低了。不等式 p'(k,j) ＜ p(k,j) 表示由於 (i,j)  友誼的存在，使得 (k,j) 存在友誼的機率降低。真實的社會可能有些 p'(k,j) < p(k,j)，有些則相反。所謂物以類聚人以群分，(i,j) 會成立友誼關係，則本來與 j 有希望成立友誼關係的 k，其 p'(k,j) 不會小於 p(k,j)；而 p(k,j) 小的，p'(k,j) 也可能更小。總體而言可能

Σ_{k: j≠k≠i} E[X(k,j) | X(i,j)=1]  不小於 Σ_{k: j≠k≠i} E[X(k,j) ]

因此，友誼詭論的現象遠是會存在。

如果把 X(i,j) 合寫成一個對稱矩陣 X 其中 X(j,i) = X(i,j), X(i,i) = 0，也就是說 X 就是本文考慮的隨機圖形的節點連線矩陣表示，或說是此隨機圖形的矩陣表現式。又令 Ei 是第 i 元素為 1 其餘元素為 0 的行向量；J 為 n 個元素都是 1 的行向量。則 X Ei 記載了所有 i 的朋友，J' X Ei 為其朋友數。所以

f(i) = E[J' X Ei],  f(j|i) = E[J' X Ej | Ej' X Ei = 1]

如果 E[J' X Ej | Ej' X Ei = 1] > E[J' X Ej | Ej' X Ei = 0]，則在 f(j) ≒ f(i) 的情形下，f(j|i) > f(i) 可以預期。又如果每個人的交友，雖非刻意，但總是自然而然地擴大友誼圈，那麼上列條件期望值的不等式是成立的，同時也意味著將呈現友誼詭論的結果。不過，f(j) ≒ f(i) 不一定成立，上列條件不等式也不是定律，因此從期望值來說，一個人的期望朋友數也不一定低於朋友的平均期望朋友數，當然實際朋友數也不一定低於朋友的朋友數。只是，基於物以類聚、志趣相投的現象，f(j) ≒ f(i) 及上述條件期望值的不等關係可能是一個友誼網絡圖的主流現象，因此呈現友誼詭論現象也就很自然了。