Exploring Social Networks: Path Length and Degrees of Separation

[John Creighto]

Since I first leaned of the concept of social networks it has fascinated me but I never really studied the topic. It seems to me a huge topic but is not widely studied compared to other areas of mathematics. What better way to study such things as the spread of information, political views, deseases, etc.

In this thread I guess I would like to see a light discussion of a number of ideas within this field and perhaps some suggestion of interesting sources of information.

Looking at the terms defined in wikipedia:
http://en.wikipedia.org/wiki/Social_network#Metrics_.28Measures.29_in_social_network_analysis

I notice only one measure of distance was measured:

Path Length
The distances between pairs of nodes in the network. Average path-length is the average of these distances between all pairs of nodes.

Well, this may in some respects be interested given that it is believed that their are only six degrees of separation between most people in the world the number would seem inadequate for modeling the spread of information, disease, ideas, etc. because well, it may only take six steps to connect two people if the path is chosen at random the probability of concecting these two people within six steps could be very small.

6 degrees of separation implies that there are at least (5x10^9)^(1/6)=41 links between each person. Given most people have over 300 friends on there facebook this doesn't sound entirely unreasonable but the number of links between people depends on the type of link. For instance if we were measuring the spread of an std the average number of sexual partners for a man in a lifetime is 7 which is less then 41.

Also my above calculation assumes a very loosely connected network and in this loosely connected network if we take a path of length six there are still (5x10^6)-1 possible other paths that do not connect these two people. Consequently well the shortest path may be close the probability of selecting this path at random is very small.

 

[John Creighto]

Random Networks

There appears to be two main random models for the structure in Social Networks. They are scale free networks and normally distributed networks.

However, if we look at communities of interests in a specific topic, discarding the major hubs of the Web, the distribution of links is no longer a power law but resembles more a normal distribution, as observed by Pennock et al. (2002) in the communities of the home pages of universities, public companies, newspapers and scientists. Based on these observations, they propose a generative model that mixes preferential attachment with a baseline probability of gaining a link.

http://en.wikipedia.org/wiki/Scale-free_network

I think they both are are what I'd intuitively expect as a normally distributed network would could arise by assigning each node a random probability of getting a new link, well the scale free network is based on an attractor principle where everyone wants to know someone famous or popular or on smaller scales friends of friends, the more friends you have the more friends you will meat through their friends.

A scale free network can be generated randomly though the
Barabási–Albert model

Well a normally distributed network can be generated by adding the links randomly and choosing some probability to add each new link.

 

[Ben1220]

start with graph theory. Learn the basics of graph theory and algorithms on graphs. Perhaps take a graph theory subject, or a discrete maths/combinatorics subject that has lots of graph theory in it.

Then move on to networks, they are special types of graphs as far as I know... Stuff you learn in that area of graph theory can be applied to any situation with a network, including social networks.