基于圖特征的介度中心近似算法研究.pdf

1、目前復(fù)雜網(wǎng)絡(luò)的研究領(lǐng)域已經(jīng)涉及到了計算機科學(xué)、生物工程、物理以及城市交通學(xué)等各個學(xué)科，與人類生活等各個方面的聯(lián)系越來越緊密。所以復(fù)雜網(wǎng)絡(luò)分析是目前研究的一個熱點。在復(fù)雜網(wǎng)絡(luò)分析中一個重要研究方向就是分析網(wǎng)絡(luò)中節(jié)點的重要程度，尋找網(wǎng)絡(luò)中的關(guān)鍵節(jié)點，例如通過控制恐怖組織的領(lǐng)導(dǎo)者可以控制整個恐怖組織，進而避免一些恐怖襲擊案件的發(fā)生；對網(wǎng)絡(luò)中的關(guān)鍵服務(wù)器加以保護，可以防止其受到病毒或者黑客的攻擊，從而達(dá)到整個網(wǎng)絡(luò)正常運行的目的；通過隔離傳染源，

2、有效預(yù)防傳染病毒的傳播與擴散；根據(jù)人體致命性的蛋白質(zhì)組成研制出新的藥物等等。上述應(yīng)用中都需要使用的算法是介度中心算法，因此介度中心算法在復(fù)雜網(wǎng)絡(luò)分析中占有重要位置。
　　雖然介度中心算法在實際應(yīng)用中的使用比較廣泛，但是還存在兩個問題。首先，介度中心算法的應(yīng)用場景不確定，目前的衡量網(wǎng)絡(luò)節(jié)點重要程度的算法比較多，還有一些其他常用關(guān)鍵點發(fā)現(xiàn)算法，如 PageRank算法等，對于何時選擇介度中心算法進行關(guān)鍵點發(fā)現(xiàn)目前還沒有研究，因此確定介

3、度中心算法的應(yīng)用場景是目前亟需解決的一個問題；其次，介度中心算法的計算量過大，運行時間長，在大數(shù)據(jù)時代不適用，現(xiàn)在最快的介度中心的算法時間復(fù)雜度為O(V*E)，大規(guī)模的圖完成該算法的時間一般比較長，對于一個擁有百萬節(jié)點的圖數(shù)據(jù)，完成計算就需要十幾個月的時間，而且雖然目前的相關(guān)工作降低了介度中心算法的運行時間，但是完成一個節(jié)點規(guī)模超過百萬的圖的介度中心值計算仍然需要數(shù)月的時間，因此介度中心算法在大數(shù)據(jù)時代不適用。
　　為了確定介度中

4、心算法的應(yīng)用場景，本文通過比較介度中心算法和 PageRank算法得到的關(guān)鍵點集合所處在網(wǎng)絡(luò)上位置的差異，根據(jù)7種網(wǎng)絡(luò)類型下的15個真實數(shù)據(jù)集的實驗結(jié)果分析出了這兩種關(guān)鍵點發(fā)現(xiàn)算法的應(yīng)用場景。介度中心算法用于查找整個網(wǎng)絡(luò)中的重要節(jié)點，PageRank算法用于查找某個領(lǐng)域內(nèi)熟知度比較高的點。
　　為了解決介度中心算法計算量過大的問題，本文通過近似算法的角度來降低介度中心算法的計算量。經(jīng)研究發(fā)現(xiàn)，目前的復(fù)雜網(wǎng)絡(luò)都呈現(xiàn)小世界網(wǎng)絡(luò)和冪律分

5、布的特點，可以考慮將圖本身的特征或者再加上其他的直觀圖特征與近似算法結(jié)合來降低介度中心算法的計算時間，使之能達(dá)到實用的程度。本文根據(jù)圖數(shù)據(jù)本身的特征提出了一種基于頂點加權(quán)的介度中心近似算法，具體做法是選取高影響力的源點與頂點加權(quán)的方式來降低介度中心算法的計算量，使用該算法的加速比平均為25，而近似結(jié)果的誤差率小于0.01％，符合在實際應(yīng)用中只關(guān)心部分重要節(jié)點排名的要求。所以，基于頂點加權(quán)的介度中心近似算法在保證近似結(jié)果精確度的前提下，大