里奇流與網路社群偵測
偵測網路中的社群(community)是圖論的一個重要課題，這樣的課題可以應用到網際網路、社群網路、疾病偵測，當然也包含了大腦的神經網路、細胞的蛋白質合成網路等。過去在網路社群的偵測有許多方法─標籤傳遞(label propagation)、隨機行走(random walk)、還有模組化(modularity)、資訊圖(infomap)等。來自yahoo、Stony brook和南加大的學者們，同時間將拓樸學上的工具─里奇流(Ricci flow)應用到了社群偵測上，並開發出python上的套件[4]，分別發表了兩篇文章在科學報告(Scientific Report)上[1-2]。
里奇流描述著在黎曼幾何(Riemann geometry)中，流形(manifold)會怎麼樣隨著時間變形，以此研究此流形的拓樸性質(topology)，簡單的範例可參考圖一[1]。這個工具在2002年的時候被用來證明龐加萊猜想。簡單來說，里奇流有點像是描述氣球被我們用手戳凹，放開時，氣球凹處會凸回去，這樣的幾何變化。
 |
| 圖一、里奇流。左圖為流形的案例，右圖為兩個網路的案例。當曲率為負的位置，彼此會遠離，曲率為正的位置，彼此會靠近，最終經由「手術」可以切斷成不同的社群[1]。 |
而要描述里奇流的方向和強度，還需要有曲率這個參數，Oliver以Wasserstein distance描述網路中兩點間的曲率，進而將曲率從黎曼幾何推廣到了圖論上，以圖二為例[3]。
 |
| 圖二、資訊從x流動到y。左圖因為x, y各來自不同community，且此二community只有他們相連，因此curvature為負的。右圖則相反，curvature為正的[3]。 |
Wasserstein distance又稱為泥土搬運距離(earth mover’s distance)。其目的是計算兩個分布對應時的最小距離，讀者可想成是A地有三個土坑，B地有兩個土堆，要怎麼樣搬運才能花費最小的代價把B地的土堆填到A地的土坑。此花費就是Wasserstein distance。
總結來說，作者將此方法應用到網路分析當中，最終成功偵測出社群的結構[1-2]，圖三[1]、圖四[2]。
 |
| 圖三、Ricci Flow讓網路結構改變[1,5]。 |
 |
| 圖四、以Oliver Ricci Curvature進行社群偵測[2]。 |
撰稿者：強敬哲 Jerry Charng
1. Ni, C. C., Lin, Y. Y., Luo, F., & Gao, J. (2019). Community detection on networks with ricci flow. Scientific reports, 9(1), 1-12.
2. Sia, J., Jonckheere, E., & Bogdan, P. (2019). Ollivier-ricci curvature-based method to community detection in complex networks. Scientific reports, 9(1), 1-12.
3. Fournier, N. Graph-based Methods for Brain Structural Connectivity Analysis.
6. Ricci Flow介紹:
留言
張貼留言