diff options
Diffstat (limited to 'doc/latex/latex/structure/correlations')
10 files changed, 388 insertions, 0 deletions
diff --git a/doc/latex/latex/structure/correlations/compute_pearson.tex b/doc/latex/latex/structure/correlations/compute_pearson.tex new file mode 100644 index 0000000..8202753 --- /dev/null +++ b/doc/latex/latex/structure/correlations/compute_pearson.tex @@ -0,0 +1,28 @@ +\myprogram{{compute\_pearson.py}} + {compute the Pearson's linear correlation coefficient + between two node properties.} + {$<$file1$>$ $<$file2$>$} + +\mydescription{Compute the Pearson's linear correlation coefficient + between two sets of (either integer- or real-valued) node + properties provided in the input files \textit{file1} + and \textit{file2}. Each input file contains a list of + lines, where the n-th line contains the value of a node + property for the n-th node. For instance, \textit{file1} + and \textit{file2} might contain the degrees of nodes at two + distinct layers of a multiplex. However, the program is + pretty general and can be used to compute the Pearson's + correlation coeffcient between any pairs of node properties. + } + +\myreturn{The program prints on \texttt{stdout} the value of the + Pearson's linear correlation coefficient between the two + sets of node properties. +} + +\myreference{\refcorrelations + + \refgrowth + + \refnonlinear +} diff --git a/doc/latex/latex/structure/correlations/compute_rho.tex b/doc/latex/latex/structure/correlations/compute_rho.tex new file mode 100644 index 0000000..957b04c --- /dev/null +++ b/doc/latex/latex/structure/correlations/compute_rho.tex @@ -0,0 +1,32 @@ +\myprogram{{compute\_rho.py}} + {compute the Spearman's rank correlation coefficient $\rho$ + between two rankings.} {$<$file1$>$ $<$file2$>$} + +\mydescription{Compute the Spearman's rank correlation coefficient + $\rho$ between two rankings provided in the input + files \textit{file1} and \textit{file2}. Each input file + contains a list of lines, where the n-th line contains the + value of rank of the n-th node. For instance, \textit{file1} + and \textit{file2} might contain the ranks of nodes induced + by the degree sequences of two distinct layers of a + multiplex. + + However, the program is pretty general and can be used to + compute the Spearman's rank correlation coefficient between + any generic pair of rankings. + + N.B.: A C implementation of this program, with the same + interface is also available in the executable + file \texttt{compute\_rho}.} + + +\myreturn{The program prints on \texttt{stdout} the value of the + Spearman's rank correlation coefficient $\rho$ between the + two rankings provided as input. } + +\myreference{\refcorrelations + + \refgrowth + + \refnonlinear + } diff --git a/doc/latex/latex/structure/correlations/compute_tau.tex b/doc/latex/latex/structure/correlations/compute_tau.tex new file mode 100644 index 0000000..e6e8589 --- /dev/null +++ b/doc/latex/latex/structure/correlations/compute_tau.tex @@ -0,0 +1,31 @@ +\myprogram{{compute\_tau.py}} + {compute the Kendall's rank correlation coefficient $\tau_b$ + between two rankings.} {$<$file1$>$ $<$file2$>$} + +\mydescription{Compute the Kendall's rank correlation coefficient + $\tau_b$ between two rankings provided in the input + files \textit{file1} and \textit{file2}. Each input file + contains a list of lines, where the n-th line contains the + value of rank of the n-th node. For instance, \textit{file1} + and \textit{file2} might contain the ranks of nodes induced + by the degree sequences of two distinct layers of a + multiplex. + + However, the program is pretty general and can be used to + compute the Kendall's rank correlation coefficient between + any generic pair of rankings. + + N.B.: This implementation takes properly into account rank + ties.} + + +\myreturn{The program prints on \texttt{stdout} the value of the + Kendall's rank correlation coefficient $\tau_b$ between the + two rankings provided as input. } + +\myreference{\refcorrelations + + \refgrowth + + \refnonlinear +} diff --git a/doc/latex/latex/structure/correlations/dump_k_q.tex b/doc/latex/latex/structure/correlations/dump_k_q.tex new file mode 100644 index 0000000..35aef8d --- /dev/null +++ b/doc/latex/latex/structure/correlations/dump_k_q.tex @@ -0,0 +1,42 @@ +M\myprogram{{dump\_k\_q}} + {compute the degree sequences of two layers of a multiplex.} + {$<$layer1$>$ $<$layer2$>$ $<$pairing$>$} + +\mydescription{Compute and dump on \texttt{stdout} the degree + sequences of two layers of a multiplex. The input + files \textit{layer1} and \textit{layer2} contain the + (undirected) edge lists of the two layers, and each line is + in the format: + + \hspace{0.5cm}\textit{src\_ID} \textit{dest\_ID} + + where \textit{src\_ID} and \textit{dest\_ID} are the IDs of the two + endpoints of an edge. + + The third file \textit{pairing} is a list of lines in the format: + + \hspace{0.5cm} \textit{IDL1 IDL2} + + where \textit{IDL1} is the ID of a node on layer $1$ + and \textit{IDL2} is the ID of the same node on layer $2$. For + instance, the line: + + \hspace{0.5cm} \textit{5 27} + + indicates that node $5$ on layer $1$ has ID $27$ on layer $2$. } + + +\myreturn{The program prints on \texttt{stdout} the degree of each +node on the two layers, in the format: + +\hspace{0.5cm} \textit{ki qi} + +where \textit{ki} is the degree of node \textit{i} on layer $1$ +and \textit{qi} is the degree of node \textit{i} on layer $2$.} + +\myreference{\refcorrelations + + \refgrowth + + \refnonlinear + } diff --git a/doc/latex/latex/structure/correlations/fit_knn.tex b/doc/latex/latex/structure/correlations/fit_knn.tex new file mode 100644 index 0000000..cb90c2b --- /dev/null +++ b/doc/latex/latex/structure/correlations/fit_knn.tex @@ -0,0 +1,50 @@ +\myprogram{{fit\_knn}} + {power-law fit of the inter-layer degree correlation + function.} + {$<$filein$>$ $<$alpha$>$} + +\mydescription{Perform a power-law fit of the inter-layer degree + correlation function: + + \begin{equation*} + \overline{q}(k) = \frac{1}{N_{q}}\sum_{q'} q' P(q'|k) + \end{equation*} + + where $k$ is the degree of a node on layer $1$, $q$ is the + degree on layer $2$ and $P(q|k)$ is the probability that a + node with degree $k$ on layer $1$ has degree $q$ on layer + $2$. The program assumes that $\overline{q}(k)$ can be + written in the form $a k^{b}$, and computes the two + parameters $a$ and $b$ through a linear fit of the log-log + plot of $\overline{q}(k)$. + + The input file \textit{filein} contains a list of lines in + the format: + + \hspace{0.5cm} \textit{ki qi} + + where \textit{ki} is the degree of node $i$ at layer $1$ + and \textit{qi} is the degree of node $i$ at layer $2$. + + The second parameter \textit{alpha} is the ratio of the + progression used to generate the exponentially-distributed + bins for the log-log plot. Typical values of \textit{alpha} + are between $1.1$ and $2.0$. + + + N.B.: The exponent $b$ computed with this method is known to + be inaccurate. +} + + + +\myreturn{The program prints on \texttt{stdout} the values of the + parameters $a$ and $b$ of the power-law fit $\overline{q}(k) + = a k^{b}$.} + +\myreference{\refcorrelations + + \refgrowth + + \refnonlinear + } diff --git a/doc/latex/latex/structure/correlations/knn_q_from_degrees.tex b/doc/latex/latex/structure/correlations/knn_q_from_degrees.tex new file mode 100644 index 0000000..cab0905 --- /dev/null +++ b/doc/latex/latex/structure/correlations/knn_q_from_degrees.tex @@ -0,0 +1,64 @@ +\myprogram{{knn\_q\_from\_degrees.py}} + {compute the inter-layer degree-degree correlation function.} + {$<$filein$>$} + +\mydescription{Compute the inter-layer degree + correlation functions for two layers of a multiplex, using + the degrees of the nodes specified in the input file. The + format of the input file is as follows + +\hspace{0.5cm} \textit{ki qi} + +where \textit{ki} and \textit{qi} are, respectively, the degree at +layer 1 and the degree at layer 2 of node \textit{i}. + + If we consider two layers of a multiplex, and we denote by + $k$ the degree of a node on the first layer and by $q$ the + degree of the same node on the second layers, the + inter-layer degree correlation function is defined as + + \begin{equation*} + \overline{k}(q) = \frac{1}{N_{k}}\sum_{k'} k' P(k'|q) + \end{equation*} + + where $P(k'|q)$ is the probability that a node with degree + $q$ on the second layer has degree equal to $k'$ on the + first layer, and $N_k$ is the number of nodes with degree + $k$ on the first layer. The quantity $\overline{k}(q)$ is + the expected degree at layer $1$ of node that have degree + equal to $q$ on layer $2$. The dual quantity: + + \begin{equation*} + \overline{q}(k) = \frac{1}{N_{q}}\sum_{q'} q' P(q'|k) + \end{equation*} + + is the average degree on layer $2$ of nodes having degree + $k$ on layer $1$. +} + + +\myreturn{The program prints on \texttt{stdout} a list of lines in + the format: + + \hspace{0.5cm} \textit{k $\overline{q}(k)$} + + where \textit{k} is the degree on layer $1$ and + $\overline{q}(k)$ is the average degree on layer $2$ of + nodes having degree equal to $k$ on layer $1$. + + The program also prints on \texttt{stderr} a list of lines in + the format: + + \hspace{0.5cm} \textit{q $\overline{k}(q)$} + + where \textit{q} is the degree on layer $2$ and + $\overline{k}(q)$ is the average degree on layer $1$ of + nodes having degree equal to $q$ on layer $2$. + } + +\myreference{\refcorrelations + + \refgrowth + + \refnonlinear + } diff --git a/doc/latex/latex/structure/correlations/knn_q_from_layers.tex b/doc/latex/latex/structure/correlations/knn_q_from_layers.tex new file mode 100644 index 0000000..f124e55 --- /dev/null +++ b/doc/latex/latex/structure/correlations/knn_q_from_layers.tex @@ -0,0 +1,80 @@ +\myprogram{{knn\_q\_from\_layers.py}} + {compute intra-layer and inter-layer degree-degree + correlation coefficients.} {$<$layer1$>$ $<$layer2$>$} + +\mydescription{Compute the intra-layer and the inter-layer degree + correlation functions for two layers given as input. The + intra-layer degree correlation function quantifies the + presence of degree-degree correlations in a single layer + network, and is defined as: + + \begin{equation*} + \avg{k_{nn}(k)} = \frac{1}{k N_k}\sum_{k'}k'P(k'|k) + \end{equation*} + + where $P(k'|k)$ is the probability that a neighbour of a + node with degree $k$ has degree $k'$, and $N_k$ is the + number of nodes with degree $k$. The quantity + $\avg{k_{nn}(k)}$ is the average degree of the neighbours of + nodes having degree equal to $k$. + + If we consider two layers of a multiplex, and we denote by + $k$ the degree of a node on the first layer and by $q$ the + degree of the same node on the second layers, the + inter-layer degree correlation function is defined as + + \begin{equation*} + \overline{k}(q) = \sum_{k'} k' P(k'|q) + \end{equation*} + + where $P(k'|q)$ is the probability that a node with degree + $q$ on the second layer has degree equal to $k'$ on the + first layer, and $N_q$ is the number of nodes with degree + $q$ on the second layer. The quantity $\overline{k}(q)$ is + the expected degree at layer $1$ of node that have degree + equal to $q$ on layer $2$. The dual quantity: + + \begin{equation*} + \overline{q}(k) = \sum_{q'} q' P(q'|k) + \end{equation*} + + is the average degree on layer $2$ of nodes having degree + $k$ on layer $1$. +} + + +\myreturn{The program creates two output files, respectively called + +\hspace{0.5cm} \textit{file1\_file2\_k1} + +and + +\hspace{0.5cm} \textit{file1\_file2\_k2} + +The first file contains a list of lines in the format: + +\hspace{0.5cm} \textit{k $\avg{k_{nn}(k)}$ $\sigma_k$ +$\overline{q}(k)$ $\sigma_{\overline{q}}$} + +where $k$ is the degree at first layer, $\avg{k_{nn}(k)}$ is the +average degree of the neighbours at layer $1$ of nodes having degree +$k$ at layer $1$, $\sigma_k$ is the standard deviation associated to +$\avg{k_{nn}(k)}$, $\overline{q}(k)$ is the average degree at layer +$2$ of nodes having degree equal to $k$ at layer $1$, and +$\sigma_{\overline{q}}$ is the standard deviation associated to +$\overline{q}(k)$. + +The second file contains a similar list of lines, in the format: + +\hspace{0.5cm} \textit{q $\avg{q_{nn}(q)}$ $\sigma_q$ +$\overline{k}(q)$ $\sigma_{\overline{k}}$} + +with obvious meaning. +} + +\myreference{\refcorrelations + + \refgrowth + + \refnonlinear + } diff --git a/doc/latex/latex/structure/correlations/rank_nodes.tex b/doc/latex/latex/structure/correlations/rank_nodes.tex new file mode 100644 index 0000000..b1a970a --- /dev/null +++ b/doc/latex/latex/structure/correlations/rank_nodes.tex @@ -0,0 +1,19 @@ +\myprogram{{rank\_nodes.py}} + {rank the nodes of a layer according to a given structural + descriptor.} {$<$prop\_file$>$} + +\mydescription{Get a file as input, whose n-th line corresponds to the value of a + certain property of the n-th node, and rank the nodes according to + that property, taking into account ranking ties properly. + + For example, if \textit{propfile} contains the degrees of the nodes + at a certain layer of the multiplex, the computes the ranking induced + by degrees, where the node with the highest degree will be assigned a + rank equal to \textbf{1} (one). +} + +\myreturn{The program prints on \texttt{stdout} a list of lines, where + the n-th line contains the rank of the n-th node corresponding to the + values of the structural descriptor provided in the input file.} + +\myreference{\refcorrelations} diff --git a/doc/latex/latex/structure/correlations/rank_nodes_thresh.tex b/doc/latex/latex/structure/correlations/rank_nodes_thresh.tex new file mode 100644 index 0000000..3b430d1 --- /dev/null +++ b/doc/latex/latex/structure/correlations/rank_nodes_thresh.tex @@ -0,0 +1,18 @@ +\myprogram{{rank\_nodes\_thresh.py}} + {rank the nodes of a layer whose value of a given structural + descriptor is above a threshold.} {$<$prop\_file$>$ $<$thresh$>$} + +\mydescription{Get a file as input, whose n-th line corresponds to the value of a + certain property of the n-th node, and rank the nodes according to + that property, taking into account ranking ties properly. The rank of + all the nodes whose value of the structural descriptor is smaller + than the threshold \textit{thresh} specified as second parameter is + set to \textbf{0} (ZERO). } + +\myreturn{The program prints on \texttt{stdout} a list of lines, where + the n-th line contains the rank of the n-th node corresponding to the + values of the structural descriptor provided in the input file, or + zero if such desxriptor is below the specified + threshold \textit{thresh}.} + +\myreference{\refcorrelations} diff --git a/doc/latex/latex/structure/correlations/rank_occurrence.tex b/doc/latex/latex/structure/correlations/rank_occurrence.tex new file mode 100644 index 0000000..96fb914 --- /dev/null +++ b/doc/latex/latex/structure/correlations/rank_occurrence.tex @@ -0,0 +1,24 @@ +\myprogram{{rank\_occurrence.py}} + {compute the intersection of two rankings.} + {$<$rank1$>$ $<$rank2$>$ $<$increment$>$} + +\mydescription{Get two rankings \textit{rank1} and \textit{rank2} + and compute the size of +the \textit{k}-intersection, i.e. the number of elements which are +present in the first k positions of both rankings, as a function +of \textit{k}. The parameter \textit{increment} determines the +distance between two subsequent values of \textit{k}. + +Each input file is a list of node IDs, one per line, where the first +line contains the ID of the highest ranked node. +} + +\myreturn{The program prints on \texttt{stdout} a list of lines in the +format: + + \hspace{0.5cm} \textit{k num\_k} + + where \textit{num\_k} is the number of nodes which are present in + the first \textit{k} positions of both rankings.} + +\myreference{\refcorrelations} |