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

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

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

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

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

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