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 numericallys 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, andtherefore 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.