network_ana

main.tex (5711B)

---

 \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 \\ 1st
 Exercise
 }
 \author{Milutin Popovic}
 \date{19. October, 2021}
 
 \begin{document}
 \maketitle
 
 \textbf{Exercise 1:} Discuss briefly advantages and disadvantages of
 representing a network by
     \begin{enumerate}
         \item an edge list
         \item an adjacency matrix.
     \end{enumerate}
 
 \textbf{Solution 1.1 Edge-list:} Advantages: Allows for compact representation of graphs (sparse
     structure) to save a lot of Memory, deleting/adding connections/nodes is easier than
     with a matrix representation.
 \newline
 Disadvantages: Might be slower to find out if a vertex/connection exists,
 since matrix lookup time is constant.
 
 \textbf{Solution 1.2 Adjacency Matrix:} Advantages: Constant lookup time. Easier to
 change the entries of the matrix, thus modifying the network.
 \newline
 Disadvantages: Slow for iteration.
 \newline
 
 \textbf{Exercise 2:} Imagine that your social network has a subnetwork where 14 of your friends
 together with you are all friends with each other. What is such a subnetwork
 called? How many edges are contained in the subnetwork?
 
 \textbf{Solution 2} 14 friends + 1 (me) = 15 people are all connected, such a
 graph is called a complete graph, the number of vertices is given by
 \begin{align}
     L_{\text{max}} = \begin{pmatrix}15 \\ 2\end{pmatrix} = \frac{15(15-1)}{2}
     = 105.
 \end{align}
 \newline
 
 \textbf{Exercise 3:}
 \begin{figure}[h!] \centering
 \begin{tikzpicture}[
     dot/.style = {draw, circle, inner sep=0.02cm, thick},
     no/.style = {},
     ]
     \node[dot](1) at (0,0) [] {1};
     \node[dot](2) at (1,0) [] {2};
     \node[dot](3) at (1,-1) [] {3};
     \node[dot](4) at (1,1) [] {4};
     \node[dot](5) at (2,0) [] {5};
     \node[dot](6) at (2,-1) [] {6};
     \node[dot](7) at (3,0) [] {7};
     \node[dot](8) at (4,1) [] {8};
     \node[dot](9) at (4,-1) [] {9};
     \node[dot](10) at (6, 0.5) [] {10};
 
     \draw[-, thick]  (1) -- (2) -- (4);
     \draw[-, thick]  (2) -- (3) -- (6);
     \draw[-, thick]  (2) -- (5);
     \draw[-, thick]  (6) -- (5) -- (7) -- (8);
     \draw[-, thick]  (7) -- (9) -- (8);
     \end{tikzpicture}
     \caption{The graph from exercise 3}
 \end{figure}
 Consider the network above and
 \begin{itemize}
     \item Write down the adjacency matrix,
     \item Write down the edge list.
     \item Draw the degree distribution by hand.
     \item Calculate the clustering coefficient, diameter and density.
     \item Find the number of d=3 paths between 2 and 3. (you may use a computer)
 \end{itemize}
 
 \textbf{Solution 3:} The adjacency matrix is a $10x10$ matrix it can be
 viewed in the `.ipynb' file. The edge - list is the following
 \begin{align}
     &(1, 2), \;\; (2 ,3), \;\; (2, 4), \;\; (2, 5), \;\; (3, 6), \;\; \nonumber\\
     &(5, 6), \;\; (5, 7), \;\; (7, 8), \;\; (7, 9), \;\; ( 8, 9).
 \end{align}
 For the clustering coefficient we obviously need to only consider node 7, 8
 and 9, because no other neighbors for a given node are connected, thus we
 have
 \begin{align}
     \langle C \rangle = \frac{1}{N}\sum_i^10 C_i = \frac{1}{10} (\frac{1}{3}
     +2) = \frac{7}{30}.
 \end{align}
 The diameter $d_{\text{max}}$ is given by the length of the longest path
 which is
 \begin{align}
     d_{\text{max}} = d_{1, 8} = d_{1, 9} = 4.
 \end{align}
 And finally for the graph density $\varrho$ we have number of vertices
 divided by number of vertices of the complete graph
 \begin{align}
     \varrho = \frac{L}{\begin{pmatrix}L_{\text{max}} \\ 2\end{pmatrix}} =
     \frac{2}{9}.
 \end{align}
 The number of $d=3$ paths between the nodes 2 and 3 are
 \begin{align}
     P_{2, 3} = \{(2, 5), (5, 6) , (6, 3)\},
 \end{align}
 exactly one. For part (f) look at '.ipynb'.
 \newline
 
 \textbf{Exercise 4:} Consider a bipartite network with N1 and N2 nodes in the
 two sets.
 \begin{enumerate}
     \item What is the maximum number of edges the network can have?
     \item How many edges cannot occur compared with a non-bipartite network of size
 \end{enumerate}
 
 \textbf{Solution 4:} The maximum number of connection is when every node in
 one network is connected to every node in the other network, meaning
 \begin{align}
     \underbrace{N_2 + N_2 + \cdots + N_2}_{N_1 \textbf{-times}} = N_1 \cdot
     N_2.
 \end{align}
 The number of edges that cannot occur in compared to a normal network of size
 $N = N_1 + N_2$ is
 \begin{align}
     \begin{pmatrix}N \\ 2 \end{pmatrix} - N_1N_2 &= \frac{(N_1 + N_2)(N_1+N_2
     -1)}{2} - N_1N_2 =\\ &= \frac{1}{2} ( N_1^2 + N_2^2) - (N_1 + N_2).
 \end{align}
 
 \nocite{code}
 \printbibliography
 
 \end{document}