1、圖劃分

詳細(xì)

Min-cut

圖G=(V,E)，V為節(jié)點(diǎn)集合，E為邊集，尋找一個(gè)劃分，使得劃分的各個(gè)分量之間的連邊權(quán)重之和最小。

Min Cut的問題

• 平凡解

  所有節(jié)點(diǎn)劃分到同一個(gè)分量中

  解決辦法：指定K

• 不均衡解

  劃分的各個(gè)分量，大小差異大

  解決辦法：限制分量大小

Min Cut的擴(kuò)展：Ratio-cut， Normalized-cut

圖劃分求解算法

• 局部方法：KL算法

  目標(biāo)：尋找圖的最優(yōu)兩路劃分

  第一步：構(gòu)造初始劃分C=C1+C2

  第二步：從C1中選擇一個(gè)節(jié)點(diǎn)a，從C2中選擇一個(gè)節(jié)點(diǎn)b，交換a和b可以使cutC減小，則交換

  重復(fù)第二步直至cutC不再減小

• 全局方法：譜劃分

  譜聚類的基本思想便是利用樣本數(shù)據(jù)之間的相似矩陣（拉普拉斯矩陣）進(jìn)行特征分解（ 通過Laplacian Eigenmap 的降維方式降維），然后將得到的特征向量進(jìn)行 K-means聚類。

2、社區(qū)發(fā)現(xiàn)

識別出網(wǎng)絡(luò)中“內(nèi)部連接緊密、與外部連接稀疏”的節(jié)點(diǎn)組。

和圖劃分的區(qū)別

• 圖劃分

  按照任務(wù)需求對網(wǎng)絡(luò)進(jìn)行劃分

  劃分的分量數(shù)通常已知

  各個(gè)分量彼此不重疊

• 社區(qū)發(fā)現(xiàn)

  尋找網(wǎng)絡(luò)固有的結(jié)構(gòu)規(guī)則

  社區(qū)個(gè)數(shù)通常未知

  社區(qū)可以重疊、嵌套

GN算法：基于邊介數(shù)的算法 詳細(xì)

步驟1：計(jì)算每條邊的介數(shù)

步驟2：刪除介數(shù)最大的邊

模塊度

詳細(xì)

回答的問題：什么樣的網(wǎng)絡(luò)劃分是一個(gè)好劃分？

直觀認(rèn)識：內(nèi)部連邊多、外部連邊少

模塊度的性質(zhì)：

取值范圍：-1和1之間值越大，劃分質(zhì)量越好

可加性：社區(qū)上的定義和節(jié)點(diǎn)上的定義一致

社區(qū)發(fā)現(xiàn)問題變成了模塊度優(yōu)化問題

給定一個(gè)網(wǎng)絡(luò)，尋找該模塊度最大的劃分

這是一個(gè)NP-hard問題，可使用多中優(yōu)化算法

• 模塊度優(yōu)化算法示例-局部優(yōu)化

初始化：每個(gè)節(jié)點(diǎn)屬于一個(gè)社區(qū)

步驟1，對于每個(gè)節(jié)點(diǎn)，判定加入其鄰居節(jié)點(diǎn)所屬的社區(qū)是否可以增加模塊度，如果能夠增加，加入使模塊度增加最大的社區(qū)，直到所有節(jié)點(diǎn)所屬的社區(qū)都不再變動為止

步驟2，將每個(gè)社區(qū)視為一個(gè)節(jié)點(diǎn)， 構(gòu)造新網(wǎng)絡(luò)

重復(fù)上述步驟至模塊度不再增加

InfoMap

兩級哈夫曼編碼

案例

3、圖建模

• 非負(fù)矩陣分解

• 隨機(jī)塊模型