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

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

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

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

相關(guān)期刊論文 前7條

1 許進(jìn);楊揚(yáng);蔣飛;金舒原;;社交網(wǎng)絡(luò)結(jié)構(gòu)特性分析及建模研究進(jìn)展[J];中國(guó)科學(xué)院院刊;2015年02期

2 雷方元;蔡君;;基于社團(tuán)特性的鏈路預(yù)測(cè)算法的研究[J];廣東技術(shù)師范學(xué)院學(xué)報(bào);2015年02期

3 傅穎斌;陳羽中;;基于鏈路預(yù)測(cè)的微博用戶關(guān)系分析[J];計(jì)算機(jī)科學(xué);2014年02期

4 張俊麗;常艷麗;師文;;標(biāo)簽傳播算法理論及其應(yīng)用研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2013年01期

5 呂琳媛;;復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)[J];電子科技大學(xué)學(xué)報(bào);2010年05期

6 張明科;陳政;于長(zhǎng)軍;朱榮花;權(quán)太范;;網(wǎng)絡(luò)化戰(zhàn)爭(zhēng)中的復(fù)雜網(wǎng)絡(luò)拓?fù)浣J];航天控制;2007年04期

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

本文編號(hào)：2878991