network_ana

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

main.tex (4075B)

      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 \newtheorem{definition}[section]{Definition}
     42 
     43 
     44 \usepackage{tcolorbox}
     45 \tcbuselibrary{skins,breakable}
     46 
     47 \pagestyle{myheadings}
     48 
     49 \markright{Popović\hfill 6-th Exercise \hfill}
     50 
     51 
     52 \title{University of Vienna\\ Faculty of Mathematics\\
     53     \vspace{1.25cm}Seminar: Introduction to complex network analysis \\ 6-th
     54 Exercise
     55 }
     56 \author{Milutin Popović}
     57 \begin{document}
     58 \maketitle
     59 
     60 \section{Exercise 6}
     61 \subsection{Consider a Barabasi-Albert}
     62 We consider a Barabasi-Albert model with a preferential attachment given by
     63 \begin{align}
     64     \Pi(k_i) = \frac{1}{m_0 + t - 1}.
     65 \end{align}
     66 With the following differential equation
     67 \begin{align}
     68     \frac{\partial k_i}{\partial t} = m \Pi(k_i) \;\;\;\; k_i(t_i) = m
     69 \end{align}
     70 we can solve for the degree dynamics. By simply integrating we get
     71 \begin{align}
     72     k_i(t) &= \int \frac{m}{m_0 +t -1}dt \nonumber\\
     73         &=m\ln(m_0 + t - 1) + c.
     74 \end{align}
     75 With the initial condition $k_i(t_i) = m$ we get the degree dynamics
     76 \begin{align}
     77     k_i(t) = m \ln(e\cdot\frac{m_0 + t - 1}{m_0 + t_i - 1}).
     78 \end{align}
     79 To calculate the degree distribution, we look at nodes with degree $k_i < k$,
     80 which by substitution is essentially
     81 \begin{align}
     82     t_i > e^{-\frac{k}{m}}e\cdot (m+t-1) -m_0 + 1.
     83 \end{align}
     84 Meaning that every node that entered after time $t_i$ has degree smaller than
     85 $k$. There are exactly $t_i - t$ such nodes, thus the probability to find
     86 such node is
     87 \begin{align}
     88     P(k) = 1 - e^{-\frac{k}{m}}e\cdot (m+t-1) +m_0 - 1.
     89 \end{align}
     90 By differentiating with respect to $k$ we get the degree distribution
     91 \begin{align}
     92     p(k) = \frac{\partial P(k_i<k)}{\partial k} =
     93     \frac{e}{m}e^{-\frac{m}{k}}(m_0 + t -1)
     94 \end{align}
     95 For $t \gg m_0$ we get
     96 \begin{align}
     97     p(k) = \frac{e}{m} e^{-\frac{e}{m}}.
     98 \end{align}
     99 \subsection{Betweeness- and Closeness Centrality}
    100 \begin{definition}
    101     The betweenness centrality of a node $k$ is given by
    102     \begin{align}
    103         g(k) = \sum_{i \neq j \neq k}
    104         \frac{\sigma_{k_ik_j}(k)}{\sigma_{k_ik_j}},
    105     \end{align}
    106     where $\sigma_{k_ik_j}$ is the number of shortest paths from node $k_i$ to
    107     node $k_j$, and $\sigma_{k_i k_j}(k)$ is the number of shortest paths
    108     from node $k_i$ to node $k_j$ that pass through node $k$.
    109 \end{definition}
    110 Betweenness centrality of a node $k$, basically describes how good the node
    111 is connected in term of shortest paths. The maximum of this function would
    112 give us a node that is especially well connected by shortest paths to most of
    113 the nodes in the network.
    114 
    115 \begin{definition}
    116     The closeness centrality $C(k)$ of a node $k$ in a connected graph with
    117     $N$ number of nodes is given by
    118     \begin{align}
    119         C(k) = \frac{N - 1}{\sum_{i} d(k_i, k)},
    120     \end{align}
    121     where $d(k_i, k)$ is the shortest distance from node $k_i$ to node $k$.
    122 \end{definition}
    123 Closeness centrality of a node $k$, resembles how well closed up with respect
    124 to a node $k$ a network is. With this function we can find nodes that are
    125 close to other nodes, i.e. how efficient a given node is.
    126 
    127 
    128 
    129 
    130 \nocite{code}
    131 \nocite{barabasi2016network}
    132 \printbibliography
    133 
    134 \end{document}