利用網路搜尋技術尋找網頁上兩人之間六度分離的關係連結

Abstract

六度分離理論是一種小世界現象：世界上任何兩個不認識的人最多透過六層認識的關係即可以將兩人串連起來。在此篇論文中，我們提出一種非監督式的六度離搜尋系統：「攀關係」，此系統將全球資訊網視為大型的社群網路資料庫，藉由搜尋引擎找出任何兩人之間以認識為基礎的關係鏈。相較於其他具有類似功能的系統，「攀關係」具有以下四種優點，一、有較高的機會可以成功找出兩人之間的關係鏈。二、關係鏈的長度不會太長。三、不需要任何事先建立好的社群網路。四、所尋找出來的關係鏈較能反映出真實世界當下的人際關係。「攀關係」主要是由「擴展」以及「猜測」兩個元件所組成，並使用雙向搜尋配合A*的搜尋策略來執行整個關係鏈搜尋的過程。我們更定義了一種名為「標準化關係距離」的關係強度評估標準，應用此評估標準在「擴展」和「猜測」兩個主要元件上，能找出具有強烈關係的人並加速搜尋的速度。最後實驗的結果顯示，「攀關係」的合理度3.066遠超過基準線1.630以及「人立方-六度」2.204。

The small-world phenomenon —“Six Degrees of Separation”— argues that everyone in the world can be connected to any other person through a chain of acquaintances that has no more than five intermediaries. In this thesis we propose an unsupervised system, the “Search-based Six-Degree Finder”, which utilizes World-Wide-Web as a partially seen large social knowledge database, and navigates on it using a search engine to discover the acquaintance-based chain between two given people. Comparing with some other systems or experiments of the similar goal, ours has four advantages: First, it allows us to find the path between people with higher successful rate. Second, it tries to find shorter paths between people. Third, it does not require any existing social network. The final advantage is that the relationships in the path have better chance to reflect the real-world relationships. Our SDF system consists of two main components, “Expand” and “Guess”, to perform the bidirectional search with A* search strategy. We further define a novel relationship strength measure, called “Normalized Relationship Distance” (NRD) to serve as the main function for Expand and Guess components. The experiments and human study reveal that discovered chains are believed to be reasonable with average grade 3.066 (from 0 to 5), which outperforms not only the baseline (1.63) but also the state-of-the-art six-degree finder “Renlifang” (2.204).