The Small World Phenomeon小世界现象.pptVIP

The Small World Phenomenon: An Algorithmic Perspective An Experiment by Milgram (1967) Chose a target person Asked randomly chosen “starters” to forward a letter to the target Name, address, and some personal information were provided for the target person The participants could only forward a letter to a single person that he/she knew on a first name basis Goal: To advance the letter to the target as quickly as possible An Experiment by Milgram (1967) Outcome revealed two fundamental components of a social network: Very short paths between arbitrary pairs of nodes Individuals operating with purely local information are very adept at finding these paths What is the “small world” phenomenon? Principle that most people in a society are linked by short chains of acquaintances Sometimes referred to as the “six degrees of separation” theory Modeling a social network Create a graph: node for every person in the world an edge between two people (nodes) if they know each other on a first name basis If almost every pair of nodes have “short” paths between them, we say this is a small world Modeling a social network Watts – Strogatz (1998) Created a model for small-world networks Local contacts Long-range contacts Effectively incorporated closed triads and short paths into the same model Modeling a social network Imagine everyone lives on an n x n grid “lattice distance” – number of lattice steps between two points Constants p,q Modeling a social network p: range of local contacts Nodes are connected to all other nodes within distance p. Modeling a social network q: number of long-range contacts add directed edges from node u to q other nodes using independent random trials Modeling a social network Watts – Strogatz (1998) Found that injecting a small amount of randomness (i.e. even q = 1) into the world is enough to make it a small world. Modeling a social network Kleinberg (2000) Why should arbitrary pairs of strangers, using only locally available informa