okay one more try so what we're going to
do today we're going to talk about the
basics of the probability theory we're
going to talk about power law
distribution uh we talk we discuss what
scale fret scale free networks are we
look at the distribution of parameter
estimations and we'll talk about zips
flaw so continuous random variable for
those guys for those we can easily
calculate probability density function
and I'm sure you're familiar with this
society okay
so probability density function PDF and
you know in fact it's just an integral
from A to B of from xdx gives us a
probability that the random variable is
within the interval from A to B and the
only thing we need for this function is
to be greater or equal than zero and the
integral over the entire um definition
domain should be equal to one we're
going to be working with so called CDF S
which is cumulative distribution
function um that is just an integral of
V at X DX or the derivative from CDF is
our distribution function and we'll see
that it is very convenient to define
what's called complementary cumulative
distribution function which is C CDF
which is in fact just a probability that
random variable is greater than X so
just to give you an idea if we have a
Gaussian distribution and I'm sure
you're very familiar with it on the left
side on the left side of the picture we
see PDF on the right hand side on the
right side it is cumulative distribution
function it looks very different if we
look at the exponential distribution um
on the very left side we'll see a
decaying density which is a PDF
exponential function then next picture
in the center that is a cumulative
distribution function and it is in
between 0 & 1 and so it pretty much
shows as the share of their different
variables that are below the particular
value that is selected and on the right
picture we see CCDF which is a
complementary cumulative distribution
function but this time it is plotted in
log log scale well in fact if you try
and calculate on the CDF and then CCDF
you realize that CCDF has the same form
as the PDF itself and so the fact that
it is a straight line in log log scale
it really means I'm sorry in log it is a
log on the on y-axis I'm sorry slop on
the y-axis it is a straight line right
and you can easily see that but if you
take an exponential function and take
logarithm on the left hand side right it
will be a logarithmic function on the
right hand side it's just X um the gain
is sort of some basic facts that you
probably remember from probability
theory now if we didn't with discrete
distribution um then we defined what's
called probability mass function or PMF
or sometimes it's called probability
density mass function
but the idea is pretty much the same so
it is equal to the probability that's
random variable is equal to X in this
case instead of integration we use
summation to normalize things and the
same way we can define a cumulative
distribution function which is just some
all values less critical than X though
we're going to be dealing in this course
with mostly discrete distributions and
experimental distributions of these
three distributions and in networks
we'll going to be looking at the
distribution of the node degrees that is
the number of nearest neighbors which is
a discrete variable okay we will look at
the formulas in continuous distribution
um the reason for that is because
discrete distribution we get all kind of
sums and the they're actually difficult
to evaluate with continuous distribution
you have integrals and it's pretty easy
to take those integrals and in the limit
and we understand that discrete
distribution functions will be a slowly
approach continuous distribution so
whatever um we'll get it as the limits
whatever we get in continuous
distribution functions we'll sort of
believe that that's the limiting
behavior of discrete so if you look at
empirical distributions and empirical
meaning we just go out there and measure
and let's for example look at the
empirical distribution of heights of say
of people or say distribution of speeds
of cars on the freeway typically they're
clustered around some value and in fact
they come from a Gaussian distribution
normal distribution and that's the top
top pictures on the slide at the same
time if you look at some other economic
data let's say for example we look at
the population of the cities and the
percentile of the cities or well number
of the cities with that population so
let's say we're going to look at the
distribution of the sizes of the cities
in the country or in the world um all of
a sudden we'll see that well there is no
typical size of the ceiling there are
some cities that are other majority of
the cities has very small population so
there are like a lot of cities were a
small population but the receipt is with
with a very large population there are
not many of them but they are out there
and so the distribution of the size of
the cities is very very different from
the distribution of say human hides
piece of cards um in some sense if say
the height of a human would be
distributed the same way as a population
as a population of the serious we would
you know see people ah
Faina 4 5 10 meters high or you know
centimeters high which we of course do
not see so it is clear that in for
example human height and see population
of cities are joined by very very very
different statistical processes
um that leads to very different
distributions so if we get look at their
population of the city distribution on
the left
um bottom left picture um you see it
decrease very very fast and you already
seen in the in the lab that in order to
see this type of a picture um you need
to plot it in log log scale and then on
the right side it is in the log log
scale it's almost linear here and we'll
see why in a second so in fact this is a
this is a power law and this is the
topic of today's lecture in power law is
really just in the function where G of X
is proportional to X to some power I
mean if you're if you remember with the
physics for example this law is not very
exotic because you know you think about
the forces that are 100 x squared over
or potential energy that 100 X and that
that examples of power laws but if
they're common in physics there they
have not been explored a lot in social
sciences or or in economics of computer
sciences
so again power law is when you from X is
some constant X to the power of alpha
and alpha in this case is positive right
so is the functional form of 1 over X to
certain power um and for this to make
sense typically would define X and be
greater recall some minimum value so X
should be greater or equal than some X
min and we need this to avoid division
by zero
now power laws are quite tricky um and
the first of all
you realize that if we want to go it's a
distributed right and so in order for
this function to be a distribution
function it has to be normalized which
means the integral over the entire
domain has to be equal to 1 well if you
look at this integral which is one
second pretty flat slide you see that we
do DX over X to the power alpha now if
alpha is equal 1 or even less or less
than 1 if alpha is 1 this integral is
logarithm and logarithm on the upper on
the upper bound at infinity will diverge
if alpha is less than 1 we'll get some
even stronger divergence so this means
that the power log function is
normalizable only for alpha greater than
1 and so it's only for alpha greater
than 1 it actually can behave as our
distribution function now what we can
take this integral if alpha greater than
1 and find your normalization constant
and sometimes it's convenient to write
the power law PDF the way it's shown at
the bottom of the slide so the only
thing I have done here is I substituted
the constant into the equation ok so the
key point here is that a power law is
really defined as a distribution
function is defined only for alpha
greater than 1 because otherwise you
cannot normalize it now here
is a very important picture um actually
I'll try to draw on it um I hope it will
not slow down the will not interrupt the
speech but we'll see how it works please
let me know if you start getting
troubles with with hearing me okay so
first of all the sort of traditional
Poisson distribution right um we have um
it goes up and then down a Poisson
distribution defined for discrete values
that's why there are dots here I will
just connect them with lines for for
ease of see then there are a couple more
distributions here there is an
exponential distribution exponential
decay here are between 1 and there is a
power law function blue one um if you
look on the inside you'll see the zoom
in region starting from somewhere here
all right let's resume the in and notice
that the power law is much much much
higher here than a Poisson or
exponential function so which means it
decays much slower than either Poisson
or exponential function so that also
means that for certain events that
Mike's that the probability of those
events are negligible input so on our
exponential functions they're quite
probable in the power law and that's why
power law function is also called a you
know fat tail function because the tails
they do not decay fast so that's one of
the things one of the critical another
critical things about power laws is that
it has fat tails which means rare events
well events far away on this on the
xxs events fear their probability is not
that small um and that's we need to have
in mind any questions on this slide okay
to move on so if we look at the power
law distribution function PDF well we
have seen it already and we can actually
calculate for this function our CCDF um
complementary a distribution function
which in fact just nothing more than
taking an integral taking an integral
and just doing it nicely and without
mistakes and that's what we get as a
result now I strongly recommend you guys
to actually take this integral yourself
there is no it's not difficult at all
but we need to be careful with the so
exponents now one thing to notice is
look this is exponent of power law
distribution function itself this is the
exponent of complimentary CDF notice
that both of them are actually power
laws it's just one of the power laws the
first one the power law itself has alpha
here um this one has one degree less um
which in fact means that we can use this
and let's say if we're going to be
looking in inter log log scale both of
them power laws itself the distribution
function and complimentary distribution
functions both of them will be straight
lines in the log log scale and we're
going to use that later on
so here's a couple more comparison and I
again I'm drilling on this because I'm
you know this is a key property of those
followers so if you look at this we see
our law this is a log log scale in fact
this is not X this supposed to be a log
and this is also log so P when looking
at the log log scale if you have a power
law then in the log log scale is going
to be a log of power x um will be a
linear function of log of X and if you
plot log of X on x axis and log of P of
X on Y axis
well we're going to get a straight line
and alpha the slope of the line and log
C is just how it's displaced
particularly well if we look at UM this
is a CCDF also exponential and so in
this picture it also will be a straight
line now we can compare it to the
exponential function and in exponential
function if we take logs you will see a
log on the left hand side but on the
right hand side it will be x itself and
so if you want to draw a to the plot it
has to be expressed again through the
log of X if you want to have logs on the
excesses and which means that if this is
a power law function this is a power law
function
these are exponents and so in a
logarithmic scale you can actually see
how much faster exponent or exponential
function decays than power law I keep
talking about it because of the
following reason um in very many cases
when we try to experimentally measure
the distribution function we would like
to decide for us where
it is exponential distribution whether
it's plus on with its galsia or whether
it's a power law and the simplest way
the easiest way to find it out is by
actually plotting in a log log scale and
seeing if we have a straight line so if
we have a straight line in a log log
scale and whether you whether you plot
the distribution function itself or
whether you plot CCDF in both cases it's
a signature of power law now in practice
we might see that there are different
parts of the space where where we'll
have different slopes of those lines so
the total distribution will be built out
of several power laws but still power
laws okay so here if you
examples this is a few examples of
empirical distributions um these are
taken from the paper by Mark Newman and
the paper is available on our site so if
you're interested you can read more
about this just shows very different
very different abuse ins that exist out
there in the world first of all the
famous one which is the word frequency
so it's the frequency of the words in
the language and we actually talk about
this a little bit later today
another example is for example the
citation network so how many papers come
how many times they have been cited
we're getting histogram and if you
notice the results a straight line here
but you know the it's not power law at
the beginning or for example book salt
I'm the same sort of idea of the power
law distribution there are majority in
there some books that are bestsellers
but there are only few of those books
right so there's a book so these have
this sellers and there are very few of
them majority of the book I'm they're
selling but not maybe not that much and
etc etc etc number of calls receive
their the magnitude of earthquakes
you know population of the city is
frequency of the names network of people
in US dollars and that sort of this is
the famous principle that um you know
that the Pareto principle that most of
them of the money most most of the
wealth belongs to just if you know a few
percentiles of the population right
twenty percent of the population owns
more than 80% of the our world currency
of world will use so um these are all
power loss now um you might get an
impression that everything in the world
is a power law well it's not
quite often there are you know a lot of
empirical distribution distributions
they do content they do contain pieces
of power law okay now Allah the one of
the reasons we keep talking about this
is power law is quite tricky compared to
it like Gaussian distribution or
exponential is very simple and
straightforward so here is another
example of issues we can get with the
power law look typically for a
distribution you know when it when some
random variable is distributed certain
way you might want to learn you what you
might want to know say the average or
mean of the variable
um deviation and you know if we talk
about Gaussian say distribution you know
that me and then variance so it's all
easy and in fact they define the
distribution well um this power law life
is somewhat different look I'm trying to
calculate a mean or average well it's
just X px and we define that it goes
from X min so you know everything is
cool and nice except for this moment
notice that when we substitute a P of X
here um the coefficient drops from alpha
to alpha minus 1 and that means that the
integral because it has goes to infinity
up here will diverge unless alpha is
greater than 2 now if alpha is greater
than 2 this integral converges and you
know there is a value for average with
standard
the Asians even worse because we have
here x-squared the power drops here two
times for this integral to converge on
infinity we need to have alpha greater
than three so this is a little bizarre
uh you know you have a bunch of data
points and what this actually tells us
that we cannot calculate the average or
deviation this is really strange right
well I mean the the truth is that you
know in in real life when we try to
calculate these things we in fact will
not go to infinity here what's going to
be happening is are we going to go to
some maximum value um the reason for
that is simply because our distribution
is not infinite so it contains finite
number of data points and data samples
and among those data those data samples
there is the largest one and and so um
there is no infinity but that bring is a
very very important and interesting
point notice that if I actually take
this integral as is but I will use
instead of instead of infinity I'll use
maximum value then of course the result
will depend on this maximum value notice
that when alpha is greater than two
alpha is greater than 2 and this x max
increases and goes to infinity and alpha
is greater than 2 then this second term
goes to zero and everything
school now if alpha is less than two if
alpha is less than two in here then what
happens is when x increases this entire
sum increases now it has minus in front
of it but if alpha is less than two
there is a minus in here so it still
remains positive but it also means that
your X average will depend on x max and
will be proportional in fact two x max
so what's going to be happening is the
following you take the bigger sample you
take the larger x max will be in that
sample and so the large x max the
largest x average and so you're going to
see this the following picture you
increase your sample size from your
distribution and all of a sudden you
will see that sample mean is not
saturating but growing and of course
variance will be growing - that happens
since if alpha less than now if alpha is
greater than - just a little bit greater
than 2 then for example for me
everything will be good it will converge
to the mean of the population but
variance still will be undefined and
only for alpha greater than 3 mean and
variance will behave nicely so what that
really means is the following when you
make experiments you rarely have access
to the entire population right when you
make experiments here is your population
here is your world well you make
experiments or get some data you
actually take a sample and you know with
nice distributions like Gaussian
distribution on the mean of the sample
right the average in the sample is
actually going converging to the average
of the population that sort of the
basics of sampler well who is power law
the mean if alpha is less than 1.7 is
going to be growing with the size of
your sample and so you need to grow the
size of a sample to the entire
population to actually get on the
correct answer okay the practical um
conclusions here is the following when
you're dealing with our laws if your
power law is less than two I mean
doesn't make any sense you're not going
to get the correct estimate of the mean
or variance if you parallel ears in
between two and three you'll get a good
estimate might get a reasonable estimate
of mean but computing variance is
useless it will depend on the sample
size and it's only for the power laws
that have alpha greater than three both
of them make sense now let's try your
microphone if I cannot compute me in aa
is everything other value I can use to
characterize the distribution all right
I either
or yeah I can read all right yeah median
so median is much more stable and this
is actually one of the cases where it
makes total sense I mean you know
sometimes when you do when you use
Gaussian distribution
I mean and and median you might ask like
why in the world would I use median mean
is good and Gaussian distribution it's
no problem but in the case like this I'm
you actually better off using median
simply because mean will depend on the
sample size right now the good news is
that pretty much all of the sort of
known distributions are have alpha
greater than two and so the mean is is
defined for them and in fact networks
and we're going to be talking about a
lot about networks in in networks the
power law is around three or a little
bit greater than three so um we're lucky
in the sense and we can deal with
sampling but what it has to be done very
carefully so I hope this example shows
you um that is a power law just taking
this simple mean is not a good idea okay
any question
so far all right the microphones
probably turned off so I will not hear
any questions
well if Andres microphone is owned all
right so one of sort of look another
name of this is a scale-invariant
distribution so why is it
scale-invariant
it's killing variant because of the
following reason um let's look on at the
value of the distribution when we do
probability of B X and B will be some
constant so this constant can be
factored out and so we can write it this
way and if you notice it seals X to the
power minus alpha so in some sense and I
guess there will be a better example
right now let's do this we can write
okay let me try to write here okay
probability of say 100 X divided by the
probability of 10 X because of this
property is will be equal to probability
of 10 X divided by the probability X all
right so this means
that we can change skills but if the
value is distributed this means that if
the value is distributed by this power
law then this ratio will stay the same
in other words the total number of
people the rate the total okay
the ratio of the total number of people
who make 100 dollars per hour to the
total not to the people who make $10 per
hour is the same as the ratio of the
number of people who make $10 per hour
to the people who make $1 per hour so
the ratio of you know total number of
large earthquakes to the ratio to the
number of medium earthquakes is equal to
the number of medium earthquakes to the
number of small earthquakes and that's
what sort of shown here on this diagram
and it's clear that there is a sort of
ratio especially if you if you think
about it in in a logarithmic scale but
this is another sort of key property of
a power law and that's why it's also
called scale invariance and in fact very
often power law networks they called
scaled invariant network and that's a
reason okay
here is a few examples of parallel
histograms and I'm not sure if you
already done this in a lab but on the
second slide right here right here you
will see something that looks like a
noise well this is not noise this is
actually property of the power law
distribution and when you zoom in you'll
realize why this is happening but it's
clear that by having that picture by
having that those oscillations um there
in fact will prevent you from really
easily to the slope of this on of the
power law so it's not clear you know if
you want to fit a straight line whether
it just goes straight here or somehow
here or maybe it should go that way um
we'll see in a second that it is much
better to actually do things like that
and the way to do it is instead of you
need PDF considering a cumulative
distribution function cumulative
distribution function actually has this
nice and much nicer behavior okay so
what others have to do with um with
networks well um here here is a sort of
the the key of the story we're going to
consider
the distribution of the node degrees of
the network so no degree is a number of
neighbors or number of friends and they
do or a number of links that that
attaches to every node and for a second
let think about networks as undirected
right
so the there is no direction on edges so
there are some nodes with a few
connections and here they are notice
their nose with a few connections there
are nodes with sort of several
connections and their nodes are really
really well connected and so the degree
of the connection or the number of this
nodes are distributed by power law so
the idea is that in most of the networks
you'll have some nodes that are very
very very well connected so they have
very high degrees but there will be not
that many of those at the same time
majority of the nodes will have low
degrees there'll be very many of those
so that's a typical power law
distribution think about it this way um
you know like say the webpage is on
there on the web I distributed based on
the power law there are some web pages
like CNN Google Yandex that have lots
and lots of links for hunting to them
and so they have very high degree but
they're not any of them at the same time
its majority of the sort of just lay
meant a layman person hey just just sort
of regular pages they are very low
degrees but there are tons and tons of
them
um the same goes with with say Facebook
or any social network you might think of
they're people that
similarly popular they're celebrities
have tons of connections but they're
only few of them majority of the people
live sort of in this side of the
distribution right there
here's a comparison what would world
look like if um the distribution was not
power law
but say you know traditional bell curve
or or Gaussian distribution right
there'll be sort of certain average
number of links that every webpage would
have and there'll be some sort of you
know some pages higher with more links
or less links um but we wouldn't have
any very very highly connected nodes
like we have Buddha's like to CNN or
other popular pages and at the same time
uh you know we will not have sort of
pages is very very few in links but we
do have that in real life
so we're living in this world and the
social networks they are they do add a
power-law distribution or scale-free
distribution so just to reiterate what I
have said what I just said
so not degree distribution it is defined
to the number of nearest neighbors so
we'll call it ki and it goes from 1 to K
max all right so we'll consider on the
connected sub graphs and the smallest
node degree for connected subgraph is
equal to 1 because you want to know to
be connected to graph and K Max is a
maximum node degree and we'll talk about
this degree distribution this is a
discrete random variable right a
discrete distribution and of course you
can normalize it you know by I'm just
counting how many nodes with degree K
over total number of nodes so in this
case power law is in a sense that we're
counting how many nodes have degree K
how many nodes has degree 1 which is how
many nodes have just only one neighbor
how many nodes have one friend versus
how many O's have two friends versus how
many knots have nodes have 100 friends
thousand friends
we could try to normalize those kind of
things and the normalization is actually
goes you know if I try to do math on
this thing I will get into Riemann
zeta-function
well we shouldn't worry about it we'll
stay with a very practical thing which
is right here so if one to do
normalization we're going to do this so
here's an example I would take and there
is a graph and you will have in homework
one of those graphs are what I what I've
done here I actually calculated the
number of notes of different degrees and
in this case the graph is directed right
so for every node we have incoming links
and we have outgoing links right and
they incoming and outgoing links they do
have different distribution which means
well slightly different distribution
which means they're either like like
like right here the red is actually
incoming incoming links and blue is a
distribution of the outgoing links and
if you notice by examine its other way
around I'm sorry the red is a
distribution of outgoing links red is
out blue is in and if you notice um this
is uh the node degree right if you think
about this this is a where this is a
piece of a web graph and in the web
graph there are some pages that have
very very high node degrees so there are
a lot of pages pointing to them in
general web pages will have less out
degree because out degree of the web
page is really
the links that person puts on the
webpage that connects it to other pages
right and the in degree it is the links
that other people put their pointing to
your page and so it's obvious they had
you know if you're putting links you
eventually will put much less links than
somebody in and then you know the total
sort of population can put links to your
page right and so that's why the in
degree um distribution will cut short
our degree we'll go that far
now again what's what this says is the
following
well let's see how many notes and well
this is normalized to be PDF right if we
don't normalize it will be just a count
of how many notes let's say have degree
distribution thousand right or how many
nodes have degree distribute has has
degree ten right what's the probability
what the probability that randomly
selected node will have a degree ten or
what the probability of that randomly
selected node will have a degree one
what probability that randomly selected
node will have a degree store a degree
hundred degree hundred um etcetera etc
right so this is a probability that
randomly selected node will have certain
degree and degrees of incoming links can
be much higher than degrees of outgoing
links um but if you notice it's it's all
scattered and um we talked about this
that you know we want we want to see
power log so we want us to feed a
straight line and it's kind of clear
that you cannot feed a line in here
really well I mean for red nodes maybe
you still can kind of go this but for
you it's very unclear what to do with
this and it's not nice it's just you
know that the fact of life because
distribution is discrete you know you
have a node that has the degree um ten
thousand and you have a node that has a
degree above it and you have a node that
has a degree below it and it's just you
know single mode with that degree and
single node
that degree in single node with that
degree all right in order to actually
feed the distribution in this case we
better look into arm run the cumulative
distribution function if I calculate
cumulative distribution function for the
same distribution which means an
cumulative distribution function is in
fact you know just an integral under
these curves that what they're going to
look like so this is cumulative
distribution function for incoming and
for outgoing links okay now in this case
it's also not a perfect straight line I
mean not at all perfect straight line
but there is a fragment here that
probably fits really well in a straight
line and we can see here there is a very
very nice feed and so we're going to
tell us that there are pieces of the
distribution that actually follow follow
the straight line so follow the power
law now what happens here um it's quite
interesting well in also here why we
have a drop well the reason for that
drop is because um I actually pulled out
a very small sample from the web which
means um I cut it out for nodes to have
connections only within the assemble um
and if it continues to if it continue to
have a connection with the outside world
I would expect this to go down that way
and and this also to continue and not
drop abruptly so that's the effect of
the finite sample size but in here it
seems like it does a pretty good job on
in predicting so if you want to do to
measure the the distribute the exponent
in in the power
which is the slope in this case right
one way to do it is to actually build um
CCDF you know plot it and then do you
can try to do linear regression or
something else in a CC CDF but before
doing it you have to you have to
actually eyeball the picture and figure
out the regions those intervals where
you want to do the mapping we really
want to do this the feeling of the
linear regression then you have a chance
to get a reasonably good approximation
for um for all right remember we want to
want to try to estimate I want to try to
find this alpha and so we can get a
pretty good estimate in here um
but of course there are better
procedures than that this is sort of a
poor man procedure which you know allows
you to eyeball things and quick quickly
get get the numbers um you can do much
better
Oh before we go there let me show you a
few examples on them on the real
networks so um this is a parallel
network there are several Pawa networks
on the left side there is what's called
their collaboration graph and there is a
world wide web and then this graph or
power grid data I'm very different very
different sizes of the networks coming
from a very different fields but and
having quite different properties like
in the first case in the collaboration
actor collaboration network is the
average degree is 28 in world wide web
average degrees 5.6 in power grid
um it's 5.5 now here it's actually
called gamma the exponent um if you
notice it's greater than 2 but sometimes
it's less than 3 now see here it's 2.3
um here it's
point three point one four it's four and
there was small fragments in fact this
is very famous paper by barabási Albert
1999 that for the first time showed
those distributions distributions for a
worldwide way up for you know a true
collaboration networks power grids and
actually attract the attention other
people attention to this power law
distributions I think it was published
in nature or in science one of those
very very high profile magazines um
theories
example this example down by computer
scientists animus is a web crawl notice
um that those pictures this is in degree
and out degree
notice that the pictures fans out it
stands out because it's not a cumulative
distribution function it is a
distribution function itself so um when
when the whole thing was just starting
and that was you know if you know this
fifteen years ago people didn't realize
that it's better to build to draw a
cumulative distribution functions so
that's one of the first papers that
showed that on the web the distribution
of the node degrees um is is following
power law okay so how do we actually
estimate the parameter what's sort of
the right way to do it or it's a
scientific way to do it well the way to
do it is to using what's called maximum
likelihood estimation imagine that every
point in your graph every point is
generated on independently from some
distribution all right so have some
distribution and those plan and that
distribution of generate generate points
for us um well if we have you know this
is a distribution with the linguist this
is our power law and I just normalized
it it with normalization then
probability of the sample is just the
probability of a bunch of independent
points in this sample so we just can
calculate this as the product of the
probabilities of every point in the
sample then we're going to use Bayes
theorem just that it says okay well the
probability of parameter alpha given our
data points is equal is can be
calculated through the probability of
our model well if we have alpha to
generate those data points times their a
priori probability or
the particular parameter alpha x divided
by the probability of the data points
right again since we're going to be
doing maximum likelihood wouldn't care
about this because we're going to be
optimizing with respect to alpha and in
fact since we don't have any our priori
ideas on what alpha has to be will
consider all sort of a priori a priority
values of alpha equal in probabilities
and so P of alpha will also be constant
for us so in some sense you know the
user base theorem here is just to invert
I'm going from generating data points
from from the distribution to actually
estimating the parameter well it's a
very track standard trick um for maximal
likelihood estimations so what you're
going to do is write down the log
likelihood and again it's it's it's
logarithmic you know if you never done
this I strongly recommend you to do it
at least once to this exercise it's log
likelihood you want to be it to be
logarithmic because you get rid of
product and you write down everything as
a sum and now those x i's are our data
points lambda our parameters and you
want to find the parameter that
optimizes this log likelihood well the
optimization is through will try to
maximize this log likelihood I just take
in standard derivative with respect to
alpha and if you differentiate this with
respect to alpha you realize that
logarithm will become 1 over alpha minus
1 this will go away because it doesn't
depend on alpha here alpha will just go
away and we'll the some remains and so
if
equating this to zero we can calculate
alpha and that's going to be well that's
going to be the estimate for for alpha
and alpha gain is our exponent the value
of the value of our exponent we can
actually also estimate standard error
I'm not going to talk about it but if
you're interested um take a look at Mark
Newman's paper it's also online as
recommended reading for this lecture um
there is a duration of how you can
actually calculate the standard error
the error estimate for this alpha so if
you notice in this formula um we have X
I which are data points and so in fact
it's very it just trivial to estimate
alpha if you try to do this you realize
that it dramatically depends on x-men
x-men is that point manage that here we
have our distribution x mean is that
point from which we start we start
taking into account the distribution and
we can move it and depending on the
position of the six mean um the estimate
of Alpha will differ so we need to find
somehow X mean that that that the best
job in describing our distribution so we
need to find out starting there on a
histogram we need to take the data
points into account when we calculate
alphas and again there is pretty
standard way to do it um we're going to
follow the following idea
um the residuals called comic world
Smirnov test we that allow us to compare
a model and experimental cumulative
dance
functions the idea is the following this
is the model that we generate right
right um and this is so so since we can
calculate PDF we can calculate CDF we
can calculate C CDF we can calculate
whatever we want so here it's it's
written for CD EPS so we can calculate
CDF from our model by setting up
parameter alpha and choosing X min and
this is the experimental data so our
common ball kolmogorov-smirnov test says
the following let's find the difference
between them and let's look for the
point
oh let's maximize it with respect to X
and finding the largest difference will
give us this D value then we can go
through different select different X
mins for each x mean we can calculate
corresponding D value okay again so this
is the curve this is a curve to find the
difference the distance between them
which is also you know curve but then we
we find the maximum distance find it in
the maximum possible distance between
them so we find that X that provides the
maximum distance in this case is right
here and that's the D value so then we
can plot the D value as a function of X
min and we're going to be looking for
the minimum in here and a third minimax
principle yeah we're going to be looking
for the minimum value on this curve um
if you done machine learning you this
might look a little bit familiar because
machine learning this is one of the way
you actually tune up parameters you go
through the tab parameter space and
you're looking for some score or error
metric and you look for the optimal in
there and in this case which is using
this common gross runoff metric to
define it so when you find X min when
you find X
in the optimal one that tells you where
on the distribution you need to start on
them the mapping where the mapping will
be the optimal um and you know the way
it knows it is simply because when we
calculate this F we do use the power law
model so if you look in the logarithmic
graph the parallel model is a straight
line and so what it says is how to
position straight line
where to start the straight line such a
way that the feet will be optimal and
sometimes it can give you you know the
starting point somewhere here somewhere
here sometimes it can tell you well you
know what you almost don't have a
straight line you just need to grab the
last couple of points to get a straight
line and that will mean that you really
don't have a parallel distribution but
sometimes you know it will be like this
so pretty much what we went over is a
very practical way to detect the power
law distribution and calculate the
coefficients so first when you do when
you have a power law data and you can
compute a PDF you can then do CCDF um
which allows you to see a straight line
in there and then you can either on a
cumulative either on CDF itself or on
complementary CDF you run comma gorman
of test and find the best spot to
actually match straight line up here
again if you're on Commodores no no of
test and and it has been done on those
examples you know we if you look closer
later on the slides you'll see there are
some lines there but I'll just sort of
emphasize here here it starts at this
point here it's here um you know on the
on it pieces here it starts straight
line matching there it's there well here
it just goes I think always through so
depending on your power law distribution
common enough test will actually give
you the point on the histogram like here
from where to start your match
okay um the last sort of piece of this
lecture is just to give you a quick
example of power laws in somewhat
different world I'm going to the actual
language processing and the reason um I
want to talk about it is because um this
idea very very powerful way to quickly
plot distributions and you know to
quickly be able to see um if we have a
power law or not without going through
histograms which is actually pretty cool
so let's consider um some you know
natural corpus some language um and just
words that that use in the language and
here's an example in this example there
is a corpus size of 85 million different
words and out of those 85 million this
is it's actually brown corpus I believe
it's around this an 8 out of the corpus
there is around 6,000 unique words ok
and in the in the in the file in this
data
I just ran strict it to minimum
frequency of 800 which means the word
occurs 800 times in in this data set
right and say for example the most
frequent word is the that is that
happens more than six million times in
this data set then be more than four
million times then off you know three
million times etc and you know this is
not the bottom of them of the actual
data said this is just the bottom of the
sample you know that the actual data
said that the frequency of word goes
goes even lower I'm so the frequency
table what frequency table is simply the
words sorted by their frequency by the
frequency with which they occur in our
corpus or you know the frequency that
they are currently in in a language
because this is a pretty large sample of
the language and in fact yes D is the
most frequent word in English right and
then it follows by B by off etc so yeah
you can you can build this easily for
Russian okay so that's called a word
frequency table well in fact um in 1930s
American linguist George Zipp studied
this and he came up with what's called
now which was now known as a zip slaw
which literally states that the
frequency of a word in a natural
language corpus is inversely
proportional to its rank in the
frequency table which sounds a little
crazy it pretty much says that the
frequency of you know the second word
will be half
the frequency of the first word the
frequency of the third word will be half
of the frequency the second of I'm sorry
will be the third of the frequency of
the first word the frequency of the
fourth word will be the quarter of the
frequency of the first word etcetera etc
etc you see that in this example it's
not exactly that way but you know close
close to it right so this low has been
adjusted and updated a little bit um to
show that in fact uh we you know we
don't use just the frequency it is just
just the ring it's one of a k2 the power
of s there is some power s and you know
for different languages and for
different actually part of the curve um
this s might be might be different but
still this law works and for example
here on this picture you see the
distribution of the words in the key
pedia um and so what's done here is
really uh
we calculated the the rank frequency
table where on one axis on one axis
there's a rank and other x is their
frequency so we just plot frequency or
the function of rank rank the function
of frequency and you notice for the Z
distribution there are two pieces right
here sort of straight part and there
they're straight part and you can map to
different straight lines and those
straight lines tell you that okay there
is a distribution um one over x squared
which is x equal to two and you know the
green one is roughly one over X so
that's a very proximate law and in fact
there has been many very many theorists
and some people believe Y is you know
they know why the language is is is
distributed that way I'm others say you
know it's it's not because of that but
the
what is that if you take em if you take
the the words in the language sort them
by the frequency on average um you know
the the rank of the word I mean sorry
the frequency of the word um it'll be
universally proportional to its ring
sort of experimental law um in fact if
you look at this you realize that well
this is you know it's it's all over
again the same power law been talking
about right it's if Kesey x power alpha
it's just instead of X we're using K
instead of s we say here alpha but this
is a power law and we're frequency is
just inversely proportional to the rank
well that's a power law is degree why
yeah so why is this interesting for us
and we're not linguist I mean it's kind
of curious but why bother
well the reason is the following the
reason is the following
um imagine that we we take items and you
know we did it with words but you can
take it with with any other items um we
can do it with you know nodes in the
graph we sort items by their frequency
in decreasing order by the frequency of
the appearance of items in decreasing
order so it's the same way as as you did
with with words okay all right now here
is a key statement that the frack
of the words with frequencies higher or
equal to the kate word it's actually in
by definition is a cumulative is
complementary cumulative distribution
function because it's defined as a
fraction right fraction of those
variables that a greater or equal to 10k
that's our definition but at the same
time this fraction of the words it's in
fact nothing else than the rank of the
word well let's look at this let's say
we take the word n and well how many
words out of all the number of words
have frequencies greater than end when
this guy this guy this guy and and
itself so there if I calculate the CDF
will be four divided by the total number
of of words but what's four well four is
really the rank of end so what happens
is the rank the rank of the word in the
frequency table is actually actually
gives us when normalized properly gives
us a complementary cumulative
distribution function this is
very trivial statement arm I encourage
you to you know look at this statement
and think about it but the consequences
are very interesting in order for us to
plot is CCDF what we need to do is to
just sort the items we have in the
decreasing order and then plot what's
called rank frequency create rank
frequency plot which is put rank of the
item in the table on the y axis and put
the frequency of its occurrence on the x
axis and if you do that we'll actually
get a plot of cumulative distribution
function of that quantity so we want to
look at the node degrees we can just
sort all the nodes in the decreasing
order and then plot um the rank of the
nodes versus under the frequencies of
the currents of those nodes and that
will create for us CCDF it's in fact if
we just want to do CCDF we don't even
need to do histograms we don't need to
do histograms we don't need to do
integration of the histograms we can
just do simple counting
um and the here's an example of that
done uh forfor zip slaw the one you just
saw so we're what I did is I took um
word ranks so I sorted words I'm based
on the frequency right and the word rank
number one has this frequency right the
word number ranked number two has this
frequency the word number five oh that's
a frequency of that word etc etc etc
okay
so when you do that and then of course
you plot this in log log scale this is
log right and this is log you'll get a
straight line and you get straight line
for zips law will get us you know almost
straight line for when when you look at
the networks and so that's sort of the
trick but very very practical trick um I
encourage you to use when you look at
the networks so that's pretty much it
for today
there are several references um they're
all available on the website I would
recommend you to read um there is a
power law of credit distribution unzips
law it's paper by Mark Newman um it's
quite lengthy uh but you know it
probably the first part of it is pretty
good and power law distribution
empirical data that's another paper it's
2009 that actually talks more about how
to measure the power law and the data
talks about kolmogorov-smirnov test and
things related to that and if you want
to learn why um you know one of the
theories why we have power laws all over
the place
well theories is the third paper the
history of generative models for power
law and log normal distribution which is
also quite an interesting read all three
of them are available on the website for
the class um and that's it for today
any questions
well it scares me when there are no
questions