UA MATH567 高維統計III 隨機矩陣7 亞高斯矩陣的應用：Stochastic Block Model與社區發現

我們來介紹亞高斯矩陣的一個應用：評估社區發現算法的效率。Community detection in networks是一個比較重要的非監督學習問題，這一講我們用Stochastic Block Model (SBM)來描述一個網絡：

假設這個網絡有$n$個節點，網絡中有兩個社區，它們的規模相當，各擁有$n/2$個節點，記這兩個社區為$C_1,C_2$，我們用$G(n,p,q)$表示這個隨機網絡，其中$p$表示某條邊連接的兩個點屬于同一個社區的概率，$q$表示某條邊連接的兩個點屬于不同社區的概率，假設$p>q$，用$A$表示這個網絡的伴隨矩陣，顯然它是一個隨機矩陣，
$$\begin{gathered} P(A_{ij}=1|i,j\in C_{1}ori,j\in C_2)=p \\ P(A_{ij}=1|i\in C_1,j\in C_{2}ori\in C_2,j\in C_1)=q \end{gathered}$$

Community detection in networks試圖回答的問題是尋找一種分割：
$$C_1?C_2=\{1,2,?,n\}$$

使得$C_1,C_2$分別包含兩個不同社區中的節點。

---

簡單分析

我們可以將$A$分解為它的期望與殘差矩陣：
$$A=E[A]+R$$

其中
$$E[A]=?\begin{array}{cc}\stackrel{C_1}{p?p}& \stackrel{C_2}{q?q}\\ p?p& q?q\\ q?q& p?p\\ q?q& p?p\end{array}?$$

不妨假設$n$是一個偶數，顯然$rankE[A]=2$，它有兩個特征值與對應的特征向量：$$\begin{gathered} {\lambda }_1=\frac{n(p+q)}{2},{\lambda }_2=\frac{n(p?q)}{2} \\ {u}_1=\frac{1}{\sqrt{n}}?\begin{array}{c}1\\ 1\\ ?\\ 1\\ 1\end{array}?,u_2=\frac{1}{\sqrt{n}}?\begin{array}{c}1\\ 1\\ ?\\ ?1\\ ?1\end{array}? \end{gathered}$$

其中$u_2$有$n/2$個$1$，$n/2$個$?1$，$u_2$是一個非常重要的值，對于一般情況，如果一個隨機網絡中有兩個社區，那么它的期望的$u_2$的符號可以指示節點的社區。于是Community detection in networks的目標是給定一個某個隨機矩陣的樣本數據集，要還原隨機矩陣的期望的特征向量。

在一般情況下，我們無法算出$E[A]$，但我們可以對$A$做類似的分解：
$$A=D+R$$

其中$D$表示確定性的部分，$R$代表隨機性，假設$R$是亞高斯矩陣，則
$$\begin{gathered} \Vert D\Vert ={\lambda }_1～n \\ P(\Vert R\Vert \le CK(\sqrt{n}+t))\ge 1?4e^{?t^2} \end{gathered}$$

這說明signal $D$比噪聲$R$更強得多，比如取$t=\sqrt{n}$，則
$$P(\Vert R\Vert \le 2CK\sqrt{n})\ge 1?4e^{?n}$$

顯然$\Vert D\Vert$的階比$\Vert R\Vert$大，接下來我們要做的分析是這個隨機噪聲會對社區發現的結果造成怎樣的影響。

---

攝動方法(perturbation method)
研究一個小噪聲矩陣對確定性矩陣的影響，我們可以使用攝動方法，下面先介紹一些需要的結論：

Weyl不等式 對于任意兩個矩陣$S,T$
$$\underset{i}{\max }|{\lambda }_i(S)?{\lambda }_i(T)|\le \Vert S?T\Vert$$

證明
$?x\in S^{n?1}$，根據三角不等式，
$${\Vert Sx\Vert }_2\le {\Vert Tx\Vert }_2+{\Vert (S?T)x\Vert }_2\le {\Vert Tx\Vert }_2+\Vert S?T\Vert$$

根據Courant-Fischer minimax定理
$$\begin{gathered} {\lambda }_i(S)=\underset{dimE=i}{\max }\underset{x\in S(E)}{\min }{\Vert Sx\Vert }_2 \\ \le \underset{dimE=i}{\max }\underset{x\in S(E)}{\min }{\Vert Tx\Vert }_2+\Vert S?T\Vert \le {\lambda }_i(T)+\Vert S?T\Vert \\ ?{\lambda }_i(S)?{\lambda }_i(T)\le \Vert S?T\Vert \end{gathered}$$

類似地，
$${\lambda }_i(T)?{\lambda }_i(S)\le \Vert S?T\Vert$$

總結

以上是生活随笔為你收集整理的UA MATH567 高维统计III 随机矩阵7 亚高斯矩阵的应用：Stochastic Block Model与社区发现 问题描述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。