Fine tune. To be reviewed: abstract, intro, conclusion.
1.1 --- a/damecco.tex Sat Nov 26 00:15:22 2016 +0100
1.2 +++ b/damecco.tex Sun Nov 27 22:57:56 2016 +0100
1.3 @@ -329,10 +329,10 @@
1.4 $lab: (V_{small}\cup V_{large}) \longrightarrow K$ is a \textbf{node
1.5 label function}, where K is an arbitrary set. The elements in K
1.6 are the \textbf{node labels}. Two nodes, u and v are said to be
1.7 - \textbf{equivalent}, if $lab(u)=lab(v)$.
1.8 + \textbf{equivalent} if $lab(u)=lab(v)$.
1.9 \end{definition}
1.10
1.11 -When node labels are also given, the matched nodes must have the same
1.12 +When node labels are given, the matched nodes must have the same
1.13 labels. For example, the node labeled isomorphism is phrased by
1.14 \begin{definition}
1.15 $G_{small}$ and $G_{large}$ are \textbf{isomorphic by the node label
1.16 @@ -345,16 +345,7 @@
1.17 \end{center}
1.18 \end{definition}
1.19
1.20 -The other two definitions can be extended in the same way.
1.21 -
1.22 -Note that edge label function can be defined similarly to node label
1.23 -function, and all the definitions can be extended with additional
1.24 -conditions, but it is out of the scope of this work.
1.25 -
1.26 -The equivalence of two nodes is usually defined by another relation,
1.27 -$\\R\subseteq (V_{small}\cup V_{large})^2$. This overlaps with the
1.28 -definition given above if R is an equivalence relation, which does not
1.29 -mean restriction in biological and chemical applications.
1.30 +Note that he other two definitions can be extended in the same way.
1.31
1.32 \subsection{Common problems}\label{sec:CommProb}
1.33
1.34 @@ -395,19 +386,19 @@
1.35 definitions and notations will be used throughout the whole paper.
1.36 \begin{definition}
1.37 A set $M\subseteq V_{small}\times V_{large}$ is called
1.38 -\textbf{mapping}, if no node of $V_{small}$ or of $V_{large}$ appears
1.39 +\textbf{mapping} if no node of $V_{small}\cup V_{large}$ appears
1.40 in more than one pair in M. That is, M uniquely associates some of
1.41 the nodes in $V_{small}$ with some nodes of $V_{large}$ and vice
1.42 versa.
1.43 \end{definition}
1.44
1.45 \begin{definition}
1.46 -Mapping $M$ \textbf{covers} a node v, if there exists a pair in M, which
1.47 +Mapping $M$ \textbf{covers} a node v if there exists a pair in M, which
1.48 contains v.
1.49 \end{definition}
1.50
1.51 \begin{definition}
1.52 -A mapping $M$ is $\mathbf{whole\ mapping}$, if $M$ covers all the
1.53 +A mapping $M$ is $\mathbf{whole\ mapping}$ if $M$ covers all the
1.54 nodes in $V_{small}$.
1.55 \end{definition}
1.56
1.57 @@ -418,9 +409,8 @@
1.58 \end{notation}
1.59
1.60 \begin{notation}
1.61 -Let $\mathbf{Pair(M,v)}$ be the pair of $v$ in $M$, if such a node
1.62 -exist, otherwise $\mathbf{Pair(M,v)}$ is undefined. For a mapping $M$
1.63 -and $v\in V_{small}\cup V_{large}$.
1.64 +Let $\mathbf{Pair(M,v)}$ be the pair of $v$ in $M$ if such a node
1.65 +exist, otherwise $\mathbf{Pair(M,v)}$ is undefined, where $M$ is a mapping and $v\in V_{small}\cup V_{large}$.
1.66 \end{notation}
1.67
1.68 Note that if $\mathbf{Pair(M,v)}$ exists, then it is unique
1.69 @@ -441,26 +431,26 @@
1.70
1.71 \begin{definition}
1.72 Let M be a mapping. A logical function $\mathbf{Cons_{PT}}$ is a
1.73 -\textbf{consistency function by } $\mathbf{PT}$, if the following
1.74 +\textbf{consistency function by } $\mathbf{PT}$ if the following
1.75 holds. If there exists whole mapping $W$ of type $PT$ for which
1.76 $M\subseteq W$, then $Cons_{PT}(M)$ is true.
1.77 \end{definition}
1.78
1.79 \begin{definition}
1.80 Let M be a mapping. A logical function $\mathbf{Cut_{PT}}$ is a
1.81 -\textbf{cutting function by } $\mathbf{PT}$, if the following
1.82 +\textbf{cutting function by } $\mathbf{PT}$ if the following
1.83 holds. $\mathbf{Cut_{PT}(M)}$ is false if $M$ can be extended to a
1.84 whole mapping $W$ of type $PT$.
1.85 \end{definition}
1.86
1.87 \begin{definition}
1.88 -$M$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$, if
1.89 +$M$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$ if
1.90 $Cons_{PT}(M)$ is true.
1.91 \end{definition}
1.92
1.93 $Cons_{PT}$ and $Cut_{PT}$ will often be used in the following form.
1.94 \begin{notation}
1.95 -Let $\mathbf{Cons_{PT}(p, M)}:=Cons_{PT}(M\cup\{p\})$ and
1.96 +Let $\mathbf{Cons_{PT}(p, M)}:=Cons_{PT}(M\cup\{p\})$, and
1.97 $\mathbf{Cut_{PT}(p, M)}:=Cut_{PT}(M\cup\{p\})$, where
1.98 $p\in{V_{small}\!\times\!V_{large}}$ and $M\cup\{p\}$ is mapping.
1.99 \end{notation}
1.100 @@ -508,7 +498,7 @@
1.101 $Cut_{PT}(p,M(s))$ are evaluated. If $Cons_{PT}(p,M(s))$ is true and
1.102 $Cut_{PT}(p,M(s))$ is false, the successor state $\tilde{s}=s\cup
1.103 \{p\}$ is computed, and the whole process is recursively applied to
1.104 -$\tilde{s}$. Otherwise, $\tilde{s}$ is not consistent by $PT$ or it
1.105 +$\tilde{s}$. Otherwise, $\tilde{s}$ is not consistent by $PT$, or it
1.106 can be proved that $s$ can not be extended to a whole mapping.
1.107
1.108 In order to make sure of the correctness, see
1.109 @@ -518,13 +508,8 @@
1.110 consistent mappings.
1.111 \end{claim}
1.112
1.113 -Note that a state may be reached in many different ways, since the
1.114 -order of insertions into M does not influence the nascent mapping. In
1.115 -fact, the number of different ways which lead to the same state can be
1.116 -exponentially large. If $G_{small}$ and $G_{large}$ are circles with n
1.117 -nodes and n different node labels, there exists exactly one graph
1.118 -isomorphism between them, but it will be reached in $n!$ different
1.119 -ways.
1.120 +Note that a state may be reached in exponentially many different ways, since the
1.121 +order of insertions into $M$ does not influence the nascent mapping.
1.122
1.123 However, one may observe
1.124
1.125 @@ -533,9 +518,9 @@
1.126 Let $\prec$ an arbitrary total ordering relation on $V_{small}$. If
1.127 the algorithm ignores each $p=(u,v) \in P(s)$, for which
1.128 \begin{center}
1.129 -$\exists (\hat{u},\hat{v})\in P(s): \hat{u} \prec u$,
1.130 +$\exists (\tilde{u},\tilde{v})\in P(s): \tilde{u} \prec u$,
1.131 \end{center}
1.132 -then no state can be reached more than ones and each state associated
1.133 +then no state can be reached more than once, and each state associated
1.134 with a whole mapping remains reachable.
1.135 \end{claim}
1.136
1.137 @@ -557,7 +542,7 @@
1.138 \end{notation}
1.139
1.140 The set $P(s)$ includes the pairs of uncovered neighbours of covered
1.141 -nodes and if there is not such a node pair, all the pairs containing
1.142 +nodes, and if there is not such a node pair, all the pairs containing
1.143 two uncovered nodes are added. Formally, let
1.144 \[
1.145 P(s)\!=\!
1.146 @@ -578,8 +563,8 @@
1.147 For example, the consistency function of induced subgraph isomorphism is as follows.
1.148 \begin{notation}
1.149 Let $\mathbf{\Gamma_{small} (u)}:=\{\tilde{u}\in V_{small} :
1.150 -(u,\tilde{u})\in E_{small}\}$\\ Let $\mathbf{\Gamma_{large}
1.151 - (v)}:=\{\tilde{v}\in V_{large} : (v,\tilde{v})\in E_{large}\}$
1.152 +(u,\tilde{u})\in E_{small}\}$, and $\mathbf{\Gamma_{large}
1.153 + (v)}:=\{\tilde{v}\in V_{large} : (v,\tilde{v})\in E_{large}\}$, where $u\in V_{small}$ and $v\in V_{large}$.
1.154 \end{notation}
1.155
1.156 $M(s)\cup \{(u,v)\}$ is a consistent mapping by $IND$ $\Leftrightarrow
1.157 @@ -656,25 +641,15 @@
1.158
1.159 \begin{definition}
1.160 An order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of
1.161 -$V_{small}$ is \textbf{matching order}, if exists $\prec$ total
1.162 +$V_{small}$ is \textbf{matching order} if exists $\prec$ total
1.163 ordering relation, s.t. the VF2 with $\prec$ on the d-th level finds
1.164 pair for $u_{\sigma(d)}$ for all $d\in\{1,..,|V_{small}|\}$.
1.165 \end{definition}
1.166
1.167 \begin{claim}\label{claim:MOclaim}
1.168 -A total ordering is matching order, iff the nodes of every component
1.169 +A total ordering is matching order iff the nodes of every component
1.170 form an interval in the node sequence, and every node connects to a
1.171 -previous node in its component except the first node of the
1.172 -component. The order of the components is arbitrary. \\Formally
1.173 -spoken, an order
1.174 -$(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of
1.175 -$V_{small}$ is matching order $\Leftrightarrow$ $\forall
1.176 -G'_{small}=(V'_{small},E'_{small})\ component\ of\ G_{small}: \forall
1.177 -i: (\exists j : j<i\wedge u_{\sigma(j)},u_{\sigma(i)}\in
1.178 -V'_{small})\Rightarrow \exists k : k < i \wedge (\forall l: k\leq
1.179 -l\leq i \Rightarrow u_{l}\in V'_{small}) \wedge
1.180 -(u_{\sigma{(k)}},u_{\sigma{(i)}})\in E'_{small}$, where $i,j,k,l\in
1.181 -\{1,..,|V_{small}|\}$\newline
1.182 +previous node in its component except the first node of each component.
1.183 \end{claim}
1.184
1.185 To summing up, a total ordering always uniquely determines a matching
1.186 @@ -782,7 +757,7 @@
1.187 where $l$ is a label and $\mathcal{M}\subseteq V_{small}$.
1.188 \end{notation}
1.189
1.190 -\begin{definition}Let $\mathbf{arg\ max}_{f}(S) :=\{u : u\in S \wedge f(u)=max_{v\in S}\{f(v)\}\}$ and $\mathbf{arg\ min}_{f}(S) := arg\ max_{-f}(S)$, where $S$ is a finite set and $f:S\longrightarrow \mathbb{R}$.
1.191 +\begin{definition}Let $\mathbf{arg\ max}_{f}(S) :=\{u\in S : f(u)=max_{v\in S}\{f(v)\}\}$ and $\mathbf{arg\ min}_{f}(S) := arg\ max_{-f}(S)$, where $S$ is a finite set and $f:S\longrightarrow \mathbb{R}$.
1.192 \end{definition}
1.193
1.194 \begin{algorithm}
1.195 @@ -810,7 +785,7 @@
1.196 \algtext*{EndWhile}
1.197 \caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
1.198 \begin{algorithmic}[1]
1.199 -\Procedure{VF2++ProcessLevel1}{$V_{d}$} \While{$V_d\neq\emptyset$}
1.200 +\Procedure{VF2++ProcessLevel}{$V_{d}$} \While{$V_d\neq\emptyset$}
1.201 \State $m\in$ arg min$_{F_\mathcal{M}\circ\ lab}($ arg max$_{deg}($arg
1.202 max$_{Conn_{\mathcal{M}}}(V_{d})))$ \State $V_d:=V_d\backslash m$
1.203 \State Append node $m$ to the end of $\mathcal{M}$ \State Refresh
1.204 @@ -858,10 +833,10 @@
1.205 M[i] =
1.206 \begin{cases}
1.207 v & if\ (u_i,v)\ is\ in\ the\ mapping\\ INVALID &
1.208 - if\ no\ node\ has\ been\ mapped\ to\ u_i.
1.209 + if\ no\ node\ has\ been\ mapped\ to\ u_i,
1.210 \end{cases}
1.211 \]
1.212 -Where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$
1.213 +where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$
1.214 means "no node".
1.215 \subsubsection{Avoiding the recurrence}
1.216 The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
1.217 @@ -884,7 +859,7 @@
1.218 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the
1.219 task is not to maintain the candidate set, but to generate the
1.220 candidate nodes in $G_{large}$ for a given node $u\in V_{small}$. In
1.221 -case of any of the three problem type and a mapping $M$, if a node $v\in
1.222 +case of any of the three problem types and a mapping $M$ if a node $v\in
1.223 V_{large}$ is a potential pair of $u\in V_{small}$, then $\forall
1.224 u'\in V_{small} : (u,u')\in
1.225 E_{small}\ and\ u'\ is\ covered\ by\ M\ \Rightarrow (v,Pair(M,u'))\in
1.226 @@ -893,7 +868,7 @@
1.227
1.228 Having said that, an algorithm running in $\Theta(deg)$ time is
1.229 describable if there exists a covered node in the component containing
1.230 -$u$, and a linear one other wise.
1.231 +$u$, and a linear one otherwise.
1.232
1.233
1.234 \subsubsection{Determining the node order}
1.235 @@ -950,7 +925,7 @@
1.236 \section{The VF2 Plus Algorithm}
1.237 The VF2 Plus algorithm is a recently improved version of VF2. It was
1.238 compared with the state of the art algorithms in \cite{VF2Plus} and
1.239 -has proven itself to be competitive with RI, the best algorithm on
1.240 +has proved itself to be competitive with RI, the best algorithm on
1.241 biological graphs. \\ A short summary of VF2 Plus follows, which uses
1.242 the notation and the conventions of the original paper.
1.243
1.244 @@ -961,7 +936,7 @@
1.245 algorithm.
1.246
1.247 \begin{definition}
1.248 -$(u,v)$ is a \textbf{feasible pair}, if $lab(u)=lab(v)$ and
1.249 +$(u,v)$ is a \textbf{feasible pair} if $lab(u)=lab(v)$ and
1.250 $deg(u)\leq deg(v)$, where $u\in{V_{small}}$ and $ v\in{V_{large}}$.
1.251 \end{definition}
1.252 $P_{lab}(L):=$ a priori probability to find a node with label $L$ in
1.253 @@ -975,8 +950,9 @@
1.254 selected, and $degreeM$ of a node is the number of its neighbours in
1.255 $M$.
1.256 \begin{algorithm}
1.257 -\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
1.258 -nyomtasson .. \algtext*{EndProcedure}%ne nyomtasson ..
1.259 +\algtext*{EndIf}%ne nyomtasson end if-et
1.260 +\algtext*{EndFor}%nenyomtasson ..
1.261 +\algtext*{EndProcedure}%ne nyomtasson ..
1.262 \algtext*{EndWhile}
1.263 \caption{}\label{alg:VF2PlusPseu}
1.264 \begin{algorithmic}[1]
1.265 @@ -1023,13 +999,76 @@
1.266 In the following, the induced subgraph isomorphism and the graph
1.267 isomorphism will be examined.
1.268
1.269 -This dataset provides graph pairs, between which all the induced subgraph isomorphisms have to be found. For run time results, please see Figure~\ref{fig:bioIND}.
1.270 +This dataset provides graph pairs, between which all the induced subgraph isomorphisms have to be found. For runtime results, please see Figure~\ref{fig:bioIND}.
1.271
1.272 In an other experiment, the nodes of each graph in the database had been
1.273 shuffled, and an isomorphism between the shuffled and the original
1.274 graph was searched. The solution times are shown on Figure~\ref{fig:bioISO}.
1.275
1.276
1.277 +\begin{figure}[H]
1.278 +\vspace*{-2cm}
1.279 +\hspace*{-1.5cm}
1.280 +\begin{subfigure}[b]{0.55\textwidth}
1.281 +\begin{figure}[H]
1.282 +\begin{tikzpicture}[trim axis left, trim axis right]
1.283 +\begin{axis}[title=Molecules IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.284 +=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.285 + west},scaled x ticks = false,x tick label style={/pgf/number
1.286 + format/1000 sep = \thinspace}]
1.287 +%\addplot+[only marks] table {proteinsOrig.txt};
1.288 +\addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark
1.289 + size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};
1.290 +\end{axis}
1.291 +\end{tikzpicture}
1.292 +\caption{In the case of molecules, the algorithms have
1.293 + similar behaviour, but VF2++ is almost two times faster even on such
1.294 + small graphs.} \label{fig:INDMolecule}
1.295 +\end{figure}
1.296 +\end{subfigure}
1.297 +\hspace*{1.5cm}
1.298 +\begin{subfigure}[b]{0.55\textwidth}
1.299 +\begin{figure}[H]
1.300 +\begin{tikzpicture}[trim axis left, trim axis right]
1.301 +\begin{axis}[title=Contact maps IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.302 +=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.303 + west},scaled x ticks = false,x tick label style={/pgf/number
1.304 + format/1000 sep = \thinspace}]
1.305 +%\addplot+[only marks] table {proteinsOrig.txt};
1.306 +\addplot table {Orig/ContactMaps.128.txt};
1.307 +\addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.308 + {VF2PPLabel/ContactMaps.128.txt};
1.309 +\end{axis}
1.310 +\end{tikzpicture}
1.311 +\caption{On contact maps, VF2++ runs almost in constant time, while VF2
1.312 + Plus has a near linear behaviour.} \label{fig:INDContact}
1.313 +\end{figure}
1.314 +\end{subfigure}
1.315 +
1.316 +\begin{center}
1.317 +\vspace*{-0.5cm}
1.318 +\begin{subfigure}[b]{0.55\textwidth}
1.319 +\begin{figure}[H]
1.320 +\begin{tikzpicture}[trim axis left, trim axis right]
1.321 + \begin{axis}[title=Proteins IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.322 + =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.323 + west},scaled x ticks = false,x tick label style={/pgf/number
1.324 + format/1000 sep = \thinspace}] %\addplot+[only marks] table
1.325 + {proteinsOrig.txt}; \addplot[mark=*,mark size=1.2pt,color=blue]
1.326 + table {Orig/Proteins.256.txt}; \addplot[mark=triangle*,mark
1.327 + size=1.8pt,color=red] table {VF2PPLabel/Proteins.256.txt};
1.328 + \end{axis}
1.329 + \end{tikzpicture}
1.330 +\caption{Both the algorithms have linear behaviour on protein
1.331 + graphs. VF2++ is more than 10 times faster than VF2
1.332 + Plus.} \label{fig:INDProt}
1.333 +\end{figure}
1.334 +\end{subfigure}
1.335 +\end{center}
1.336 +\vspace*{-0.5cm}
1.337 +\caption{\normalsize{Induced subgraph isomorphism on biological graphs}}\label{fig:bioIND}
1.338 +\end{figure}
1.339 +
1.340
1.341 \begin{figure}[H]
1.342 \vspace*{-2cm}
1.343 @@ -1090,75 +1129,10 @@
1.344 \end{subfigure}
1.345 \end{center}
1.346 \vspace*{-0.6cm}
1.347 -\caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioISO}
1.348 +\caption{\normalsize{Graph isomorphism on biological graphs}}\label{fig:bioISO}
1.349 \end{figure}
1.350
1.351
1.352 -\begin{figure}[H]
1.353 -\vspace*{-2cm}
1.354 -\hspace*{-1.5cm}
1.355 -\begin{subfigure}[b]{0.55\textwidth}
1.356 -\begin{figure}[H]
1.357 -\begin{tikzpicture}[trim axis left, trim axis right]
1.358 -\begin{axis}[title=Molecules IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.359 -=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.360 - west},scaled x ticks = false,x tick label style={/pgf/number
1.361 - format/1000 sep = \thinspace}]
1.362 -%\addplot+[only marks] table {proteinsOrig.txt};
1.363 -\addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark
1.364 - size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};
1.365 -\end{axis}
1.366 -\end{tikzpicture}
1.367 -\caption{In the case of molecules, the algorithms have
1.368 - similar behaviour, but VF2++ is almost two times faster even on such
1.369 - small graphs.} \label{fig:INDMolecule}
1.370 -\end{figure}
1.371 -\end{subfigure}
1.372 -\hspace*{1.5cm}
1.373 -\begin{subfigure}[b]{0.55\textwidth}
1.374 -\begin{figure}[H]
1.375 -\begin{tikzpicture}[trim axis left, trim axis right]
1.376 -\begin{axis}[title=Contact maps IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.377 -=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.378 - west},scaled x ticks = false,x tick label style={/pgf/number
1.379 - format/1000 sep = \thinspace}]
1.380 -%\addplot+[only marks] table {proteinsOrig.txt};
1.381 -\addplot table {Orig/ContactMaps.128.txt};
1.382 -\addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.383 - {VF2PPLabel/ContactMaps.128.txt};
1.384 -\end{axis}
1.385 -\end{tikzpicture}
1.386 -\caption{On contact maps, VF2++ runs in near constant time, while VF2
1.387 - Plus has a near linear behaviour.} \label{fig:INDContact}
1.388 -\end{figure}
1.389 -\end{subfigure}
1.390 -
1.391 -\begin{center}
1.392 -\vspace*{-0.5cm}
1.393 -\begin{subfigure}[b]{0.55\textwidth}
1.394 -\begin{figure}[H]
1.395 -\begin{tikzpicture}[trim axis left, trim axis right]
1.396 - \begin{axis}[title=Proteins IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.397 - =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.398 - west},scaled x ticks = false,x tick label style={/pgf/number
1.399 - format/1000 sep = \thinspace}] %\addplot+[only marks] table
1.400 - {proteinsOrig.txt}; \addplot[mark=*,mark size=1.2pt,color=blue]
1.401 - table {Orig/Proteins.256.txt}; \addplot[mark=triangle*,mark
1.402 - size=1.8pt,color=red] table {VF2PPLabel/Proteins.256.txt};
1.403 - \end{axis}
1.404 - \end{tikzpicture}
1.405 -\caption{Both the algorithms have linear behaviour on protein
1.406 - graphs. VF2++ is more than 10 times faster than VF2
1.407 - Plus.} \label{fig:INDProt}
1.408 -\end{figure}
1.409 -\end{subfigure}
1.410 -\end{center}
1.411 -\vspace*{-0.5cm}
1.412 -\caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioIND}
1.413 -\end{figure}
1.414 -
1.415 -
1.416 -
1.417
1.418
1.419 \subsection{Random graphs}
1.420 @@ -1168,7 +1142,7 @@
1.421 experiments, please see the top of each chart.
1.422 \subsubsection{Graph isomorphism}
1.423 To evaluate the efficiency of the algorithms in the case of graph
1.424 -isomorphism, connected graphs of less than 20 000 nodes have been
1.425 +isomorphism, random connected graphs of less than 20 000 nodes have been
1.426 considered. Generating a random graph and shuffling its nodes, an
1.427 isomorphism had to be found. Figure \ref{fig:randISO} shows the runtime results
1.428 on graph sets of various density.
1.429 @@ -1276,29 +1250,15 @@
1.430 \end{figure}
1.431
1.432
1.433 -
1.434 -
1.435 -
1.436 -
1.437 -
1.438 -
1.439 -
1.440 -
1.441 -Considering the graph isomorphism problem, VF2++ consistently
1.442 -outperforms its rival especially on sparse graphs. The reason for the
1.443 -slightly super linear behaviour of VF2++ on denser graphs is the
1.444 -larger number of nodes in the BFS tree constructed in
1.445 -Algorithm~\ref{alg:VF2PPPseu}.
1.446 -
1.447 \subsubsection{Induced subgraph isomorphism}
1.448 -This section provides a comparison of VF2++ and VF2 Plus in the case
1.449 +This section presents a comparison of VF2++ and VF2 Plus in the case
1.450 of induced subgraph isomorphism. In addition to the size of the large
1.451 graph, that of the small graph dramatically influences the hardness of
1.452 a given problem too, so the overall picture is provided by examining
1.453 small graphs of various size.
1.454
1.455 -For each chart, a number $0<\rho< 1$ has been fixed and the following
1.456 -has been executed 150 times. Generating a large graph $G_{large}$,
1.457 +For each chart, a number $0<\rho< 1$ has been fixed, and the following
1.458 +has been executed 150 times. Generating a large graph $G_{large}$ of an average degree of $\delta$,
1.459 choose 10 of its induced subgraphs having $\rho\ |V_{large}|$ nodes,
1.460 and for all the 10 subgraphs find a mapping by using both the graph
1.461 matching algorithms. The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1,
1.462 @@ -1610,7 +1570,7 @@
1.463 considered and the small graphs had proportionally few nodes ($\rho =
1.464 0.05$, or $\rho = 0.1$), then VF2 Plus produced some inefficient node
1.465 orders (e.g. see the $\delta=10$ case on
1.466 -Figure~\ref{fig:randIND10}). If these examples had been excluded, the
1.467 +Figure~\ref{fig:randIND10}). If these instances had been excluded, the
1.468 charts would have seemed to be similar to the other ones.
1.469 Unsurprisingly, as denser graphs are considered, both VF2++ and VF2
1.470 Plus slow slightly down, but remain practically usable even on graphs