Identity and Search in Social Networks. Watts, Dodds, Newman. Science 2002.


  1. Begins with reference to Travers and Milgrim’s 6-degrees letter experiement
  2. Some chains were only 2 or 3 links long – people are able to anticipate who would be likely to be closely connected to someone without knowing their full social network or everything about them
  3. They call the ability to quickly find a target “searchability.”  This property exists in some types of networks, (for example, where there are a few very highly connected hubs, or exists in a lattice that closely corresponds to the search space of interest, but social networks aren’t like that <Not sure, I think they are very much like that.>
  4. They consider that social networks are hierarchical, with acquaintances fitting in at different places
  5. <People may have other features aside from location in acquaintance tree it seems like, and would make sense>
  6. Probability of people knowing each other is the distance between the groups they belong to (based on a measure of homophily)
  7. Ah i see, each feature describing people has its own associated hierarchy just for that feature
  8. The distance between people is based on the closest distance among all distances – means that this metric violates the triangle inequality
  9.  Individuals can work off two pieces of information in their model:
    1. Social distance, which can be measured globally, but is inexact
    2. Network structure, which is exact, but can only be measured locally
  10. They implement the greedy algorithm Milgram proposed, simply forwarding the message to the friend with the smallest social distance from the target
  11. They consider a network searchable, if given a probability of failure at each step (which occurred in the actual experiment as 1/4 people did not forward the message), that a message starting at any point can reach its target with at least some fixed probability
  12. They argue that social networks plausibly fit into networks that would need to be parameterized in a certain manner to be searchable as they define it: “Hence our model suggests that seachability is a generic property of real-world social networks.”
    1. For example, socail networks are homopholous (and they don’t have to be highly homopholous to have the desired characteristics)
    2. Increasing number of dimensions/features dramatically reduces chain length, which also makes sense <although i wonder if they have features completely independent – I bet that with homophily, the features among different people cluster>. Although on the other hand, if there is too many features, everyone will be very close by some metric, as the number of features grows very large, the chain devolves into a random walk
  13. They compute the measure for homophily that is consistent with the results Milgram got, and those parameters have the values that would make the graph easily searchable
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: