Chapter 13

13 Agent-based Modeling

1. ERRG
2. BAPA

Erdos-Renyi Random Graphs

1. Random Degree Distributions

2. A network with little structure, one in which is highly entropic and
nodes are connected seemingly at random is called the Erdos-Renyi Random Graph. Gilbert
produced a similar network a year earlier, but Renyi revisitng a previous Erdos work
produced this method of a network. While the original network was static, it was later
adapted by network scientists in the form of a growing network.

3. Constructing ERRG Topology

4. Erdos-Renyi random graphs are constructed as follows: begin with a small
network, for example a ring network of size N. At each time-step, add a link m to a node
at random. This means that each node in the network is equally likely to receive the
additional link. Over time this results in a network of high entropy, with little
discernible structure. There are examples of ERRGs, for example the connectivity of roads and highways
in the United States. This means that the overall connectivity follows normal
distribution and relevant bionomial statistics such as the average and median are valid. In
contrast, a more complex network could be something simpler, and more efficient, such
as teh connectivity of airlines and the distribution of their hubs. In this case
such simple mathematics might not be as appropriate.

5. ERRG Algorithm

6. When we apply the ERRG algorithm, we are ignoring the degrees of the
nodes and therefore selecting a node at random. This means that there is no internal
learning in the network, no algorithm with nontrivial results. The network is not
necessarily efficiently designed.

7. Normal Statistics, averages, etc.

8. This also means that when we take the average of a node that it actually
is the average of the network. This also means that if this was the type of network that
existed in social engagement, then current measurements of the engagement rates would still
be valid. It is in fact the reason that ERRGs don’t exist in the real world in the
complex way, that allows heterogeneity to take place, and therefore
nontrivial structural and robust topologies to exist in networks in the real-world.

APPENDIX B: ERDOS-RENYI RANDOM

GRAPHS

The foundation of modern network theory is usually attributed to the work
of Erdos and Renyi in the 1959 paper “On Random Graphs”. Though Gilbert proposed a similar model
for creating a graph with tunable density slightly earlier, the better method proposed by
Erdos-Renyi involves creating a graph of fixed nodes and initial links, and then selecting two
nodes at random from the graph and pairing them. The psuedocode could be generated like this:

Ɣ Generate n nodes on an unconnected graph.Ɣ Generate initial links m. Ɣ Do process until links m = total number of links.
ż Select two nodes at random and form a link between them with probability
p.

ż Conditions:

Ŷ If two nodes are already connected, choose different nodes.Ŷ If the two nodes are actually the same node, choose different nodes.
For example, let’s assume that the probability is 0.5 or 50%. We can
simulate this numerically with a coin flip. Thus our algorithm is:

Ɣ Select two nodes at random.Ɣ Flip a coin, if it is heads choose one, if it is tails choose the other.
In this algorithm, we will create an empty graph, generate initial links
and form a link between at a probability. For those interested in programming, be sure to add a
conditional for the possibility of a duplicate. So we do our coin flips n times and obtain our list of total degrees. We do
this by counting up

how many edges each node has and obtain a table like this:

This looks very familiar to us. It is a Poisson distribution. The peak of
the curve is its average. Thus, in random graphs, the average node has the average number of
connection, and therefore the average is dependent upon the initially probability, p. Let’s take a slightly modified version of the canonical Erdos-Renyi Random
Graph (ERRG). In this case we will use the following algorithm:

Ɣ Begin with a network of N nodes,Ɣ At each time-step add a new node and connect it at random to one of the
nodes This is because the original ERRG model is actually not a growing network,
but rather is an empty network with nodes connected to each other with probability. Instead
of taking nodes and adding links, we just add a new node and link at each time-step. In our
modified case, the network is growing, so we can analyze the dynamics of it. We get the same
result and we not longer need to worry about our conditions., so for our purposes its
basically the same thing At each time-step our probability is , and thus growing with the size of
the network. Let’s consider our initial graph, and see where the new node, F, will join:

We have said that each node will have an equal probability of being
selected, and that this probability is equal to . Thus each node has a chance of being 39 selected.
An incoming node would choose indiscriminately between the five nodes. So, an incoming node
makes a connection decision with these odds:

Let’s say that node connects to node . What happens in the next step? Well
now N=6, so each probability is thus. If we were to add a new node, the would follow these
probabilities:

More ERRG

What is considered classical network theory is centered around the
Erdos-Renyi Random Graph (ERRG) model. For our purposes, we will say that a slightly modified ERRG
model adds a new agent to the network with equal probability to all agents. Thus, in a
2-agent networks, nodes A and B can be chosen with equal probability, or its 50% likely that either
will be selected. We can simply model this by flipping a coin: if it’s heads we add a link to a.A,
if it’s tails, we add it to a.B. coin flip outcome: tails Okay, so we flipped a coin and it’s tails, so let’s add it to a.B and
create our second edge, e.2. Now our network looks like this:

So we’ve added a.C, and now we want to add another node. The question is,
now which one do we pick? This outcome of this decision is ultimately the divergence between
classical and complex network theory. In classical network theory, we would seem to
follow the same process, except this time we have three nodeas and therefore have a 1/3rd
or 33% probability of selecting each node:

If do this process over and over again, we obtain an Erdos-Renyi Random
Graph, where the average node has the average number of links. No node has too many links,
none too few. The degree distribution of a random graph looks like this:

What does this say? Well the x-axis is the number of degrees. The y-axis is
the frequency of this degree occurring. So to interpret this, we would say that 50% of the
nodes have 1 link, about 25% have two links, 12.5% have three links. And his decays
exponentially relatively quickly. Then at the right side of the x-axis we have the more connected
links, which have really low probabilities. For example only 1 node has 17 links, the maximum. This
node occurs 0.002% of the time. In fact, less than 1% of the nodes have more than 7
links. So even after adding 20,000 nodes– twenty thousand nodes–at random, the highest only
had 17 connections. This is not a graph that screams efficient nontrivial topological
self-organization to anyone. We have in effect created a randomly generated network, one without any
discernable

macrostructure based on a probability p. But random networks have a
significant downfall: they poorly represent ‘real-world’ networks. Because network generation is a
cumulative process, we things don’t just happen randomly. In fact, in this
highly entropic scenario, non-trivial self-organization does not occur. Nothing forms in random networks. This is
precisely because the network growth is dependent upon a distribution of
randomness. We have also seen that small rules at the micro-level can result in
macro-level patterns. We have seen that rewiring or generating a network can result in a greater
emergent network property. So far we have discussed structured and random networks, but the
remainder of this Project will be concerned with those of non-trivial structure. It turns out this method of modeling random networks, one which had been
generally for about 50 years prior could not describe the networks that were being discovered
in the late 90s. The degree distributions of real-world scale-free networks just didn’t look
like that. And further, this mechanism of straight-up random attachment didn’t work; it didn’t fit any
data, not static, not dynamic. This problem became more obvious when the ability to obtain and
analyze humongous data sets began to proliferate and the alleged ubiquity of
scale-free networks came into light. To really explain how networks form in
the real world, we need a less random Mechanism.

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
different. 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. Preferentiality,If the distribution follows a power law, then we know the generative
mechanism does not result in random attraction. There exists a natural bias toward more connected
nodes, which is preserved with scale-invariance.

We can make a generalization which says that the total number of profile
likes will be related to the future number of profile likes with a probability. That is the current
linear market share of the profile likes is equal to the probability that same percentage of nodes
will connect to that node. However it’s not necessarily true that the value of the profile likes is
static, in the sense that the preferentiality may change over time. It is important to compare the
current rates with one another to understand how the profiles are varying dynamically. Just
because a profile had a signficant number of likes due to their particular place in society, does
not mean they should be benchmarked at this same rate. Socially adept analysts understand that heuristic analysis involves a
variety of perspectives with proper knowledge of each strenghts and limtations.

Show how BAPA measures preferentiality This means that the probability of the market share is related to the
preferentiality or propinquity of additional nodes. This means that we can get an estimate of how the
profile has been behaving recently. This means that the difference Show logarithmic interpretation.