So, let's see, what is a network model?
Informally a network model is a process randomized or deterministic for generating a graph.
We can think of models of static graphs or evolving graphs.
Models of static graphs get a set of
parameters pi and the size of the graph n as input and return a graph as an output.
Models of evolving graphs get a set of parameters pi, an
initial graph G0 and return graph Gt for each time t as output.
If the model is deterministic D defines a single graph for each value of n or t. In contrast, a
randomized model defines a probability space
where Gn is the set of all graphs of size n and p is a probability distribution
over the set Gn. We can do the same for each t also.
We call this a family of random graphs R or a random graph R.
In the 1950s Paul Erdos and Alford Renyi
introduced their now-classical notation of a random graph to model non-regular complex networks.
The basic idea of the Erdos-Renyi random graph model is this:
The Gn,p model getting the number of vertices in and a parameter p between 0 & 1, and for each pair i,j
generate the edge i,j independently with probability p.
In a related but not identical model one can select m links uniformly at random.
The degree distribution of an ER graph follows a binomial distribution.
But for a large ER network, it can be approximated by a Poisson distribution.
The tails of degree distribution an ER graph is typically narrow,
meaning that the node degrees tends to be tightly clustered around the mean degree.
There will be no region in the network that have large density of edges.
Do you know why?
This is a beautiful and elegant
theory studied exhaustively for the last 60 years and many deep theorems about the properties of ER graphs
have been established.
Random graphs had been used as idealized network models, but unfortunately they do not capture reality.
Let's look closer to some of the real-life network properties.
The degree distribution of many real-life networks follows a power-law.
These distributions usually are so skewed that it makes sense to plot the histogram in log-log form
where the characteristic distribution then becomes clear.
Very low degrees are possible and there are few nodes with large number of connections:
hierarchy.
So we need models that better capture the characteristics of real graphs in terms of
degree sequences, clustering coefficients, short path length.
Graphs that its degree distribution is
approximately a power law distribution, called a scale-free. In a scale-free network, each node is connected to at least one other.
Most are connected to only one while a few are connected to many.
The adjacency matrix of ER graph is a uniform distribution of ones, while in contrast, the
adjacency matrix of scale-free is ones lumped in column and rows for few nodes.
The SF (scale-free) model focuses on the distance reducing capacity of high degree nodes,
called hubs, to create shortcuts that carry network flow. The most notable
characteristic in a scale-free network is the hierarchy.
The smaller ones closely follow the major hubs. Other nodes with even a smaller degree in terms
follow these smaller hubs and so on. This hierarchy allows for a fault-tolerant behavior.
It seems a scale-free network has what we look for but how can we generate data with power law degree distributions?
This question was first considered by price in
1965 as a model for citation networks.
Each new paper is generated with m citations and new papers cite previous papers the probability proportional
to their in-degree.
Each paper is considered to have a default citation and the probability of
citing a paper with degree k is proportional to k+1.
The degree distribution of citation networks is a power law with exponent alpha
equals to 2 plus 1 over m. In a later paper in
1976, Price proposed the mechanism to explain the occurrence of a power loss in citation networks
which he called cumulative advantage. But today it is more commonly known as preferential attachment.
A decade later, Barabasi and Albert suggested a generative model, which is a special case of the Price model.
The BA model gets an initial sub graph, G0, and m,
the number of edges per new node, as input. The nodes arrive one at the time. each node connects to m other nodes,
selecting them with probability proportional to their degree.
Result is a power law distribution with exponent alpha almost equal to 3.
BA model produces scale-free networks, which is time-invariant.
It means it stays the same as more nodes added.
Removal of either assumptions destroys the scale-free
property. Without node addition in time, we ended with a fully connected network after enough time.
Without preferential attachment, we get exponential connectivity.
If we compare the average length of the shortest
distance between any two vertices in ER and BA model, we see for the same number of connections and nodes,
ER networks have larger diameter than a scale-free networks.
So far we've focused on obtaining graphs with power law distributions on the degrees.
What about other properties? The real-life networks tend to have high clustering coefficient and
also they are small-worlds. Can we combine these two properties?
Small-world graphs are based on Milgram's famous work in
1967. The substantive point is that networks are a structured such that even when most of the connections are local,
any pair of nodes can be connected by a small number of intermediate steps.
It works on two parameters: the clustering coefficients and the average distance separating nodes in the network denoted by L.
In a highly clustered ordered network, a single random connection will create a shortcut
that decreases L, the average distance between nodes in the network dramatically.
Watts demonstrates that small world properties can occur in graph with a surprisingly a small number of shortcuts.
According to him, large natural networks have very sparse connectivity.
No central node,
but large clustering coefficient larger than in ER graphs of the same size.
And also, they have short average path length.
To construct such a graph,
he suggests we'll start with a regular graph such as ring, and
for i equals to 1 to n where n is the number of notes select the vertex j with probability proportional
To Rij and generate an edge between i and j.
Repeat until z edges are added to each vertex.
Then we have a small word graph
The resulting graph has properties both of regular and random graphs.
It has large clustering coefficients and a small average shortest path length. There is high probability that a nodes
contacts or neighbors in such a graph are connected to each other.
Can we say every scale-free network is a small world?
How about the converse?
In this section we learned about three network models that generate different type of networks.
We learned about their properties and this table gives an overview on their topological differences.