基于標(biāo)簽傳播算法的Web社區(qū)發(fā)現(xiàn)研究

閻海玲　周瑞　袁春艷

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

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

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

其中標(biāo)簽傳播算法具有簡(jiǎn)單、高效的特點(diǎn)，但是準(zhǔn)確性有待于提高。其主要原因在于在選取節(jié)點(diǎn)的鄰接點(diǎn)時(shí)隨機(jī)選取，這種隨機(jī)性導(dǎo)致計(jì)算結(jié)果不一致，從而導(dǎo)致社區(qū)劃分的準(zhǔn)確性降低。針對(duì)標(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ù)劃分為同一個(gè)社區(qū)。也即一個(gè)節(jié)點(diǎn)應(yīng)該和它的大多數(shù)鄰接點(diǎn)劃分為同一個(gè)社區(qū)。將網(wǎng)絡(luò)看做是一個(gè)無(wú)向圖，首先給圖中每一個(gè)節(jié)點(diǎn)隨機(jī)分配一個(gè)唯一的標(biāo)簽（初始時(shí)可以認(rèn)為每一個(gè)節(jié)點(diǎn)就是一個(gè)單獨(dú)的社區(qū)），然后將一個(gè)節(jié)點(diǎn)的標(biāo)簽更新為所有鄰接點(diǎn)的標(biāo)簽中數(shù)量最多的那個(gè)標(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)建成一個(gè)圖，每一個(gè)數(shù)據(jù)點(diǎn)就是圖中的一個(gè)節(jié)點(diǎn)，假設(shè)這個(gè)圖是全連接的，包含已標(biāo)注過(guò)的和未標(biāo)注的兩種數(shù)據(jù)。節(jié)點(diǎn)v和節(jié)點(diǎn)w的邊表示他們的關(guān)聯(lián)度。給每個(gè)節(jié)點(diǎn)隨機(jī)分配一個(gè)標(biāo)簽以代表它所屬的社區(qū)，遍歷圖中每一個(gè)節(jié)點(diǎn)，將每一個(gè)節(jié)點(diǎn)的標(biāo)簽更新為它的所有鄰接點(diǎn)中標(biāo)簽數(shù)目最多的那個(gè)標(biāo)簽，如果數(shù)目最多的標(biāo)簽同時(shí)存在多個(gè)，則在其中隨機(jī)選擇一個(gè)進(jìn)行更新，最終同一標(biāo)簽的節(jié)點(diǎn)劃分為同一個(gè)社區(qū)結(jié)構(gòu)。每一個(gè)節(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ù)目最多的那個(gè)標(biāo)簽。也即v的鄰接點(diǎn)中哪個(gè)社區(qū)的標(biāo)簽最多，v就屬于哪個(gè)社區(qū)。標(biāo)簽傳播算法時(shí)間復(fù)雜度接近線(xiàn)性：對(duì)圖中每個(gè)節(jié)點(diǎn)分配標(biāo)簽的時(shí)間復(fù)雜度為O（n），每次迭代時(shí)間為O（ m），劃分出所有社區(qū)的復(fù)雜度為O（n +m）。

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

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

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

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

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

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

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

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

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

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

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

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

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

中心頁(yè)面與權(quán)威頁(yè)面之間相輔相成互相增強(qiáng)的關(guān)系有助于權(quán)威頁(yè)面的發(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)中客觀(guān)存在的Web頁(yè)面集合，通過(guò)Web社區(qū)的發(fā)現(xiàn)，可以有效地發(fā)現(xiàn)與某一主題密切相關(guān)的Web頁(yè)面集合。設(shè)Web社區(qū)G有n個(gè)節(jié)點(diǎn)和m條邊，將每一個(gè)Web頁(yè)面設(shè)定為一個(gè)節(jié)點(diǎn)，頁(yè)面間的超鏈接設(shè)定為邊。鏈接到該頁(yè)面的Web頁(yè)面?zhèn)€數(shù)為入度，該頁(yè)面鏈接的其他頁(yè)面的個(gè)數(shù)為出度。由此得出一個(gè)有向加權(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稱(chēng)為弧尾（tail）或始點(diǎn)（initial node），w稱(chēng)為弧頭（head）或終點(diǎn)（terminal node） 。

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

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

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

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

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

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

5 結(jié)束語(yǔ)

隨著Internet的迅速發(fā)展，Web資源朝著多元化、復(fù)雜化方向飛速增長(zhǎng)，但是對(duì)于用戶(hù)來(lái)說(shuō)只有很小一部分具有使用價(jià)值。因此，從復(fù)雜的Web系統(tǒng)資源中發(fā)現(xiàn)有利用價(jià)值的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ì)算機(jī)應(yīng)用與軟件，2016，33（08）：269-272.

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

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

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

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

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