社會(huì)網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的發(fā)現(xiàn)算法研究.pdf

1、在我們的生活中網(wǎng)絡(luò)無(wú)處不在，典型的人類社會(huì)網(wǎng)、生活中的朋友圈、微博圈、各種社交網(wǎng)站如臉譜（Facebook）等這些都屬于社會(huì)網(wǎng)絡(luò)的范疇。社會(huì)網(wǎng)絡(luò)并不是一個(gè)新的研究領(lǐng)域，早在十九世紀(jì)就已經(jīng)有學(xué)者開始針對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行研究，而今隨著社會(huì)與科技的發(fā)展，現(xiàn)代科學(xué)研究的進(jìn)一步加深，也促進(jìn)了對(duì)復(fù)雜網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)的研究。
　　研究社會(huì)網(wǎng)絡(luò)就離不開研究網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)這一基本內(nèi)容，關(guān)鍵節(jié)點(diǎn)挖掘是以尋找網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)為目的的，關(guān)鍵節(jié)點(diǎn)在衡量網(wǎng)絡(luò)的抗

2、毀性、網(wǎng)絡(luò)效率、魯棒性等方面具有重大意義。在挖掘出網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)后，就可以有針對(duì)性的制定相應(yīng)策略，以達(dá)到對(duì)網(wǎng)絡(luò)的有效控制，從而使網(wǎng)絡(luò)能更好的服務(wù)于人類。
　　現(xiàn)在的很多研究者提出了各種關(guān)鍵節(jié)點(diǎn)挖掘算法，依據(jù)這些算法的基本思想進(jìn)行劃分，可以分為基于網(wǎng)絡(luò)全局信息和基于網(wǎng)絡(luò)局部信息的算法?；诰W(wǎng)絡(luò)全局信息的算法特點(diǎn)是挖掘結(jié)果的精準(zhǔn)度較高，但是算法的復(fù)雜度也高，通常都高于O(N3)，這類算法在選取節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)時(shí)通常以節(jié)點(diǎn)的全局信息為

3、考量，如節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置是不是更接近整個(gè)網(wǎng)絡(luò)的中心，該類算法由于計(jì)算復(fù)雜度過高，因此不適用于大型網(wǎng)絡(luò)，尤其是海量數(shù)據(jù)處理，如處理節(jié)點(diǎn)數(shù)量過億，且網(wǎng)絡(luò)整體集聚系數(shù)較高的網(wǎng)絡(luò)；而基于網(wǎng)絡(luò)局部信息的算法，其特點(diǎn)是只選取節(jié)點(diǎn)的局部信息作為其重要性的衡量指標(biāo)，例如最簡(jiǎn)單的以節(jié)點(diǎn)的度值作為其重要性評(píng)價(jià)指標(biāo)，稍微復(fù)雜一些的如考量節(jié)點(diǎn)的度以及其鄰居節(jié)點(diǎn)的度值總和為評(píng)價(jià)指標(biāo)，該類算法在計(jì)算節(jié)點(diǎn)的重要性評(píng)價(jià)指標(biāo)時(shí)僅選取了節(jié)點(diǎn)自身的固有信息或節(jié)點(diǎn)及其有限層

4、鄰居節(jié)點(diǎn)的信息，故其計(jì)算復(fù)雜度低，但在挖掘結(jié)果的精準(zhǔn)度上不高。
　　基于以上問題，本文通過對(duì)近年來(lái)關(guān)鍵節(jié)點(diǎn)挖掘算法代表性文獻(xiàn)的研究，分析了目前一些具有代表性的關(guān)鍵節(jié)點(diǎn)挖掘算法，在此基礎(chǔ)上，基于網(wǎng)絡(luò)局部半局部信息，提出了一種新的社會(huì)網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)挖掘算法。節(jié)點(diǎn)的重要性是一個(gè)相對(duì)的概念，可以用“高”和“低”來(lái)表達(dá)其重要的程度，故可以構(gòu)建一個(gè)用于表達(dá)節(jié)點(diǎn)重要性程度的識(shí)別框架θ=(high,low)，分別定義兩個(gè)指標(biāo)fi和gi，其中fi表

5、示節(jié)點(diǎn)vi及其鄰居節(jié)點(diǎn)的度之和，gi表示節(jié)點(diǎn)的集聚系數(shù)，并對(duì)該指標(biāo)進(jìn)行了歸一化處理，基于這兩個(gè)指標(biāo)，依據(jù)D-S證據(jù)理論，可以分別構(gòu)建各自的基本概率分配函數(shù)(BPA) mfi和mpi，其含義是在識(shí)別框架θ=(high,low)下，這兩個(gè)指標(biāo)對(duì)于節(jié)點(diǎn)重要性“高”和“低”支持的程度，最后通過D-S證據(jù)理論合成公式，對(duì)mfi和mpi進(jìn)行合并，得到一個(gè)新的節(jié)點(diǎn)重要性的評(píng)價(jià)指標(biāo)DSC(D-S clustering centrality)中心性指標(biāo)，

6、該指標(biāo)對(duì)節(jié)點(diǎn)重要性的“高”和“低”以概率的形式進(jìn)行了量化，以得到關(guān)鍵節(jié)點(diǎn)重要性的排序結(jié)果。
　　由于該算法只考慮了網(wǎng)絡(luò)的局部信息，因此算法的時(shí)間復(fù)雜度較低。在仿真實(shí)驗(yàn)和實(shí)證網(wǎng)絡(luò)上的測(cè)試結(jié)果表明，該算法在時(shí)間復(fù)雜度上明顯優(yōu)于一些代表性的挖掘算法，如基于節(jié)點(diǎn)介數(shù)中心性指標(biāo)的挖掘算法、基于節(jié)點(diǎn)接近中心性指標(biāo)的挖掘算法等。與其它基于網(wǎng)絡(luò)局部或半局部信息的挖掘算法相比，該算法在挖掘的精準(zhǔn)度也有顯著的提高。
　　本文對(duì)社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)重