4:05 pm May 12th, 2008 by wkallander

This paper[1] presents a model to explain the navigable nature of social networks.

The authors argue that social dynamics can be modeled by only six characteristics:

1. Individuals (nodes) in the social network have identities, which are defined as sets of characteristics they attribute to themselves. Taken together, these characteristics uniquely identify them.
2. Individuals (nodes) in the social network cluster the set of all individuals into a hierarchy based on similarity between groups. Higher levels denote that child groups are more generally alike, whereas lower levels represent more specific similarity. They also note that this hierarchy is shallow, by bounding the height of the hierarchy by terminating its formation when the size of the groups has shrunk to a “cognitively manageable” size, or something that is reasonable to humans.
3. Intra-group interaction is the defining factor for links between individuals. Since these groups are formed based on homophily, and since the likelihood of two individuals having a link between them decreases with decreasing similarity, the likelihood two individuals in different groups decreases as similarity between their respective groups decreases.
4. There are multiple hierarchies of possible groups that may be formed, one per characteristic (dimension). Since similarity between individuals is generalized to these trees, the number of dimensions necessary to ensure searchability is what is being analyzed in this paper.
5. Social distance between two individuals is therefore the minimum lowest common ancestor of the two nodes in any of their dimensions (e.g. across all of the group hierarchies). The authors are careful to note that this is not a true metric, since it violates the triangle inequality. That is to say that the distance is not transitive.
6. The only network path information visible to individuals is their immediate neighbors. So, local network paths are known, but the global optimal paths are hidden.

The authors contend that a simple algorithm that combines social distance between to nodes, along with local neighbor path information is sufficient for the network to be navigable. Since this information appears to be readily available to social networks, the authors surmise that all social networks are inherently searchable as a result.

One other interesting finding of this study is the discovery that, as the number of dimensions increases, the ability to find a messaging route actually decreases. So, knowing fewer characteristics and basing similarity judgments on this restricted set of characteristics yields better results.

[1] Watts, Duncan J.; Dodds, Peter Sheridan; Newman, M. E. J., 2002. “Identity and Search in Social Networks“. Science, Volume 296, Issue 5571, pp. 1302-1305.

This entry was posted on Monday, May 12th, 2008 at 4:05 pm and is filed under ECS289M, Graphs. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.