在線社會網(wǎng)絡的演化模型及關鍵技術研究.pdf

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

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

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

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

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