Identity and Search in Social Networks

Citation

@article{watts02,

 author = {Watts, D.J. and Dodds, P.S. and Newman, M.E.J.},
 journal = {Science},
 keywords = {2002 RMP_CFL dodds networks newman social watts},
 pages = 1302,
 title = {Identity and Search in Social Networks},
 volume = 296,
 year = 2002

}

Abstract from the paper

Social networks have the surprising property of being “searchable”: Ordinary people are capable of directing messages through their network of acquaintances to reach a specific but distant target person in only a few steps. We present a model that offers an explanation of social network searchability in terms of recognizable personal identities: sets of characteristics measured along a number of social dimensions. Our model defines a class of searchable networks and a method for searching them that may be applicable to many network search problems, including the location of data files in peer-to-peer networks, pages on the World Wide Web, and information in distributed databases.

Online version

• Science page
• Alternative link

Summary

In this paper, Watts et al proposed a model to explain the phenomenon mentioned an earlier paper by Travers et al, where the authors described a very interesting sociological observation: The average length of the acquaintance chains for the letters that eventually reached the target was about six. The two major sociological characteristics that Watts et al mentioned and further investigate in the paper are //homophily// (the tendency of like to associate with like, parameterized by a) and //social dimensionality// (the number of hierarchies one may belong to, parameterized by H), then the probabilistic model was built based on six assumptions on how the social network is formed. A simulation experiment was conducted to investigate the impacts of parameters a and H and try to understand the underlying mechanism of the phenomenon.

Objective

The principal objective is to determine the conditions under which the average length of a message chain connecting a randomly selected sender s to a random target t is small.

Background

In the late 1960s, Travers and Milgram conducted an experiment in which randomly selected individuals in Boston, Massachusetts, and Omaha, Nebraska, were asked to direct letters to a target person in Boston, each forwarding his or her letter to a single acquaintance whom they judged to be closer than themselves to the target. Subsequent recipients did the same. The average length of the acquaintance chains for the letters that eventually reached the target was about six.

Modeling

• Prior works to explain the searchability in social network

1. a network that possesses a certain fraction of hubs [highly connected nodes which, once reached, can distribute messages to all parts of the network]
2. a network that is built upon an underlying geometric lattice that acts as a proxy for "social space"

• Proposed model following six contentions about social network

1. Individuals in social networks are endowed not only with network ties, but identities
2. Individuals break down, or partition, the world hierarchically into a series of layers, where the top layer accounts for the entire world and each successively deeper layer represents a cognitive division into a greater number of increasingly specific groups.
3. Group membership, in addition to defining individual identity, is a primary basis for social interaction (10, 11) and therefore acquaintanceship.
4. Individuals hierarchically partition the social world in more than one way (for example, by geography and by occupation).
5. On the basis of their perceived similarity with other nodes, individuals construct a measure of "social distance", which is defined as the minimum ultrametric distance over all dimensions between two nodes.
6. Individuals forward a message to a single neighbor given only local information about the network.

• The stochastic process is then defined to capture the contentions by introducing parameters, probabilities, distances, and other related modeling elements.

1. Similarity x_ij between individuals i and j as the height of their lowest common ancestor level in the resulting hierarchy, setting x_ij = 1 if i and j belong to the same group. The hierarchy is fully characterized by depth l and constant branching ratio b.
2. Choosing an individual i at random and a link distance x with probability p(x) = cexp[-ax], where a is a tunable parameter and c is a normalizing constant.
3. A node's identity is then defined as an H-dimensional coordinate vector, and Each node i is randomly assigned a coordinate in each of H dimensions.
4. "Social distance" yij is defined as the minimum ultrametric distance over all dimensions between two nodes i and j.

Results

1. Almost all searchable networks display a > 0 and H > 1, consistent with the notion that individuals are essentially homophilous (that is, they associate preferentially with like individuals) but judge similarity along more than one social dimension.
2. Although increasing the number of independent dimensions from H = 1 yields a dramatic reduction in delivery time for values of a > 0, this improvement is gradually lost as H is increased further.
3. By introducing parameter choices that are consistent with Milgram's experiment (N = 10^8, p = 0.25), as well as with subsequent empirical findings (z = 300, H = 2), it is able to compare the distribution of chain lengths in the proposed model with that of Travers and Milgram for plausible values of a and b.

Further thoughts & Study Plan

Papers you may want to read to understand this paper.

• J. Travers, S. Milgram, Sociometry 32, 425 (1969).

1. To fully understand the background the problem and resolve some concern about the experiment, e.g., what about the rest 80% letters that didn't reach the destination. If we waited for several more days, would the number of arrived letters go up? Doesn't it mean the actual average number of hops should be greater than 6?

• Try to investigate the paper that cite this paper to see if any real world experiments have been conducted or real world applications have been invented based on the model.

1. The experiment is easy to reimplement and reproduce, so to better understand the mechanism, it is a good idea to write a piece of matlab code to observe if we could obtain a similar result.
2. A major concern about the problem is there is no real world experiment conducted on either traditional social network or virtual social network, except a simulation experiment.