社團結構是復雜網(wǎng)絡的重要特征之一,可以用來表達網(wǎng)絡的一些功能和特征;鏈路預測用已知網(wǎng)絡拓撲結構特征和節(jié)點屬性預測兩個節(jié)點之間產生連邊的概率,兩者對復雜系統(tǒng)的研究和應用都具有重要的理論和現(xiàn)實意義。為了降低標簽傳播算法在社團發(fā)現(xiàn)中由于隨機性引發(fā)的聚類結果不穩(wěn)定的問題,使用社團歸屬度來確定社團個數(shù)和社團初始形狀,很大程度上改進了標簽傳播的隨機選擇缺點。提出的LPA-CBD(Label Propagation Algorithm Based on Community Belonging Degree,基于社團歸屬度的標簽傳播算法)算法首先尋找平均吸引力最大節(jié)點的初始社團,然后通過社團歸屬度來優(yōu)化或擴大初始社團,在得到網(wǎng)絡的初始社團劃分后,對剩余節(jié)點利用標簽傳播算法進行標簽選擇。實驗通過在十個真實網(wǎng)絡以及3個人工網(wǎng)絡上測試,并與經典的LPA、隨機游走算法、BGLL算法、GN算法、快速貪心算法、Leading Eigenvector等社團發(fā)現(xiàn)算法在社團數(shù)量、算法準確度和模塊度等評價指標上對比,實驗證明LPA-CBD算法在各個指標上表現(xiàn)良好,不僅具有較低的算法復雜度和較高的社團發(fā)現(xiàn)質量,并且提高了原始標簽傳播算法的穩(wěn)定性。社團結構是網(wǎng)絡中普遍存在的拓撲特征之一,許多真實網(wǎng)絡的社團結構不但具有層次性,還具有重疊性,目前大多數(shù)工作只研究網(wǎng)絡的層次性和重疊性的一個方面。Ahn在2010年發(fā)表的文章證明了層次性和重疊性是網(wǎng)絡社團結構相同現(xiàn)象的兩個方面,本文在Ahn的方法的基礎上提出了社團檢測的新算法:SAoLG(Spectral Analsis of Line Graph,線圖的譜分析),將譜分析方法應用到邊社團發(fā)現(xiàn)上,進行了兼顧層次性和重疊性的社團檢測研究,實驗中使用的網(wǎng)絡有一個標準網(wǎng)絡、兩個社團結構清晰的網(wǎng)絡(空手道俱樂部網(wǎng)絡和海豚社交網(wǎng)絡)以及四個真實網(wǎng)絡,實驗結果的評價準則選擇模塊度modularity、劃分密度PD(Partition Density)、社團數(shù)目CN(Community Number)、節(jié)點覆蓋率CR(Coverage Rate)、未覆蓋節(jié)點數(shù)UV(Uncovered Vertices)、節(jié)點劃分準確率Accuracy、正確劃分節(jié)點數(shù)CDV(Correctly Divided Vertices),實驗對比算法分別為Ahn的算法(LC算法)、CPM算法和GN算法,實驗結果表明SAoLG算法實現(xiàn)了網(wǎng)絡的重疊社團檢測并且社團劃分的結果優(yōu)于其他三個經典的社團檢測算法。網(wǎng)絡的社團結構同樣影響著復雜網(wǎng)絡鏈路預測的準確性。利用圖的拉普拉斯矩陣的特征向量作為樣本空間進行社團結構劃分能夠收斂到全局最優(yōu),是很好的劃分社團結構的方法之一。通過引入基于拉普拉斯矩陣的相似度計算方法,提出一種鏈路預測新算法:LPbSA(Link Prediction based on Spectral Analysis,基于譜分析的鏈路預測),將對節(jié)點提取屬性特征進行邊的預測轉化為直接對邊提取屬性特征并根據(jù)其屬性值進行預測。LPbSA算法首先獲取網(wǎng)絡拉普拉斯矩陣的特征值和特征向量,選擇最小非平凡特征向量的維數(shù)為2維和3維,分別獲取2維和3維最小非平凡特征向量對應的相似度(文中使用角距離、歐式距離以及曼哈頓距離三種相似度),得到網(wǎng)絡中所有節(jié)點對之間可能存在的邊的6個屬性,然后使用機器學習算法對邊進行分類,分類變量的值為0和1,其中0表示節(jié)點對之間無連邊,1表示節(jié)點對之間有連邊,這樣就將網(wǎng)絡的鏈路預測問題轉換成了對邊的分類預測問題,實驗在七個真實數(shù)據(jù)集上分別與基于節(jié)點局部信息的相似性指標、基于路徑的相似性指標和基于隨機游走的相似性指標三類算法共18個相似性指標的鏈路預測結果作對比,實驗結果證明了LPbSA算法的可行性、有效性。
【學位單位】：蘭州大學
【學位級別】：博士
【學位年份】：2018
【中圖分類】：O157.5
【部分圖文】：

實現(xiàn)對客戶群的細分，從而推出不同的消費套餐及潛在流失用戶的挽留方法；在生物領域，通過對生物網(wǎng)絡的社團劃分來對基因進行分類，方便科學家研究基因組包含的遺傳信息和相互關系，從而為預防和治療許多疾病提供科學依據(jù)；在電子商務領域，通過對電子商務網(wǎng)絡的社團劃分幫助電子商務用戶尋找具有相似瀏覽、相似購買行為的客戶，實現(xiàn)精準的推薦服務。所有這些應用，都涉及到對事物或實體的分類問題，可以說分類是人類解決真實世界問題的基本方法之一。現(xiàn)實生活中的復雜系統(tǒng)元素數(shù)目很多，元素與元素之間往往存在強烈的耦合作用，可以將這些復雜系統(tǒng)描述為復雜網(wǎng)絡，通過復雜網(wǎng)絡的理論方法研究復雜系統(tǒng)成為目前科學界研究的一個熱點。社團結構是復雜網(wǎng)絡的一個顯著特征，網(wǎng)絡中的社團與社團之間往往不是絕對分離、沒有任何關聯(lián)的，具有重疊性的社團檢測的研究更接近于真實網(wǎng)絡的構成。不同于傳統(tǒng)的定義，社團是節(jié)點的劃分，邊社團把社團定義成一系列邊的集合，這樣節(jié)點可能擁有幾條邊，這些邊又屬于幾個社團，因此這個節(jié)點可能屬于兩個或更多的社團。本論文主要研究了復雜網(wǎng)絡中的社團檢測以及社團結構對鏈路預測影響的相關問題，圖 1-1 是一個航空網(wǎng)絡示意圖，該圖中節(jié)點和連邊錯綜復雜，是一個典型的復雜系統(tǒng)。

圖 1-2 復雜網(wǎng)絡小世界特性，六度分割理論（圖片源自：tp://blog.csdn.net/zdy0_2004/article/details/50388376）小世界特性經常用兩個特征來衡量，特征路徑長度(C聚集系數(shù)(Clustering Coefficient)。路徑長度是指連通網(wǎng)絡連邊數(shù)，網(wǎng)絡中所有節(jié)點之間的路徑長度的平均值就是網(wǎng)集系數(shù)假設一個節(jié)點連接著 條邊，那么這 條邊連接的節(jié)邊數(shù)為 ( ) ，實際存在的邊數(shù)和最多可能存在邊數(shù)集系數(shù)。所有節(jié)點的聚集系數(shù)的平均值就是網(wǎng)絡的聚集聚集系數(shù)反映相鄰兩個人之間朋友圈的重合度。標度特性(Scale-free)�，F(xiàn)實世界中的網(wǎng)絡大多不是隨機網(wǎng)點擁有很大的度，而其他大部分節(jié)點的度很小的情況，也冪律分布，這就是網(wǎng)絡的無標度特性，研究中把符合冪律網(wǎng)絡，圖 1-3 是一個擁有 10 萬個節(jié)點的無標度網(wǎng)絡的度映了復雜網(wǎng)絡的異質性，各節(jié)點之間的度數(shù)具有嚴重的

1-3 擁有 10 萬個節(jié)點的無標度網(wǎng)絡示意圖（引自網(wǎng)站//blog.csdn.net/zdy0_2004/article/details/50388376結構特性。圖 1-4 是網(wǎng)絡社團結構特性的一種描述，分”中就有社團劃分的含義，現(xiàn)實世界中復雜網(wǎng)絡的如各種朋友圈、同事圈、親人圈、同學圈等，這種集的程度。復雜網(wǎng)絡的社團檢測是本論文的重點研究
【參考文獻】

相關期刊論文 前7條

1 許進;楊揚;蔣飛;金舒原;;社交網(wǎng)絡結構特性分析及建模研究進展[J];中國科學院院刊;2015年02期

2 雷方元;蔡君;;基于社團特性的鏈路預測算法的研究[J];廣東技術師范學院學報;2015年02期

3 傅穎斌;陳羽中;;基于鏈路預測的微博用戶關系分析[J];計算機科學;2014年02期

4 張俊麗;常艷麗;師文;;標簽傳播算法理論及其應用研究綜述[J];計算機應用研究;2013年01期

5 呂琳媛;;復雜網(wǎng)絡鏈路預測[J];電子科技大學學報;2010年05期

6 張明科;陳政;于長軍;朱榮花;權太范;;網(wǎng)絡化戰(zhàn)爭中的復雜網(wǎng)絡拓撲建模[J];航天控制;2007年04期

7 李一寧;汪小帆;;復雜網(wǎng)絡上的一種映射網(wǎng)絡模型[J];系統(tǒng)仿真學報;2007年11期

本文編號：2878991