Small World Phenomenon
Date Issued
2008
Date
2008
Author(s)
Ho, Jing-Mao
Abstract
The small world phenomenon, the principle that most of people are linked by short chains of acquaintances, is first studied as a problem in social science. It is also feature of a range of networks arising in nature and technology. Early experiments showed that it has two properties: first, short chains are widespread, and second,ndividuals with local information are able to find the chains. Kleinberg proposed a family of network models and a greedy algorithm, showing that there is a unique model within the family for which the greedy algorithm’s running time is O(log2 N). We study Kleinberg’s theorems and give some models based on Kleinberg’s family:torus, grids of high dimension, and cube.
Subjects
small world phenomenon
six degrees of separation
algorithm
time complexity
network model
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R91922052-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):e087e5863a8efb404d13ca97497a53aa