閻海玲　周瑞　袁春艷

摘要：標(biāo)簽傳播算法是社區(qū)發(fā)現(xiàn)的經(jīng)典算法，優(yōu)點(diǎn)是思路簡單，快速高效；缺點(diǎn)是隨機(jī)性強(qiáng)，每次迭代結(jié)果不一致，準(zhǔn)確率不高。Web系統(tǒng)是一個由超文本鏈接構(gòu)成的巨大的信息源，將改進(jìn)的標(biāo)簽傳播算法用于Web社區(qū)發(fā)現(xiàn)，有助于快速在大量的Web頁面中發(fā)現(xiàn)有利用價值的信息。

關(guān)鍵詞：標(biāo)簽傳播；Web；社區(qū)發(fā)現(xiàn)

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：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

客觀世界可以看成是復(fù)雜的網(wǎng)絡(luò)系統(tǒng)，是由形態(tài)各異的子系統(tǒng)構(gòu)成。每一個子系統(tǒng)表現(xiàn)出社區(qū)結(jié)構(gòu)的特性。在客觀世界中，不同的社區(qū)結(jié)構(gòu)表示不同的內(nèi)容，具有不同的含義。例如人際關(guān)系網(wǎng)中，相識的關(guān)系密切的朋友可以劃分為同一個社區(qū)；在生物學(xué)系統(tǒng)網(wǎng)中，相同功能的組織單位可以劃分為一個社區(qū)。對社區(qū)發(fā)現(xiàn)的研究，可以在不同領(lǐng)域獲取可靠有價值的信息。近年來，社區(qū)研究的主要方法劃分為四大類：圖分割方法、W-H算法、層次聚類法以及標(biāo)簽傳播算法[1]。

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

1 標(biāo)簽傳播算法

標(biāo)簽傳播算法（Label Propagation Algorithm，LPA）的基本思想就是相似的數(shù)據(jù)應(yīng)該具有相同的標(biāo)簽，具有相同標(biāo)簽的數(shù)據(jù)劃分為同一個社區(qū)。也即一個節(jié)點(diǎn)應(yīng)該和它的大多數(shù)鄰接點(diǎn)劃分為同一個社區(qū)。將網(wǎng)絡(luò)看做是一個無向圖，首先給圖中每一個節(jié)點(diǎn)隨機(jī)分配一個唯一的標(biāo)簽（初始時可以認(rèn)為每一個節(jié)點(diǎn)就是一個單獨(dú)的社區(qū)），然后將一個節(jié)點(diǎn)的標(biāo)簽更新為所有鄰接點(diǎn)的標(biāo)簽中數(shù)量最多的那個標(biāo)簽，最終標(biāo)簽相同的節(jié)點(diǎn)劃分為同一社區(qū)結(jié)構(gòu)。

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

標(biāo)簽傳播算法詳細(xì)步驟：

①初始時，給每個節(jié)點(diǎn)隨機(jī)分配一個唯一的標(biāo)簽（每個節(jié)點(diǎn)是一個單獨(dú)的社區(qū)）；

②用每個節(jié)點(diǎn)的鄰接點(diǎn)的標(biāo)簽中最多的標(biāo)簽來更新自身的標(biāo)簽。

③反復(fù)執(zhí)行步驟②，直到每個節(jié)點(diǎn)的標(biāo)簽穩(wěn)定不再發(fā)生變化為止。

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

2 幾種改進(jìn)的基于標(biāo)簽傳播的非重疊社區(qū)發(fā)現(xiàn)算法

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

以上改進(jìn)的標(biāo)簽傳播算法，主要是針對在標(biāo)簽傳播過程中，對于某一個節(jié)點(diǎn)，當(dāng)其鄰接點(diǎn)的標(biāo)簽最多的個數(shù)不唯一時，隨機(jī)選一個。這種隨機(jī)性導(dǎo)致每次迭代結(jié)果不一致，降低了社區(qū)發(fā)現(xiàn)的準(zhǔn)確性。針對這種不確定性，在算法中引入某種衡量的參數(shù)，更新節(jié)點(diǎn)的標(biāo)簽時，若該節(jié)點(diǎn)的鄰接點(diǎn)的最多標(biāo)簽數(shù)目有多個時，不再是隨機(jī)選取一個標(biāo)簽進(jìn)行傳播，而是根據(jù)衡量的參數(shù)值來選取，從而提高了算法的準(zhǔn)確性和穩(wěn)定性，社區(qū)結(jié)構(gòu)的質(zhì)量也就隨之提高。

3 Web社區(qū)發(fā)現(xiàn)相關(guān)的基本概念

Web作為一個巨大的信息源，其內(nèi)容和形式多種多樣，并沒有一個完全統(tǒng)一的規(guī)格和模式。正是由于具有這樣的特點(diǎn)，人們起初認(rèn)為Web頁面是無結(jié)構(gòu)數(shù)據(jù)。但是隨著互聯(lián)網(wǎng)的迅速發(fā)展和Web資源的急速擴(kuò)充，對Web網(wǎng)絡(luò)研究的逐漸深入，人們意識到Web資源應(yīng)該是介于結(jié)構(gòu)化和無結(jié)構(gòu)數(shù)據(jù)之間，屬于半結(jié)構(gòu)化數(shù)據(jù)。按照不同的標(biāo)準(zhǔn)劃分，可以劃分為不同的社區(qū)。在Web社區(qū)發(fā)現(xiàn)過程中需要注意以下幾種特殊含義的頁面：噪音頁面、權(quán)威頁面和中心頁面。

噪音頁面，如果一個Web頁面的內(nèi)容和Web社區(qū)的主題不相關(guān)，則把這個頁面稱之為噪音頁面。噪音頁面越少，社區(qū)質(zhì)量越高。

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

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

中心頁面與權(quán)威頁面之間相輔相成互相增強(qiáng)的關(guān)系有助于權(quán)威頁面的發(fā)現(xiàn)以及高質(zhì)量Web社區(qū)的發(fā)現(xiàn)。

4 改進(jìn)的標(biāo)簽傳播算法在Web社區(qū)發(fā)現(xiàn)的應(yīng)用

Web社區(qū)是互聯(lián)網(wǎng)中客觀存在的Web頁面集合，通過Web社區(qū)的發(fā)現(xiàn)，可以有效地發(fā)現(xiàn)與某一主題密切相關(guān)的Web頁面集合。設(shè)Web社區(qū)G有n個節(jié)點(diǎn)和m條邊，將每一個Web頁面設(shè)定為一個節(jié)點(diǎn)，頁面間的超鏈接設(shè)定為邊。鏈接到該頁面的Web頁面?zhèn)€數(shù)為入度，該頁面鏈接的其他頁面的個數(shù)為出度。由此得出一個有向加權(quán)圖。

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

其形式化定義為：

G=（V ，E）

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

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

圖中n個節(jié)點(diǎn)構(gòu)建一個n×n的矩陣，通過節(jié)點(diǎn)之間的邊傳播標(biāo)簽。邊的權(quán)值越大，表示兩個節(jié)點(diǎn)越接近，該節(jié)點(diǎn)的標(biāo)簽越容易傳播。

將標(biāo)簽傳播算法用于Web社區(qū)發(fā)現(xiàn)時，可以考慮從兩個方面進(jìn)行改進(jìn)：分別在初始化過程中和在標(biāo)簽傳播過程中。改進(jìn)思路如下：

①標(biāo)簽初始化過程

在標(biāo)簽初始化過程中，可以給節(jié)點(diǎn)或邊添加權(quán)重，將無向圖轉(zhuǎn)化為有向網(wǎng)描述節(jié)點(diǎn)的傳播優(yōu)先級，可以初步確定社區(qū)中心節(jié)點(diǎn)從而提高社區(qū)劃分的質(zhì)量。

②標(biāo)簽傳播過程

在標(biāo)簽傳播過程中，可以對標(biāo)簽選擇的隨機(jī)性進(jìn)行改進(jìn)。將Web頁面內(nèi)容的相似度或者超鏈接的點(diǎn)擊率作為衡量的參數(shù)來計算邊的權(quán)值，描述節(jié)點(diǎn)的傳播優(yōu)先度，然后選取權(quán)值最大的鄰接點(diǎn)進(jìn)行標(biāo)簽傳播。例如在基于隨機(jī)游走相似度矩陣的改進(jìn)標(biāo)簽傳播算法中，將Web頁面內(nèi)容的相似度或者超鏈接的點(diǎn)擊率作為節(jié)點(diǎn)間的相似度，選取相似度最高的鄰接點(diǎn)進(jìn)行標(biāo)簽傳播。

5 結(jié)束語

隨著Internet的迅速發(fā)展，Web資源朝著多元化、復(fù)雜化方向飛速增長，但是對于用戶來說只有很小一部分具有使用價值。因此，從復(fù)雜的Web系統(tǒng)資源中發(fā)現(xiàn)有利用價值的Web社區(qū)顯得尤為重要。嘗試將改進(jìn)的標(biāo)簽傳播算法用于Web社區(qū)發(fā)現(xiàn)，進(jìn)一步完善Web社區(qū)發(fā)現(xiàn)的理論基礎(chǔ)，提高Web社區(qū)發(fā)現(xiàn)的質(zhì)量特性，促進(jìn)復(fù)雜網(wǎng)絡(luò)理論的發(fā)展完善，其理論基礎(chǔ)可以推廣到其他復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。

參考文獻(xiàn)：

[1] 宋琛，張賢坤，費(fèi)松，等.基于隨機(jī)游走相似度矩陣的改進(jìn)標(biāo)簽傳播算法[J].計算機(jī)應(yīng)用與軟件，2016，33（08）：269-272.

[2] 張素智，孫嘉彬，王威.基于節(jié)點(diǎn)聚集系數(shù)的分布式標(biāo)簽傳播算法[J].計算機(jī)應(yīng)用與軟件，2016，33（04）：125-128+142.

[3] 李磊，倪林.基于模塊度優(yōu)化的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[J].計算機(jī)系統(tǒng)應(yīng)用，2016， 25（09）：212-215.

[4] 張超，武先強(qiáng)，董榮勝.一種改進(jìn)的基于相干鄰居親近度的標(biāo)簽傳播算法[J].廣西科學(xué)院學(xué)報，2017，33（01）：12-18.

[5] 徐成林，陳志剛，黃瑞，等.用于社區(qū)發(fā)現(xiàn)的LPA_LRDC標(biāo)簽傳播算法[J].小型微型計算機(jī)系統(tǒng)，2017，38（08）：1746-1750.

[6] 張金增.一種改進(jìn)的Web社區(qū)挖掘算法[D].鄭州大學(xué)，2009.