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

  更多相關(guān)文章： 關(guān)鍵節(jié)點挖掘 社會網(wǎng)絡(luò) DS證據(jù)理論 集聚系數(shù)

【摘要】：在我們的生活中網(wǎng)絡(luò)無處不在，典型的人類社會網(wǎng)、生活中的朋友圈、微博圈、各種社交網(wǎng)站如臉譜（Facebook）等這些都屬于社會網(wǎng)絡(luò)的范疇。社會網(wǎng)絡(luò)并不是一個新的研究領(lǐng)域，早在十九世紀(jì)就已經(jīng)有學(xué)者開始針對社會網(wǎng)絡(luò)進(jìn)行研究，而今隨著社會與科技的發(fā)展，現(xiàn)代科學(xué)研究的進(jìn)一步加深，也促進(jìn)了對復(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ò)的抗毀性、網(wǎng)絡(luò)效率、魯棒性等方面具有重大意義。在挖掘出網(wǎng)絡(luò)的關(guān)鍵節(jié)點后，就可以有針對性的制定相應(yīng)策略，以達(dá)到對網(wǎng)絡(luò)的有效控制，從而使網(wǎng)絡(luò)能更好的服務(wù)于人類。 現(xiàn)在的很多研究者提出了各種關(guān)鍵節(jié)點挖掘算法，依據(jù)這些算法的基本思想進(jìn)行劃分，可以分為基于網(wǎng)絡(luò)全局信息和基于網(wǎng)絡(luò)局部信息的算法�；诰W(wǎng)絡(luò)全局信息的算法特點是挖掘結(jié)果的精準(zhǔn)度較高，但是算法的復(fù)雜度也高，通常都高于O(N3)，這類算法在選取節(jié)點重要性評價指標(biāo)時通常以節(jié)點的全局信息為考量，如節(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é)點的局部信息作為其重要性的衡量指標(biāo)，例如最簡單的以節(jié)點的度值作為其重要性評價指標(biāo)，稍微復(fù)雜一些的如考量節(jié)點的度以及其鄰居節(jié)點的度值總和為評價指標(biāo)，該類算法在計算節(jié)點的重要性評價指標(biāo)時僅選取了節(jié)點自身的固有信息或節(jié)點及其有限層鄰居節(jié)點的信息，故其計算復(fù)雜度低，但在挖掘結(jié)果的精準(zhǔn)度上不高。 基于以上問題，本文通過對近年來關(guān)鍵節(jié)點挖掘算法代表性文獻(xiàn)的研究，分析了目前一些具有代表性的關(guān)鍵節(jié)點挖掘算法，在此基礎(chǔ)上，基于網(wǎng)絡(luò)局部半局部信息，提出了一種新的社會網(wǎng)絡(luò)中關(guān)鍵節(jié)點挖掘算法。節(jié)點的重要性是一個相對的概念，可以用“高”和“低”來表達(dá)其重要的程度，故可以構(gòu)建一個用于表達(dá)節(jié)點重要性程度的識別框架 (high,low)，分別定義兩個指標(biāo)f i和g i，其中表示節(jié)點v i及其鄰居節(jié)點的度之和，表示節(jié)點的集聚系數(shù)，并對該指標(biāo)進(jìn)行了歸一化處理，基于這兩個指標(biāo)，依據(jù)D-S證據(jù)理論，可以分別構(gòu)建各自的基本概率分配函數(shù)(BPA)m fi和m pi，其含義是在識別框架 下，這兩個指標(biāo)對于節(jié)點重要性“高”和“低”支持的程度，最后通過D-S證據(jù)理論合成公式，對和進(jìn)行合并，，得到一個新的節(jié)點重要性的評價指標(biāo)DSC(D-Sclustering centrality)中心性指標(biāo)，該指標(biāo)對節(jié)點重要性的“高”和“低”以概率的形式進(jìn)行了量化，以得到關(guān)鍵節(jié)點重要性的排序結(jié)果。 由于該算法只考慮了網(wǎng)絡(luò)的局部信息，因此算法的時間復(fù)雜度較低。在仿真實驗和實證網(wǎng)絡(luò)上的測試結(jié)果表明，該算法在時間復(fù)雜度上明顯優(yōu)于一些代表性的挖掘算法，如基于節(jié)點介數(shù)中心性指標(biāo)的挖掘算法、基于節(jié)點接近中心性指標(biāo)的挖掘算法等。與其它基于網(wǎng)絡(luò)局部或半局部信息的挖掘算法相比，該算法在挖掘的精準(zhǔn)度也有顯著的提高。 本文對社會網(wǎng)絡(luò)中的節(jié)點重要性排序算法進(jìn)行了細(xì)致的研究，以構(gòu)建新的節(jié)點重要性評價指標(biāo)為出發(fā)點，分析總結(jié)了目前的主流挖掘算法，對網(wǎng)絡(luò)中關(guān)鍵節(jié)點挖掘這一網(wǎng)絡(luò)科學(xué)中的基本問題進(jìn)行了研究。
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前9條

1 孫全,葉秀清,顧偉康;一種新的基于證據(jù)理論的合成公式[J];電子學(xué)報;2000年08期

2 赫南;李德毅;淦文燕;朱熙;;復(fù)雜網(wǎng)絡(luò)中重要性節(jié)點發(fā)掘綜述[J];計算機(jī)科學(xué);2007年12期

3 于俊清;劉青;何云峰;;基于感興趣區(qū)域的H.264視頻加密算法[J];計算機(jī)學(xué)報;2010年05期

4 任曉龍;呂琳媛;;網(wǎng)絡(luò)重要節(jié)點排序方法綜述[J];科學(xué)通報;2014年13期

5 王冰,修志龍,唐煥文;基于復(fù)雜網(wǎng)絡(luò)理論的代謝網(wǎng)絡(luò)結(jié)構(gòu)研究進(jìn)展[J];中國生物工程雜志;2005年06期

6 陳勇,胡愛群,胡嘯;通信網(wǎng)中節(jié)點重要性的評價方法[J];通信學(xué)報;2004年08期

7 陳靜;孫林夫;;復(fù)雜網(wǎng)絡(luò)中節(jié)點重要度評估[J];西南交通大學(xué)學(xué)報;2009年03期

8 章忠志,榮莉莉,周濤;一類無標(biāo)度合作網(wǎng)絡(luò)的演化模型[J];系統(tǒng)工程理論與實踐;2005年11期

9 任卓明;邵鳳;劉建國;郭強(qiáng);汪秉宏;;基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點重要性度量方法研究[J];物理學(xué)報;2013年12期

本文編號：1221584