1笨篷、圖劃分
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)
識(shí)別出網(wǎng)絡(luò)中“內(nèi)部連接緊密担钮、與外部連接稀疏”的節(jié)點(diǎn)組。
和圖劃分的區(qū)別
-
圖劃分
按照任務(wù)需求對(duì)網(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ù)最大的邊
模塊度
回答的問題：什么樣的網(wǎng)絡(luò)劃分是一個(gè)好劃分箫津？
直觀認(rèn)識(shí)：內(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)化算法示例-局部?jī)?yōu)化
初始化：每個(gè)節(jié)點(diǎn)屬于一個(gè)社區(qū)
步驟1，對(duì)于每個(gè)節(jié)點(diǎn)田炭，判定加入其鄰居節(jié)點(diǎn)所屬的社區(qū)是否可以增加模塊度师抄，如果能夠增加，加入使模塊度增加最大的社區(qū)诫肠，直到所有節(jié)點(diǎn)所屬的社區(qū)都不再變動(dòng)為止
步驟2司澎，將每個(gè)社區(qū)視為一個(gè)節(jié)點(diǎn)， 構(gòu)造新網(wǎng)絡(luò)
重復(fù)上述步驟至模塊度不再增加
InfoMap
兩級(jí)哈夫曼編碼
3栋豫、圖建模
非負(fù)矩陣分解
隨機(jī)塊模型
