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 2nd level seems to be developing into a Hub with
lots more “child” nodes.
Have fun with social networks!
PG
No comments:
Post a Comment