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

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

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

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

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

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