dn3

dn3.tex

\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage[utf8x]{inputenc}   % omogoča uporabo slovenskih črk kodiranih v formatu UTF-8 
\usepackage[slovene,english]{babel}    % naloži, med drugim, slovenske delilne vzorce
\usepackage[pdftex]{graphicx}  % omogoča vlaganje slik različnih formatov 
\usepackage{fancyhdr}          % poskrbi, na primer, za glave strani
\usepackage{amssymb}           % dodatni simboli
\usepackage{amsmath}           % eqref, npr.
\usepackage{listings} %code
\usepackage{color} %code color
\usepackage[pdftex,colorlinks,citecolor=black,filecolor=black,linkcolor=black,urlcolor=black,pagebackref]{hyperref}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\lstset{
 frame=tb,
  language=Python,
  aboveskip=3pt,
  belowskip=3pt,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=left,
  stepnumber=1,    
  firstnumber=1,
  numberfirstline=true,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace = true,
numbersep=4pt,
framexleftmargin=10pt,
framesep= 2pt,
frame=shadowbox,
linewidth = 18cm,
tabsize=2,
xleftmargin=20pt,
rulesepcolor=\color{gray},
captionpos = b,
float=htpb
}
\renewcommand{\lstlistingname}{Koda}

\begin{document}
\selectlanguage{slovene}
\thispagestyle{empty}
\parindent 0pt
\vfill
\large

\begin{center}
\LARGE{\bf \textsf{CS224w:\\Social and Information Network Analysis} \\*[4ex]
\Large{
Assignment number:\hrulefill \\
Submission time: \hrulefill \quad and date:}} \today
\end{center}

\vfill

Fill in and include this cover sheet with each of your assignments. It is an honor code violation to write down the wrong time. Assignments are due at 9:30 am, either handed in at the beginning of class or left in the submission box on the $1^{st}$ floor of the Gates building, near the east entrance.

Each student will have a total of {\em two} free late periods. {\em One late period expires at the start of each class.} (Homeworks are usually due on Thursdays, which means the first late periods expires on the following Tuesday at 9:30am.) Once these late periods are exhausted, any assignments turned in late will be penalized 50\% per late period. However, no assignment will be accepted more than {\em one} late period after its due date. 

\vfill
\vfill

{\Large
\textbf{Your name:} Tomaž Tomažič \\
\textbf{Email: } [email protected]  \underline{\hspace*{5cm}} \textbf{SUID: } 63100281 \\*[2ex] }
Collaborators:\hrulefill
\vfill

\vfill

I acknowledge and accept the Honor Code.\\*[3ex]
\bigskip
\textit{(Signed)}\hrulefill

\vfill
\vfill

\begin{center}
\normalsize{(For CS224w staff only)\\
\bigskip
Late periods:\quad 1 \quad 2}
\end{center}


\begin{center}
\linespread{1.3}
\large
\begin{tabular}{|c|r|}\hline
Section & \hspace*{1.5cm} Score \\ \hline \hline
1 &  \\ \hline
2 &  \\ \hline
3 &  \\ \hline
4 &  \\ \hline
5 &  \\ \hline
6 &  \\ \hline
\hline
Total & \hspace*{2.5cm} \\ \hline
\end{tabular}
\end{center}
Comments:


\clearpage
% ---- 1
\section{}
\subsection{}
Greedy vzame najprej C in nato A ali B, otpimalna rešitev pa najprej A in nato B
Torej: 
$$S = {C,A}$$ 
$$T = {A,B}$$
\begin{figure}[ht!] \includegraphics[width=8cm]{1_a.png} \end{figure}

\subsection{}
V vsaki podmnožici je napisno število vozlišč, prav tako vsaka točka (A, B, C, D) predstavlja eno vozlišče.
Greedy v prvem koraku zavzame množico B, v drugem C in tretjem D, skupaj je {\tt27 + 17 + 17 = 61 } vozlišč. Optimalna rešitev zavzame najprej C, v drugem koraku D in nato A, skupaj je {\tt26 + 26 + 25 = 77}. Razmerje je {\tt61 / 77 = 0.79}
Torej: 
$$S = {B,C,D}$$
$$T = {C,D,A}$$
\begin{figure}[ht!] \includegraphics[width=5cm]{1_b.png} \end{figure}

\subsection{}
Da nimamo prekrivanja množic vozlišč ki jih lahko dosežemo iz enega vozlišča. Torej da so vse množice disjunktne. S tem bo greedy vedno dobil optimalno rešitev.

% ------2
\section{}
\subsection{} 
\begin{figure}[ht!] \includegraphics[width=10cm]{2_a.png} \end{figure}

\subsection{}
\begin{figure}[ht!] \includegraphics[width=7cm]{2_b.png} \end{figure}
Števila ki so nič sem izpustil, ker nam nič ne koristijo in tudi ni mogoče izračunati logaritma na njih.

\subsection{}
Vrednost $$alfa = 1.75005091611$$ Da vrednost lahko izboljšamo tako da spustimo zadnje vrednosti zaradi šuma. Z izpustitvijo zadnjih 200 vrednosti je $$alfa = 1.92909446334$$

\subsection{}
Za ccdf dobim vrednost $$alfa = 1.98046552757$$.

\subsection{}
Za maximum likelihood dobim vrednost $$alfa = 1.99534706416$$.

\subsection{}
Povprčje z metodo najmanjših kvadratov = 1.75260296727\\
Povprčje z metodo najmanjših kvadratov z izboljšavo = 1.95006880974\\
Povprčje z metodo najmanjših kvadratov na CCDF = 1.98024192594\\
Povprčje z metodo maximum likelihood = 1.99970206459\\

Varianca z metodo najmanjših kvadratov = 0.000226329788224 \\
Varianca z metodo najmanjših kvadratov z izboljšavo = 0.000227850071148 \\
Varianca z metodo najmanjših kvadratov na CCDF = 1.00788544783e-06 \\
Varianca z metodo maximum likelihood = 8.20621792111e-06 \\

% --- 3
\section{}
\subsection{} 

\begin{figure}[ht!] \includegraphics[width=7cm]{3_1donquijote_txta.png} \caption{donquijote} \end{figure}
\begin{figure}[ht!] \includegraphics[width=7cm]{3_1mobydick_txta.png} \caption{moby dick} \end{figure}

\subsection{}
\subsection{}

Različnih besed je $$m^y$$
$$a = ln(m)$$
\subsection{}
$$((1-q)/m)^y * q$$
$$(1-q)/m = e^{log((1-q)/m))}$$
$$b = ln ((1-q)/m)$$
% ----4
\section{}
\subsection{}
Z zeleno je označeno naključen graf. Z rumeno avtonomni sistem. Z rdečo pa PA.
Vidimo da lahko z napadom v vseh primerih prej uničimo omrežje kot pa z naključnim izpadom.
Avtonomni sistemi so najbolj občutljivi na napade, naključni pa najmanj.
V drugi sliki ko brišemo manj vozlišč že lahko opazimo da je naključno omrežje enako odporno na napade kot na izpade, v primeru avtonomnega sistema ali pa PA pa sta sistema bolj odporna na izpade in manj na napade.
\begin{figure}[ht!] \includegraphics[width=10cm]{4_1a.png} \caption{y=50} \end{figure}
\\\\\\\\\\\\\\\\\\\\\\
\begin{figure}[ht!] \includegraphics[width=10cm]{4_1b.png} \caption{y=2} \end{figure}

\subsection{}
Vidimo lahko da so naključna omrežja veliko bolj robustna ker so bolj odporna na napade, saj ne razpadejo tako hitro kot avtonomni sistemi.

\begin{figure}[ht!] \includegraphics[width=10cm]{4_2a.png} \caption{y=50} \end{figure}

\begin{figure}[ht!] \includegraphics[width=10cm]{4_2b.png} \caption{y=2} \end{figure}

\section{Koda:}
\begin{lstlisting}[caption = {2.3}]
#2
import snap
import random
import matplotlib.pyplot as plot
import collections
import numpy
import math

def max_likelihood(y, x_min):
    lst = [ math.log(x / float(x_min)) for x in y]
    return 1 + len(y) * (sum(lst) ** -1)

def method(isPlot=False):
  random_numbers = sorted([ 1/(1-random.random()) for _ in range(100000) ])
  r_dict = collections.defaultdict(lambda: 0)

  r = sorted([ round(i) for i in random_numbers if round(i)>0])

  probability = 0
  hist = []
  for i in r:
    r_dict[ i ] += 1.0/100000

  for i in sorted(r_dict.keys()):
    probability += r_dict[ i ]
    hist.append(probability)


  y = [ i**( -2.0 ) for i in random_numbers ]

  if isPlot:
    fig = plot.figure()
    ax = fig.add_subplot(111)

    ax.plot( r_dict.keys(), r_dict.values(), 'go')
    ax.plot( random_numbers, y, 'r-')
    ax.set_yscale('log')
    ax.set_xscale('log')
    plot.savefig("2.b.png")

  #2.C
  #a =  vrednost
  #b = ponovitev
  a = []
  b = []
  for i in random_numbers:
    a.append(math.log(round(i)))
    b.append(math.log(round(i)))

  X = numpy.vstack([numpy.log(r_dict.keys()).T, numpy.array(r_dict.values()).T]).T
  c2=  numpy.linalg.lstsq(X, numpy.log(r_dict.values()).T)[0][0] * -1

  #imporved

  X = numpy.vstack([numpy.log(r_dict.keys()[5:-200]).T, numpy.array(r_dict.values()[5:-200]).T]).T
  c2impr = numpy.linalg.lstsq(X, numpy.log(r_dict.values()[5:-200]).T)[0][0] * -1

  hist.reverse()
  #2.d
  X = numpy.vstack([numpy.log(sorted(r_dict.keys())).T, numpy.array(hist).T]).T
  d2 =  1+1- numpy.linalg.lstsq(X, numpy.log(hist).T)[0][0] * -1


  e2 = max_likelihood(random_numbers,1)

  return (c2,c2impr,d2,e2)

c2 = []
c2impr = []
d2 = []
e2 = []
for _ in range(100):
  (c20,c2impr0,d20,e20)=method()
  c2.append(c20)
  c2impr.append(c2impr0)
  d2.append(d20)
  e2.append(e20)
  
avg1 = numpy.average( c2 )
avg2 = numpy.average( c2impr )
avg3 = numpy.average( d2 )
avg4 = numpy.average( e2 )

var1 = numpy.var( c2 )
var2 = numpy.var( c2impr )
var3 = numpy.var( d2 )
var4 = numpy.var( e2 )

print avg1, avg2, avg3, avg4, var1, var2, var3, var4
#3
from snap import *
import random
import collections
import os
import matplotlib.pyplot as plot
import math

def max_likelihood(y, x_min):
    lst = [ math.log(x / float(x_min)) for x in y]
    return 1 + len(y) * (sum(lst) ** -1)

def plot_file(file_name):
  words = open(file_name).readlines()
  in_dict = collections.Counter( words )
  allwords = len(words)*1.0

  distinctwords = len(set(words))*1.0

  x = [] 
  y = []
  d = collections.defaultdict(lambda: 0)

  for i in in_dict.itervalues():
    d[i] += i
  
  for i in in_dict.itervalues():
    x.append( i )
    y.append( d[i]/ distinctwords )


  x = [] 
  y = []
  z = []
  for i in in_dict.iterkeys():
    x.append(in_dict[i]/allwords)
    y.append( d[in_dict[i]] )
    z.append( in_dict[i]/allwords*1.15 )


  alfa =  max_likelihood(y, 10)

  fig = plot.figure()
  ax = fig.add_subplot(111)
  ax.plot( x, y, 'y+')
  ax.plot( z, y, 'g+')
  ax.set_yscale('log')
  ax.set_xscale('log')
  plot.savefig("3.1%sa.png" %(file_name))



plot_file('mobydick.txt')
plot_file('donquijote.txt')
#4
from snap import *
import random
import matplotlib.pyplot as plot
import collections

n = 10670
m = 22002
#generate Graphs
# generate GNM
def generate():
  Gnm = TUNGraph.New()

  for i in range(n):
    Gnm.AddNode(i)
  for _ in range(m):
    Gnm.AddEdge( random.randint(0, n-1), random.randint(0, n-1))

  SaveEdgeList(Gnm, 'Gnm.txt')

  #######
  # load AS
  Gas = LoadEdgeList(PUNGraph, "oregon.txt", 0, 1)
  SaveEdgeList(Gas, 'Gas.txt')
  #generate PA
  Gpa = TUNGraph.New()
  #nodes
  for i in range(n):
    Gpa.AddNode(i)
  #complete graph
  edges = []
  for i in range(40):
    for j in range(i+1, 40):
      Gpa.AddEdge(i,j)
      edges.append((i,j))
  #2 edges
  for i in range(40, n):
    j = random.randint(0, len(edges)-1)
    r = int(round(random.random()))
    Gpa.AddEdge(i, edges[j][r])
    edges.append((i, edges[j][r]))

    j = random.randint(0, len(edges)-1)
    r = int(round(random.random()))
    Gpa.AddEdge(i, edges[j][r])
    edges.append((i, edges[j][r]))


  print len([i.GetId() for i in Gpa.Edges()]), "edgov mora bit okol 22000",  len([i.GetId() for i in Gpa.Nodes()])
  SaveEdgeList(Gpa, 'Gpa.txt')
############
# generate()
Gas = 0
Gnm = 0
Gpa = 0
def refresh():
  global Gas
  global Gnm
  global Gpa
  Gas = LoadEdgeList(PUNGraph, "Gas.txt", 0, 1)
  Gnm = LoadEdgeList(PUNGraph, "Gnm.txt", 0, 1)
  Gpa = LoadEdgeList(PUNGraph, "Gpa.txt", 0, 1)

def delete_failure(G, del_frac, untill):
  Glst = [i.GetId() for i in G.Nodes()]
  length = len(Glst)
  length_without_deleted = length
  delete_step = length/del_frac
  i = 0.0
  diam = []
  step = []
  wcc = []
  while( (length - length_without_deleted) / float(length) < untill ):
    i += 1
    for _ in range(delete_step):
      rnd = random.randint(0, length-1)
      while (Glst[rnd]) == -1 :
        rnd = random.randint(0, length-1)
      G.DelNode( Glst[rnd] )
      Glst[rnd] = -1
      length_without_deleted -= 1

    diam.append( GetBfsFullDiam(G, 20, False))
    step.append( delete_step*i/length )
    wcc.append(GetMxWccSz(G))

  return diam, step, wcc

def delete_attack(G, del_frac, untill):
  Glst = [i.GetId() for i in G.Nodes()]
  length = len(Glst)
  length_without_deleted = length
  delete_step = length/del_frac
  i = 0.0
  diam = []
  step = []
  wcc = []
  while( (length - length_without_deleted) / float(length) < untill ):
    i += 1
    for _ in range(delete_step):
      G.DelNode( GetMxDegNId(G) )
      length_without_deleted -= 1

    diam.append( GetBfsFullDiam(G, 20, False))
    step.append( delete_step*i/length )
    wcc.append(GetMxWccSz(G))
  
  return diam, step, wcc

refresh()
(failure_Gas_diam0, failure_Gas_step0, failure_Gas_wcc0) = delete_failure(Gas, 100, 50.0/100)
(failure_Gnm_diam0, failure_Gnm_step0, failure_Gnm_wcc0) = delete_failure(Gnm, 100, 50.0/100)
(failure_Gpa_diam0, failure_Gpa_step0, failure_Gpa_wcc0) = delete_failure(Gpa, 100, 50.0/100)
refresh()
(attack_Gas_diam0, attack_Gas_step0, attack_Gas_wcc0) = delete_attack(Gas, 100, 50.0/100)
(attack_Gnm_diam0, attack_Gnm_step0, attack_Gnm_wcc0) = delete_attack(Gnm, 100, 50.0/100)
(attack_Gpa_diam0, attack_Gpa_step0, attack_Gpa_wcc0) = delete_attack(Gpa, 100, 50.0/100)

refresh()
(failure_Gas_diam1, failure_Gas_step1, failure_Gas_wcc1) = delete_failure(Gas, 1000, 2.0/100)
(failure_Gnm_diam1, failure_Gnm_step1, failure_Gnm_wcc1) = delete_failure(Gnm, 1000, 2.0/100)
(failure_Gpa_diam1, failure_Gpa_step1, failure_Gpa_wcc1) = delete_failure(Gpa, 1000, 2.0/100)
refresh()
(attack_Gas_diam1, attack_Gas_step1, attack_Gas_wcc1) = delete_attack(Gas, 1000, 2.0/100)
(attack_Gnm_diam1, attack_Gnm_step1, attack_Gnm_wcc1) = delete_attack(Gnm, 1000, 2.0/100)
(attack_Gpa_diam1, attack_Gpa_step1, attack_Gpa_wcc1) = delete_attack(Gpa, 1000, 2.0/100)


fig = plot.figure()
ax = fig.add_subplot(111)
ax.plot( failure_Gas_step0, failure_Gas_diam0,  'y+-')
ax.plot( failure_Gnm_step0, failure_Gnm_diam0,  'g+-')
ax.plot( failure_Gpa_step0, failure_Gpa_diam0,  'r+-')
ax.plot( attack_Gas_step0, attack_Gas_diam0,  'y.-')
ax.plot( attack_Gnm_step0, attack_Gnm_diam0,  'g.-')
ax.plot( attack_Gpa_step0, attack_Gpa_diam0,  'r.-')
plot.savefig("4.1a.png")

fig = plot.figure()
ax = fig.add_subplot(111)
ax.plot( failure_Gas_step1, failure_Gas_diam1, 'y+-')
ax.plot( failure_Gnm_step1, failure_Gnm_diam1, 'g+-')
ax.plot( failure_Gpa_step1, failure_Gpa_diam1, 'r+-')
ax.plot( attack_Gas_step1, attack_Gas_diam1, 'y.-')
ax.plot( attack_Gnm_step1, attack_Gnm_diam1, 'g.-')
ax.plot( attack_Gpa_step1, attack_Gpa_diam1, 'r.-')
plot.savefig("4.1b.png")

#4.2
fig = plot.figure()
ax = fig.add_subplot(111)
ax.plot( failure_Gas_step0, failure_Gas_wcc0,   'y+-')
ax.plot( failure_Gnm_step0, failure_Gnm_wcc0,   'g+-')
ax.plot( failure_Gpa_step0, failure_Gpa_wcc0, 'r+-')
ax.plot( attack_Gas_step0, attack_Gas_wcc0,   'y.-')
ax.plot( attack_Gnm_step0, attack_Gnm_wcc0,   'g.-')
ax.plot( attack_Gpa_step0, attack_Gpa_wcc0,   'r.-')
plot.savefig("4.2a.png")

fig = plot.figure()
ax = fig.add_subplot(111)
ax.plot( failure_Gas_step1, failure_Gas_wcc1,   'y+-')
ax.plot( failure_Gnm_step1, failure_Gnm_wcc1,   'g+-')
ax.plot( failure_Gpa_step1, failure_Gpa_wcc1,   'r+-')
ax.plot( attack_Gas_step1, attack_Gas_wcc1,   'y.-')
ax.plot( attack_Gnm_step1, attack_Gnm_wcc1,   'g.-')
ax.plot( attack_Gpa_step1, attack_Gpa_wcc1,   'r.-')
plot.savefig("4.2b.png")


\end{lstlisting}
\end{document}