網(wǎng)絡(luò)重要結(jié)構(gòu)特征識(shí)別

張海峰安徽大學(xué)2016.4.10網(wǎng)絡(luò)的重要結(jié)構(gòu)特征識(shí)別提綱鏈路預(yù)測(cè)——朋友推薦模型社團(tuán)劃分——weakclique識(shí)別重疊網(wǎng)絡(luò)識(shí)別有影響力節(jié)點(diǎn)朋友推薦的鏈路預(yù)測(cè)

定義G（V，E）為一個(gè)無(wú)向網(wǎng)絡(luò)，其中V為節(jié)點(diǎn)集合，E為邊集合。網(wǎng)絡(luò)總的節(jié)點(diǎn)數(shù)為N，邊數(shù)為M。該網(wǎng)絡(luò)共有

個(gè)節(jié)點(diǎn)對(duì)N（N-1）/2，即全集U。給定一種鏈路預(yù)測(cè)的方法，對(duì)每對(duì)沒有連邊的節(jié)點(diǎn)對(duì)

賦予一個(gè)分?jǐn)?shù)值

，然后將所有未連接的節(jié)點(diǎn)對(duì)按照該分?jǐn)?shù)值從大到小排序，排在最前面的節(jié)點(diǎn)對(duì)出現(xiàn)連邊的概率最大。問(wèn)題描述實(shí)驗(yàn)設(shè)計(jì)AUC精確度CN指標(biāo)如果兩個(gè)陌生人有很多的共同朋友，那么這兩個(gè)人成為朋友的可能性就比較大。

則節(jié)點(diǎn)i與j的CN相似性指標(biāo)可以定義為：AA指標(biāo)與RA指標(biāo)度小的共同鄰居節(jié)點(diǎn)貢獻(xiàn)要大于度大的共同鄰居的節(jié)點(diǎn)。

例如：a圖中A與B都認(rèn)識(shí)一個(gè)導(dǎo)師，而b圖中A與B都認(rèn)識(shí)成龍。顯然a中A，B認(rèn)識(shí)的可能性最大。

在RA和AA指標(biāo)中節(jié)點(diǎn)3會(huì)把自身以及他和節(jié)點(diǎn)1的共同鄰居4以等概率介紹給節(jié)點(diǎn)1.實(shí)際上，節(jié)點(diǎn)3只會(huì)把2，5，7介紹給節(jié)點(diǎn)1。朋友推薦模型的動(dòng)機(jī)通過(guò)節(jié)點(diǎn)3介紹鄰居給節(jié)點(diǎn)1.FR相似性指標(biāo)計(jì)算節(jié)點(diǎn)i通過(guò)l介紹給j的可能性為：分母減1表示不會(huì)把l自身介紹給j；

表示不會(huì)把l和j的共同鄰居介紹給j.節(jié)點(diǎn)i介紹給j的可能性為：節(jié)點(diǎn)i和節(jié)點(diǎn)j的相似性指標(biāo)為：f231=1/3,f241=1/2;f21=1/3+1/2=5/6;f132=1/2,f142=1/2;f12=1/2+1/2=1;則1與2的相似性指標(biāo)為：11/12朋友推薦模型的優(yōu)點(diǎn)1.兩節(jié)點(diǎn)的共同鄰居越多，相似性越高。2.度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)。3.節(jié)點(diǎn)更傾向被推薦到具有“局部群落”結(jié)構(gòu)的節(jié)點(diǎn)上。注:a,b,c三個(gè)圖中節(jié)點(diǎn)1和節(jié)點(diǎn)3的CN，AA，RA指標(biāo)都相同，但在朋友推薦模型中：從左到右可以發(fā)現(xiàn)隨著{2,3}之間的“局部群落現(xiàn)象”越來(lái)越大，f_{123}的概率分別是1/3,1/2以及1.因此朋友推薦模型傾向把節(jié)點(diǎn)推薦給具有“局部群落結(jié)構(gòu)”的節(jié)點(diǎn)上。4.具有更高的分辨率。節(jié)點(diǎn)偏向鏈接具有“局部群落特征”現(xiàn)象的驗(yàn)證Step1:網(wǎng)絡(luò)中的邊分成是否具有“局部群落結(jié)構(gòu)”根據(jù)兩個(gè)端點(diǎn)的共同鄰居數(shù)是否大于一個(gè)給定的閾值。（文中取平均值）Step2:三個(gè)節(jié)點(diǎn)構(gòu)成的三元組的所有7種構(gòu)型：節(jié)點(diǎn)偏向連接具有“局部群落特征”現(xiàn)象的驗(yàn)證Step3:定義P_1,P_2,P_3如下：A,如果兩條都是strong-tielinks，則相連的概率P_1為

（N_i表示第i種構(gòu)型在網(wǎng)絡(luò)中的數(shù)量）：B,如果兩條邊一個(gè)是strong-tielink一個(gè)是commonlink，則相連的概率P_2為：C,如果兩條邊一都是commonlink，則相連的概率P_3為：Step4:比較P_1,P_2,P_3之間的大小關(guān)系判斷節(jié)點(diǎn)是否更偏向鏈接具有“局部群落特征”的現(xiàn)象。當(dāng)P_1>P_2且P_1>P_3時(shí)，稱這種現(xiàn)象存在，進(jìn)一步，P_1>P_2>P_3,稱這種現(xiàn)象是significant.基于真實(shí)網(wǎng)絡(luò)對(duì)偏向連接“局部群落特征”現(xiàn)象的驗(yàn)證RN表示網(wǎng)絡(luò)自身，NN表示原網(wǎng)絡(luò)的零模型。藍(lán)色表示此現(xiàn)象是significant，紅色表示不具有此現(xiàn)象。結(jié)論：真實(shí)網(wǎng)絡(luò)中普遍存在這種現(xiàn)象——節(jié)點(diǎn)更偏向連接到具有“局部群落結(jié)構(gòu)”的節(jié)點(diǎn)。因此該算法的優(yōu)越性。與RA算法的比較結(jié)論：RA相似性高的點(diǎn)對(duì)也會(huì)導(dǎo)致對(duì)應(yīng)的FR相似性也高，但是FR高的不一定導(dǎo)致RA相似性指標(biāo)高。如子圖g,j所示。在Yeast網(wǎng)絡(luò)中，點(diǎn)對(duì){A,C}和{A,B}的共同鄰居都很多，因此都具有“局部群落”結(jié)構(gòu)，F(xiàn)R指標(biāo)可以給出A,B連接的概率很高。而基于RA指標(biāo)，由于C的度很大，所以A和B相連的概率很小。實(shí)際上A和B確實(shí)真實(shí)存在。其中0≤alpha≤1；當(dāng)alpha=0時(shí)，為RA指標(biāo)，方便比較；當(dāng)alpha=1時(shí)，與FR指標(biāo)有異曲同工之處。給出FR的更一般形式：?jiǎn)枺寒?dāng)alpha逐漸增加時(shí)，鏈路預(yù)測(cè)的結(jié)果是什么樣呢？偏向連接“局部群落結(jié)構(gòu)”節(jié)點(diǎn)對(duì)鏈路預(yù)測(cè)的影響（1）如果P1>P2>P3，alpha越大，鏈路預(yù)測(cè)中的精度就越高。（2）如果P1<P3，P2<P3，alpha越大，朋友推薦模型在鏈路預(yù)測(cè)中的精度就越低。

正反兩面都說(shuō)明此現(xiàn)象在對(duì)鏈路預(yù)測(cè)起到起到重要作用?；趙eak-clique方法識(shí)別具有重疊結(jié)構(gòu)的社團(tuán)網(wǎng)絡(luò)背景與動(dòng)機(jī)1，很多真實(shí)網(wǎng)絡(luò)具有社團(tuán)結(jié)構(gòu)，且如何對(duì)社團(tuán)進(jìn)行準(zhǔn)確劃分具有很多應(yīng)用；

2，網(wǎng)絡(luò)中的有些節(jié)點(diǎn)往往屬于不同的社團(tuán)，即重疊結(jié)構(gòu)的社團(tuán)網(wǎng)絡(luò)；3，著名的cliquepercolationmethod(CPM)缺點(diǎn)：時(shí)間復(fù)雜度很高；4，標(biāo)簽傳播方法(labelpropagation)缺點(diǎn)：不能分出小的社團(tuán)結(jié)構(gòu)；5，Linkcommunity缺點(diǎn)：導(dǎo)致重疊度過(guò)高……如何發(fā)展一種有效的方法識(shí)別具有重疊結(jié)構(gòu)的社團(tuán)網(wǎng)絡(luò)是值得思考的問(wèn)題,我們?cè)贑PM的基礎(chǔ)上發(fā)展一種weakcliquepercolationmethod(W-CPM).Weak-clique的定義Weak-clique:兩個(gè)相鄰的節(jié)點(diǎn)u和v，他們weak-clique定義為：即：u,v和他們的鄰居以及他們之間連邊構(gòu)成的導(dǎo)出子圖。節(jié)點(diǎn)a和c構(gòu)成的weak-clique是a,b,c,e,f.（d不屬于weak-clique）Weak-clique的選取首先根據(jù)一個(gè)指標(biāo)選擇一個(gè)節(jié)點(diǎn)u，再選擇一個(gè)和u相似度最高的節(jié)點(diǎn)v,然后得到u和v構(gòu)成的weak-clique.紅色表示u和v構(gòu)成的weak-clique.Weak-clique間的合并首先定義兩個(gè)weak-clique的相似性，當(dāng)相似性大于一個(gè)給定閾值T則合并。T的大小可以確定分成兩個(gè)社團(tuán)還是一個(gè)社團(tuán)部分實(shí)驗(yàn)結(jié)果——運(yùn)行時(shí)間無(wú)論是隨著節(jié)點(diǎn)的增加還是網(wǎng)絡(luò)平均度的增加，時(shí)間W-CPM復(fù)雜度都很低。部分實(shí)驗(yàn)結(jié)果——NMI精確度閾值T對(duì)結(jié)果的影響關(guān)鍵節(jié)點(diǎn)識(shí)別（單源和多源）單源——萬(wàn)有引力模型節(jié)點(diǎn)的重要性不僅僅與自身有關(guān)，且與鄰居、次鄰居、甚至次次鄰居的重要性有關(guān)；距離越遠(yuǎn)，對(duì)中心節(jié)點(diǎn)的影響越小。因此定義節(jié)點(diǎn)i的影響力為：多傳播源——著色方法核心思想：用著色圖方法把網(wǎng)絡(luò)節(jié)點(diǎn)分成不同的集合，同一個(gè)顏色的節(jié)點(diǎn)歸為一個(gè)集合，同一個(gè)集合