Social Network Analysis
15B1NCI732
( Network Models – Random Graph
)
1
Erdos-Renyi Random Graphs
There are two definitions of a random network:
• G(N, L) Model: Undirected graph consisting of N nodes, connected with L randomly placed links
• G(N, p) Model: Undirected graph consisting of N nodes, where each node pair is connected with
probability p.
Hence, the G(N, p) model fixes the probability p that two nodes are connected and
the G(N, L)) model fixes the total number of links L.
To construct a random network we follow these steps:
1. Start with N isolated nodes.
2. Select a node pair and generate a random number between 0 and 1. If the number exceeds p,
connect the selected node pair with a link, otherwise leave them disconnected.
3. Repeat step (2) for each of the N(N-1)/2 node pairs.
The network obtained after this procedure is called a random graph or a random network. Two
mathematicians, Pál Erdős and Alfréd Rényi, have played an important role in understanding the
properties of these networks.
Random Graph Model G(n,p)
We get a different
graph each time,
so G(n,p) is a
family of graphs
Graphs for
n=5
p = 0.2
No. of edges
possible without
self loops
So, what then is the probability that G(n,p) generates these graphs?
There are multiple ways to generate a graph with m edges.
Probability there exist exactly L links in the
network
Degree Distribution of G(N,p)
The degree distribution of a graph in the G(N,p) ensembles is a Binomial
distribution, for small networks.
For sparse networks (for which <k> << N), it resembles Poisonn distribution.
In a random network the probability that node i has exactly k links is the product of three
terms:
• The probability that k of its links are present, or pk.
• The probability that the remaining (N-1-k) links are missing, or (1-p)N-1-k
• The number of ways we can select k links from N- 1 potential links a node can have
Let P(k) denote the fraction
of nodes having degree k
Some Statistical Properties of Random Networks
• Average number of links <L> = p[N(N-1)/2]
• Average Degree = p (N-1)
• Average Path length = ln(N)/ln<k>
• Expected local clustering coefficient for a node = p
• Global clustering coefficient = p
Evolution of Random Graphs
Point of
Phase
Transition
when
diameter
value starts
to shrink
p = random graph generation probability, c = average degree, ds = diameter,
slc = size of largest component, l = average path length
*In the above figure, as p gets larger, the graph gets denser.
When p is very small, the following is found:
1. No giant component is observed in the graph.
2. Small isolated connected components are formed.
3. The diameter is small because all nodes are in isolated components, in which they are
connected to a handful of other nodes.
As p gets larger, the following occurs:
4. A giant component starts to appear.
5. Isolated components become connected and the diameter values increase.
As p continues to get larger, the diameter starts shrinking as nodes get connected to each other via
different paths (that are likely to be shorter). The point where diameter value starts to shrink in a
random graph is called phase transition. At the point of phase transition:
6. The giant component which just started to appear, starts to grow.
7. The diameter (which just reached its max. value), starts decreasing.
Fact: Phase transition in random graphs occurs when c = 1 [ i.e. when p = 1/(n-1) ]
Evolution: Topological Transitions
Supercritical regime Fully connected regime
Subcritical regime Critical regime
<k> > 1 <k> >= ln N
<k> < 1 <k> = 1
p > 1/N p >= (ln N)/N
p < 1/N p = 1/N
Single giant component
No giant component No giant component Single giant component
Size of largest component = N
Size of largest component = ln Size of largest component = Giant component has loops
Small clusters are trees Giant component has loops
N N2/3
No isolated nodes or clusters
Clusters are trees Clusters may contain loops
Practice Question
Consider random network model as G(N,p) where N= 12, edge creation
probability is p=0.2. Find the following:
• Probability that there exist exactly 60 links in the network
• Average number of links in the network
• Average node degree
• Standard deviation of node degree
• Average path length
• Average clustering coefficient of any node in network
• Expected local clustering coefficient for a node that has exactly 5 neighbors
Solution:
Solution (contd.):
References
• Zafarani, Reza, Mohammad Ali Abbasi, and Huan Liu. Social media
mining: an introduction. Cambridge University Press, 2014.
• Barabási, A. L. (2016). Network science. Cambridge university press.
• Dr. Natarajan Meghanathan, Theoretical Network Models, Department
of Computer Science, Jackson State University, Jackson, MS
([Link]
• [Link]
• [Link]