一、社團結構的描述

如上圖，每個社團內部的節點之間的連接相對較為緊密，各個社團之間的連接相對來說比較稀疏。
生活中許多實際網絡都具有較為明顯的社團結構。
社團結構分析與計算機科學中的圖分割和社會學中的分級聚類等有著密切的關系。圖分割問題的一個實際例子是并行計算，找到這類分割問題的精確解是一個NP難題，當圖的規模很大時不存在有效解法。分級聚類是尋找社會網絡中社團結構的一類傳統算法。它基于各個節點之間連接的相似性或者強度，把網絡自然的劃分為各個子群。根據向網絡中添加邊還是從網絡中移除邊，這類算法又可以分為兩類：凝聚方法和分裂方法。

二、模塊度

模塊度的基本想法是把劃分社團后的網絡與相應的零模型進行比較，以度量社團劃分的質量。
所謂與一個網絡對應的零模型，就是指與該網絡具有某些相同的性質而在其它方面完全隨機的隨機圖模型。
下面來介紹度模塊的概念。
對于一個給定的實際網絡，假設找到了一種社團劃分，那么所有社團的內部的邊數的總和可計算如下：

其中A=（a${}_{ij}$）是實際網絡的鄰接矩陣，C${}_i$與C${}_j$分別表示節點i和節點j在網絡中所屬的社團：如果這兩個節點屬于同一個社團，$\delta$取值為1，否則$\delta$取值為0。
對于與該實際網絡對應的一個相同規模的零模型，如果用相同的社團劃分，那么所有社團內部的邊數總和的期望值為：

其中p${}_{ij}$是零模型中節點i和節點j之間的連邊數的期望值。
一個網絡的模塊度就定義為該網絡的社團內部邊數與相應的零模型的社團內部邊數之差占整個網絡邊數M的比例，即

在理論上，對于與原網絡具有相同度序列但不具有度相關性的一個常用零模型：配置模型，我們有p${}_{ij}$=k${}_i$k${}_j$/(2M)，k${}_i$與k${}_j$分別為原網絡中節點i和節點j的度。因此，常用的模塊度定義為：

其中

B=b(${}_{ij}$)${}_{N\times N}$也稱為模塊度矩陣。
實際網絡數據通常包含的是節點之間的連邊信息，而不會直接給出各個節點的度值。為此，下面給出模塊度的一種更便于實際計算的形式。
記e${}_{vw}$為社團v和社團w之間的連邊占整個網絡邊數的比列，有：

記a${}_v$為一端與社團v中節點相連的連邊的比列，則有：

注意到

于是度模塊定義也可以寫為：

上式意味著，只要根據網絡連邊數據統計出每個社團v內部節點之間的連邊數占整個網絡邊數的比例e${}_{vv}$，以及一端與社團v中節點相連的連邊的比例a${}_v$，就可計算出模塊度。

三、加權和有向網絡的模塊度

模塊度公式可以直接推廣到加權網絡情形，只需把邊數用邊的權值之和代替，節點度值用節點強度代替，從而有：

其中，W是網絡中所有邊的權值之和，s${}_i$是節點i的強度，即與節點i相連的所有邊的權重和，w${}_{ij}$是網絡中節點i與節點j之間的連邊的權值。s${}_i$s${}_j$/2W是相應的零模型中節點i與節點j之間的連邊的期望的權值。W${}_c$是社團C內部所有邊的權重和，S${}_c$是所有與社團C內部的點相關聯的邊的權重和。
注意到對于具有M條邊的無向網絡，鄰接矩陣的非零元素的個數為2M，并且所有節點的度值之和為2M；對于具有M條邊的有向網絡，鄰接矩陣的非零元素的個數為M，并且所有節點的入度(出度)之和為M。因此，無向網絡的模塊度公式推廣到有向情形可表示為；

其中k${}_i^{out}$、k${}_i^{in}$分別表示節點i的出度和入度。
把上面兩個式子結合，就得到一般的加權網絡的模塊度公式：

其中，s${}_i^{out}$、s${}_i^{in}$分別表示節點i的出強度和如強度。

總結

以上是生活随笔為你收集整理的社团结构与模块度的全部內容，希望文章能夠幫你解決所遇到的問題。

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