\chapter{Node degree statistics}

\section{Introduction}
In a graph, the degree $k$ of a node is the number of edges connected to this node.
If the graph is directed, we can make a distinction between the in-degree 
(the number input arcs) and the out-degree (number of output arcs). In this case, the degree of the 
node consists in the sum of the in-degree and of the out-degree of this node.

Different nodes having different degrees, this variability
is characterized by the degree distribution function $P(k)$,
which gives the probability that a node has exactly $k$ edges,
or, in other words gives the observed frequency of a node
of degree $k$.

Scale-free graphs were first described by Barabasi 
based on the study of the web connectivity, followed
by several different biological networks \cite{Jeong2000}.

A graph is scale-free if the distribution of the vertex degree ($k$) follows a power-law distribution of
the form $P(k) ~ k^{-\gamma}$.

The main property of such graphs is that it should have on one hand some highly connected nodes, called hubs, which are central to the network topology, and \textit{keep the network together} and on the other hand a lot of poorly connected nodes linked to the hubs.

In the following, we will check if this scale free property also applies to the two-hybrid network described by Uetz \textit{et al} \cite{Uetz:2000} by computing the degree of each node and plotting the node degree distribution of the graph.
\section{Analysis of the node degree distribution of a biological network}
\subsection{Study case}

In this demonstration, we will analyze the node degree distribution of 
the first published yeast protein interaction network. This network is the first
attemp to study the yeast interactome using the two-hybrid method  and contains 865 interactions between 926
proteins \cite{Uetz:2000}.

\subsection{Protocol for the web server}

\begin{enumerate}

\item In the \neat menu, select the command \program{node topology statistics}. 

  In the right panel, you should now see a form entitled
  ``graph-topology''.

\item Click on the button \option{DEMO}. 

  The form is now filled with a graph in the tab-delimited format, and the parameters have been
  set up to their appropriate value for the demonstration, i.e., the degree of all nodes will be computed. 
  At the top of the form, you can read some information about the goal of the
  demo, and the source of the data.
  
  As this is a protein - protein interaction graph, we can consider that an interaction between a protein A with a 
  protein B corresponds to an interaction between protein B and protein A. The graph is thus not directed. 
  
  You can uncheck the compution of the closeness and betweenness as these statistics will not be discussed in this section and as this process will increase the computation time.

\item Click on the button \option{GO}. 

  The computation should take less than one minute. 
  On one hand, the result page displays a link to the result file and on the other hand the graphics and raw data of the node degree distribution are also available. These will be discussed in the \textit{Interpretation of the results} section.

\end{enumerate}

\subsection{Protocol for the command-line tools}

If you have installed a stand-alone version of the NeAT distribution,
you can use the program \program{graph-topology} on the
command-line. This requires to be familiar with the Unix shell
interface. If you don't have the stand-alone tools, you can skip this
section and read the next section (Interpretation of the results).

We will now describe the use of \program{graph-topology} as a command line tool. 
The two two-hybrid dataset described
in the previous section may be downloaded at the following address \url{http://rsat.ulb.ac.be/rsat/data/neat\_tuto\_data/}. 
This is the file \file{uetz\_2001.tab}.

\begin{enumerate}

\item The first step consist in applying \program{graph-topology} on the two-hybrid dataset. To this, go into the
directory where you downloaded the file \file{uetz\_2001.tab} and use this command. 
	
\begin{lstlisting}
graph-topology -v 1 -i uetz_2001.tab -return degree -all \
   -o uetz_2001_degrees.tab
\end{lstlisting}The file \file{uetz\_2001\_degrees.tab} is created and contains the degree of each node of the Uetz \textit{et al} data set.

\item In the second step, we will study the degree distribution of the
  nodes. To this, we use the program \program{classfreq} from the RSAT
  suite that compute the distribution of a set of number. As the graph
  we are working with is undirected, we will only compute this degree
  distribution for the global degree of the nodes which is the second
  column of the file \file{uetz\_2001\_degrees.tab} obtained in the
  previous step.
	
\begin{lstlisting}
classfreq -i uetz_2001_degrees.tab -v 1 -col 2 -ci 1 \
   -o uetz_2001_degrees_freq.tab
\end{lstlisting}

\item Finally, we will display the distribution graph in the PNG
  format in order to visualize the degree distribution and determine
  if it has a scale free behaviour. The program XYgraph from \RSAT
  will be used for this purpose. Note that we could use other tools
  like \program{Microsoft Excel} or \program{R}. The results will be
  stored in the file \file{uetz\_2001\_degrees\_freq.png} that you can
  open with any visualization tool.

\begin{lstlisting}
XYgraph -i uetz_2001_degrees_freq.tab \
   -title 'Global node degree distribution (interaction graph: Uetz 2001)' \
   -xcol 2 -ycol 4,6 -xleg1 Degree -lines \
   -yleg1 'Number of nodes' -legend -header -format png \
   -o uetz_2001_degrees_freq.png
\end{lstlisting}

\end{enumerate}

\subsection{Interpretation of the results}

\subsubsection{graph-topology result file}

Open the resulting file produced by \program{graph-topology}.
According to the requested level of verbosity (\option{-v \#} option),
the file begins with some lines starting with the '\#' or ';' symbols
that contains some information about the graph and the description of
the columns.

The results consists in a two columns data set.
\begin{enumerate}
 \item Node name
 \item Global degree
\end{enumerate}

Note that if you used the '-directed' option, the resulting file
contains 3 more columns specifying the in-degree, the out-degree and
whether the node is only a source node or a target node.

\subsubsection{Node degree distribution}

Let us first have a look at the node degree distribution data file
produced by the \program{classfreq} program (raw data).  This file is
a tab-delimited file containing 9 columns. Each line consists in a
value interval. In our case, the value is the degree of the nodes.

\begin{enumerate}
 \item Minimal value of the interval
 \item Maximal value of the interval
 \item Central value of the interval
 \item Frequency : Number of elements in this class interval (number
   of nodes having a degree comprised betwee the minimal and the
   maximal values.
 \item Cumulative frequency.
 \item Inverse cumulative frequency
 \item Relative frequency : number of elements in this class over the
   total number of elements
 \item Relative cumulative frequency
 \item Inverse relative cumulative frequency
\end{enumerate}

The first result line contains the distribution results for the nodes
having only one neighbour (i.e. degree comprised between 1 and 2),
from it we can see that 577 over 926, i.e., 62\% of the nodes have a
degree of one.  Moreover, about 90\% of the nodes have a degree lower
than 4. This is indicative of the scale-free nature of the interaction
network.

The figure best illustrates the scale-freeness of the graph.  When
looking at the graphical representation of this distribution, we can
see two curves.  The blue curve represents the absolute frequency and
the green curve the inverse cumulative frequency.  The exponential
decrease of both curves shows that there are a lot more nodes poorly
connected than highly connected (hubs). The Uetz graph thus presents a
scale free behaviour.
