基于“小世界”網絡原理約簡在線社交網絡的算法研究

徐常福　萬一紅　鐘葉　胡文蓓　林容如

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

關鍵詞：社交網絡；“小世界”；約簡社交網絡；信任評估

0引言

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

1算法模型

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

1.1約簡原始社交網絡

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

1.2計算信任網絡中用戶個體問的信任值

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

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

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

2實驗評估

2.1實驗設計

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

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

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

3結論

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