圖數(shù)據(jù)管理與挖掘-第三講 社區(qū)發(fā)現(xiàn)算法 北京大學(xué)2021暑期-鄒磊教授
PART I: Community Detection Algorithm
社區(qū)發(fā)現(xiàn)算法，本質(zhì)是聚類方法。
一、傳統(tǒng)方法：層次聚類
【先不考慮社區(qū)之間overlapping的情況】
距離的定義：1. 獨(dú)立路徑條數(shù)；2. 加權(quán)平均距離
怎么度量分得好不好？
modularity（模塊化程度？）
社區(qū)內(nèi)有多少條邊-同e同v情況下的隨機(jī)圖上有多少條邊的期望
怎么理解？就是實(shí)際情況邊數(shù)越大越像是個(gè)社區(qū)（
二、中心度和社區(qū)結(jié)構(gòu)
邊的中心度（betweenness）：某條邊所通過(guò)的最短路徑的數(shù)量
連接社區(qū)之間的邊會(huì)有較高的中心度，刪去這些邊得到的子圖就是不錯(cuò)的社區(qū)了
算法巧妙，但是低效率（任何兩點(diǎn)之間的最小路徑實(shí)際上就很耗復(fù)雜度了）
三、Clique Percolation（可重合社區(qū)的發(fā)現(xiàn)）
社區(qū)發(fā)現(xiàn)希望子圖能夠盡可能接近c(diǎn)lique
有可能重復(fù)，引入X(v)集合記錄已經(jīng)考慮過(guò)的結(jié)點(diǎn)
k-clique社區(qū)算法：
- 找到所有極大團(tuán)
- 根據(jù)團(tuán)的大小、分享結(jié)點(diǎn)的情況等信息，建立一個(gè)矩陣
- 根據(jù)k進(jìn)行矩陣轉(zhuǎn)換和壓縮，得到0-1矩陣
- 得到的獨(dú)立部分就與k-clique社區(qū)等價(jià)
每個(gè)節(jié)點(diǎn)都至少含k個(gè)連接的最大子圖， “剝洋蔥”，去掉degree小的部分
用k-core可以削去原始圖中的非核心部分，從而極大減小圖的規(guī)模，使用k-clique算法后再還原原始圖
遍歷、迭代。
根據(jù)鄰居在哪個(gè)社區(qū)進(jìn)行劃分
===
PART II: Community-Affiliation Graph
該算法基于圖生成模型
圖生成：Model to Network
社區(qū)關(guān)系：Network to Model to Communities
===
PART III: Community Search
每一步不斷去掉一個(gè)點(diǎn)（考慮當(dāng)前G中degree最小的點(diǎn)），直到：要么
- 當(dāng)前query nodes set里的節(jié)點(diǎn)已經(jīng)不再連通
- 意圖刪除的下一個(gè)節(jié)點(diǎn)是query node
此時(shí)得到的G_t并不是所需的結(jié)果。
過(guò)程中得到的各個(gè)G_s中包含Q的強(qiáng)連通分量的有最小度的結(jié)點(diǎn)，其所對(duì)應(yīng)的G_s即為G_{opt}
使得子圖中的每條邊都包含至少(k-2)個(gè)子圖內(nèi)部的三角形的最大子圖
邊的支持度（在多少個(gè)三角形中）
子圖trussness，邊trussness
優(yōu)點(diǎn)：半徑固定，連通性強(qiáng)，參數(shù)少，多項(xiàng)式時(shí)間復(fù)雜度
====
PART IV: Graph Partition
可以用來(lái)為超大圖劃分（圖計(jì)算分布式場(chǎng)景下切分任務(wù)）
