基于“小世界”網(wǎng)絡(luò)原理約簡(jiǎn)在線社交網(wǎng)絡(luò)的算法研究

徐常?！∪f(wàn)一紅　鐘葉　胡文蓓　林容如

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

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

0引言

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

1算法模型

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

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

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

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

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

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

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

2實(shí)驗(yàn)評(píng)估

2.1實(shí)驗(yàn)設(shè)計(jì)

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

本實(shí)驗(yàn)采用了較為常見(jiàn)的四個(gè)精度指標(biāo)來(lái)評(píng)估本論文提出的算法的有效性，分別為：絕對(duì)誤差（Absolute error）、精度（Precision）、召回率（Re-call）和F分?jǐn)?shù)（F-Score），計(jì)算公式如表2.1所示。其中表示實(shí)際中信任的用戶集，表示當(dāng)前算法預(yù)測(cè)為信任的用戶集。

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

3結(jié)論

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