network_ana

Complex Network Anlysis
git clone git://popovic.xyz/network_ana.git
Log | Files | Refs

main.tex (3702B)

      1 \documentclass[a4paper]{article}
      2 
      3 
      4 \usepackage[T1]{fontenc}
      5 \usepackage[utf8]{inputenc}
      6 \usepackage{mathptmx}
      7 
      8 %\usepackage{ngerman}	% Sprachanpassung Deutsch
      9 
     10 \usepackage{graphicx}
     11 \usepackage{geometry}
     12 \geometry{a4paper, top=15mm}
     13 
     14 \usepackage{subcaption}
     15 \usepackage[shortlabels]{enumitem}
     16 \usepackage{amssymb}
     17 \usepackage{amsthm}
     18 \usepackage{mathtools}
     19 \usepackage{braket}
     20 \usepackage{bbm}
     21 \usepackage{graphicx}
     22 \usepackage{float}
     23 \usepackage{yhmath}
     24 \usepackage{tikz}
     25 \usetikzlibrary{patterns,decorations.pathmorphing,positioning}
     26 \usetikzlibrary{calc,decorations.markings}
     27 
     28 \usepackage[backend=biber, sorting=none]{biblatex} \addbibresource{uni.bib}
     29 
     30 \usepackage[framemethod=TikZ]{mdframed}
     31 
     32 \tikzstyle{titlered} =
     33     [draw=black, thick, fill=white,%
     34         text=black, rectangle,
     35         right, minimum height=.7cm]
     36 
     37 
     38 \usepackage[colorlinks=true,naturalnames=true,plainpages=false,pdfpagelabels=true]{hyperref}
     39 \usepackage[parfill]{parskip}
     40 \usepackage{lipsum}
     41 
     42 
     43 \usepackage{tcolorbox}
     44 \tcbuselibrary{skins,breakable}
     45 
     46 \pagestyle{myheadings}
     47 
     48 \markright{Popović\hfill 1st Exercise \hfill}
     49 
     50 
     51 \title{University of Vienna\\ Faculty of Mathematics\\ \vspace{1.25cm}Seminar: Introduction to complex network analysis \\ 1st
     52 Exercise
     53 }
     54 \author{Milutin Popovic}
     55 \date{17. October, 2021}
     56 
     57 \begin{document}
     58 \maketitle
     59 
     60 \section{Balanced (Cayley-) tree}
     61 A Balanced (Cayley-) tree, is a tree with a central node
     62 and $k>1$ number of neighbors. Each neighboring node has another $k$
     63 neighbors up to a distance $h>0$ from the central node. These nodes are leaf
     64 nodes. For a given $h>0$ and $k>1$ the expression for the number of nodes $N$ is
     65 \begin{align}
     66     N = 1 + k\sum_{i=0}^{h-1} (k-1)^i = 1 + k\cdot\frac{\left((k-1)^{h} -
     67     1)\right.}{k-2}
     68 \end{align}
     69 Obviously the number of leaf nodes is then
     70 \begin{align}
     71     N_l = k\cdot(k-1)^{h-1},
     72 \end{align}
     73 thus the number of inner nodes (without the central node) is
     74 \begin{align}
     75     N_{in}  = k\cdot\frac{(k+1)^{h-1} - 1}{k-2}.
     76 \end{align}
     77 The ratio between the inner nodes and the outer nodes is given by
     78 \begin{align}
     79     \frac{N_{in}}{N_l} = \frac{1 - (k-1)^{1-h}}{k-2}.
     80 \end{align}
     81 Meaning that for $k$ and $h$ with the following condition
     82 \begin{align}
     83     \frac{1 - (k-1)^{1-h}}{k-2} > 1,
     84 \end{align}
     85 the number of inner nodes exceeds the number of leaves.
     86 
     87 Furthermore The diameter of a Cayley tree in terms of the number of nodes is
     88 \begin{align}
     89     d_{max} = 2\cdot h = 2\cdot \log_{k-1}\left(\frac{(N-1) (k-2)
     90         k}{k}\right).
     91 \end{align}
     92 And the clustering coefficient $C$ is obviously
     93 \begin{align}
     94     C = 0.
     95 \end{align}
     96 \section{Erdős–Rényi (NR) Network}
     97 Now we look at NR networks, which are random graphs denoted by $G(N, p)$ of $N=5000$
     98 Nodes with a connection probability of $p=0.002$ for a node. The expected
     99 number of edges $\langle L \rangle$ is
    100 \begin{align}
    101     \langle L \rangle  =p \begin{bmatrix} N \\ 2 \end{bmatrix} = 24995,
    102 \end{align}
    103 the average number of degrees $\rangle k \rangle$is
    104 \begin{align}
    105     \langle k \rangle = p \cdot (N-1) = 9.998.
    106 \end{align}
    107 The network is in the regime of ``super connected'' and its critical value of
    108 $p=p_c$ can be calculated by considering
    109 \begin{align}
    110     \langle k \rangle = 1 = p_c (N - 1) \;\;\;
    111     \Rightarrow \;\;\; p \simeq 0.0002.
    112 \end{align}
    113 The expected size of the giant component is in the range of $1$, of a
    114 ``connected'' graph.
    115 
    116 For a network of $N=100$ and $\langle k \rangle = 5$ we would have
    117 \begin{align}
    118     p = 0.04
    119 \end{align}
    120 For a network of $N=1000$ and $\langle k \rangle = 20$ we would have
    121 \begin{align}
    122     p = 0.02
    123 \end{align}
    124 \section{Coding Exercises}
    125 See jupyter notebook or \cite{code}
    126 
    127 \nocite{code}
    128 \printbibliography
    129 
    130 \end{document}