Transcript The New Science of Networks

The New Science of
Networks
Lindsay Meyer
*Based on the work of Professor AlbertLaszlo Barabasi (Notre Dame)
Linked
Much of my information
Comes from this book
Historical Perspective
Konigsberg Bridge Dilemma


Connecting 7 bridges
“Can one walk across the 7 bridges and
never cross the same path twice?”
Eulers Solution: Graph Theory






A collection of nodes, connected by links
Nodes = pieces of land, Links = bridges
Nodes with an odd number of links must be
the starting or end point of the journey
Continuous paths may only have 1 starting
and 1 end point
Such a path can NOT exist on a graph that
has more than two nodes with an odd
number of links
Konigsburg = 4 nodes, no path
Eulers Take-Home Message



“Graphs or networks have hidden
properties in their construction that
limit or enhance our ability to do
things with them”
A sudden change in layout can help
remove constraints
IE: Building a new bridge and
increasing the the number of links of
two nodes to four (an even number)
Social Networks: The Party…



The expensive,
unlabeled wine
scenario
100 guests
which cluster
into groups of 23 people
These people
mingle…
So you have “mingling”…



Suddenly, people begin moving on to other
social clusters, but there are invisible links
between those who initiated contact with
each other
Subtle paths connect people to each
other… the “secret” gets out as people
share this special knowledge with their new
friends
Erdos & Renyi: 30 mins and everyone in
the room is somehow connected. “If each
person gets to know one other guest, then
soon everyone will be drinking the reserve
port!”
Other examples of networks

Remember, a network is a
bunch of nodes connected by
links
Computers – Phone lines
 Molecules – Biochemical rxns
 Companies – Consumers (trade)
 Nerve cells – Axons
 Islands – Bridges

That MAGIC

MOMENT!!!
“The moment when your expensive
wine is in DANGER”
Mathematicians call it the emergence of
a giant component
 Physicists call it percolation and explain
it with phase change
 Sociologists would say that a
community formed
The big picture: when we randomly pick
and connect nodes together, something
special happens. Before it’s a bunch of
tiny isolated clusters and after, nearly
everyone is joined!

6 Degrees of Separation
Milgrams experiment to see how connected
people were between distant cities (ie: Omaha to
Boston)
HOW HE DID IT:
1.
Sent out letters with postcards to be returned to
Harvard
2.
Stipulation: If you did not know the target, then
forward the letter on to someone who might have
better odds of knowing the person THAT YOU
KNOW
3.
If you know the target, mail the folder directly to
the person
*The results? One letter only took two steps, but on
average, it took 5.5 people to make it to the target
person (with 42 of the original 160 letters actually
returning to Cambridge)

6 Degrees of Separation?!
2
5
4
1
6
3
So perhaps this isn’t
actually accurate, for we
are all connected… by
the means of our class 
(ps. Thank you www.thefacebook.com)
Scale-Free Networks & 80-20


“Various complex systems have an
underling architecture governed by
shared organizing principles”
We know this stuff like the pro’s:


Some nodes have tons of connections
to other nodes (and are known as hubs)
and these networks are scale-free
Characteristics include: highly robust yet
very vulnerable to coordinated attack
Examples, please…
SCALE FREE NETWORKS
So about this 80-20 thing?






80% of peas are produced by 20% of
peapods
80% of the land in Italy is owned by 20% of
the population
80% of profits are produced by 20% of the
employees (Murphy’s Law of Management)
80% of customer service problems are
created by 20% of consumers
80% of decisions are made during 20% of
meeting time
80% of crime is committed by 20% of
individuals
Bell Curve

Many things in nature are follow
a “normal distribution” or bell
curve with empirical rule: http://wwwstat.stanford.edu/~naras/jsm/NormalDensity/NormalDensity.html
Versus Power Law



In networks the power law describes
the degree distribution
The exponent is the degree
exponent; there is no peak
Consider the internet and links from
webpage to webpage, an obvious
network



Number of web pages with k incoming
links: N(k) ~ k-γ
Slope of line of log-log plot = 2.1
Outgoing = 2.5
Network Governance

Two laws: growth and
preferetia
attachmet



Assume that new nodes connect via
two links (will always choose the
node with more connections)
This is how we get the “highly
connected hubs” and the power law
is modeled
“Rich-get-richer” phenomenon
From Networks…

“The goal before us is to understand complexity. To
achieve that, we move beyond structure and
topology and start focusing on the dynamics that
take place along the links. Networks are only the
skeleton of complexity, the highways for the
various processes that make our world hum… Our
quest to understand nature has hit a glass ceiling
because we do not yet know how to fit the pieces
together. The complex issues with which we are
faced, in fields from communications systems to
cell biology, demand a brand new framework…
Now we must follow these maps to complete the
journey, fitting the pieces to one another, node by
node and link by link, and capturing their dynamic
interplay.”
~Albert – Laszla Barabasi, “Linked” pp. 225-226
To Complexity!!!