徐常?！∪f一紅　鐘葉　胡文蓓　林容如

摘要：本文主要考慮到直接在大規(guī)模在線社交網(wǎng)絡(luò)下評估用戶個體問信任成本太高，因此，我們提出一種基于“小世界”網(wǎng)絡(luò)原理約簡在線社交網(wǎng)絡(luò)的算法。為驗證該方法的有效性，我們在Epinions數(shù)據(jù)集上進行了多方面的實驗測試。實驗結(jié)果表明，約簡后的信任網(wǎng)絡(luò)可以較好地評估原始在線社交網(wǎng)絡(luò)中用戶個體問的信任程度。

關(guān)鍵詞：社交網(wǎng)絡(luò)；“小世界”；約簡社交網(wǎng)絡(luò)；信任評估

0引言

隨著Internet的普及和盛行，每天都有數(shù)以萬計的新用戶加入到在線社交網(wǎng)絡(luò)中，來與其他用戶進行信息交流和交互，其中很多是互不相識的用戶。因此，評估這些用戶之間的信任程度，對提高社交網(wǎng)絡(luò)服務(wù)質(zhì)量和加強其安全性具有非常重要的作用。本文提出一種基于“小世界”網(wǎng)絡(luò)原理約簡在線社交網(wǎng)絡(luò)的算法（SWRSN）。該算法對原始社交網(wǎng)絡(luò)進行了約簡，采用了用戶活動域（domain）信息，該信息相對于其它信任信息來說是客觀的、穩(wěn)定的。因此，該算法具有較低的復雜度，并且對惡意攻擊也有一定的魯棒性。

1算法模型

本算法主要包括三個關(guān)鍵步驟：（1）原始社交網(wǎng)絡(luò)的約簡，即根據(jù)“小世界”網(wǎng)絡(luò)原理約簡原始社交網(wǎng)絡(luò)；（2）計算信任網(wǎng)絡(luò)中用戶個體問的信任值，即通過計算約簡的信任網(wǎng)絡(luò)中用戶個體問的信任值，從而間接評估原始社交網(wǎng)絡(luò)中用戶個體問信任程度。

1.1約簡原始社交網(wǎng)絡(luò)

約簡原始社交網(wǎng)絡(luò)的整個過程其主要是原始的信任網(wǎng)絡(luò)基礎(chǔ)上，根據(jù)“小世界”網(wǎng)絡(luò)原理，采用廣度優(yōu)先算法搜索盡可能多的源節(jié)點到目標節(jié)點之間的短路徑（最大步長Max Length=6），并且刪除路徑中任意一條邊的信任值小于給定信任閾值（一般設(shè)置信任閾值th=0.5）的路徑。

1.2計算信任網(wǎng)絡(luò)中用戶個體問的信任值

在本節(jié)中，主要是在約簡的信任網(wǎng)絡(luò)基礎(chǔ)上，計算源節(jié)點要目標節(jié)點的預(yù)測信任值。這里我們采用4種較為常見的信任評估策略，如表1.1所示。下面介紹信任傳播和信任整合操作。

信任傳播操作：從source節(jié)點到target節(jié)點路徑中用戶的信任傳播。兩種較為常見的傳播操作是取最小值（Min）傳播和取乘積傳播（Multi）。前者是指取路徑上最小的推薦信任值，后者是指取路徑上所有推薦信任值的乘積。

信任整合操作：從source節(jié)點到target節(jié)點中所有路徑的信任整合。兩種較為常見的信任整合操作為取最大值（Max）和取加權(quán)平均值（WAve）。前者是指取所有路徑中最大的信任傳播值，后者是指取所有路徑的信任傳播值的加權(quán)平均值。

2實驗評估

2.1實驗設(shè)計

本論文主要采用留一法進行實驗。采用數(shù)據(jù)集為Epinions，該數(shù)據(jù)集為社交網(wǎng)絡(luò)中較為典型的實驗測試數(shù)據(jù)集。如果Sollrce到target之間有一條直接的信任邊，則這條邊將被隱去。這時，source到target之間的信任值將通過它們之間信任圖來計算。

本實驗采用了較為常見的四個精度指標來評估本論文提出的算法的有效性，分別為：絕對誤差（Absolute error）、精度（Precision）、召回率（Re-call）和F分數(shù)（F-Score），計算公式如表2.1所示。其中表示實際中信任的用戶集，表示當前算法預(yù)測為信任的用戶集。

由表2.2可知，最小的Precision為0.7248，說明本論文提出的BDSWRSN算法具有較好的信任預(yù)測精度。此外，最小的F-Score為0.5875，剩下F-Score都在0.62以上，這也說明BDSWRSN算法的可以較為有效地幫助預(yù)測在線社交網(wǎng)絡(luò)中用戶個體問信任程度。

3結(jié)論

在本文中，我們采用了一種標準的留一法評估技術(shù)和社交網(wǎng)絡(luò)測試中常用的Epinions數(shù)據(jù)集，采用信任預(yù)測精度作為衡量指標，對本文提出的基于“小世界”網(wǎng)絡(luò)約簡在線社交網(wǎng)絡(luò)算法（SWRSN）進行了有效性地評估。實驗結(jié)果顯示，采用Multi-Wave信任評估策略，約簡后的信任網(wǎng)絡(luò)的F-Score為0.6504，這說明SWRSN算法可以較好地評估原始在線社交網(wǎng)絡(luò)中用戶個體間的信任程度。