馬 峻，萬(wàn) 劼

（首都經(jīng)濟(jì)貿(mào)易大學(xué) 安全與環(huán)境工程學(xué)院，北京 100070）

0 引言

復(fù)雜網(wǎng)絡(luò)廣泛存在于社會(huì)各個(gè)領(lǐng)域。社交網(wǎng)站用戶構(gòu)成的社交網(wǎng)絡(luò)，反映的是社交網(wǎng)站用戶之間的好友關(guān)系或關(guān)注(收聽(tīng))關(guān)系；商店顧客與商品構(gòu)成的購(gòu)買關(guān)系網(wǎng)絡(luò)，反映的是顧客對(duì)商品的購(gòu)買關(guān)系；其他諸如航空網(wǎng)絡(luò)、國(guó)家的電力網(wǎng)絡(luò)、蛋白質(zhì)相互作用網(wǎng)絡(luò)、食物鏈網(wǎng)絡(luò)等。不論是什么種類的網(wǎng)絡(luò)，一個(gè)網(wǎng)絡(luò)可抽象為由點(diǎn)集P和邊集E組成的圖G=(P,E)，設(shè)R是從P到其自身的一個(gè)二元關(guān)系，即R?P×P，對(duì)任意(x,y)∈P×P，如果xRy，則從x有一條有向連邊指向y，連邊反映了x與y的一種二元關(guān)系，如果(x,y)≠(y,x)，則構(gòu)成一個(gè)不對(duì)稱關(guān)系，否則為對(duì)稱關(guān)系。但在數(shù)量方面，同樣規(guī)模的網(wǎng)絡(luò)中，二元不對(duì)稱關(guān)系的潛在數(shù)量往往比二元對(duì)稱關(guān)系多；在信息量方面，二元不對(duì)稱關(guān)系更具有方向性，因此描述二元不對(duì)稱關(guān)系的網(wǎng)絡(luò)要比描述二元對(duì)稱關(guān)系的網(wǎng)絡(luò)包含更多的信息量。網(wǎng)絡(luò)中存在的這種關(guān)系對(duì)于網(wǎng)絡(luò)影響力的拓展以及網(wǎng)絡(luò)資源的有效利用具有很大的價(jià)值[1]，二元不對(duì)稱關(guān)系相對(duì)于二元關(guān)系的研究更具有普遍性和研究意義。

目前針對(duì)社會(huì)網(wǎng)絡(luò)中的二元關(guān)系的預(yù)測(cè)主要基于的信息可分為三類，第一類是根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)屬性信息進(jìn)行預(yù)測(cè)；第二類是根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行預(yù)測(cè)；第三類是上述兩類的混合方法，即在預(yù)測(cè)中既使用節(jié)點(diǎn)屬性信息也使用網(wǎng)絡(luò)結(jié)構(gòu)信息。文獻(xiàn)[2，3]表明使用節(jié)點(diǎn)屬性信息對(duì)社會(huì)網(wǎng)絡(luò)中的二元關(guān)系進(jìn)行預(yù)測(cè)求解可以得到較好的效果，但是使用節(jié)點(diǎn)屬性信息存在著以下問(wèn)題：第一，大量的節(jié)點(diǎn)屬性信息很難獲取，可靠性也難以得到保證；第二，需要大量的資源來(lái)存儲(chǔ)、讀取節(jié)點(diǎn)屬性信息。但是根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行關(guān)系預(yù)測(cè)求解一般不存在上述兩個(gè)問(wèn)題。

根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行關(guān)系預(yù)測(cè)求解中，一類是基于節(jié)點(diǎn)相似度的關(guān)系預(yù)測(cè)求解方法，另一類是基于似然分析的預(yù)測(cè)求解方法?；谙嗨贫鹊年P(guān)系預(yù)測(cè)求解方法較為簡(jiǎn)便，需要的假設(shè)前提較少，而基于似然分析的關(guān)系預(yù)測(cè)求解方法較為復(fù)雜，且需要建立在較多的假設(shè)(如層次結(jié)構(gòu)、社團(tuán)結(jié)構(gòu)等)之上，使用較少。文獻(xiàn)[4]將節(jié)點(diǎn)相似度與機(jī)器學(xué)習(xí)方法相結(jié)合，收到了較好的求解效果，但是還存在一些有待解決的問(wèn)題；其次，基于節(jié)點(diǎn)相似性的關(guān)系預(yù)測(cè)方法在處理二部分網(wǎng)絡(luò)時(shí)會(huì)遇到困難，例如很多常用的相似度指標(biāo)是無(wú)法計(jì)算的，這時(shí)一般需要使用一些更為復(fù)雜的相似度指標(biāo)，或者采用集合投影和協(xié)同過(guò)濾的方法[5-7]，這些方法或是較為復(fù)雜，或是有待完善。而神經(jīng)網(wǎng)絡(luò)(Artificial Neural Network，ANN)作為一種非線性動(dòng)力學(xué)模型廣泛用在各個(gè)領(lǐng)域預(yù)測(cè)求解，但是神經(jīng)網(wǎng)絡(luò)在進(jìn)行社會(huì)網(wǎng)絡(luò)關(guān)系預(yù)測(cè)計(jì)算中，由于社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)性和時(shí)變性導(dǎo)致網(wǎng)絡(luò)資源拓展的不確定性，同時(shí)社會(huì)網(wǎng)絡(luò)規(guī)模大、小世界性小社團(tuán)等特性導(dǎo)致網(wǎng)絡(luò)鄰接關(guān)系矩陣稀疏和不均勻性，產(chǎn)生社會(huì)網(wǎng)絡(luò)預(yù)測(cè)求解中輸入數(shù)據(jù)維數(shù)高，同時(shí)網(wǎng)絡(luò)中存在的不平衡性也極大地影響了神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)計(jì)算的效果[8]，為此，本文針對(duì)這兩個(gè)問(wèn)題，在提出相應(yīng)降維算法基礎(chǔ)上，建立了如何克服不平衡性從而提高模型求解效果的方法。

1 問(wèn)題描述

本文采用BP神經(jīng)網(wǎng)絡(luò)對(duì)社會(huì)網(wǎng)絡(luò)二元不對(duì)稱關(guān)系進(jìn)行預(yù)測(cè)求解的基本邏輯過(guò)程如下頁(yè)圖1所示。

圖1 利用BP神經(jīng)網(wǎng)絡(luò)進(jìn)行社會(huì)網(wǎng)絡(luò)二元不對(duì)稱關(guān)系預(yù)測(cè)求解邏輯過(guò)程

T=(SR)反映訓(xùn)練集所有樣本在整個(gè)網(wǎng)絡(luò)的連接關(guān)系。

P=(UV)反映了預(yù)測(cè)求解集所有樣本在整個(gè)網(wǎng)絡(luò)的連接關(guān)系。

S和U分別是訓(xùn)練和預(yù)測(cè)求解的輸入值，R是訓(xùn)練輸出值，V是預(yù)測(cè)求解輸出值。S，U，R是鄰接矩陣的已知部分，V是鄰接矩陣的未知部分。

實(shí)際應(yīng)用中V的某些部分可能是已知的，但鑒于一般V占整個(gè)鄰接矩陣的比例較?。ú淮笥?/9），而考慮V的已知部分會(huì)增大算法和代碼的復(fù)雜度，因此將V的全部設(shè)為未知。如果只需要預(yù)測(cè)求解V的部分列向量，那么就不需要獲取關(guān)于R的全部信息，只需要知道R所對(duì)應(yīng)列向量的取值。

根據(jù)圖1，預(yù)測(cè)求解需要大量的訓(xùn)練樣本，因此An×n的m會(huì)很大，如果將S和U這種高維向量直接作為輸入，則算法復(fù)雜度會(huì)很大，因此需要采取適當(dāng)方法進(jìn)行降維；另外由于網(wǎng)絡(luò)中大部分節(jié)點(diǎn)對(duì)是不存在關(guān)系的（這種情形也被稱為數(shù)據(jù)不平衡），而神經(jīng)網(wǎng)絡(luò)算法通常以訓(xùn)練誤差最小化為目標(biāo)求解模型，這會(huì)導(dǎo)致模型傾向做出關(guān)系不存在的預(yù)測(cè)，而實(shí)際應(yīng)用中更多被關(guān)注的是存在的關(guān)系，將存在的關(guān)系判斷為不存在所導(dǎo)致的損失經(jīng)常遠(yuǎn)大于將不存在的關(guān)系判斷為存在所導(dǎo)致的損失，因此需要對(duì)模型進(jìn)行進(jìn)一步的處理。

2 數(shù)據(jù)降維

2.1 數(shù)據(jù)降維方法

根據(jù)圖1，在利用神經(jīng)網(wǎng)絡(luò)進(jìn)行關(guān)系預(yù)測(cè)時(shí)，需要將關(guān)系矩陣An×n中Sm×m的m個(gè)變量取值全部直接輸入到神經(jīng)網(wǎng)絡(luò)輸入層，通常較大的m將導(dǎo)致神經(jīng)網(wǎng)絡(luò)規(guī)模也會(huì)變大，將大大增加算法的復(fù)雜度，因此有必要設(shè)法減少輸入層的節(jié)點(diǎn)數(shù)。

根據(jù)鄰接關(guān)系矩陣An×n，m個(gè)原始輸入變量的取值只有0與1兩種可能，又因?yàn)檫@個(gè)變量的順序是固定不變的，因此神經(jīng)網(wǎng)絡(luò)輸入層其實(shí)是一個(gè)長(zhǎng)度為m的0-1向量，為此可以將其固定長(zhǎng)度轉(zhuǎn)化為一個(gè)整數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)的降維。具體方法如下：

設(shè)πn為全體n維0-1向量構(gòu)成的集合，Z為整數(shù)集。對(duì)?x∈πn，x可被表述為如下形式：

再做如下映射：

對(duì)于f，有如下命題成立：

命 題 1：對(duì) ?x1,x2∈πn，若x1≠x2，則 必 有f(x1)≠f(x2)。

采用反證法可以對(duì)上述命題進(jìn)行證明。

命題1說(shuō)明：f可將不同長(zhǎng)度的0-1向量轉(zhuǎn)化為不同整數(shù)，并且通過(guò)fn進(jìn)行數(shù)據(jù)降維的過(guò)程中不會(huì)丟失原有的任何信息。

2.2 存在的問(wèn)題

理論上任意n維0-1向量可以轉(zhuǎn)化為一維整數(shù)，因此可以將m個(gè)輸入變量轉(zhuǎn)化為一個(gè)輸入變量，這樣神經(jīng)網(wǎng)絡(luò)的輸入層節(jié)點(diǎn)數(shù)最少只需要一個(gè)，而不是m個(gè)。但是，如果僅僅用一個(gè)十進(jìn)制數(shù)替代原先的m個(gè)變量，那么可能會(huì)大大增加神經(jīng)網(wǎng)絡(luò)的訓(xùn)練難度。

例如：設(shè)m為5，樣本A的原始輸入向量為(1，0，0，0，1)，轉(zhuǎn)化為十進(jìn)制數(shù)，即為17。樣本B的原始輸入向量為(0，0，0，0，1)，轉(zhuǎn)化為十進(jìn)制數(shù)，即為1。A和B只在一個(gè)位置上不同，應(yīng)該說(shuō)兩個(gè)樣本比較相似。但是轉(zhuǎn)化為十進(jìn)制數(shù)后，兩個(gè)樣本對(duì)應(yīng)的輸入值要相差16倍。再設(shè)樣本C的輸入向量為(0，1，1，1，0)。C與A在所有位置上都不同，但是C的輸入向量轉(zhuǎn)化為十進(jìn)制后為14，反而與A比較接近。一般來(lái)說(shuō)，A與B的輸出值往往是相同的，而A與C的輸出值更可能是不同的。這意味著輸出值對(duì)輸入值的變化非常敏感，而且通過(guò)神經(jīng)網(wǎng)絡(luò)得出的預(yù)測(cè)函數(shù)會(huì)有高頻且大幅的波動(dòng)。

雖然神經(jīng)網(wǎng)絡(luò)算法比很多其他算法更善于處理此類非線性的回歸，但在輸入值與輸出值之間幾乎毫無(wú)線性相關(guān)性的情況下，如果訓(xùn)練樣本并不是很多，那么神經(jīng)網(wǎng)絡(luò)也較難做出準(zhǔn)確的預(yù)測(cè)。

2.3 分段降維算法

解決上述問(wèn)題的辦法是將原始m維輸入向量分為k段（k＞1），提高算法效率同時(shí)保證算法的有效性。m維的輸入向量分為k段，每段轉(zhuǎn)化為一個(gè)整數(shù)，輸入變量轉(zhuǎn)化為k個(gè)整數(shù)。這樣對(duì)于任意一個(gè)樣本集，設(shè)原始輸入向量x=(a1,a2,…,am)（ai∈{0,1}，i=1,2,…,m），分段降維結(jié)果y=(b1,b2,…,bk)∈Zk（k≤m）。

k的取值既不能太大，也不能太小。如果k太大，達(dá)不到降低神經(jīng)網(wǎng)絡(luò)輸入層維數(shù)的目的，如果k太小，則輸出值對(duì)輸入值的變化會(huì)很敏感，從而增加神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的難度。由于k實(shí)際上就是輸入層的節(jié)點(diǎn)數(shù)，因此k是一個(gè)影響神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的變量，而神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)也會(huì)影響預(yù)測(cè)的效果。

分段降維算法如下：

步驟1：ifk|m!=int

步驟1.1：設(shè)h=m'/(k-1)

步驟1.2：Forj=0tok-2

依次將 (ajh+1,ajh+2,…ajh+h)記為Aj+1,將x的最后(m-m')個(gè)分量(am'+1,am'+2,…,am)記為Ak

步驟2：ifk|m=int

步驟2.1：設(shè)h=m/k

步驟2.2：Forj=0tok-1

依次將 (ajh+1,ajh+2,…ajh+h)記為Aj+1,將x的最后(m-m')個(gè)分量(am'+1,am'+2,…,am)記為Ak

步驟3：得到分為k段的向量x，記為(A1,A2,…,Ak)

步驟4：Forj=0tok

?Aj∈{A1,A2,…,Ak}將Aj轉(zhuǎn)化為整數(shù)f(Aj)

bj=f(Aj)

步驟5：得到k維整數(shù)向量y=(b1,b2,…,bk)∈Zk

上述將An×n劃分為An×n的過(guò)程中，可以保證An×n都有相同的維數(shù)An×n，并且能使An×n盡量大。這樣，An×n就能較為“均勻”地被劃分為An×n段。同時(shí)由于分段降維算法對(duì)于每個(gè)二進(jìn)制數(shù)都會(huì)與一個(gè)十進(jìn)制數(shù)一一對(duì)應(yīng)，因此降維前后的數(shù)據(jù)之間存在一一映射，降維并沒(méi)有使數(shù)據(jù)所包含的信息量減少，整個(gè)數(shù)據(jù)降維過(guò)程是可逆的。

3 模型綜合法

數(shù)據(jù)的降維提高了神經(jīng)網(wǎng)絡(luò)計(jì)算的效率，但是由于復(fù)雜社會(huì)網(wǎng)絡(luò)存在關(guān)系的復(fù)雜性，以及所擁有的冪律特性導(dǎo)致在利用神經(jīng)網(wǎng)絡(luò)進(jìn)行關(guān)系預(yù)測(cè)時(shí)存在的不平衡性問(wèn)題，即對(duì)于關(guān)系比較密集的社會(huì)網(wǎng)絡(luò)，預(yù)測(cè)出不存在的關(guān)系實(shí)際是存在的，反之在稀疏關(guān)系網(wǎng)絡(luò)預(yù)測(cè)出存在的關(guān)系實(shí)際是不存在的，這種不平衡性是由于模型本身造成的[8]，為了消除這種不平衡性，本文構(gòu)建預(yù)測(cè)模型綜合評(píng)價(jià)指標(biāo)基本上建立模型綜合方法，具體實(shí)現(xiàn)過(guò)程如下。

3.1 基本評(píng)價(jià)指標(biāo)

神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型的評(píng)價(jià)是建立在鄰接矩陣An×n基礎(chǔ)上，設(shè)Y=(aij)(n-m)×q是An×n中V的一個(gè)子矩陣，表示V中全部待預(yù)測(cè)的部分，q是待預(yù)測(cè)的列向量的數(shù)量。X=(bij)(n-m)×q是對(duì)Y的預(yù)測(cè)值（Y為真實(shí)值）。||A表示任意有限集合A的基數(shù)，N+表示正整數(shù)集，則有：

Np=(n-m)q，即Np為Y的元素總數(shù)；

Nt=|{(i,j)∈N+×N+|aij=bij}|，即Nt為預(yù)測(cè)正確的次數(shù)；

Mp=|{(i,j)∈N+×N+|aij=1}|，即Mp為預(yù)測(cè)集中真正存在的連邊數(shù)量；

Mt=|{(i,j)∈N+×N+|aij=bij=1}|，即Mt為在連邊真實(shí)存在的條件下，正確預(yù)測(cè)的次數(shù)。

評(píng)價(jià)指標(biāo)有兩個(gè)。一個(gè)是總預(yù)測(cè)準(zhǔn)確率P1，另一個(gè)是正類預(yù)測(cè)準(zhǔn)確率P2。

從本質(zhì)看P1反映的是模型整體的預(yù)測(cè)準(zhǔn)確率，P2反映的是模型對(duì)關(guān)系存在性的發(fā)現(xiàn)能力。之所以要進(jìn)一步計(jì)算P2，是因?yàn)樵诜治鰧?shí)際問(wèn)題中，人們往往更關(guān)注關(guān)系的存在性，而對(duì)關(guān)系的不存在性并不那么關(guān)注，從廣義上來(lái)看，關(guān)系的存在性與不存在性的受重視程度是不同的，P2會(huì)增強(qiáng)模型對(duì)非重視關(guān)系的發(fā)現(xiàn)能力。

因此P1和P2是評(píng)價(jià)模型預(yù)測(cè)效果的兩個(gè)基本指標(biāo)，兩個(gè)指標(biāo)缺一不可。如果忽視P2，而只看P1，那么將正類誤判為負(fù)類的概率就難以得到控制。另一方面，如果P2很高而P1很低，那么總的誤判損失還是會(huì)很大。為了彌補(bǔ)這個(gè)缺陷，本文建立基于P1和P2基本指標(biāo)的綜合評(píng)價(jià)指標(biāo)。

3.2 綜合評(píng)價(jià)指標(biāo)

將基本指標(biāo)P1和P2加權(quán)平均可以得到一個(gè)新的綜合指標(biāo)Pc，Pc可由式（4）確定：

γ1和γ2的取值是與使用者對(duì)P1和P2的重視程度有關(guān)，但是在實(shí)際應(yīng)用中Pc計(jì)算方法未必能真實(shí)體現(xiàn)使用者對(duì)P1和P2的重視程度。這是因?yàn)镻1和P2的標(biāo)準(zhǔn)差可能會(huì)有很大差異，在許多復(fù)雜網(wǎng)絡(luò)中(尤其是連邊較為稀疏網(wǎng)絡(luò)中)，由于真實(shí)存在的連邊要比節(jié)點(diǎn)對(duì)總數(shù)少很多，往往P2的標(biāo)準(zhǔn)差要比P1大很多，影響P2的偶然隨機(jī)因素要比P1大，P1的差異更大程度上是模型本身因素導(dǎo)致的。為了消除上述影響，只有對(duì)P1和P2做調(diào)整，使兩者的標(biāo)準(zhǔn)差相同，才能更加客觀地評(píng)價(jià)模型的預(yù)測(cè)能力。

設(shè)σi是Pi的標(biāo)準(zhǔn)差，則P1σ1和P2σ2具有相同的標(biāo)準(zhǔn)差，帶入公式（4）可得到：

其中γi由人為主觀決定。σi是Pi總體的性質(zhì)，無(wú)法直接結(jié)算，但是可以根據(jù)不?同模型得到的Pi值，通過(guò)計(jì)算Pi的樣本標(biāo)準(zhǔn)差 ，再將作為σi的估計(jì)值。

3.3 模型綜合

利用神經(jīng)網(wǎng)絡(luò)進(jìn)行關(guān)系預(yù)測(cè)時(shí)，不同的模型參數(shù)，相同的輸入其輸出的預(yù)測(cè)結(jié)果也不同，在這里把擁有不同參數(shù)的神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型稱為不同的分類器。在實(shí)際問(wèn)題求解過(guò)程中，如果以預(yù)測(cè)效果最好的一個(gè)分類器預(yù)測(cè)結(jié)果為準(zhǔn)，可能會(huì)導(dǎo)致較大的誤判風(fēng)險(xiǎn)，因?yàn)橐粋€(gè)分類器預(yù)測(cè)效果的好壞，通常需要通過(guò)已知樣本進(jìn)行檢測(cè)才能得出，當(dāng)一個(gè)分類器在用于檢測(cè)模型效果的已知樣本上表現(xiàn)出良好效果時(shí)，雖然可以認(rèn)為該分類器的預(yù)測(cè)能力是較強(qiáng)的，但其未必會(huì)在待預(yù)測(cè)的未知樣本上也能取得最好的效果。即使該分類器在未知樣本上的預(yù)測(cè)能力仍然是最強(qiáng)的，其預(yù)測(cè)效果也未必好于將多個(gè)分類器綜合得出的結(jié)果。因此，相對(duì)于僅僅“信任”一個(gè)分類器的做法，本文將若干個(gè)分類器組合起來(lái)進(jìn)行預(yù)測(cè)，降低結(jié)果的誤判風(fēng)險(xiǎn)。基本原理是對(duì)各神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型賦予權(quán)重，根據(jù)各個(gè)分類器的預(yù)測(cè)值加權(quán)平均來(lái)獲得最終預(yù)測(cè)結(jié)果，加權(quán)平均值表達(dá)形式如下：

其中，H為分類器個(gè)數(shù)，yi是第i個(gè)分類器的預(yù)測(cè)值，βi第i個(gè)分類器的權(quán)重系數(shù)。問(wèn)題的關(guān)鍵轉(zhuǎn)換為如何得到每個(gè)分類器的βi值。

在公式（6）中，βi值的大小是與預(yù)測(cè)效果成正比的，如果只考慮兩個(gè)分類器ρ1和ρ2的情形下，分類器ρi（i=1,2）的權(quán)重系數(shù)βi的計(jì)算公式為：

其中，Pc(ρi)是分類器ρi對(duì)檢測(cè)集樣本的預(yù)測(cè)效果綜合評(píng)價(jià)指標(biāo)Pc的值。在其他條件不變的情況下，βi與Pc(ρi)成正比，說(shuō)明預(yù)測(cè)效果越好，權(quán)重系數(shù)越大。而φ(ρ1,ρ2)是兩個(gè)分類器ρ1和ρ2預(yù)測(cè)值相同的概率，，其中Ns是用于檢測(cè)集樣本總數(shù)，yρ1,i和yρ2,i分別是分類器ρ1和ρ2對(duì)第i個(gè)檢測(cè)集樣本的預(yù)測(cè)值。

根據(jù)公式（7），φ(ρ1,ρ2)越大，則βi越小。如果φ(ρ1,ρ2)達(dá)到最大值1，則有：

這樣，在使用兩個(gè)預(yù)測(cè)結(jié)果完全相同的分類器的情況下，兩個(gè)分類器權(quán)重系數(shù)總和與僅僅保留其中一個(gè)分類器的情況下的權(quán)重系數(shù)是相同的。如果φ(ρ1,ρ2)達(dá)到最小值0，則βi=Pc(ρi)，說(shuō)明當(dāng)兩個(gè)預(yù)測(cè)結(jié)果完全不同的分類器組合起來(lái)時(shí)，他們各自的權(quán)重都不會(huì)被削弱。

把式（7）式擴(kuò)展到兩個(gè)以上分類器的情形，在有H個(gè)分類器情況下，第i（i=1,2,…H）個(gè)分類器ρi的權(quán)重系數(shù)βi的計(jì)算公式為：

由于φ(ρi,ρi)=1，因此式（8）又能寫成以下形式：

因此，模型綜合的權(quán)值βi求解過(guò)程為：

步驟1：從已知樣本中抽出一部分，將其作為檢測(cè)集樣本，并用各分類器對(duì)檢測(cè)集樣本進(jìn)行預(yù)測(cè)，得出預(yù)測(cè)值；

步驟2：根據(jù)第一步的預(yù)測(cè)結(jié)果，計(jì)算各分類器的Pc值；

步驟3：計(jì)算每?jī)蓚€(gè)分類器預(yù)測(cè)值相同的概率φ(ρi,ρj)；

步驟4：利用式（9）計(jì)算βi。

4 實(shí)例驗(yàn)證

本文以美國(guó)政治博客引用關(guān)系網(wǎng)絡(luò)為實(shí)例（數(shù)據(jù)來(lái)源于www.linkprediction.org 2014年6月），網(wǎng)絡(luò)中節(jié)點(diǎn)是博客文章，如果博客文章A引用了博客文章B，則在網(wǎng)絡(luò)中代表文章A的節(jié)點(diǎn)會(huì)有一條有向邊指向代表文章B的節(jié)點(diǎn)。驗(yàn)證數(shù)據(jù)選用這一網(wǎng)絡(luò)的一個(gè)導(dǎo)出子網(wǎng)絡(luò)進(jìn)行實(shí)證分析，該子網(wǎng)絡(luò)包含150個(gè)節(jié)點(diǎn)，將網(wǎng)絡(luò)中的節(jié)點(diǎn)編號(hào)為1～150號(hào)，并將這150個(gè)節(jié)點(diǎn)構(gòu)成的集合記為Np。以1～100號(hào)節(jié)點(diǎn)為訓(xùn)練集，101～150號(hào)節(jié)點(diǎn)為預(yù)測(cè)集。為檢驗(yàn)算法效果，假定有序節(jié)點(diǎn)對(duì)集合Yp={(x,y)|x∈Np,y∈Np,101≤x≤150,106≤y≤150}中的二元關(guān)系存在性是未知的，其余節(jié)點(diǎn)對(duì)的二元關(guān)系存在性是已知的。然后從106～150號(hào)節(jié)點(diǎn)中隨機(jī)選擇10個(gè)節(jié)點(diǎn)，構(gòu)成集合Kt，利用本文提出的方法對(duì)有序節(jié)點(diǎn)對(duì)集合Y={(x,y)|x∈Np,y∈Kt,101≤x≤150}中的二元關(guān)系存在性進(jìn)行預(yù)測(cè)。

神經(jīng)網(wǎng)絡(luò)求解約束條件設(shè)置：①訓(xùn)練的最大迭代次數(shù)為1000；②連接函數(shù)選擇為L(zhǎng)ogistic函數(shù)；③初始開(kāi)始進(jìn)行訓(xùn)練的次數(shù)選為50；④訓(xùn)練的學(xué)習(xí)率取值為0.01；⑤訓(xùn)練時(shí)觀察模型誤差的頻率是每迭代10次觀察一次；⑥迭代收斂的判斷標(biāo)準(zhǔn)是相鄰兩次觀察到的誤差值相差小于5×10-7。

不同分類器的參數(shù)調(diào)整是：①輸入向量的維數(shù)k；②隱藏層的節(jié)點(diǎn)數(shù)s；③正類樣本權(quán)重c。

將Yt={(x,y)|x∈Np,y∈Np,101≤x≤150,101≤y≤105}作為檢測(cè)集，以檢測(cè)不同參數(shù)下模型的預(yù)測(cè)效果。在k取10和20、s取15和30、c取5和6情況下，三個(gè)參數(shù)的全部組合共是8，分別在這8個(gè)參數(shù)組合下對(duì)檢測(cè)集進(jìn)行預(yù)測(cè)實(shí)驗(yàn)。測(cè)試實(shí)驗(yàn)發(fā)現(xiàn)s為30，c為6情況下的兩個(gè)模型預(yù)測(cè)效果最好。于是s取為30，c取為6，再分別取k為5、15和25，進(jìn)行三組實(shí)驗(yàn)。

根據(jù)算法1，在k取5情況下的數(shù)據(jù)降維是：

根據(jù)公式（2）和（3）計(jì)算得到11個(gè)參數(shù)組合下預(yù)測(cè)模型評(píng)價(jià)指標(biāo)如表1所示。

表1 參數(shù)組合及預(yù)測(cè)模型評(píng)價(jià)指標(biāo)

計(jì)算出表1中任意兩個(gè)模型預(yù)測(cè)值相同的概率如表3所示。

表2 各個(gè)預(yù)測(cè)模型綜合評(píng)價(jià)指標(biāo)值

表3 任意兩個(gè)模型預(yù)測(cè)值相同的概率

根據(jù)公式（9）各個(gè)模型權(quán)重系數(shù)βi如表4所示。

表4 各個(gè)模型的權(quán)重系數(shù)（歸一化前）

依據(jù)表1中11個(gè)模型對(duì)Y中的關(guān)系進(jìn)行預(yù)測(cè)，得出各模型對(duì)Y中有序各節(jié)點(diǎn)對(duì)關(guān)系存在性的預(yù)測(cè)值，然后對(duì)于每個(gè)待預(yù)測(cè)的有序節(jié)點(diǎn)對(duì)，根據(jù)式(6)并采用表4的βi值計(jì)算各模型預(yù)測(cè)值的加權(quán)平均，該加權(quán)平均值即為整個(gè)模型最終的預(yù)測(cè)值。將各模型的預(yù)測(cè)值以及模型最終預(yù)測(cè)值與真實(shí)值做比較，計(jì)算各模型的P1值和P2值以及模型綜合的預(yù)測(cè)效果P1值和P2如下頁(yè)表5所示。

從表5可以看出，最終對(duì)預(yù)測(cè)值求加權(quán)平均后得到的綜合模型的P2值是所有模型中最高的。雖然3號(hào)模型和8號(hào)模型的P2值與最終綜合模型的P2值相同，但這兩個(gè)模型的P1值都相對(duì)較低。在P1值方面，除去10號(hào)模型與11號(hào)模型以外，其他模型的P1值都比最終綜合模型低。10號(hào)模型與11號(hào)模型的P1值比最終綜合模型的P1值略高，但在P2值方面卻不如最終綜合模型。根據(jù)表5，可以計(jì)算出各模型的Pc值(其中對(duì)P1和P2的重視程度相同)如表6所示。

表5 各模型的預(yù)測(cè)效果以及模型綜合法預(yù)測(cè)效果

表6 各個(gè)模型的預(yù)測(cè)效果綜合評(píng)價(jià)指標(biāo)值

從表6可知，在對(duì)P1和P2的重視程度相同的前提下，綜合模型的Pc值是最高的?？梢?jiàn)綜合模型預(yù)測(cè)效果比單個(gè)模型要好。

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

隨著互聯(lián)網(wǎng)+的不斷發(fā)展，社會(huì)網(wǎng)絡(luò)逐步滲透到社會(huì)各個(gè)領(lǐng)域，充分利用網(wǎng)絡(luò)資源拓展服務(wù)成為互聯(lián)網(wǎng)經(jīng)濟(jì)時(shí)代面臨的一個(gè)突出問(wèn)題，而有效地預(yù)知網(wǎng)絡(luò)中二元不對(duì)稱關(guān)系可以為用戶準(zhǔn)確地把握措施的實(shí)施提供了有力的支持。本文基于社會(huì)網(wǎng)絡(luò)的復(fù)雜性和動(dòng)態(tài)性，利用神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)特性，構(gòu)建了預(yù)測(cè)時(shí)高維輸入向量降維的算法，在建立模型綜合評(píng)價(jià)指標(biāo)基礎(chǔ)上，構(gòu)造了具有消除不平衡性的模型綜合預(yù)測(cè)方法，實(shí)例驗(yàn)證表明，本文所提算法和方法是有效的。