Social Network Theory

Social Network Theory

In the last few decades, interest in Social Networks has seen explosive growth with Facebook being the poster child. Indeed work had gone on before that time in Physics especially in the area of “random networks” (Erdos and Renyi are famous names). In such networks, each new node is randomly connected to any previous node and its evolution studied.

The work of Barabasi and others showed that while the physics of Random Networks was interesting, it had little to do with “human made” networks such as Web, Internet, friendship networks, etc. They all fall into the category of “Scale-Free Networks”.

Scale-Free Network (SFN) Model:

“Scale-free” refers to the nature of some networks where its diameter (average # of links to reach a node from the present node; remember “six degrees of separation” between people) is mostly unchanged as the network grows in size.

SFN’s degree (# of links per node) is distributed as a power law (and not a binomial distribution which is the case for a purely random network). A well-known example of power law is Pareto distribution (“80/20 rule”). SFNs arise in networks that grow and have preferential attachment property while growing (exhibits “rich get richer” and “first mover advantage” phenomena).

Figure 1: Pareto distribution (example of a Power Law distribution)

If a “fitness” rating is attached to each node, a new phenomenon of “winner takes all” emerges (Google search engine will rate very high among websites as an example). This has been shown to be a “Bose-Einstein” condensate state (somewhat similar to condensation transitions that occur in traffic jams where long queues of cars are found, in wealth distribution models where a few people might have a hugefraction of all the wealth and in operating systems usage where Windows has close to 90% market share).

For more on Social Network Theory, see Scale-Free Networks: A Decade and Beyond by Barabasi for a pain-free summary. (Science, Vol 325, 24 July 2009; pp 412-413).

Real Social Networks:

Real social network has 3 major features:

1. Clusters (of friends who “hang out”).

2. Weak links (to your long forgotten high school classmates).

3.Hubs (politicians and others with massive number of contacts).

Figure 2: Natural social network structure with Cluster Groups

Comparing the Pareto (power law) distribution that governs SFNs, we can see that Hubs with many links (large “k”) are nodes that occur rarely whereas Clusters with few links are nodes that occur very often. Here we elaborate a mid-scale situation where certain nodes have a fair number of links and occur with some frequency – we call them “Cluster Groups”. They arise in cases where a certain Member belongs to multiple Clusters, their family cluster, work cluster, golf club cluster, etc. The same Member belongs to many Clusters that are tightly coupled leading to a Custer Group.

Failure Modes:

Failure modes of SFNs have been widely studied. The main 2 observations are that (1) SFN is robust to Failure and (2) SFN is vulnerable to attacks.

Failure means random loss of network elements such as some computers or local routers going down in the Internet. Attack refers to concerted take-down of major “hub” routers. It has been shown that removal of a small percent (15 to 20%) of “hub” routers will pull apart the network and “cascading failure” will spread (due to routers NOT under attack being unable to carry the extra load from “hub” routers) leading to total network failure.

Here are N=10 and N=100 examples; d=2 in both cases.

The N=100 example already shows some interesting features. Remember “Hubs”? One would expect the “root” node at the very top to be a Hub but the left-most node in the 2^nd level seems to be developing into a Hub with lots more “child” nodes.

Have fun with social networks!

PG