標簽傳播在社會網絡中的運用范文

本站小編為你精心準備了標簽傳播在社會網絡中的運用參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《計算機工程與應用雜志》2014年第十四期

1研究現狀

針對在大規模網絡結構中進行聚類時，需要事先知道聚類數目、規模等先驗信息，或者聚類算法的計算代價比較大的情況，Raghavan等人提出了基于標簽傳播[8]的簡單快速算法。在算法中，初始化時每個節點被賦予唯一的數字標簽，在之后的每步中，將所有節點以隨機序列排列，根據鄰接節點當前出現頻率最高的標簽依次確定隨機序列中節點的標簽。如此迭代，在幾乎線性的時間內實現了節點聚類。由于算法的終止條件是事先約定的一個準則，并非函數值的最大化或者最小化，因此滿足停止條件的網絡劃分結果不唯一，但Raghavan等人通過計算發現這些不同的網絡劃分之間具有極大的相似性。并且提出將各種網絡劃分結果進行聚合，可以發現重疊的簇結構。該算法僅將已知的網絡結構作為啟發式搜索條件，在線性時間O(m+n)內實現高效聚類，且適用于含有百萬節點的大規模網絡。Barber和Clark指出LPA算法在將不同聚類結果進行聚合時，若不同的劃分方案中簇結構越小，那么聚合后的簇結構也就越多，是該算法存在的一個比較嚴重的缺陷。為了解決該問題，他們在過程中引入了一些限制，在目標函數H（對H進行極大化，等價于原始的LPA算法）上增加了一些數據項，提高了LPA算法的性能[9]。Leung等人在對線性時間的LPA算法進行分析總結的基礎上，提出了在社會網絡結構中進行實時聚類的方法，改善了LPA算法簇結構規模不均勻的缺陷，并且證明了標簽傳播的啟發式方法在大規模網絡中進行聚類更準確、更高效[10]。此外，Long等人提出的基于圖相似的CLGA算法[11]，Narasimhamurthy等人提出的圖模型分解方法[12]，Zarei和Samani提出了基于Newman的反簇結構概念，將網絡看成一個圖，通過在原圖的補圖中尋找反簇結構，進而得到原簇的結構的算法[12]等。國內的研究學者也對這一問題進行了相關研究[13-14]。基于局部信息的聚類方法通常是考慮網絡中節點的局部近鄰信息，在大規模數據集中，可以高效地找到網絡最優劃分或者近似最優劃分，一般具有概念簡單，易于實現，算法復雜度相對較低等優點。但縱觀每個基于局部信息的啟發式聚類算法，又分別有它各自的局限性。

2基于節點屬性相似度的標簽傳播算法

2.1問題描述LPA算法僅以網絡拓撲結構作為向導，根據節點之間的連接，可高效地進行網絡聚類，這是LPA算法的優點。但現實世界中的絕大多數網絡，除了具有拓撲結構特征，網絡中的節點自身的屬性信息也很容易獲取，如科學家合著網絡中，每個學者都有其主要的研究方向。因此，LPA算法忽略了節點本身的屬性信息，僅考慮連接的局部信息，而且LPA算法具有較大的隨機性，這會致使算法對網絡劃分可能并非最優，甚至出現節點的錯誤劃分。下面通過一個實例來形象、直觀地說明該算法存在的問題。一個小型的人際交互網絡如圖1所示，其中每個節點代表一個人，每個人所屬的學校用節點旁的字母表示。根據標簽傳播算法，顯然網絡可以被劃分為兩個簇結構，A大學{v1v2v3v4v5v6}，B大學{v7v8v9v10}。現在仔細分析v6節點，在標簽傳播過程中，根據連接節點與其鄰節點的連接情況來看，它的候選集合有兩個：{v4v5}和{v9v10}對應的標簽分別為A大學和B大學。隨機選擇其一，如：A大學，但根據它的實際屬性來看，它是屬于B大學的，因此節點出現了錯誤的劃分，影響了網絡聚類的質量。即使在下一輪的迭代過程中，它被劃分到正確的結構中，但這也是需要付出時間代價的。針對上述情況，本文綜合考慮節點屬性信息，在保證原算法時間復雜度的基礎上，引入節點屬性相似度的概念，提出基于節點屬性相似度的標簽傳播算法，致力于提高網絡劃分效果，降低算法的時間開銷。

2.2節點屬性相似度在給出LPA-SNA算法的具體描述前，先給出計算節點屬性相似度所需的一些基本概念及定義。本文要用到的重要的表示符號如表1所示。

2.3LPA-SNA算法描述及實現在原始的LPA算法的基礎上，當待更新節點的大部分鄰節點所屬的簇結構不止一個，即該節點的鄰接子系統不唯一時，基于節點屬性相似度的標簽傳播算法（LPA-SNA）計算每個鄰接子系統中節點屬性的平均值，進而計算待更新節點與各鄰接子系統的屬性相似度，并選取令相似度maxSimi(SiSNir)最高的子系統的標簽作為當前節點的標簽。由于一般的原始網絡包含節點及邊的信息，算法每次迭代時，要根據鄰居節點標簽信息來決定當前節點的標簽，如果每次都統計該節點有哪些鄰節點，算法運行時需要耗費大量的時間。因此，對LPA-SNA算法進行實現時，要先進行預處理，首先讀入包含網絡G節點及邊信息的文件，并根據讀入的G的拓撲結構，構造對應的鄰接表結構體ALGraph，ALGraph包含頂點表節點結構體VNode和邊表節點結構體ArcNode，而VNode存儲了每個節點的鄰節點數量及其屬性信息，ArcNode存儲了鄰居節點位置信息及邊信息。LPA-SNA算法包括以下5個步驟：（1）初始化網絡中的節點標簽，依次為每個節點分配唯一的數字標簽，即對于節點v，令Cv(0)=v。（2）令迭代計數器t=1。（3）以隨機順序排列網絡中的節點，并將排序結果存放在向量X中。其中，Max_Vertex_Number為宏定義，表示網絡包含的節點數量。在迭代過程中，為了按照隨機順序對節點標簽進行更新，算法定義的隨機數組RandArray[Max_Vertex_Number]，存儲0~Max_Vertex_Number-1的隨機排列的數據，并設計函數RandInPlace(RandArray)來實現對數組中數據元素的隨機排序。

3實驗分析

本文LPA-SNA算法的實驗環境是Inter®CoreTM2.66GHz，2GB內存，MicrosoftWindowsXP操作系統的PC機；選用VisualC++6.0開發環境。為了對改進的LPA-SNA算法的可行性及有效性進行實驗論證，選擇美國大學足球賽程網絡[15]、科學家合著網絡兩個數據集進行實驗。

3.1美國大學足球賽程網絡數據集實驗首先，將LPA和LPA-SNA算法應用美國大學足球賽程網絡。Newman提供的美國大學足球賽程網絡，是分析社會網絡聚類的經典的數據集，根據2000年秋季常規賽的比賽計劃構建的，包含115個代表大學足球隊的節點，616條表示兩個大學球隊之間進行了比賽的邊。這些球隊構成了一個具有簇結構特性的網絡，通常8到12個足球隊組成一個小組，不同小組間的球隊比賽的可能性要少于同一小組內的球隊間比賽的可能性。將LPA算法與LPA-SNA算法分別應用在該包含12個簇結構的數據集上。為了不使算法陷入固定化、模式化的情況，在每次迭代過程中，LPA與LPA-SNA算法中節點更新順序都是隨機的。但由于存在該隨機策略，多次運行兩種算法時會產生不同的聚類效果。為了更加真實地分析算法的性能，在美國大學足球網絡上分別將這兩種算法運行30次，并且得到相關數據如表2所示。另外，為了更加直觀地比較LPA與LPA-SNA算法在運行速度、網絡劃分質量方面的性能，本文對兩種算法在足球賽程網絡上多次運行時的時間、網絡模塊度兩個參數值情況繪制了對比折線圖，如圖2、3所示。根據表2所提供的實驗數據結果可以看出，引入節點屬性相似度的LPA-SNA算法的平均迭代次數少于LPA算法，當節點候選集合標簽不唯一時，通過計算節點屬性與候選鄰接子系統的屬性相似度選擇最佳的標簽，使得節點很快被劃分到正確的網絡中，因此平均運行時間更低，效率更高。同時，觀察網絡聚類模塊度的平均值，可以看出LPA-SNA算法的平均Q值更大，說明LPA-SNA算法中所劃分出的簇結構內部節點聯系得更加緊密，對網絡劃分質量更高。另外，從迭代次數范圍、運行時范圍兩個參數來分析，LPA算法的數據范圍更大。通過圖2、3可以看出，LPA算法的運行時間、模塊度值的變化幅度要大，而LPA-SNA算法參數范圍區間相對較小，運行時間及模塊度變化幅度相對較小。上述數據說明，LPA算法在每次迭代過程中，由于節點順序排列具有隨機性，當最高標簽頻率不一致時，標簽選擇也具有隨機性，導致算法對網絡劃分的隨機性比較大。而LPA-SNA算法通過引入節點屬性相似度，降低了原始LPA算法的隨機性，提高原始算法運行時間、聚類質量的同時，也具有更好的穩定性。原始的足球賽程網絡數據集具有12個簇結構，為了進一步分析LPA算法及LPA-SNA算法網絡聚類性能的差異，本文從上述的運行30次的聚類結果中將美國足球賽程網絡均劃分為12個簇結構時的情況進行簡單統計，綜合考慮運行時間和模塊度兩個參數，選取性能比較均衡情況下的兩種算法對應的網絡劃分，如圖4所示。該情況下，兩種算法的迭代次數、模塊度Q值、運行時間3種情況如表3所示。將LPA-SNA算法與LPA算法與足球賽程網絡的真實劃分情況進行對比分析，發現LPA算法在模塊度為0.5807時得出的簇結構個數為12，運行0.047s，有16個節點劃分錯誤，其中五邊形表示的MidAmerican小組被劃分到兩個簇結構中，正確率為86.08%，而LPA-SNA算法在網絡中挖掘12個簇結構時的模塊度為0.5974，運行時間為0.035s，有10個節點劃分錯誤，正確率為91.30%。

3.2科學家合著網絡數據集實驗DBLP（DigitalBibliography&LibraryProject）是由德國的Trier大學建立的，收錄計算機科學領域內的出版物，包括書籍、期刊和會議論文，作者及合著者的姓名等相關內容，提供非常全面的信息。目前為止，它至少已收錄13000000條書目記錄，由于文獻的質量比較高且具有實時性，可以快速反映領域內最新研究動態，因此它極具權威性，受到計算機領域學者們的廣泛認可。此外，DBLP數據集可免費獲取，因此本文從DBLP網站中搜集部分數據作為實驗研究對象。首先，搜集來自DBLP的6個領域20個會議上發表文章的學者，其中涉及的會議領域及名稱如下所示。選擇在會議中發表文章較多的1590個學者作為科學家合著網絡的節點，如果兩個學者共同合作了文章，那么在網絡中他們之間就對應存在一條邊，以此構建一個科學家合著網絡，并將學者的研究領域、發表文章的期刊名稱作為節點屬性信息。在該節點具有文本屬性的科學家合著網絡數據集上，分別實現LPA及LPA-SNA算法。本文通過引用這些屬性信息，計算節點屬性相似度，為節點選擇最佳的標簽。通過對該數據集進行聚類，比較PLA及PLA-SNA算法的性能。按照數據的搜集過程可知，在科學家合著網絡真實數據集原則上應該劃分為6個簇結構。將LPA算法和改進的LPA-SNA算法運行在網絡上，得到的簇結構數量分別4個、6個，如表4所示。ComputerVisionUtilize領域的CVPR會議中發表文章的作者經常參加IJCAI、AAAI、ICML和ECML會議，由于LPA算法僅使用網絡的拓撲結構，根據網絡中節點的連接關系，很容易將CVPR中的學者劃分到ArtificialIntelligence領域中。但ComputerVisionUtilize領域的學者雖然經常使用人工智能的方法，但它仍存在著一些獨特的方法，如分割、對象跟蹤和圖像建模等，因此，ComputerVisionUtilize領域的學者應該隸屬單獨的一個簇結構。另外，InformationandKnowledgeMan-agement領域的CIKM中的文章涉及的研究領域非常廣泛，吸引了許多信息分析、數據挖掘、數據庫等領域的研究學者。但是很顯然，與這些領域的任何一個會議相比較，CIKM有著自己獨特的研究主題，因此它也應該形成獨立的簇結構。原始的LPA算法僅根據節點間的連接來聚類，因此很容易將ComputerVisionUtilize與InformationandKnowledgeManagement中的節點劃分到其他簇結構中，造成網絡劃分為4個簇結構，而LPA-SNA算法在引入節點屬性相似度以后，將DBLP的20個會議中的作者正確地劃分為6個簇結構。另外，在該合著網絡上多次運行LPA與LPA-SNA算法，實驗得到的其他性能方面的數據如表5所示。如圖5、6為對算法運行30次的時間、模塊度參數。結合表5的統計數據與圖5、6兩種算法的運行時間、網絡模塊度參數折線圖可以看出，在科學家合著網絡上，LPA-SNA算法的聚類速度、網絡劃分質量也明顯優于LPA算法。引入節點屬性相似度以后，使具有多個鄰接子系統的節點根據其屬性特征很快地找到和本身接近的簇結構，降低了LPA算法的迭代次數，減少了時間開銷，提高了網絡聚類的質量。

4總結

在對基于局部信息的LPA算法進行深入研究的基礎上，引入節點屬性相似度的概念，提出了LPA-SNA算法。它以網絡結構為主要依據的同時，考慮節點屬性信息，對大規模數據集網絡進行聚類，一定程度上克服了原始的LPA算法的隨機策略，提高了算法的聚類速度與網絡劃分質量。通過在美國大學生足球賽程網絡、科學家合著網絡數據集上運行LPA與LPA-SNA算法，驗證了LPA-SNA算法的可行性與有效性。目前基于局部信息的聚類算法研究已取得了很大的進展，能夠有效地探測社會網絡的簇結構，但隨著應用領域的不斷拓展，網絡聚類問題的多樣化，簇結構挖掘仍不能完全發現網絡的全部功與特性。因此，如何針對各種不同類型的網絡，設計出更加高效，無需先驗知識指導，利用局部信息即可挖掘簇結構的算法，仍是今后需努力的一個方向。

作者：夏磊張樂君國林張勇實張健沛楊靜單位：哈爾濱工程大學計算機科學與技術學院大連飛創信息技術有限公司