# Nonparametric test to compare link prediction algorithms

I have some experimental data, and I want to use a non-parametric test to verify my results. I am considering link-prediction on complex networks.

I have a complex network $N$ and an algorithm/model $A$ which finds structure in $N$. I then remove some of the edges in $N$, first $10\%$, then $30\%$ up to $90\%$. For each of these states of $N$, I use $A$ to infer the structure, and then compute and AUC-score. I repeat this procedure 3 times, so I get a total of 15 scores.

Now I take a new algorithm $A'$, which is a modification of $A$, and perform the same tests for $A'$. I now have 30 scores, 15 for $A$, and 15 for $A'$.

     10%   30%   50%   70%   90%
A1    x     x     x     x     x
A2    x     x     x     x     x
A3    x     x     x     x     x
A'1   x     x     x     x     x
A'2   x     x     x     x     x
A'3   x     x     x     x     x


Now I want to use a non-parametric test (probably a rank-sum test), to verify that $A$ is better at inferring structure in the networks. How do I go about doing this?

I am using MATLAB for my experiments, so a call to ranksum($x,y$) is the solution to "how to do the test". What I am looking for here, is the arguments $x,y$, and if there are any things I need to consider about independence?

There seem to be two obvious possibilities for the input: $$x = [A_1 (10\%), A_2 (10\%), A_3 (10\%), A_1 (30\%), \ldots , A_3 (90\%)]$$ $$y = [A'_1 (10\%), A'_2 (10\%), A'_3 (10\%), A'_1 (30\%), \ldots , A'_3 (90\%)]$$ or $$x = [A_1 (10\%), A_1 (30\%), \ldots, A_1 (90\%), A_2 (10\%), \ldots, A_3 (90\%)]$$ $$y = [A'_1 (10\%), A'_1 (30\%), \ldots, A'_1 (90\%), A'_2 (10\%), \ldots, A'_3 (90\%)]$$

Are any of these correct, and if only one of them, why?

• As stated in the question, the $10\%$ refers to removing 10 percent of the edges from the network. Making $A$ into $A'$ does not take time and energy, actually $A'$ is just a simplification of $A$. – utdiscant May 18 '12 at 20:22
• To answer your questions: They are removed at random. $A'$ can be viewed as a model nested in $A$. I see your point about the weight of each outcome. I am interested in "proving" that $A$ in general, does not outperform $A'$, and there does not seem to be a most important percentage to consider. – utdiscant May 18 '12 at 20:52