基于標簽傳播算法的Web社區發現研究

閻海玲　周瑞　袁春艷

摘要：標簽傳播算法是社區發現的經典算法，優點是思路簡單，快速高效；缺點是隨機性強，每次迭代結果不一致，準確率不高。Web系統是一個由超文本鏈接構成的巨大的信息源，將改進的標簽傳播算法用于Web社區發現，有助于快速在大量的Web頁面中發現有利用價值的信息。

關鍵詞：標簽傳播；Web；社區發現

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2018）02-0254-03

Research on Web Community Detection Based on Label Propagation Algorithm

YAN Hai-ling，ZHOU Rui，YUAN Chun-yan

（XingZhi College of Xian University of Finance and Economics，Xi'an 710038，China ）

Abstract：Label propagation algorithm is a classical method for community detection， it's advantage is high efficiency and simplicity， it's disadvantage is strong randomness and low accuracy quality because the results of iteration every time are inconsistent. Web system is a huge information source that made up of hypertext links. It's useful in that it uses improved label propagation algorithm on Web community detection.

Key words：label propagation；Web；community detection

客觀世界可以看成是復雜的網絡系統，是由形態各異的子系統構成。每一個子系統表現出社區結構的特性。在客觀世界中，不同的社區結構表示不同的內容，具有不同的含義。例如人際關系網中，相識的關系密切的朋友可以劃分為同一個社區；在生物學系統網中，相同功能的組織單位可以劃分為一個社區。對社區發現的研究，可以在不同領域獲取可靠有價值的信息。近年來，社區研究的主要方法劃分為四大類：圖分割方法、W-H算法、層次聚類法以及標簽傳播算法[1]。

其中標簽傳播算法具有簡單、高效的特點，但是準確性有待于提高。其主要原因在于在選取節點的鄰接點時隨機選取，這種隨機性導致計算結果不一致，從而導致社區劃分的準確性降低。針對標簽傳播算法的缺點，研究者們提出了多種改進的方法。在標簽傳播基本算法的基礎之上提出了多種基于標簽傳播算法的新思路。

1 標簽傳播算法

標簽傳播算法（Label Propagation Algorithm，LPA）的基本思想就是相似的數據應該具有相同的標簽，具有相同標簽的數據劃分為同一個社區。也即一個節點應該和它的大多數鄰接點劃分為同一個社區。將網絡看做是一個無向圖，首先給圖中每一個節點隨機分配一個唯一的標簽（初始時可以認為每一個節點就是一個單獨的社區），然后將一個節點的標簽更新為所有鄰接點的標簽中數量最多的那個標簽，最終標簽相同的節點劃分為同一社區結構。

標簽傳播算法是基于圖的，將網絡系統轉化為圖進行研究。將所有的數據構建成一個圖，每一個數據點就是圖中的一個節點，假設這個圖是全連接的，包含已標注過的和未標注的兩種數據。節點v和節點w的邊表示他們的關聯度。給每個節點隨機分配一個標簽以代表它所屬的社區，遍歷圖中每一個節點，將每一個節點的標簽更新為它的所有鄰接點中標簽數目最多的那個標簽，如果數目最多的標簽同時存在多個，則在其中隨機選擇一個進行更新，最終同一標簽的節點劃分為同一個社區結構。每一個節點的標簽取決于它鄰接點的標簽：假設節點v的鄰接點有v1至zk，將v的標簽更新為v1至vk 中標簽數目最多的那個標簽。也即v的鄰接點中哪個社區的標簽最多，v就屬于哪個社區。標簽傳播算法時間復雜度接近線性：對圖中每個節點分配標簽的時間復雜度為O（n），每次迭代時間為O（ m），劃分出所有社區的復雜度為O（n +m）。

標簽傳播算法詳細步驟：

①初始時，給每個節點隨機分配一個唯一的標簽（每個節點是一個單獨的社區）；

②用每個節點的鄰接點的標簽中最多的標簽來更新自身的標簽。

③反復執行步驟②，直到每個節點的標簽穩定不再發生變化為止。

圖1為只有4個節點的單個社區標簽傳播的過程，首先為4個節點隨機分配 A、B、C、D 四個不同的標簽（初始時認為4個節點各自屬于一個社區），而后隨機選取節點B進行更新，節點B在3個鄰居標簽中隨機更新為標簽A。然后選擇節點C，節點C的鄰居節點中只有一個頻率最高的標簽A，其標簽更新為A，最后節D點的三個鄰接點標簽均為A，則節點D的標簽也更新為A。此時，所有節點均劃分為同一社區，算法結束。

2 幾種改進的基于標簽傳播的非重疊社區發現算法

針對傳統的標簽傳播算法的準確性低下的特點，眾多研究者在傳統標簽算法的基礎上進行了改進。如：宋琛的基于隨機游走相似度矩陣的改進標簽傳播算法，引入隨機游走的算法計算節點間的相似度，得到衡量節點間相似度的矩陣，然后選擇相似度最高的鄰接點傳播，從而達到提高準確性的目的；張素智、孫嘉彬、王威等提出的基于節點聚集系數的分布式標簽傳播算法，在標簽更新過程中引入節點聚類系數，提出一種結合MapReduce分布式計算框架的社區發現算法——DisLPA算法，提高了準確率同時改善了計算瓶頸問題。李磊，倪林提出了基于模塊度優化的標簽傳播社區發現算法——LPAMP。該算法降低了標簽傳播算法的隨機性，增強了穩定性，并且提高了準確率。張超，武先強，董榮勝在現有的基于相干鄰居親近度的標簽傳播算法中，引入節點間依賴度，提高了社區發現的準確性，減少了標簽傳播過程花費的時間。徐成林，陳志剛，黃瑞等人在標簽傳播過程中綜合考慮節點重要性以及鄰居標簽的數量提出LRDC，顯著地提高了社區發現的準確性和穩定性。endprint

以上改進的標簽傳播算法，主要是針對在標簽傳播過程中，對于某一個節點，當其鄰接點的標簽最多的個數不唯一時，隨機選一個。這種隨機性導致每次迭代結果不一致，降低了社區發現的準確性。針對這種不確定性，在算法中引入某種衡量的參數，更新節點的標簽時，若該節點的鄰接點的最多標簽數目有多個時，不再是隨機選取一個標簽進行傳播，而是根據衡量的參數值來選取，從而提高了算法的準確性和穩定性，社區結構的質量也就隨之提高。

3 Web社區發現相關的基本概念

Web作為一個巨大的信息源，其內容和形式多種多樣，并沒有一個完全統一的規格和模式。正是由于具有這樣的特點，人們起初認為Web頁面是無結構數據。但是隨著互聯網的迅速發展和Web資源的急速擴充，對Web網絡研究的逐漸深入，人們意識到Web資源應該是介于結構化和無結構數據之間，屬于半結構化數據。按照不同的標準劃分，可以劃分為不同的社區。在Web社區發現過程中需要注意以下幾種特殊含義的頁面：噪音頁面、權威頁面和中心頁面。

噪音頁面，如果一個Web頁面的內容和Web社區的主題不相關，則把這個頁面稱之為噪音頁面。噪音頁面越少，社區質量越高。

權威頁面：人們普遍公認在某一個主題上具有權威性的頁面。當一個Web頁面的設計者在該頁面上創建指向另一個頁面的超鏈接是，可以認為該設計者對另一頁面的認可。如果一個Web頁面被不同的Web頁面設計者認可，則可以從某一角度說明該頁面的重要性，從而發現權威頁面。一個權威頁面很少讓它的超鏈接指向其相同領域競爭者的頁面。

中心頁面：指向權威頁面的超鏈接集合的頁面。一個好的中心頁面指向很多好的權威頁面。而一個好的權威頁面被很多好的中心頁面所指向。

中心頁面與權威頁面之間相輔相成互相增強的關系有助于權威頁面的發現以及高質量Web社區的發現。

4 改進的標簽傳播算法在Web社區發現的應用

Web社區是互聯網中客觀存在的Web頁面集合，通過Web社區的發現，可以有效地發現與某一主題密切相關的Web頁面集合。設Web社區G有n個節點和m條邊，將每一個Web頁面設定為一個節點，頁面間的超鏈接設定為邊。鏈接到該頁面的Web頁面個數為入度，該頁面鏈接的其他頁面的個數為出度。由此得出一個有向加權圖。

首先給出有向圖的形式化定義：

其形式化定義為：

G=（V ，E）

V={x|x∈DataObject}，E={| v，w∈V∧p（v，w）}

P（v，w）表示從頂點v到頂點w有一條直接通路。若 ∈E（G） ，表示從頂點v到頂點w有一條弧。其中：v稱為弧尾（tail）或始點（initial node），w稱為弧頭（head）或終點（terminal node） 。

圖中n個節點構建一個n×n的矩陣，通過節點之間的邊傳播標簽。邊的權值越大，表示兩個節點越接近，該節點的標簽越容易傳播。

將標簽傳播算法用于Web社區發現時，可以考慮從兩個方面進行改進：分別在初始化過程中和在標簽傳播過程中。改進思路如下：

①標簽初始化過程

在標簽初始化過程中，可以給節點或邊添加權重，將無向圖轉化為有向網描述節點的傳播優先級，可以初步確定社區中心節點從而提高社區劃分的質量。

②標簽傳播過程

在標簽傳播過程中，可以對標簽選擇的隨機性進行改進。將Web頁面內容的相似度或者超鏈接的點擊率作為衡量的參數來計算邊的權值，描述節點的傳播優先度，然后選取權值最大的鄰接點進行標簽傳播。例如在基于隨機游走相似度矩陣的改進標簽傳播算法中，將Web頁面內容的相似度或者超鏈接的點擊率作為節點間的相似度，選取相似度最高的鄰接點進行標簽傳播。

5 結束語

隨著Internet的迅速發展，Web資源朝著多元化、復雜化方向飛速增長，但是對于用戶來說只有很小一部分具有使用價值。因此，從復雜的Web系統資源中發現有利用價值的Web社區顯得尤為重要。嘗試將改進的標簽傳播算法用于Web社區發現，進一步完善Web社區發現的理論基礎，提高Web社區發現的質量特性，促進復雜網絡理論的發展完善，其理論基礎可以推廣到其他復雜網絡的社區發現。

參考文獻：

[1] 宋琛，張賢坤，費松，等.基于隨機游走相似度矩陣的改進標簽傳播算法[J].計算機應用與軟件，2016，33（08）：269-272.

[2] 張素智，孫嘉彬，王威.基于節點聚集系數的分布式標簽傳播算法[J].計算機應用與軟件，2016，33（04）：125-128+142.

[3] 李磊，倪林.基于模塊度優化的標簽傳播社區發現算法[J].計算機系統應用，2016， 25（09）：212-215.

[4] 張超，武先強，董榮勝.一種改進的基于相干鄰居親近度的標簽傳播算法[J].廣西科學院學報，2017，33（01）：12-18.

[5] 徐成林，陳志剛，黃瑞，等.用于社區發現的LPA_LRDC標簽傳播算法[J].小型微型計算機系統，2017，38（08）：1746-1750.

[6] 張金增.一種改進的Web社區挖掘算法[D].鄭州大學，2009.