network_ana

main.tex (4952B)

---

 \documentclass[a4paper]{article}
 
 
 \usepackage[T1]{fontenc}
 \usepackage[utf8]{inputenc}
 \usepackage{mathptmx}
 
 %\usepackage{ngerman}	% Sprachanpassung Deutsch
 
 \usepackage{graphicx}
 \usepackage{geometry}
 \geometry{a4paper, top=15mm}
 
 \usepackage{subcaption}
 \usepackage[shortlabels]{enumitem}
 \usepackage{amssymb}
 \usepackage{amsthm}
 \usepackage{mathtools}
 \usepackage{braket}
 \usepackage{bbm}
 \usepackage{graphicx}
 \usepackage{float}
 \usepackage{yhmath}
 \usepackage{tikz}
 \usetikzlibrary{patterns,decorations.pathmorphing,positioning}
 \usetikzlibrary{calc,decorations.markings}
 
 \usepackage[backend=biber, sorting=none]{biblatex} \addbibresource{uni.bib}
 
 \usepackage[framemethod=TikZ]{mdframed}
 
 \tikzstyle{titlered} =
     [draw=black, thick, fill=white,%
         text=black, rectangle,
         right, minimum height=.7cm]
 
 
 \usepackage[colorlinks=true,naturalnames=true,plainpages=false,pdfpagelabels=true]{hyperref}
 \usepackage[parfill]{parskip}
 \usepackage{lipsum}
 
 
 \usepackage{tcolorbox}
 \tcbuselibrary{skins,breakable}
 
 \pagestyle{myheadings}
 
 \markright{Popović\hfill 1st Exercise \hfill}
 
 
 \title{University of Vienna\\ Faculty of Mathematics\\
     \vspace{1.25cm}Seminar: Introduction to complex network analysis \\ 5th
 Exercise
 }
 \author{Milutin Popović}
 \begin{document}
 \maketitle
 
 Looking at a social graph with $N$ nodes, the expected degree of a random
 node is $\langle k\rangle$. Each of $\langle k \rangle$ edges points to a
 different node. The probability that a random edge is connected to a node
 $i$ with degree $k_i$ is
 \begin{align}\label{eq: annd}
     p(k_i) = \frac{k_i}{\sum_{j}^N k_j} \;\;\;\;
 \end{align}
 for all $i = 1,\dots,N$. Thus the average degree is calculated by the
 weighted average
 \begin{align}
     \langle k_{nn} \rangle = \sum_i^N k_i p(k_i) = \frac{\sum_i^N
     k_i^2}{\sum_j^N k_j} = \frac{\langle k^2\rangle}{\langle k\rangle}.
 \end{align}
 For scale-free networks we have a power law distribution, meaning
 \begin{align}
     p(k) = c\cdot k^{-\gamma}
 \end{align}
 Thereby we can calculate the $n-th$ moment of the degree distribution
 \begin{align}
     \langle k^n \rangle = \int_{k_{\text{min}}}^{k_{\text{max}}} k^n p(k) dk
     = c \frac{k_{\text{max}}^{n-\gamma+1} -
     k_{\text{min}}^{n-\gamma+1}}{n-\gamma +1}
 \end{align}
 We can substitute the $1$-st and $2$-th moment of the degree distribution in
 to the equation \ref{eq: annd}, giving us
 \begin{align}
     \langle k_{nn} \rangle \frac{}{} = \frac{\gamma-2}{\gamma-3}\; \cdot \;
     \frac{k_{\text{max}}^{3-\gamma} -
     k_{\text{min}}^{3-\gamma}}{k_{\text{max}}^{2-\gamma} -
 k_{\text{min}}^{2-\gamma}}
 \end{align}
 In the cases of $\gamma \rightarrow 2$ and $\gamma \rightarrow 3$ we have the
 friendship paradox. Let us compute both cases
 \begin{align}\label{eq: scalefree}
     \lim_{\gamma \rightarrow 2} = \frac{\gamma-2}{\gamma-3}\; \cdot \;
     \frac{k_{\text{max}}^{3-\gamma} -
     k_{\text{min}}^{3-\gamma}}{k_{\text{max}}^{2-\gamma} -
 k_{\text{min}}^{2-\gamma}},
 \end{align}
 we will need to use the L'Hopital rule once since we have the case
 $\frac{0}{0}$. By applying differentiation in both the numerator and the
 denominator we get
 \begin{align}
     \lim_{\gamma \rightarrow 2}& \frac{
     \frac{d}{d\gamma}}{\frac{d}{d\gamma}}\frac{(\gamma-2)}{(\gamma-3)}
     \frac{(k_{\text{max}}^{3-\gamma} -
     k_{\text{min}}^{3-\gamma})}{(k_{\text{max}}^{2-\gamma} -
 k_{\text{min}}^{2-\gamma})}=\nonumber \\
     &= \frac{k_{\text{max}} - k_{\text{min}}}{\ln(k_{\text{max}}) -
     \ln(k_{\text{min}})}.
 \end{align}
 Similarly for the $\gamma \rightarrow 3$ case we need to apply the rule of
 l'Hopital, giving us
 \begin{align}
     \lim_{\gamma \rightarrow 3}& \frac{
     \frac{d}{d\gamma}}{\frac{d}{d\gamma}}\frac{(\gamma-2)}{(\gamma-3)}
     \frac{(k_{\text{max}}^{3-\gamma} -
     k_{\text{min}}^{3-\gamma})}{(k_{\text{max}}^{2-\gamma} -
 k_{\text{min}}^{2-\gamma})}=\nonumber\\
     &= \frac{k_{\text{max}}k_{\text{min}}\left(\ln(k_{\text{max}}) -
     \ln(k_{\text{min}})\right)}{k_{\text{max}} - k_{\text{min}}}.
 \end{align}
 We can compare this to a random network which follows a Poisson distribution,
 where the 1st and 2nd moments are
 \begin{align}
     \langle k^2 \rangle = k^2 \\
     \langle k \rangle = k,
 \end{align}
 giving us
 \begin{align}
     \langle k_{nn}\rangle = \frac{k^2}{k} = k.
 \end{align}
 
 We will now take \ref{eq: scalefree} and substitute $k_{\text{max}}$ with the
 natural cutoff (largest expected hub) to get an approximate expression
 depending on the number of nodes $N$. Explicitly we substitute
 \begin{align}
     k_{\text{max}} = k_{\text{min}} N^{\frac{1}{\gamma -1}}.
 \end{align}
 This will give us
 \begin{align}
     \langle k_{nn} \rangle = k_{\text{min}}\frac{2- \gamma}{3-\gamma}
     \frac{N^{\frac{3-\gamma}{\gamma-1}} - 1}{N^{\frac{2-\gamma}{\gamma-1}} -
     1} \;\;\;\; \underset{N\rightarrow \infty}{{\longrightarrow}} \;\; \infty
 \end{align}
 
 \nocite{code}
 \nocite{barabasi2016network}
 \printbibliography
 
 \end{document}