在線社會(huì)網(wǎng)絡(luò)的演化模型及關(guān)鍵技術(shù)研究.pdf

1、隨著各種在線社會(huì)網(wǎng)絡(luò)的飛速發(fā)展，社會(huì)網(wǎng)絡(luò)研究的節(jié)點(diǎn)規(guī)模上升到了數(shù)百萬(wàn)甚至是千萬(wàn)級(jí)。在線社會(huì)網(wǎng)絡(luò)具有規(guī)模巨大，鏈路眾多，關(guān)系復(fù)雜等特點(diǎn)。網(wǎng)絡(luò)演化和結(jié)構(gòu)特征研究是在線社會(huì)網(wǎng)絡(luò)研究的兩個(gè)重要方面，并可進(jìn)一步擴(kuò)展成為演化模型、關(guān)鍵用戶識(shí)別和鏈路預(yù)測(cè)這三個(gè)問題。其中，網(wǎng)絡(luò)演化研究的實(shí)質(zhì)是網(wǎng)絡(luò)的生成機(jī)制，具體包括網(wǎng)絡(luò)中各組成部分之間的關(guān)系及其整體特征，是從局部對(duì)網(wǎng)絡(luò)的宏觀整體研究。中心性和用戶行為是刻畫網(wǎng)絡(luò)演化的兩個(gè)重要指標(biāo)，其中，中心性既對(duì)社會(huì)網(wǎng)

2、絡(luò)的演化有著重要的影響，也是衡量用戶重要性的關(guān)鍵指標(biāo)之一，用戶行為則是另一個(gè)評(píng)估用戶重要性的關(guān)鍵指標(biāo)，也是鏈路預(yù)測(cè)的關(guān)鍵依賴條件之一。在此基礎(chǔ)上，網(wǎng)絡(luò)演化、關(guān)鍵用戶識(shí)別和鏈路預(yù)測(cè)這三個(gè)問題形成了一個(gè)有機(jī)的整體。本文主要針對(duì)網(wǎng)絡(luò)演化和結(jié)構(gòu)特征兩個(gè)方面所涉及的上述三個(gè)問題進(jìn)行深入研究，提出一系列模型與算法。本文的主要?jiǎng)?chuàng)新點(diǎn)工作和成果包括：
　　網(wǎng)絡(luò)演化方面
　　(1)針對(duì)現(xiàn)有網(wǎng)絡(luò)演化模型難以準(zhǔn)確刻畫在線社會(huì)網(wǎng)絡(luò)加速增長(zhǎng)過(guò)程中老用

3、戶對(duì)新用戶產(chǎn)生關(guān)注關(guān)系這一問題，依次提出了概率復(fù)制增長(zhǎng)模型、加速?gòu)?fù)制增長(zhǎng)模型和帶更新過(guò)程的加速概率復(fù)制增長(zhǎng)模型，通過(guò)解析計(jì)算、模擬仿真和實(shí)際網(wǎng)絡(luò)測(cè)量，結(jié)果均顯示了上述模型與真實(shí)在線社會(huì)網(wǎng)絡(luò)拓?fù)涮卣鞯囊恢滦?，能夠很好的刻畫真?shí)網(wǎng)絡(luò)的演化進(jìn)程。
　　(2)針對(duì)當(dāng)前尚缺乏網(wǎng)絡(luò)拓?fù)涮匦詳?shù)學(xué)刻畫方法這一問題，給出了針對(duì)前面所提出的三個(gè)網(wǎng)絡(luò)演化模型的度分布、平均最短路徑和簇聚集系數(shù)的解析方法，通過(guò)理論分析得出上述三個(gè)拓?fù)涮卣髟鲩L(zhǎng)規(guī)律的同時(shí)，也

4、對(duì)基于加速增長(zhǎng)機(jī)制的演化模型網(wǎng)絡(luò)特征的理論分析提供了借鑒和參考。
　　網(wǎng)絡(luò)結(jié)構(gòu)特征方面
　　(3)針對(duì)目前在線社會(huì)網(wǎng)絡(luò)關(guān)鍵用戶識(shí)別算法識(shí)別率低、排序片面等問題，考慮用戶間動(dòng)態(tài)“提及”關(guān)系及其頻率的相對(duì)重要性，通過(guò)迭代方式量化了在線社會(huì)網(wǎng)絡(luò)用戶的關(guān)鍵性，在此基礎(chǔ)上，提出了一種基于用戶關(guān)系的關(guān)鍵用戶識(shí)別算法，并給出了算法收斂性和時(shí)間復(fù)雜度分析。和主流算法對(duì)比，該算法可以避免僵尸粉欺騙、名人的普通朋友重要性偏高、排序片面等問題，能

5、夠更好地識(shí)別出在線社會(huì)網(wǎng)絡(luò)中的關(guān)鍵用戶。
　　(4)針對(duì)現(xiàn)有在線社會(huì)網(wǎng)絡(luò)鏈路預(yù)測(cè)準(zhǔn)確度和精確度較低的問題，提出了一個(gè)基于用戶行為特征的稀疏學(xué)習(xí)算法。該算法以用戶關(guān)注關(guān)系作為分類特征基礎(chǔ)，考慮用戶間的“提及”關(guān)系，引入用戶行為特征矩陣作為約束條件，利用核投影機(jī)(KPM)算法實(shí)現(xiàn)從高維Hilbert空間到最佳D維空間的選取，在此基礎(chǔ)上實(shí)現(xiàn)用戶間的有效鏈路預(yù)測(cè)。我們給出了該算法的表示定理并證明了算法的收斂性。實(shí)驗(yàn)結(jié)果表明，該算法鏈路預(yù)測(cè)