JOUR 601 Lecture Notes - Lecture 43: Preferential Attachment, Graph Theory, Network Theory
This preview shows half of the first page. to view the full 3 pages of the document.
Traditionally, research in graph theory focuses its attention very much on studying graphs that
are static even though all real-world networks are dynamic in nature.
How they have evolved over time is a defining feature to their typology and overall makeup
Much of network theory is still focused on trying to explore the basics of static graphs as the
study of their dynamics results in the addition of a whole new setoff parameters in our models
that takes us on a whole new level of complexity
Growing a network means adding more nodes to it and adding more links to it that increase the
In our random model, links were placed between nodes at random with some given probability
Growing the network here just meant growing the probability to have more links develop over
An interesting thing we find when we do this is that there are thresholds and phase transitions
during the network’s development
Thresholds mean by gradually increasing our link probability parameter some properties to the
network suddenly appear when we pass our critical value
Our first threshold is when our degree goes above 1 over the total number of nodes in the
At this threshold, we start to get our first connection.
At degree 1, when every node has on average one connection, the network appears to be
connected. We see giant components emerging in the network. This means one dominant
In this, we start to have cycles. This means that there are feedback loops in the network and a
threshold occurs when nodes have an average degree of log n.
At this point, everything starts to be connected meaning there is a path to other nodes in a
network. This is what we see in a random network.
Most real-world networks are not random as they are subject to some resource constraints
and they have preferential attachment giving them clusters that we don’t see in random graphs
You're Reading a Preview
Unlock to view full version