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

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

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

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

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

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

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