Transcript Network Formation - SCCS - Swarthmore College Computer Society

Network Formation
Can we model it?
Oh
yeahhhhhhh!
Let’s see what Neo Martinez has to say!
General Information for Models
• Firstly, a “trophic species”
is a group of taxa
(organisms) that share
the same predators and
prey in a food web
• Food webs are
represented by a matrix
with S rows and columns,
which represents a food
web with S trophic
species.
• Visualizing the matrix,
S^2 links are possible,
but there are only L
actual links
• Directed connectance
(C)=L/S^2
The Random (Erdős–Rényi) Model
• Links in the random model all
occur with a probability equal
to C, which means that this
model does not take into
account any biological
structuring (trophic levels or
any kind of special
relationships). There is no
“pecking order”, and most
nodes have about the same
number of links (no hubs).
Thus, the model isn’t
particularly accurate for
biological systems.
• Most networks follow the
“scale free” or power-law
degree distribution, while this
follows the Poisson degree
distribution (there is a “modal
hump” for degree)
• We’ll talk about this more later
Cascade Model
• Each trophic species gets a random value
from 0-1
• Each species has a probability 2CS/(S-1)
of eating species with values less than its
own.
• This works a little better because now
things are a bit more ordered and we
have a semblance of a food chain, but…
“underestimates interspecific trophic similarity, overestimates food-chain length”
.8
.05
.9
The Niche Model
• Also assigns random numbers from 0-1,
called “niche values”
• Species can consume a range (r) of other
species. C is the range from r/2 to n.
• Allows for cannibalism and looping
Results
Other Models for Other Things
• The Niche model is good
for modeling networks
that are already
developed, but not
necessarily for predicting
how nodes are added
and how the network
grows.
• For that, you can use the
Barabasi-Albert model,
which incorporates both
growth and “preferential
attachment”.
The Barabasi-Albert Model…
• Power-law degree distribution:
• Power-law allows for ‘preferential attachment’
• Interactions between nodes can be represented
in a network model by direction of edges, or the
number of “in” edges and “out” edges, which, in
the case of a food web, would represent who
eats what; the Barabasi-Albert model is NOT
directed, because the fact that when a new node
is introduced, its “in degree” is 0, so nothing
would ever connect to it. The BA assumes that
each new node is connected to m other existing
nodes (has a degree of m when it enters).
…Sacrifices Realism for Simplicity
• If p(k)=fraction of nodes with degree k,
then the probability that a new edge will
attach to a node with that degree k is
(k*p(k))/(2m), where, if you recall, m is the
number of edges for each new node.
There is a 2 in the denominator to indicate
that there is no longer a direction (so each
edge provides two degrees).
Thus,
• Based on the prior
information, time plays a
role and older nodes
have more edges. The
model assumes new
nodes are added in
discreet time intervals.
• An example: this model
can be used for the
internet (the older a site,
the more hits it gets,
especially if it started out
with a lot of hits).
Some helpful sources:
-http://www.lce.hut.fi/teaching/S-114.220/k2005b/TH_14032005.pdf
-The Newman reading:
http://www.sccs.swarthmore.edu/users/08/bblonder/phys120/docs/new
man.pdf
-The Movie:
http://vw.indiana.edu/07netsci/entries/submissionspg2.html#diversity