標簽傳播算法在社會網絡中的應用研究

摘 要： 近年來，社會網絡簇結構挖掘取得了長足的進展，廣泛應用在社會網、生物網和萬維網等領域中。如何挖掘社會網絡中各種潛在結構和信息成為研究熱點。標簽傳播算法是一種能夠利用少量已標記節點的標簽信息去預測大量的未標記節點的標簽的半監督學習算法。介紹了標簽傳播算法理論，給出了標簽算法的特點，總結了標簽傳播算法在社會網絡中的應用及發展趨勢。

關鍵詞： 標簽傳播； 社區發現； 社會網絡

中圖分類號： TP301 文獻標識碼： A 文章編號：2095-2163（2013）03-0037-04

Applied Research of Label Propagation Algorithm in Social Network

LUO Qiubin， ZHU Hong， LI Yunhui， CONG Eryong

（College of engineering， Harbin University， Harbin 150086， China）

Abstract： In the recently years， detecting communities of social networks has made considerable progress， has been widely applied in the social networks， World Wide Web， biological networks and many other fields. How to tap the potential structure and information in social networks has been known as hotspot.The label propagation algorithm （LPA） is a graph-based semi-supervised learning algorithm， which can predict the information of unlabeled nodes by a few of labeled nodes. This paper introduces the theoretical study of label propagation algorithm， provides its characteristics， and summarizes its applications and trends of developments in social network.

Key words： Label Propagation； Community Discovery； Social Network

0 引 言

在Web2.0技術高度普及的信息化時代，人們利用互聯網去查找、發布和共享信息，通過這種交互信息方式實現個人交際圈的延伸和擴展。從數據挖掘觀點來看，社會網絡是由圖表示的個體關系的數據集。圖中的節點表示網絡中的對象或者個體，圖中的邊線表示網絡中對象之間的聯系或者相互作用的連接關系；節點和邊都可以帶有屬性，可以具有類標號，鏈接一般是單向的但不必是二元的，這種表示圖一般很大。顯然，圖論中的圖為社會網絡的研究提供了一種直觀表現形式[1]。半監督學習（Semi-Supervised Learning， SSL）是一種將監督學習和無監督學習相結合的方法，其主要思想是：基于數據分布上的模型假設，利用少量的已標注數據進行指導并預測未標注數據的標記，再整合歸并至標記的數據集中[2]。標簽傳播算法[3]（label propagation algorithm， LPA）是由Zhu于2002 年提出，就是一種基于圖的半監督學習方法，其基本思路是用已標記節點的標簽信息去預測未標記節點的標簽信息。

本文簡要介紹了該算法的基本理論和特點，分析了其在社會網絡中的主要應用，討論其優缺點，并給出了可能的發展方向。

1 標簽傳播算法

1.1 基本理論

標簽傳播算法利用樣本間的關系，建立關系完全圖模型，在完全圖中，節點包括已標注和未標注數據，其邊表示兩個節點的相似度，節點的標簽按相似度傳遞給其他節點，標簽數據就像是一個源頭，可以對無標簽數據進行標注，節點的相似度越大，標簽越容易傳播。由于該算法簡單易實現，執行時間短，復雜度低且分類效果好，引起了國內外學者的廣泛關注和積極投入，并將其廣泛地應用到多媒體信息分類、虛擬社區挖掘等各類熱點領域中。

根據LPA 算法基本理論，每個節點的標簽按相似度傳播給相鄰節點，在節點傳播的每一步，每個節點根據相鄰節點的標簽來更新自己的標簽，與該節點相似度越大，其相鄰節點對其標注的影響權值越大，相似節點的標簽越趨于一致，其標簽就越容易傳播。在標簽傳播過程中，保持已標注數據的標簽不變，使其如一個源頭般將標簽傳向未標注數據。最終，當迭代過程結束時，相似節點的概率分布也趨于相似，可以劃分到同一個類別中，從而完成標簽傳播過程[3]。

1.2 算法描述

具體算法如下。

令（x1，y1）…（x1，y1）是已標注數據，YL={y1…yl}∈{1…C}是類別標簽，類別數C已知，且均存在于標簽數據中。令（xl+1，yl+1）…（xl+u，yl+u）為未標注數據，YU={yl+1…yl+u}不可觀測，l≤u，令數據集X={x1…xl+u}∈RD。問題由此轉化為：從數據集X 中，利用YL的學習，為未標注數據集YU的每個數據找到對應的標簽。實現過程為：

首先，將所有數據作為節點（包括已標注和未標注數據），創建一個完全連接圖，其邊的權重計算公式如下：

wij=exp-d2ijσ2=exp-∑Dd=1（xdi-xdj）2σ2

（1）

其中，dij表示任意兩個節點的歐氏距離，權重wij受控于參數σ。

為衡量一個節點的標注通過圖中某邊傳播到其他節點的概率，在此定義一個（l+u）*（l+u）概率傳遞矩陣T ，矩陣元素Tij的計算公式如下：

Tij=P（j→i）=wij∑l+uk=1wkj

（2）

其中，Tij是節點j 到i的傳播概率。

同時，定義一個（l+u）×C的標注矩陣Y，令Yic=δ（yi，c）。其中，第i行表示節點yi的標注概率，第c列表示類別，若Yic=1，則表示節點yi屬于c類別，否則為0。

通過概率傳遞，使其概率分布集中于給定類別，再通過邊的權重值來傳遞節點標簽。矩陣Y 的初始值并不重要，但是要確保其中每行都實現了標準化。具體描述如表1所示。

表1 LPA算法描述

Tab.1 The Label Propagation Algorithm description

LPA算法描述

輸入： u 個未標注數據， l 個標注數據及其類別C 。

輸出： u 個未標注數據的標注。

第一步，初始化，利用公式（1）計算邊權重矩陣wij，得到數據間的相似度。

第二步，根據上式得到的wij，利用公式（2）計算節點j 到i 的傳播概率。

第三步，定義一個（l+u）×C維的標注矩陣Y。

第四步，每個節點按傳播概率將其周圍節點傳播的標注值按權重相加，并更新自己的概率分布：

Fij=∑l+u k=1Tij， 1≤i≤l+u； 1≤j≤C

（3）

第五步，限定已標注數據，將已標注數據的概率分布重新賦值為初始值。重復步驟四，直至收斂。

Fij=Yij，1≤i≤l；1≤j≤C

（4）

1.3 標簽傳播算法的特點第3期 羅秋濱，等：標簽傳播算法在社會網絡中的應用研究 智能計算機與應用 第3卷

LPA是一種半監督學習算法，只需利用少量的訓練標簽作為指導，利用未標注數據的內在結構、分布規律和鄰近數據的標記，即可預測和傳播未標記數據的標簽；無論數據分布的具體形狀，都能通過標簽傳播，將其歸并到同一個類。因此，可以處理包括音頻、視頻、圖像及文本在內的各類標注、檢索及分類，而且具有算法簡單，執行速度快，可擴展性強，有效性好等一系列優點。社會網絡組織形式豐富多樣，需要處理的數據包括短文本、音頻、視頻等綜合類別，這使得LPA在社會網絡領域具有良好的針對性和適應性。

2 標簽傳播算法在社會網絡中的應用

2.1 社會網絡分析的基本概念

社會網絡分析（ Social Network Analysis 簡稱為SNA） 是適應社會結構和社會關系的研究需要順應發展起來的一種分析方法。社會網絡指的是由多個結點（ 一組社會行動者） 以及各結點之間的連線（行動者之間的關系） 組成的集合。通常可用于描述和測量行動者之間的關系或通過這些關系流通的各種有形及無形的東西，比如信息、資源等。

在真實世界中，復雜網絡在整體上呈現著一些基本統計特性，譬如：“小世界效應”是指復雜網絡具有短路徑長度和高聚類系數的特點[4]；“無標度特性”，是指復雜網絡中的結點之度服從冪率分布特征[5]。“社區結構特性”，是指復雜網絡中普遍存在著“同一社區內部的結點相互連接緊密、而不同社區間的結點相互連接稀疏”的特點[6]。

2.2 應用于社區發現

社區挖掘研究對于分析復雜網絡的拓撲結構、理解復雜網絡的功能、發現復雜網絡中的隱性規律以及預測復雜網絡的行為具有著重要的理論意義，呈現了廣闊的應用前景。自從2002年Girven和Newman[6] 提出社區挖掘的概念至今，新的理論方法層出不窮，新的應用領域與日俱增。社區結構是復雜網絡最重要的拓撲特性之一。當今社會網絡中，發現社區結構有助于理解用戶分布和用戶行為。

標簽傳播算法在社區發現中有較多應用。2007 年，Raghavan 等[7]首次提出將LPA 應用于社區發現，該算法簡稱為RAK 算法。其主要思想是利用網絡結構作為指導來探測社區結構，每個節點可初始化為一個獨特的標簽，并在每一步迭代中，其節點標簽選定為該節點為其大多數鄰近節點的標簽，并在這個重復進行的過程中，密集連接的節點組由一個獨特標簽變換成一個具有共識的社區節點，那些具有相同標簽的節點便組合構成了同一個社區。該算法的流程包括：初始化、標簽更新、添加具有相同標簽的頂點歸屬于同一個社區。而且算法通過在空手道俱樂部網和美國大學橄欖球網的相應實驗，結果表明其社區檢測效果良好。此后，很多學者都展開了相關方面的深入研究，不斷改進RAK 算法，使之更好地應用于社區發現。

Barber [8]等為了避免LPA 中所有頂點都分配到同一社區，改進RAK 算法，提出一種模塊化標簽傳播算法（Modularity-specialized label propagation algorithm， LPAm），即基于約束的LPA 監測網絡社區。給定一個目標函數，使得LPA 受到約束，引入一個變量使其社區的模塊度值實現最大化，將社區發現問題轉化為目標函數最優化的求解問題。在具有相同標簽彼此連接的頂點個數基礎上，定義一個目標函數H，利用LPA 算法發現H 函數的局部最優值。

Liu等[9]針對上述LPAm 易在模塊空間中陷入局部極大值，從而導致社區檢測不準確的問題，提出將LPAm與多步貪婪凝聚算法（Multi-step Greedy Agglomerative Algorithm，MSG）相融合，設計了一種模塊化、專業化的標簽傳播算法（ Modularity-specialized label propagation algorithm， LPAm+）。該算法利用MSG 同時合并多個相似社區，能夠避免陷入局部最大值，更加精準地進行網絡社區檢測。

2.3 應用于語義網

SemTagP[10]算法是對LPA算法的擴展。與LPA算法中傳播隨機分配的標簽不同，SemTagP算法中為用戶分配的標簽是用戶自身使用的標簽，且在傳播過程中進一步考慮了標簽的泛化關系。通過這種傳播方式，能夠將擁有具體標簽的成員劃歸到同一上位詞標簽構成的社區中。語義標簽傳播過程如圖1所示。

圖1 語義標簽傳播示意圖

Fig.1 Semantics Label Propagation

由圖1可見，其中的sport為football、golf、swim、rugby的上位詞，program為Java、Python、Lisp的上位詞，且右圖中同一底色的節點均在同一社區內。

算法將社會網絡當作有向圖處理，但卻未做加權分析。同時，算法僅考慮了標簽間的語義關系，而未充分開發用戶交互關系的語義信息，例如通過用戶交互關系的類型或親密程度來評價用戶間的影響力。

ISLPA[11]算法仍使用語義標簽作為傳播對象，與SemTagP算法不同，ISLPA算法在傳播過程中并不檢測標簽間的語義關系，而是根據標簽的語義關系和網絡社區劃分的尺度要求，在標簽傳播前預先對標簽進行統一的語義處理。在語義標簽傳播更新過程中，算法將在線社會網絡抽象為有向加權圖，圖中節點表示用戶，邊表示用戶交互關系，邊的權值表示某種交互關系對應的影響力。在不同交互關系下的鄰居節點具有不同的影響力，因此要根據用戶交互關系為邊賦予權值。根據邊的連接關系和邊的權值大小為每個節點生成一個候選標簽列表，標簽列表含有語義標簽及其對應的分數。各個節點選擇對應列表中分數最大的標簽，更新原有標簽。算法迭代運行，直到節點的標簽不再變化時，算法終止。

LPA-SNA[12]算法在原始 LPA 算法的基礎上，當待更新節點的大部分鄰居節點所屬的簇結構不止一個，即該節點的鄰接子系統不唯一時，基于節點屬性相似度的標簽傳播算法（LPA-SNA）將計算每個鄰接子系統中節點屬性的平均值，進而計算待更新節點與各鄰接子系統的屬性相似度，同時選取可令相似度MaxSimi（si，SNir）最高的子系統的標簽作為當前節點的標簽。算法以網絡結構為主要依據的同時，又考慮了節點屬性信息，對大規模數據集網絡進行聚類，一定程度上克服了原始LPA 算法的隨機策略，提升了算法的聚類速度，也提高了網絡劃分質量。

2.4 應用于推薦系統

互聯網技術的迅猛發展帶來了信息爆炸。而個性化推薦系統通過建立用戶與信息產品之間的二元關系，利用已有的選擇過程或相似性關系挖掘每個用戶潛在感興趣的對象，進行個性化推薦，其本質就是實現信息過濾。個性化推薦系統不僅在社會經濟中具有重要的應用價值，而且也是一個值得重點研究的科學問題。

標簽推薦系統依據其推薦策略可分成基于內容的標簽推薦系統、協同標簽推薦系統、基于圖的標簽推薦系統。其中，基于圖的標簽推薦系統是將用戶、資源、標簽三者的關系構成三維的圖結構，利用圖結構進行標簽推薦[13]。有代表性的是FolkRank[14]，其主要思想采用了重要性傳遞理論。重要的用戶采用了重要的標簽所標注的資源，意味著該資源也是重要的，同理，標注在重要資源上的標簽，該標簽也是重要的。基于此思想，標簽系統中資源、用戶、標簽三者的關系將通過這種方式互相增強，形成了完全的三維關系圖結構，采用基于圖遍歷的算法即可完成標簽推薦，常見的推薦思想是采用隨機走算法在關系確定的圖結構中為用戶確定推薦的標簽。

2.5 其他應用

個性化社會標簽是社會網絡一系列算法的研究實現基礎。標簽傳播算法還可以應用于網頁的重要度排序，可擴展到垃圾信息的屏蔽、信任評價等；另一方面，標簽傳播算法也可以合并遷移學習，進行情感分類方面的研究。

3 結束語

社會網絡的研究還剛起步，很多領域還有待進一步地開拓與研發。LPA是一種通用的半監督學習新方法，能夠利用少量已標注節點預測未標記節點的標簽信息，該算法在理論和實際應用中表現了眾多的優越性能。本文介紹了LPA在社會網絡研究中的基本應用，包括社區發現、語義網、推薦系統等。隨著研究的深入，LPA算法在社會網絡中的應用將得到進一步深化與發展。

參考文獻：

[1]張林安. 多關系社會網絡社區挖掘方法研究[D]. 哈爾濱：哈爾濱工程大學，2011.

[2]張俊麗，常艷麗，師文.標簽傳播算法理論及其應用研究綜述[J].計算機應用研究， 2013， 30（1）：21-25.

[3]ZHU X J， GHAHRAMANI Z. Learning from labeled and unlabeled data with label propagation： Technical Report CMU-CALD-02-107[R]. Pittsburghers， USA： Carnegie Mellon University， 2002.

[4]WATTS D J， STROGATZ S H. Collective dynamics of small-world networks[J]. Nature， 1998， 393 （6638）： 440-442.

[5]BARABASI A L， ALBERT R. Emergence of scaling in random networks[J]. Science， 1999， 286（5439）： 509-512.

[6]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of National Academy of Science， 2002， 9（12）： 7821-7826.

[7]RAGHAVAN U N， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E， 2007， 76：1-12.

[8]BARBER M J. Detecting network communities by propagating labels under constraint[EB/OL]. （2011-6-18），[2012-3-28]. http：//arxiv.org/ abs/0903.31-38.

[9]LIU X， MURATA T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks. [EB/OL].（2010-3-19）.[2012-5-1] http：//arxiv.org/pdf/0910.1154.pdf