MODELS
POWER GRAPH Model A
This is a very simple model involving only one parameter, called
β,
which is the probability of adding edges.
At each step, toss a biased coin having "head" with probability β.
- If the coin toss yields "tail", the model
generates a new vertex with a self loop.
- Otherwise the model randomly selects two vertices u and v
and adds a new
edge uv. The probability that u
is chosen is proportion to the indegree of u at the current time.
The probability that v
is chosen is proportion to the outdegree of v at the current time.
A special case of this model has the indegree and outdegree being
the same.
Both indegree and outdegree distributions follow the
Power Law with power beta =
1+1/β.
POWER GRAPH Model B
This is a modified version of Model A.
Two biased coins are used to generate different powers for
indegree and outdegree distributions.
At each step, toss two biased coins having "head"s with probability
of β1 and β2, respectively.
- If both tosses yield "head"s,
a new vertex is generated with two self loops.
- If both tosses yield "tail"s, a new edge uv is added
as in MODEL A. The probability that u
is chosen is proportional to the indegree of u,
and the probability that v
is chosen is proportion to the outdegree of v.
- Suppose the first toss yields a "head" and the second one yields a "tail".
The model generates a new vertex u with a self loop.
Choose v from current vertex set with probability proportional to
its indegree and add edge uv.
- Suppose the first coin yields a "tail" and the second one yields a "head".
The model generates a new vertex v with a self loop.
Choose u from current vertex set with probability proportional to
its outdegree and add edge uv.
In this model, the indegree distribution follows the
Power Law with power
1+1/β1. The outdegree distribution follows the
Power Law with power
1+1/β2.
POWER GRAPH Model C
In this model we take a different approach. We do not attempt to
answer how a graph comes to have a power law degree sequence. Rather,
we take that as a given. In this model, all graphs with a given power
law degree sequence are equi-probable. The goal is to derive
structural properties which hold with probability asymptotically
approaching 1. Such an approach, while potentially less accurate than
the detailed modeling approach above, has the advantage of being
robust: the structural properties derived in this model will be true
for the vast majority of graphs with the given degree sequence. Thus,
we believe that this model will be an important complement to random
graph generation models. Here is how to generate
a random graph with
a given degree sequence.
- Form a set L containing deg (v) distinct copies of each
vertex v.
- Choose a random matching of the elements of L.
- For two vertices u and v, the number of edges joining
u and v is equal to the number of edges in the matching of L
joining copies of u to copies of v.
Models A and B are designed by our project team .
Maintained by Lincoln
Last modified date: 2000-04-23