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

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

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

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

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

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