社會網絡中的社區(qū)發(fā)現(xiàn)與鏈接預測算法研究.pdf

1、社會網絡是社會科學與計算機科學的交叉研究方向。隨著互聯(lián)網的發(fā)展，以臉譜網、微博為代表的在線社交網絡平臺興起，傳統(tǒng)的以幾十人為研究對象的社會網絡分析研究讓位于動輒成千上萬個節(jié)點規(guī)模的在線社會網絡。與傳統(tǒng)社會網絡類似，在線社會網絡的基本研究單位也是一個社會圖，可以用與傳統(tǒng)社會網絡分析類似的算法進行研究。然而，在線社會網絡與傳統(tǒng)社會網絡在兩個方面有非常大的不同：1）在線社會網絡的規(guī)模非常巨大，其節(jié)點和鏈接數動輒數以百萬計；2）在線社會網絡的關

2、聯(lián)關系非常復雜，兩個節(jié)點間的關系往往在數秒內發(fā)生變化。種種這些特點，需要有對傳統(tǒng)社會網絡分析的方法和算法進行發(fā)展以適應新的應用環(huán)境。
　　社區(qū)發(fā)現(xiàn)算法大致分為以下幾種：使用圖分割方法將社會網絡中的節(jié)點分到指定的幾個社區(qū)，這種方式需要指定社區(qū)的數目和大小，而實際上這種情況往往不成立。層次聚類算法往往得到多個不同的解。模塊函數方法需要的計算量非常大，不適合在當前線社會網絡環(huán)境。由此，基于譜聚類算法，引入了一種正定譜聚類算法。譜聚類算法

3、利用降維降低聚類的復雜度，且不需要事先制定分區(qū)的數目和大小。正定譜聚類算法則通過機器學習的方法挑選樣本然后再降維進一步地降低了聚類的復雜度，使得算法更加適合于在線社會網絡的環(huán)境。
　　基于社會網絡中的兩點間距離的圖構建方式是譜聚類和正定譜聚類算法的基礎。這種圖構建方式是整個算法的瓶頸部分，需要消耗大量的計算資源。同時這種構圖方式不能適應基準的變化，且沒有利用社會關系圖中的整體信息。針對這些缺點，引入了一種稱之為?1-圖的圖構建方式

4、，這種圖構建是一種稀疏構建方式，適合于在線社會網絡。另外，針對在線社會網絡中大量存在的有向社會網絡情況，介紹了一種基于隨機游走的圖拉普拉斯矩陣來進行處理。
　　此外，通過對社會網絡的鏈接預測問題的研究，將其抽象為一個二分類問題，可以使用機器學習的方式進行處理。在核投影機(Kernel Projection Machine,KPM)算法的基礎上，提出了一種名為截斷KPM算法的分類算法，給出了這個算法的表示定理并予以證明。同時，給出了

5、截斷KPM算法的兩個收斂定理，并對這兩個定理進行了證明。實驗結果表明，截斷KPM算法能在更寬的截斷閾值范圍內取得更高的預測精度。
　　社會網絡中存在著大量的未標記樣本，如何有效地利用這些未標記樣本也是一個重要研究點。通過研究已有的半監(jiān)督學習算法，將一種名為自訓練半監(jiān)督算法的方法引入到截斷KPM算法中來，提出了一種名為半監(jiān)督截斷KPM算法的半監(jiān)督分類算法。在對比實驗中，半監(jiān)督截斷KPM算法比KPM算法在預測精度上有了更大的提高，且預