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

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

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

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

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

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