Exploiting Search Techniques to Discover Six Degrees of Separation between People from Web
Date Issued
2009
Date
2009
Author(s)
Tseng, Chien-Lin
Abstract
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).
Subjects
social network
six degrees of separation
web search
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96922063-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):7c4df2be229d6f6d4e78137b184bf049