\section{Experiments}

gLabTrie has been tested on a dataset of social, communication and biological networks. All experiments has been performed on the following configuration: Intel Core i7-2670 2.2Ghz CPU with a RAM of 8 GB. Tab. 1 describes the features of the selected networks.

\begin{table}
\centering
\label{NetFeatures}
\caption{Networks used for experiments.}
\begin{tabular}{llllll}
\hline\noalign{\smallskip}
Name & Type & Nodes & Edges & Reference \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
\textsc{flights} & undirected & 2,939 & 15,677 & \cite{opsahl2011why} \\
\textsc{blogs} & directed & 1,224 & 16,715 & \cite{adamic2005political} \\
\textsc{ppi} & undirected & 9,506 & 37,054 & \cite{prasad2009human} \\
\textsc{dblp} & directed & 12,591 & 49,728 & \cite{ley2002dblp} \\
\textsc{foldoc} & directed & 13,356 & 120,239 & \cite{batagelj2002network} \\
\textsc{internet} & undirected & 20,305 & 42,568 & \cite{dimitropoulos2005inferring} \\
\hline
\end{tabular}
\end{table}

\textsc{flights} is a network extracted from Openflights.org (http://openflights.org), representing all possible air routes between different airports around the world in 2011 \cite{opsahl2011why}. \textsc{blogs} is a directed network of hyperlinks between weblogs on US politics of 2004 \cite{adamic2005political}. \textsc{ppi} is a protein-protein interaction (PPI) network in human, taken from HPRD database \cite{prasad2009human}.
\textsc{dblp} is the citation network of DBLP, a database of scientific publications, where each node in the network is a publication and edges connect two citations A and B iff A cites B \cite{ley2002dblp}. \textsc{foldoc} is an oriented semantic network taken from the on-line computing dictionary FOLDOC (http://foldoc.org), where nodes are computer science terms and edges connect two terms X and Y iff Y is used to explain the meaning of X \cite{batagelj2002network}. \textsc{internet} represents the business relationships between autonomous systems (ASes) of Internet in 2005 \cite{dimitropoulos2005inferring}.

Nodes of each network have been annotated with the following labels. In \textsc{flights}, airports have been associated to one of the five continents. In \textsc{blogs}, nodes have been classified depending on their political leaning (liberal and conservative). For the labeling of nodes in \textsc{ppi}, we used Gene Ontology (GO) \cite{ashburner2000gene}, a hierarchical dictionary of terms related to biological processes, components and functions, which have been extensively used for the analysis of biological networks so far \cite{maere2005bingo,bindea2009cluego}. We annotated proteins with GO processes up to the first level of the hierarchy yielding 11 nodes labels. Ten of them represent specific kinds of biological processes (whole-organism process, metabolism, regulation, cellular organization, development, localization, signaling, response to stimulus, biological adhesion and reproduction). A special label representing the generic biological process has been associated to proteins for which we did not have GO annotations. \textsc{dblp} nodes has been annotated with different kinds of publications (articles, inproceedings, proceedings, books, incollections, phd thesis and master thesis) or "www" if the node refers to a cited website. \textsc{internet} ASes have been partitioned into seven classes (large ISPs, small ISPs, customers, universities, internet exchange points, network information centers, not classified) according to the taxonomy described in \cite{dimitropoulos2006revealing}. Computing terms in \textsc{foldoc} have been labeled according to their domains (jargons, computer science, hardware, programming, graphics and multimedia, science, people and organizations, data, networking, documentation, operating systems, languages, software, various terms). 

We compared the no-index version of gLabTrie with the index-based approach. We run our algorithm using default randomization parameters ($N_{rand}=100$, $p=0.01$ and $f=2$). 

%For each network, we first computed indexes of different size $K$ and evaluated the space required to store all $K$-subgraphs of the input network on disk (Tab. 2). We set the maximum space allowed for storing the occurrences to 500 GB.%

%\begin{table}
%\label{IndexDisk}
%\centering
%\caption{Space on disk required to store all possible $K$-subgraphs.}
%\begin{tabular}{llllll}
%\hline\noalign{\smallskip}
%Network & $K$=3 & $K$=4 & $K=5$ \\
%\noalign{\smallskip}
%\hline
%\noalign{\smallskip}
%\textsc{flights} & 12 MB & 989 MB & 79 GB \\
%\textsc{blogs} & 20 MB & 2 GB & 190 GB \\
%\textsc{ppi} & 21 MB & 1.5 GB & 125 GB \\
%\textsc{dblp} & 36 MB & 4.8 GB & $>$500 GB \\
%\textsc{internet} & 223 MB & 137 GB & $>$500 GB \\
%\textsc{foldoc} & 46 MB & 5 GB & $>$500 GB \\
%\hline
%\end{tabular}
%\end{table}

The performance of gLabTrie has been evaluated with respect to three parameters:
\begin{enumerate}
\item[a)] $m$: the motif size, i.e. the number of its nodes;
\item[b)] $c$: the number of motif constraints, i.e. the number of specified node labels in the query;
\item[c)] $l$: the number of labels in the input networks.
\end{enumerate}
For tests a) and b) we used real labels, while in case c) we ran our algorithm with randomly assigned labels. To measure the influence of these parameters, we varied the parameter of interest and assigned default values to the other ones ($m=4$, $c=4$ and $l=2$). For each test, we ran gLabTrie on a set of 10 random queries. In the experiments with real labels, label constraints for random queries were generated according to the frequency of a node label: the more frequent a label $x$, the higher the probability that $x$ is added as a label constraint to the query. In the tests with artificial labels, label constraints were added to the queries according to the uniform distribution of node labels. 

Tab. 2 reports the running times for building indexes for motif of size $m$ up to 4 in networks annotated with real labels. In all cases, the performance of gLabTrie strongly depends on the size of the network, its orientation (undirected graphs contain more instances of a certain topology on average) and the number of labels. Most of the time is spent in storing all the motif occurrences of a given size into the database. The number of occurrences increases exponentially with $m$. 

\begin{table}
\centering
\label{BuildTime}
\caption{Running times (minutes) to build indexes on varying motif size.}
\begin{tabular}{llllll}
\hline\noalign{\smallskip}
Network & $m=3$ & $m=4$ \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
\textsc{flights} & 8.59 & 245.39 \\
\textsc{blogs} & 7.78 & 566.83 \\
\textsc{ppi} & 21.72 & 425.59 \\
\textsc{dblp} & 30.91 & 1211.91 \\
\textsc{foldoc} & 46.28 & 1486.59 \\
\textsc{internet} & 87.48 & 40605.23 \\
\hline
\end{tabular}
\end{table}

 
Tab. 3 shows the results of the comparison between the no-index and the index-based approach of gLabTrie on querying motifs of different sizes, up to size 4. For each network and each motif size, we reported the mean and the standard deviation. In both cases, the running time includes the time needed to retrieve all the subgraphs matching a given query. 

\begin{table}
\centering
\label{MotifSize}
\caption{Running times (sec) for querying motifs of different size with no-index and index-based approach.}
\begin{tabular}{lccc}
\hline\noalign{\smallskip}
Network \, & $m$ & No-index & Index \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
\multirow{2}{*}{\textsc{flights}} &\, 3 \, & $333.02 \pm 4.71$ & $0.01 \pm 0.01$ \\
&\, 4 \, & $364.81 \pm 38.70$ & $0.56 \pm 0.86$ \\
\hline
\noalign{\smallskip}
\multirow{2}{*}{\textsc{blogs}} &\, 3 \, & $155.36 \pm 2.27$ & $0.08 \pm 0.15$ \\
&\, 4 \, & $960.07 \pm 159.01$ & $1.44 \pm 0.54$ \\
\hline
\noalign{\smallskip}
\multirow{2}{*}{\textsc{ppi}} &\, 3 \, & $872.68 \pm 21.77$ & $0.01 \pm 0.01$ \\
&\, 4 \, & $866.10 \pm 5.17$ & $0.06 \pm 0.10$ \\
\hline
\noalign{\smallskip}
\multirow{2}{*}{\textsc{dblp}} &\, 3 \, & $553.46 \pm 4.02$ & $0.11 \pm 0.09$ \\
&\, 4 \, & $882.63 \pm 152.05$ & $6.28 \pm 5.06$ \\
\hline
\noalign{\smallskip}
\multirow{2}{*}{\textsc{foldoc}} &\, 3 \, & $1290.23 \pm 8.45$ & $0.02 \pm 0.01$ \\
&\, 4 \, & $1308.40 \pm 12.55$ & $0.75 \pm 0.22$ \\
\hline
\noalign{\smallskip}
\multirow{2}{*}{\textsc{internet}} &\, 3 \, & $2116.65 \pm 6.38$ & $0.70 \pm 2.04$ \\
&\, 4 \, & $2649.60 \pm 1305.87$ & $670.22 \pm 200.59$ \\
\hline
\end{tabular}
\end{table}

The results show (unsurprisingly) that the index-based approach is much faster (100s of times) than having no index. We define $q_{min}$ to be the minimum number of query operations required to recoup the time cost of building the index. For $m=3$, $q_{min} \simeq 2$, so the time cost of building the index is recouped after two queries on average, while for $m=4$ we have $q_{min}\simeq 44$.

It is worth noting that the benefit of the index decreases as the size of the network (measured in terms of the number of its nodes) increases. For instance, in the \textsc{internet} network, which is by far the biggest network in our dataset, when $m=4$ the index-based approach is only 4 times faster than the no-index one. In this case, the disappointing performance of the index-based approach is due to the very high number of query occurrences that the algorithm must retrieve from the dataset, resulting in a large number of I/O operations. In the \textsc{internet} network with $m=4$ the I/O time is 99\% of the total running time, on average. 

In Tab. 4, we compare the running times of the no-index and the index-based approach on querying motifs with a variable number of label constraints in the query. Again, network nodes have been annotated with real labels. We set $m=4$ and we varied $c$ from 1 to 4.

\begin{table}
\centering
\label{ConstraintSize}
\caption{Running times (sec) for querying motifs with variable number of label constraints with no-index and index-based approach.}
\begin{tabular}{lccc}
\hline\noalign{\smallskip}
Network \, & $c$ & No-index & Index \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
\multirow{4}{*}{\textsc{flights}} &\, 1 \, & $685.06 \pm 155.22$ & $13.35 \pm 9.6$ \\
&\, 2 \, & $576.76 \pm 116.71$ & $5.70 \pm 4.93$ \\
&\, 3 \, & $412.65 \pm 61.02$ & $2.09 \pm 3.32$ \\
&\, 4 \, & $343.85 \pm 17.17$ & $0.52 \pm 1.06$ \\
\hline
\noalign{\smallskip}
\multirow{4}{*}{\textsc{blogs}} &\, 1 \, & $2214.74 \pm 8.36$ & $48.32 \pm 2.75$ \\
&\, 2 \, & $1953.47 \pm 199.11$ & $21.20 \pm 20.42$ \\
&\, 3 \, & $1430.81 \pm 336.02$ & $15.83 \pm 20.09$ \\
&\, 4 \, & $829.10 \pm 214.59$ & $6.16 \pm 13.74$ \\
\hline
\noalign{\smallskip}
\multirow{4}{*}{\textsc{ppi}} &\, 1 \, & $1228.73 \pm 221.05$ & $10.79 \pm 10.18$ \\
&\, 2 \, & $1116.63 \pm 216.56$ & $9.35 \pm 11.52$ \\
&\, 3 \, & $897.56 \pm 34.87$ & $0.51 \pm 0.75$ \\
&\, 4 \, & $861.30 \pm 9.43$ & $0.04 \pm 0.06$ \\
\hline
\noalign{\smallskip}
\multirow{4}{*}{\textsc{dblp}} &\, 1 \, & $4041.38 \pm 316.75$ & $139.08 \pm 1.84$ \\
&\, 2 \, & $3186.24 \pm 693.96$ & $80.60 \pm 34.95$ \\
&\, 3 \, & $1867.96 \pm 475.73$ & $40.26 \pm 18.37$ \\
&\, 4 \, & $871.19 \pm 131.45$ & $7.43 \pm 4.14$ \\
\hline
\noalign{\smallskip}
\multirow{4}{*}{\textsc{foldoc}} &\, 1 \, & $3751.95 \pm 686.84$ & $78.29 \pm 50.07$ \\
&\, 2 \, & $2075.93 \pm 334.84$ & $7.24 \pm 2.42$ \\
&\, 3 \, & $1288.12 \pm 42.41$ & $2.47 \pm 2.15$ \\
&\, 4 \, & $1212.23 \pm 16.79$ & $0.58 \pm 0.46$ \\
\hline
\noalign{\smallskip}
\multirow{4}{*}{\textsc{internet}} &\, 1 \, & $57988.44 \pm 13722.07$ & $11642.50 \pm 5519.74$ \\
&\, 2 \, & $28082.31 \pm 13974.45$ & $8984.35 \pm 6945.80$ \\
&\, 3 \, & $9165.14 \pm 5849.21$ & $3660.06 \pm 3297.24$ \\
&\, 4 \, & $2101.29 \pm 35.61$ & $0.71 \pm 1.05$ \\
\hline
\end{tabular}
\end{table}

As the number of query label constraints defined by the user increases, the performance of both approaches improves. However, the more selective the query, the greater the benefit of the index. The gain enjoyed by the index is proportional to the size of the network and the number of constraints, because of the exponential decrease of the number of occurrences matching the query. For example, when $c$ goes from 1 to 4, the no-index approach becomes $\simeq$ 28 times faster and the index-based approach $\simeq$ 16400 times faster in the \textsc{internet} network, while in the \textsc{blogs} network the two algorithms are only $\simeq$ 3 and $\simeq$ 15 faster, respectively.

Tab. 5 summarizes the results of the comparison between the performance of the two approaches when the number of labels vary. To perform these experiments, we annotated network nodes with artificial labels. Given a set of $l$ labels, each node has been associated with a random unique label between 1 and $l$, according to a uniform distribution. We ran five different series of experiments with $l=2,6,10,14,18$. In each series, we set $m=4$ and $c=4$.
 
\begin{table}
\centering
\label{NumLabels}
\caption{Running times (sec) for querying motifs with variable number of node labels with no-index and index-based approach.}
\begin{tabular}{lccc}
\hline\noalign{\smallskip}
Network \, & $l$ & No-index & Index \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
\multirow{5}{*}{\textsc{flights}} &\, 2 \, & $483.08 \pm 35.09$ & $4.97 \pm 1.29$ \\
&\, 6 \, & $331.79 \pm 3.18$ & $0.09 \pm 0.03$ \\
&\, 10 \, & $327.36 \pm 0.63$ & $0.03 \pm 0.01$ \\
&\, 14 \, & $326.89 \pm 0.39$ & $0.04 \pm 0.02$ \\
&\, 18 \, & $327.00 \pm 0.82$ & $0.09 \pm 0.02$ \\
\hline
\noalign{\smallskip}
\multirow{5}{*}{\textsc{blogs}} &\, 2 \, & $931.77 \pm 254.88$ & $7.37 \pm 2.32$ \\
&\, 6 \, & $192.27 \pm 29.18$ & $0.29 \pm 0.18$ \\
&\, 10 \, & $160.67 \pm 5.44$ & $0.55 \pm 0.05$ \\
&\, 14 \, & $151.54 \pm 2.77$ & $1.16 \pm 0.12$ \\
&\, 18 \, & $149.44 \pm 1.36$ & $2.25 \pm 0.10$ \\
\hline
\noalign{\smallskip}
\multirow{5}{*}{\textsc{ppi}} &\, 2 \, & $1066.70 \pm 95.43$ & $2.10 \pm 1.66$ \\
&\, 6 \, & $870.64 \pm 5.42$ & $0.17 \pm 0.12$ \\
&\, 10 \, & $861.66 \pm 1.72$ & $0.04 \pm 0.02$ \\
&\, 14 \, & $860.80 \pm 1.55$ & $0.05 \pm 0.03$ \\
&\, 18 \, & $851.23 \pm 2.16$ & $0.10 \pm 0.07$ \\
\hline
\noalign{\smallskip}
\multirow{5}{*}{\textsc{dblp}} &\, 2 \, & $1686.55 \pm 496.97$ & $32.66 \pm 20.59$ \\
&\, 6 \, & $623.22 \pm 25.33$ & $1.59 \pm 0.94$ \\
&\, 10 \, & $571.75 \pm 11.92$ & $1.23 \pm 0.76$ \\
&\, 14 \, & $559.46 \pm 5.47$ & $0.57 \pm 0.36$ \\
&\, 18 \, & $555.38 \pm 2.36$ & $1.32 \pm 0.64$ \\
\hline
\noalign{\smallskip}
\multirow{5}{*}{\textsc{foldoc}} &\, 2 \, & $2749.55 \pm 539.16$ & $18.67 \pm 6.22$ \\
&\, 6 \, & $1266.62 \pm 43.13$ & $0.81 \pm 0.83$ \\
&\, 10 \, & $1218.74 \pm 10.16$ & $1.01 \pm 0.80$ \\
&\, 14 \, & $1204.28 \pm 6.85$ & $1.63 \pm 0.88$ \\
&\, 18 \, & $1201.15 \pm 1.64$ & $3.07 \pm 0.98$ \\
\hline
\noalign{\smallskip}
\multirow{5}{*}{\textsc{internet}} &\, 2 \, & $17270.40 \pm 5731.44$ & $1154.77 \pm 2030.07$ \\
&\, 6 \, & $2595.38 \pm 382.33$ & $94.18 \pm 106.23$ \\
&\, 10 \, & $2250.07 \pm 111.54$ & $23.98 \pm 20.00$ \\
&\, 14 \, & $2162.81 \pm 44.00$ & $5.68 \pm 4.18$ \\
&\, 18 \, & $2113.16 \pm 20.06$ & $5.08 \pm 4.59$ \\
\hline
\end{tabular}
\end{table}

The time costs of both approaches decrease when the number of node labels increase. In all networks, the greatest reduction of the running time happens when we move from $l=2$ to $l=6$. 
