BAPA Appendix
So let's do essentially the same thing, except this time with one caveat. Instead of choosing a
node at random, let's make the decision based on some property of the node. We need a way
to sort of rank the nodes, to make them not equal. Let's consider analyzing them by about the
only property we know about them other than that they exist, their degree.
When we had five nodes, we said that the probability of connecting to node F was this:
Which means that each node essentially had the odds of being chosen once every five times in
the same way one side of a coin has the odds of being chosen once every two times:
So let's instead of measuring this probability as 1/N, let's measure it in a different way:
- Ɣ For each node, count up the number of degrees
- Ɣ Divide this number by the total number of degrees in the network
So let's instead of measuring this probability as 1/N, just picking out any node at random, we're
weighting it in the sense that we reward those with more degrees. So if we re-think of the odds,
it's not anymore, because the table is no longer equal:
We see that there are 8 total degrees (because we are only dealing with an undirected graph so
both nodes count one degree to their total, not 1/2 of one), and further we see that node has the
most with 3, next with 2, and the rest with 1. Therefore, the probability of being chosen as the
node is actually 3/8, is 3/8th, and , and are each 1/8th. So what's the network emergence
implication of this? Let's look at the graph again, except this time lets scale it visually to the
degree of each node:
The size is related to the probability that it will be selected. Thus we immediately see, that B is
the most likely to be chosen. In fact, has equal probability as , and of being chosen combined.
This is literally the start of the hub-like evolutionary topology seen in scale-free networks. Now
instead of , this time let's say the random number generator selected . The topology is now:
We see that already 's positive feedback scheme is already turning the node into a hub. At each
step, this node is more likely to get more and more incoming links. We can formalize the
Barabasi-Albert Preferential Attachment (BAPA) algorithm as:
- Ɣ Start with a graph of n nodes
- Ɣ At each time-step add m new nodes with probability P(k) = k_i / sum(k_j)
We see that this mechanism does not simply connect at random, and this biased decision
making is integral to the development of scale-free networks nontrivial hublike topology.
What happens when we run our BAPA mechanism over and over again? What happens to the
degree distribution?
In a way, it almost like it decays like an exponential except for one huge difference. Look at how
apparent the hub topology is. The highest node on the ERRG had 17 links. The highest here
has over 400. The next highest, over 100. Further, there's a bunch of nodes of varying degree in
between. They're all very infrequent, but they're are there and integral to the integrity of the
system.
Let's put them on the same graph, and discuss the real difference between these two graphs.
So it's clear that while the BAPA initially decays at a similar rate with ERRG, ultimately the
exponential decays much faster. The extension of this hub-toplogy, the right part of the graph
where there is red but no blue, this the literally what the 'long tail' is
Let's discuss scale-free network's claim to fame. If we instead, plot our data logarithmically, that
is on a log-log plot, we see the real nontrivial result of scale-free networks:
So we see ERRG decays faster, and there are lots of mid-range nodes with BAPA, but let's look
only over the linear range, which we can do because the hubs -- although they are there -- are
each an individual case, so their actual position along the x-axis is not as mandatory to know:
If we project our estimator out with a power-law fit, we see we get a straight line. And more
importantly, we find this line in the network data obtained in the real-world: in social systems, in
technological systems, in biological systems. They all have this line with an exponent and the
exponent, is always such that . Barabasi-Albert Preferential Attachment therefore makes scale-
free networks really well.
