Power Laws
Degree Distribution
Let $f_d$ denote the fraction of vertices of degree $d$ in a given network (where the total number of vertices are $n\times f_d$).
- Degree Distribution
- The sequence of $(f_0, f_1, \ldots f_{n-1})$ of a given network.
This is an array of values, not a scalar.
Therefore, given a network with $n=20$, $f_{12}$ means that there is one vertex with degree 12:
\[n\times f_{12}=20\times0.05=1\]Power Laws
We may believe that there is a linear relationship between the log of $f_d$ and the value of $d$ for a given network:
\[\log f_d=-\alpha\times\log d+c\]this implies:
\[10^{\log f_d}=10^{-\alpha\times\log d}\times 10^c\]and therefore:
\[f_d=\frac{10^c}{d^\alpha}\]Mathematical laws stating that a function $f(x0$ is proportional to $x^{-\alpha}$ (for some positive constant $\alpha$) are called power laws.
Model Fitting
We should be careful when noticing linear trends in data we should say:
The data we have fits (with a certain confidence) a power law.
Power Law Detection
We may want to check if a set of data fits a power-law distribution.
Power Law Detection General Method
- Find the degree distribution.
- Plot the points $(\log d+1, \log f_d)$ having $f_d\neq 0$.
- Use statistical methods to asses the statement: “the data at hand shows a degree distribution that obeys a power-law”.
Power Law Detection with Linear Regression
In general data is given as array of values $X$ and $Y$:
- This is usually points $(X_i, Y_i)$ which equals $(\log(i+1),f_i)$ for all $i$ where the given network has at least one vertex of degree $i$.
Find the line of best fit in the form:
\[y = c_1x+c_0\]using:
\[\begin{aligned} c_1&=\frac{\sum X_iY_i-(\sum X_i\sum Y_i)/N}{\sum X_i^2-(\sum X_i)^2/N}\\ c_0&=\frac1N\left(\sum Y_i-c_1\sum X_i\right) \end{aligned}\]This line minimises error which is calculated by:
\[E=\sum(Y_i-y_i)^2\]