Community detection using boundary nodes in complex networks 閱讀筆記

05-16

來自專欄每周一篇機器學習論文筆記

作者：Mursel Tasgin and Haluk O. Bingol

來源：arxiv

原文網址：https://arxiv.org/pdf/1802.09618.pdf

轉載請註明出處：

每周一篇機器學習論文筆記?

zhuanlan.zhihu.com

註：以下文章包括原paper內容和筆記作者個人理解，如有錯誤或出入請指正。

Abstract

在本篇文章中，作者提出了一種新的局部社區發現演算法，能夠通過邊界節點來識別邊界線，進而發現網路中的社區結構。作者使用了一種改進版本的標籤傳播演算法來進行社區發現，按照文中介紹，該演算法速度快且效果好，並且可拓展為並行實現。

Introduction

我們生活中，有許許多多的系統是由網路構成的，如社交網路、蛋白質網路等等。而社區指的是網路中內部節點間連接緊密且與外部其他節點連接較為稀疏的結構。對於現有的社區發現演算法來說，因為時間複雜度高的原因，所以它們大多無法用於大型的網路。對於大型網路，局部社區發現演算法就能比較適用，因為它們只是使用網路中的局部信息來進行社區發現，這樣就大大減小了演算法的複雜度。

在本文中，作者提出了一種新的社區發現演算法，這個演算法使用了局部方法，試圖使用邊界節點來識別出社區邊界線，進而做到社區的劃分。

Background

這一部分主要只講一些跟本文演算法直接相關的東西。

一些標記符號：

- 無權圖 $G=<V,E>$

- $V = {v_1, v_2, ..., v_n}$ 表示節點集

- $E = {e_{i,j}}$ 表示邊集

三角關係

在社區發現中，三角關係發揮著非常重要的作用。在文中，作者使用了兩種跟三角形有關的規則，第一種是聚類係數，第二種是公共鄰居數。

聚類係數：

分子是節點i所處的三角形個數，分母是節點i和其所有鄰居可能組成的所有三角形個數

公共鄰居數：

節點i和節點j鄰居的交集的個數

Interior Node(內部節點)：所有的鄰居節點和它自己都在同一個社區中的節點。

Boundary Node(邊界節點)：不是內部節點的節點就是邊界節點。

Related Work

因為這篇文章中也有用到標籤傳播的思想，也算是一篇改進類論文，所以需要在這介紹一下標籤傳播的鼻祖：LPA(label propagation algorithm)。

LPA演算法的思想和步驟其實很簡單：首先我們假設每個節點就是一個社區，所以每個社區都給予一個標籤；進入迭代過程，每個節點統計出其鄰居節點中出現次數最高的標籤，並把自己的標籤改成這個標籤，有那麼一點從眾的意思，如果出現多個標籤出現次數相同，則隨機選一個就可以；一直迭代，直到演算法收斂即可。

LPA演算法非常簡單，但是卻在社區發現領域非常經典，這是因為它只需要用到自己和自己鄰居的節點信息就可以完成演算法，所以效率會比較高，在社區發現效果還可以接受的情況下，這種局部社區發現演算法是比較適合用來處理大規模網路的。

Algorithm

先直接上演算法流程：

初始化：將每個節點假定為一個數量為1的社區，因為所有的節點標籤都不一樣，所以所有的節點都是邊界節點，將所有節點加入boundary list中。（這個跟LPA一樣）
Initial heuristic(初始合併)：使用簡單高效的方法對各個社區進行一輪合併，這一步也可以跟LPA的迭代步一樣，用鄰居的次數最高標籤來進行社區的合併。這一步主要是想減少社區數，加速後面的迭代。
迭代過程：（當boundary list為空時停止迭代）

從boundary list中隨機選擇一個節點，並在boundary list中刪除該節點。
在選中節點的鄰居中選出能使benefit score最高的社區標籤作為該節點的新標籤（benefit score會在下文介紹）
如果選中的節點更新標籤，檢查它的鄰居節點會不會在更新後變成邊界節點。如果是，則將它們加入boundary list（boundary list其實是一個集合，重複元素只會記錄一次）

從上面的流程可以看出，其實本文提出的演算法跟LPA的框架其實非常像，都是只用到了一階的鄰居，都是通過迭代到收斂。不同的地方是，本文的演算法是以boundary list為迭代對象和終止條件的；第二個不同的點就是使用了benefit score來進行社區選擇的衡量，使用不同的衡量標準可能會得到不同的benefit score，這可以讓這個演算法的表現擁有更多的可能性或側重。

benefit score：對於節點i的每個鄰居節點j，我們賦予一個值 $b_i(j)$ 作為benefit score。它代表的是當邊界節點i假設屬於社區j的收益。

對於計算benefit score的標準，文中作者一共提出了7種方法可以選擇：

獨立(Individually)，將每個鄰居節點都看作是一個候選項，選取 $b_i(j)$ 最大的節點的標籤作為更新節點的新標籤：

I-R：給每個鄰居一個0到1之間隨機值作為 $b_i(j)$
I-CC：使用聚類係數作為 $b_i(j)$
I-CN：使用公共鄰居數作為 $b_i(j)$

組(Group)，將相同標籤的鄰居節點合起來看作是一個候選標籤組，選取 $b_i(j)$ 之和最大的標籤組的標籤作為更新節點的新標籤：

G-R：鄰居中同標籤節點的I-R之和
G-CC：鄰居中同標籤節點的I-CC之和
G-CN：鄰居中同標籤節點的I-CN之和
G-1：令每個鄰居的 $b_i(j)=1$ ，並求鄰居中同標籤節點的 $b_i(j)$ 之和，這其實上就是LPA的標籤更新標準

Experiment

實驗部分可見原文。

尾巴

個人認為，這篇文章只是對LPA進行小改動，較為簡單，但是局部社區發現我覺得還是一個值得思考探索的方向，而且文中作者提出的基於邊界點進行迭代和多個衡量標準確實提供了更多的可能性，感覺這就是這篇文章的亮點。

堅持不易，點波關注吧~