Similarity metrics from social network analysis for content recommender systems

Abstract

Online judges are online systems that test solutions in programming contests and practice sessions. They tend to become large live repositories of problems, with hundreds, or even thousands, of problems. This wide problem statement availability becomes a challenge for new users who want to choose the next problem to solve depending on their knowledge. This is due to the fact that online judges usually lack meta information about the problems and the users do not express their own preferences either. Nevertheless, online judges collect a rich information about which problems have been attempted, and solved, by which users. In this paper, we consider all this information as a social network, and use social network analysis techniques for creating similarity metrics between problems that can be then used for recommendation.

Keywords

Online judges recommender systems social network analysis similarity metrics link prediction

1. Introduction

Online judges are online systems that test programs in programming contests and practice sessions [12]. They are able to compile and execute the code sent by users and deliver a verdict regarding its correctness according to the problem statement. Usually, execution time and memory consumption are restricted in order to force the users to look for efficient solutions. Examples of such systems are the UVa Online Judge (https://uva.onlinejudge.org) and Codeforces (http://codeforces.com/), to mention just two of them.

These systems are usually used for training on-site programming contests such as ACM-ICPC International Collegiate Programming Contest. Some of them are not mere problem repositories with automatic judges, but they also hold on-line contests that coincide with the publication of new problems. This way, users may practice with fresh problems and their final standing is reflected in different rankings managed by the system.

Moreover, most of them can even emulate past online and on-site contests for those users that could not participate in them. The user just manifests his intention of joining a past contest and the system starts a virtual contest for him. System displays problem statements and a ranking where the real submissions sent by the user are merged with submissions that were made by participants in the original contest.

For that reason, online judges are valuable resources for expert users who want to increase their performance on competitive programming. Unfortunately, these systems pay little or no attention to the newbies who are not biased by programming contests but just want to practice algorithms or data structures. Usually they are overwhelmed by the great amount of problems in the archive and they have no idea about which one they should try to solve next. The main reason is that online judges do not usually have any recommendation mechanism that guides those users. At most, they use the Global Ranking Method, which recommends the problem with more correct solutions in the system that the user has not resolved yet.

Having a recommender system on online judges is not easy, though. The users hardly ever rate problems, they do not express their preferences on their profiles and the information about the problem set is nonexistent or, at most, the problems are just tagged with the programming concepts that should be used in their solutions.

This paper introduces a technique to incorporate recommendation methods into these online judges. In order to do that, we characterize the user–problem interaction (which users have solved which problems) as an implicit social network. Then, we apply Social Network Analysis (SNA) techniques to extract information about the problems that will be used for a recommendation. In particular, we suggest the use of similarity-based link prediction techniques over the implicit user–problem interaction network to predict new links, which can be interpreted as a way to recommend problems to the users.

The experimental evaluation uses datasets from two different online judges with very different sizes and target audiences. The first one comes from Acepta el reto1

¹
https://www.aceptaelreto.com (Spanish only).

(Spanish translation of Take on the challenge), an online judge developed by some of the authors and focused mainly on CS students. The second dataset was extracted from the mentioned UVa Online Judge, probably the oldest and one of the most recognized programming contest training sites [18]. Our evaluation will point out that using link prediction similarity-based methods we are able to build recommender systems whose performance is comparable to those based on classical recommendation methods without the need of additional knowledge about the recommended content.

The remainder of this work runs as follows. Next section describes online judges in general and Acepta el reto and UVa online judge, in particular. It is followed by the description of how to characterize the user interaction of online judges as a social network. Section 4 describes the link prediction problem and enumerates the similarity metrics that we have used in our recommendation algorithms. Section 5 describes the experimental setup and the evaluation results. Then the related work is presented (Section 6) and, finally, a section with conclusions and future work closes this work.

2. Online judges

Online judges are software platforms designed to evaluate programming exercises. They were born due to the necessity of managing programming contests, but they soon became repositories of problems used in previous contests, providing competitive learning platforms to practice or, more recently, to help in curricular learning.

Online judge users choose the next problem to confront and then try to solve it submitting code solutions in one of the accepted languages. The system compiles the source code and runs it against a set of test cases, whose solutions are known by the judge. The output generated by the submitted solution is compared with the official solution and a verdict is provided.

From the system point of view, a submission can be seen as a tuple $(d, p, u, c, v)$ where d is the submission date, p and u are the problem and user respectively, c is the source code sent by the user, and v is the verdict emitted by the judge. Verdicts change slightly between online judges, but some of them are nearly universal:

AC (Accepted):

The solution submitted was correct because it produced the right answer and it did not exceed the time and memory usage thresholds.

PE (Presentation Error):

The solution was almost correct, though it failed to write the output in the exact required format (having an excess of blanks or line endings, for example).

CE (Compile Error):

The solution did not compile.

WA (Wrong Answer):

The program failed to write the correct answer for one or more test cases.

RTE (Runtime Error):

The program crashed during the execution (because of segmentation fault, floating point exception…).

TLE (Time Limit Exceeded):

The execution took too long and was canceled.

MLE (Memory Limit Exceeded):

The solution consumed too much memory and was aborted.

OLE (Output Limit Exceeded):

The program tried to write too much information. This usually occurs if the program enters an infinite loop.

All these verdicts are available in both online judges used in this paper, Acepta el reto and UVa online judges, although both of them have also some other less important verdicts not considered here.

Fig. 1.

Submissions (left) and cumulative submissions (right) in ACR online judge between 2014-02 and 2017-02, categorized by verdict.

Acepta el reto (ACR) is an online judge created by two of the authors in 2014. It focuses on Spanish students, who find it hard to use other judges (with English statements) because of the language barrier. Problems are tagged according to the programming concepts needed to solve them, the kind of data structures required and some other aspects. It accepts solutions programmed using C, $C + +$ and Java.

At the time of this writing (March 2017), ACR has nearly 5,000 registered users, 288 problems and more than 110,000 submissions. Figure 1 shows the number of submissions and its cumulative count per month, categorized by verdicts. The high number of submissions around March and December is due to a local contest organized by the authors. The online judge contains the problems of past editions and contestants use it for training purposes. Runtime errors (RTE) and all the verdicts related to limits exceeded (TLE, MLE and OLE) are grouped for clarity. Presentation Error and Accepted verdicts have been also joined together. After all, solutions evaluated as Presentation Error are close to being correct, usually just deleting extra blanks at the end of the lines. Although a bad token separator can ruin, for example, a network protocol, this is not the case for the kind of problems that online judges focus on.

Fig. 2.

Submissions (left) and cumulative submissions (right) in UVa online judge between 1997 and 2016, categorized by verdict.

Concerning UVa online judge, it has nearly 900,000 users, more than 4,700 problems and about 19 millions of submissions in C, $C + +$ , Java, Pascal and, more recently, Python. Figure 2 shows the submissions statistics for the UVa online judge during its long life. The real number of submissions is nearly twice that shown in the figure. The size of the UVa online judge is huge, and our crawling method cannot cope with problems with more than $2^{15}$ submissions, so they have been removed.

We carried out an exploratory analysis of both datasets in order to familiarize with the data contained in them and find relevant information for our recommendation purposes. We confirmed that it is common in both online judges that users who get a negative verdict try to fix their code and then resubmit it. We also discovered that it is quite usual to receive resubmissions of users who already solved the problem. In this case, users perform optimizations in their solutions in order to make them faster and climb positions in the system ranking. Sometimes, those optimizations are not correct and the new solutions are evaluated with a negative verdict. Nevertheless, from the point of view of the system, users solve a problem when they obtain their first Accepted verdict, and the problem remains solved despite the non-AC verdicts in subsequent submissions.

Table 1

Descriptive analysis of the submissions in ACR and UVa online judges: the original datasets (raw) and the filtered dataset (Accepted), where only the first AC–PE verdict for each user–problem submission is considered

	ACR		UVa

	Raw	Accepted	Raw	Accepted
Metric
# Submissions	110,364	18,067	9,676,911	3,331,003
# Problems	289	289	4,727	4,710
# Users	3,678	2,892	174,519	144,716
Density	0.10	0.02	0.012	0.005
Earliest submission	2014-02-17	2014-02-17	1997-05-06	1997-05-06
Latest submission	2017-02-13	2017-02-13	2017-02-06	2017-02-06
Time span	1,092 days	1,092 days	7,216 days	7,216 days
Problems
Maximum # submissions per problem	5,613	1,157	28,502	13,650
Median # submissions per problem	232	33	493	134
Average # submissions per problem	381.88	87.03	2047.16	707.219
Minimum # submissions per problem	8	1	2	1
# Problems with at least 10 submissions	276	229	4,653	4,306
# Problems with at least 50 submissions	216	29	4,233	3,270
# Problems with at least 100 submissions	146	96	3,830	2,629
Users
Maximum # submissions per user	2,576	249	15,276	4,705
Median # submissions per user	10	3	11	4
Average # submissions per user	30.01	6.84	55.45	23.02
Minimum # submissions per user	1	1	1	1
# Users with at least 5 submissions	2,415	801	114,791	61,310
# Users with at least 10 submissions	1,790	407	89,583	42,529
# Users with at least 20 submissions	1,198	145	64,105	27,371
Verdicts
# Submissions with AC–PE	36,824	18,067	3,511,647	3,331,003
# Submissions with CE	7,061	–	721,684	–
# Submissions with Runtime-Limit Error	31,924	–	1,696,643	–
# Submissions with Wrong Answer	33,443	–	3,710,439	–

For our recommendation purposes, all these resubmissions contribute to add noise to the dataset. Our recommendation is based on the relationship between users and problems and, from the point of view of a user, a problem can be:

Unattempted: the user did not submit any solution to that problem yet.

Attempted: the user submitted one or more solutions to the problem, but all of them were invalid.

Solved: the user submitted one or more solutions to the problem, and at least one of them was judged as Accepted.

The recommendation approach described in this paper works with the implicit social network created using the relationship between users and problems. In that sense, the key point is whether a user has solved a problem, not just attempted it. For this reason, we filter the datasets so only Accepted submissions are considered. Nevertheless, due to the proximity between AC and PE verdicts, they are considered synonymous. Table 1 provides a catalogue of descriptive statistics, as proposed in [4], about both versions of the datasets: the original (Raw) submission dataset and the filtered (Accepted) dataset.

3. User interactions as a social network

A social network is a group of individuals or entities that are related to each other, traditionally represented as a graph. In an online judge system, user–problem interactions can be abstracted and represented into a user–problem non-weighted bipartite network G, where nodes belong exclusively to one of two disjoint sets, the problem-set $P = {p_{1}, \dots, p_{m}}$ or the user-set $U = {u_{1}, \dots, u_{n}}$ . Therefore, we define an adjacency matrix $A = {a_{i j}}$ , where $a_{i j} = 1$ , if the user $u_{i}$ attempted to solve (or correctly solved, depending on the use of the matrix) the problem $p_{j}$ .

The network representation allows us to analyse the user–problem interactions that occurred in the online judge system using the methods and metrics defined by the Social Network Analysis field [8]. Link prediction is a technique used in social network analysis that aims to predict new links that might be formed between nodes in a future time or to predict missed links in the current network [15]. Then, problem recommendation in an online judge system can be viewed as a link prediction problem: given a graph that explicitly represents the interactions between users and problems, how can we predict new links between one user and other problems?

Instead of using a bipartite graph we will define a non-bipartite graph where the user–problem interactions will be transformed into implicit relationships among problems. To do that, we employ a mechanism called network projection, a process that aims to transform a bipartite graph into a non-bipartite one. This transformation is depicted in Fig. 3.

Fig. 3.

Illustration (from Wikipedia) of a bipartite network (a), as well as its X projection (b) and Y projection (c).

We employ a network projection in order to create the Problem-projection graph, a network containing only Problem nodes where two nodes are connected if they have at least one common user that solved both problems. To avoid losing information from the original network about user interactions we use a simple weighting method, where an edge $(p_{i}, p_{j})$ is weighted with the number of different users that attempted to solve both $p_{i}$ and $p_{j}$ problems. This way, the problem recommendation task can be reformulated as: given the problems resolved by a user, how can we predict new links between these problems and future interesting problems? Our proposal consists on reusing the metrics employed by similarity-based link prediction methods for recommending purposes, as we will describe in the next section.

4. Link prediction and similarity metrics

Link prediction algorithms are a family of graph-based algorithms that aims to predict new links that might be formed between nodes in a future time or to predict missed links in the current network [15]. The alternative approaches to predict these links are the following [24]:

Similarity-based methods, which compute the proximity or similarity between pairs of unconnected nodes in order to predict new links.

Learning-based methods, which use machine learning algorithms to classify non-connected pairs of nodes as positive or negative potential links.

Similarity metrics employed in the former approach can be also classified into:

Node-based metrics, which compute the similarity using node attributes.

Neighbour-based metrics, which compute the similarity using each node neighbourhood.

Path-based metrics, which do not only use node neighbours but also the paths between two nodes.

Random walk-based metrics, which use transition probabilities from a node to its neighbours and to non-connected nodes in order to simulate social interactions.

We will focus on similarity-based methods and we will employ a variation of these metrics in order to calculate a similarity score that expresses how similar two problems are in the graph according to the solutions submitted for these problems. These scores will be employed in the recommendation process for suggesting similar problems to the ones that a user successfully solved.

Before we describe the specific similarity metrics used in our study, first we need to introduce some notation:

$N (x)$ represents the neighbours of node x.

$| N (x) |$ represents the number of neighbours (or node degree) of node x.

$WD (x)$ represents the weighted node degree of node x, which means the sum of the weights in the edges directly connected to node x.

$A_{x y}$ represents the weight of the edge that links node x and node y; in our context, this weight expresses the number of users that have resolved both problem x and y.

Most of these metrics are detailed in [13,24] and some of them are defined in two different flavours: unweighted and weighted metrics [16]. Note that most of these metrics are not normalized and produce similarity scores that are not between 0 and 1. This is not a problem in our approach, however, because we only use the similarity scores to create a similarity ranking between problems.

Next, we describe the similarity metrics used in our study.

4.1. Edge weight

This simple metric measures the similarity between two nodes as the weight of the edge that links them. Two problems are more similar if there are more users that solved both. No connection between two nodes is represented by $A_{x y} = 0$ . Although an unweighted version of this metric exists ( $A_{x y} = 1$ if the edge exists; 0 otherwise), we have not used it because it cannot be employed as a similarity metric. $\begin{matrix} EW (x, y) = A_{x y} \end{matrix}$

4.2. Common neighbours

This metric measures the similarity between two nodes as the number of neighbours they have in common. The rationale behind this metric is that the greater the intersection of the neighbour sets of any two nodes, the greater the chance of future association between them. This metric has a weighted version (WCN). $\begin{array}{l} CN (x, y) = | N (x) \cap N (y) | \\ WCN (x, y) = \sum_{z \in N (x) \cap N (y)} A_{x z} + A_{y z} \end{array}$

4.3. Jaccard neighbours

This is an improvement of $CN (x, y)$ as it measures the number of common neighbours of x and y compared with the number of total neighbours of x and y. This metric does not have an equivalent weighted version. $\begin{matrix} JN (x, y) = \frac{| N (x) \cap N (y) |}{| N (x) \cup N (y) |} \end{matrix}$

4.4. Adar/Adamic

This metric considers evaluating the likelihood that a node x is linked to a node y as the sum of the number of neighbours they have in common. This metric also measures the intersection of neighbour-sets of two nodes in the graph, but emphasizing in the smaller overlap. This metric also defines a weighted version (WAA). $\begin{array}{l} AA (x, y) = \sum_{z \in N (x) \cap N (y)} \frac{1}{log | N (z) |} \\ WAA (x, y) = \sum_{z \in N (x) \cap N (y)} \frac{A_{x z} + A_{y z}}{log (1 + WD (z))} \end{array}$

4.5. Preferential attachment

This metric is based on the consideration that nodes create links, with higher probability, with those nodes that already have a larger number of links. The similarity between nodes x and y is calculated as the product of the degree of the nodes x and y, so the higher the degree of both nodes, the higher is the similarity between them. This metric has the drawback of leading to high similarity values for highly connected nodes to the detriment of the less connected ones in the network. The weighted version (WPA) is an improvement of the previous one, where the edge weights are considered when computing the degree of nodes x and y. $\begin{array}{l} PA (x, y) = | N (x) | \cdot | N (y) | \\ WPA (x, y) = WD (x) \cdot WD (y) \end{array}$

5. Experimental setup and evaluation results

The absence of user ratings and the very shallow description of the problems make very difficult and ineffective the use of classical approaches based on collaborative filtering or content-based techniques. For this reason, in this section we evaluate the performance of previous similarity-based link prediction metrics to recommend new problems to the online judge users based on the problems that those users solved before.

For this evaluation, we developed a recommender system that performs recommendations based on the problem-projection graph described in Section 3. In particular, given a problem already solved by a user, the system recommends the k most similar problems according to the problem-projection graph and the similarity metric chosen.

We used two different datasets in this evaluation: ACR and UVa. As detailed before, both datasets differ in their size: number of users, submissions and problems. Since the UVa dataset contains several times more problems and users than ACR, we expect that the UVa domain will be a harder challenge that will test the scalability of our approach.

For both datasets we follow the next steps:

We select a particular timestamp t to split the submission dataset into two sets for training and evaluation. The training set contains the submissions made before time t and we use it to create the problem–problem graph and compute the similarity matrix between problems. The evaluation set contains the submissions made after time t and it is used to validate the recommendations.

Using the training set, we build the projection graph, where nodes represent problems and edges between nodes represent that at least one user solved both problems – a user submission achieved an accepted (AC) or a presentation error (PE) verdict in both problems. Edge weights correspond to the number of users who solved both problems. Due to the high density of the projection graph, we filter the edges whose weight is below a defined threshold.

Using the problem–problem graph we compute the problem similarity matrix for each similarity metric involved in the evaluation.

We select the users to whom we are going to recommend new problems. In order to evaluate the recommendations provided to those users at time t, we require that those users have solved a minimum number of problems before t and have attempted a minimum number of problems after time t. The problems solved before t will be the input for the recommender system and the set of problems attempted after t will be used to validate the recommendations.

Finally, the recommendations are evaluated using the following standard evaluation metrics for recommender systems [9,17,22]:

Precision, Recall and F-Score in top k recommendations.

At least one hit (1-hit): ratio of recommendations in which at least one recommended problem was attempted by the user. It corresponds to the metric Success@k with a success condition of guessing right at least one problem.

Mean Reciprocal Rank (MRR): it evaluates the quality of a ranked list of recommendations based on the position of the first correct item. Since we only provide one list of recommendations per user, the MRR can be computed as follows: $\begin{matrix} MRR = \frac{1}{{rank}_{i}} \end{matrix}$ where ${rank}_{i}$ is the position of the first correct item.

5.1. ACR evaluation

Table 2
Evaluation results by similarity metrics with $k = 3$ for ACR dataset

Similarity Precision Recall F-Score 1-hit MRR

Adar/Adamic (AA) 0.135 0.007 0.013 0.305 0.201

Common Neighbours (CN) 0.132 0.007 0.013 0.299 0.198

Edge Weights (EW) 0.189 0.016 0.027 0.418 0.296

Jaccard Neighbours (JN) 0.137 0.007 0.013 0.312 0.205

Preferential Attachment (PA) 0.137 0.007 0.012 0.301 0.202

Weighted Adar/Adamic (WAA) 0.142 0.007 0.013 0.316 0.214

Weighted Common Neighbours (WCN) 0.140 0.007 0.013 0.315 0.214

Weighted Preferential Attachment (WPA) 0.147 0.007 0.013 0.315 0.217

Similarity	Precision	Recall	F-Score	1-hit	MRR
Adar/Adamic (AA)	0.135	0.007	0.013	0.305	0.201
Common Neighbours (CN)	0.132	0.007	0.013	0.299	0.198
Edge Weights (EW)	0.189	0.016	0.027	0.418	0.296
Jaccard Neighbours (JN)	0.137	0.007	0.013	0.312	0.205
Preferential Attachment (PA)	0.137	0.007	0.012	0.301	0.202
Weighted Adar/Adamic (WAA)	0.142	0.007	0.013	0.316	0.214
Weighted Common Neighbours (WCN)	0.140	0.007	0.013	0.315	0.214
Weighted Preferential Attachment (WPA)	0.147	0.007	0.013	0.315	0.217

We used the date 2015-08-16 to split the ACR dataset into two different subsets for training and evaluation. This date was chosen because it was in the middle of the submission period analysed (2014-02-17 to 2017-02-13). It is worth noting that this division does not imply that the training and evaluation dataset have the same size, due to the evolution of the number of submissions along the online judge lifetime. In fact, in order to split the submissions into two sets with approximately the same size, we should have chosen a date around 2016-03-14.

Next we created a problem-projection graph with 157 nodes and 7,899 edges, and a density of 32.05% after filtering the edges with $weight < 5$ , i.e. only connecting problems solved simultaneously by at least 5 users. This was necessary because the unfiltered graph had a density close to 100%. For the evaluation process, we selected the users who had solved at least 5 different problems before 2015-08-16 and submitted at least 5 different problems after that day (no matter the status that they achieved). Only 42 users fulfilled these constraints. However, we performed 1,143 recommendations using the problems solved by these users and each different similarity metric. Table 2 summarizes the results of the evaluation recommending 3 problems each time ( $k = 3$ ) and computing the average values for all those users.

Fig. 4.

Evolution of the precision, 1-hit and MRR metrics for Edge Weights similarity according to the minimum number of submissions required from a user in order to perform a recommendation.

We can extract some interesting conclusions from these results. First, the Precision, 1-hit and MRR values of the Edge Weights performs the best results and dominates all the other similarities in every evaluation metric. Edge Weights obtains a precision value of 18.9%, 1-hit of 41.8% and MRR of 29.6% recommending only 3 problems to the user, far from the next best similarity metric. The weighted versions of the similarity metrics seem to work better that the ones without weights.

Recall (and therefore F-Score) values are really small, but this fact can be explained because we compare a list of 3 recommendations with all the problems the user attempted to solve after the split time. For example, if we increase the number of recommendations to $k = 50$ the recall of Edge Weights increases significantly to 13%. However, we think that it does not make sense to recommend so many problems to a user in an online judge. Our intuition is that 3–5 problems is a good number of recommendations, but an evaluation with real users is needed in order to prove this hypothesis.

Fig. 5.

Precision, 1-HIT and MRR evolution when increasing the number of recommended problems for ACR dataset.

The number of problems that a user has solved affects the quality of the recommendations. This problem is known as the cold start problem [20] and it is related to recommendations for novel users or new items. Figure 4 shows the precision, 1-hit and MRR values for the Edge Weights similarity metric when we recommend problems to users with a minimum number of problems solved. The results improve as long as more information is available about the user (in this case in terms of the problems already solved), and we can provided better recommendations. The same effect occurs with the other similarity metrics.

Figure 5 shows the evolution of the precision, 1-hit and MRR metrics when we increase the number of recommendations (parameter k) from 1 to 10. For the sake of simplicity, we have removed the non-weighted similarity metrics CN, AA and PA from the figure because they always achieve worse results than the weighted versions WCN, WAA and WPA. As we expected, the precision decreases slowly because the last recommended problems are usually not as good as the first ones (their similarity is smaller). The trade off between the quality of recommendations and the number of choices available to the users is not easy to decide, and we will have to perform some tests with real users to adjust it. On the other hand, the probability of guessing right at least one problem increases as we make more recommendations. The same effect occurs with MRR, which takes into account the position of the relevant problem in the recommendation list. However, the growth slows down for lists with more than 5 elements. For every value of k, Edge Weights dominates all the other similarities.

5.2. UVa evaluation

The evaluation with the UVa dataset imposes a harder computation process due to the size of the dataset. For this reason, the training and evaluation sets have been reduced, including only submissions during the six months previous and after the split timestamp, which, in this case, was 2007-03-23. Despite this shrinkage, the graph created for the recommender system contains 1,433 nodes (different problems) and 232,163 edges, after the edge weight filtering process with a weight threshold value of 10. Additionally, the selection of users to whom perform recommendations was made increasing the minimum number of problems solved before the split timestamp and problems attempted after the split date. This way, 666 users fulfilled these requirements and the evaluation was executed with a total of 35,816 recommendations. Table 3 summarizes the results of the evaluation using $k = 3$ and computing the average values for all those users.

Table 3
Evaluation results by similarity metrics with $k = 3$ for UVa dataset

Similarity Precision Recall F-Score 1-hit MRR

Adar/Adamic (AA) 0.083 0.001 0.002 0.194 0.134

Common Neighbours (CN) 0.088 0.002 0.003 0.206 0.149

Edge Weights (EW) 0.119 0.005 0.009 0.272 0.183

Jaccard Neighbours (JN) 0.082 0.001 0.002 0.186 0.127

Preferential Attachment (PA) 0.078 0.001 0.002 0.179 0.121

Weighted Adar/Adamic (WAA) 0.073 0.001 0.003 0.167 0.115

Weighted Common Neighbours (WCN) 0.073 0.001 0.003 0.167 0.114

Weighted Preferential Attachment (WPA) 0.061 0.007 0.002 0.144 0.009

Similarity	Precision	Recall	F-Score	1-hit	MRR
Adar/Adamic (AA)	0.083	0.001	0.002	0.194	0.134
Common Neighbours (CN)	0.088	0.002	0.003	0.206	0.149
Edge Weights (EW)	0.119	0.005	0.009	0.272	0.183
Jaccard Neighbours (JN)	0.082	0.001	0.002	0.186	0.127
Preferential Attachment (PA)	0.078	0.001	0.002	0.179	0.121
Weighted Adar/Adamic (WAA)	0.073	0.001	0.003	0.167	0.115
Weighted Common Neighbours (WCN)	0.073	0.001	0.003	0.167	0.114
Weighted Preferential Attachment (WPA)	0.061	0.007	0.002	0.144	0.009

Fig. 6.

Precision, 1-HIT and MRR evolution when increasing the number of recommended problems for UVa dataset.

The evaluation with the UVa dataset confirms that the Edge Weights metric achieves the best results in Precision, 1-hit and MRR values. However, the values are significantly lower than the ones obtained in the ACR dataset recommending only 3 problems. Even when the number of recommended problems grows, the results remain below the ACR dataset figures. Additionally, the differences between the weighted and the non-weighted versions flip and in most of cases the non-weighted metrics outperform the weighted versions. We suppose that the density in the UVa graph undermines the evaluation results with the weighted metrics. To prove that, we revisited the ACR experiment creating the graph without filtering the edges and filtering the edges with $weight < 3$ . In both cases, we obtained better results using the weighted metrics. These results require a deeper study of the causes, and as part of the future work, we would like to investigate the inclusion of other edge filtering algorithms that enhance the information provided by the edges, like the backbone extraction method [23].

The analysis of the minimum number of submissions required and the cold start problem was omitted for this dataset. Finally, Fig. 6 shows the evolution of the precision, 1-hit and MRR metrics when we increase the number of recommendations (parameter k) from 1 to 10 in UVa dataset. For the sake of simplicity, we plot the evolution for Edge Weights and the unweighted metrics. As occurred with ACR dataset, 1-hit and MRR metrics increase as long as the number of recommended problems grows. This growth decreases in MRR for recommendations with more than 5 elements. However, the precision remains nearly constant for values of $k > 5$ . As in the other dataset, Edge Weights dominates all the other similarities for every k value.

6. Related work

Online judges are online repositories that store large amounts of programming exercises. These repositories traditionally suffer the problem of how to find resources that best match the user’s knowledge or his/her preferences. Recommendation systems help users in this task recommending items similar to those a user has liked in the past [19]. Similarity is therefore one of the most important metrics in these systems.

Some recommendation approaches that aim to suggest resources apply collaborative filtering, a technique that imposes that the user must rate the resources in order to find similar preferences [7]. Systems like CoFind [6], CYCLADES [2] or ISIS [5] are examples of online repositories that use collaborative technique engines. Commonly, online judges like ACR hardly ever provide mechanisms to rate problems so these techniques cannot be applied. Our approach does not need explicit ratings but it uses the implicit results (attempted-accepted) in user submissions, which represent the interactions among users and problems in the online judge.

On the other hand, content-based techniques require descriptions of the item characteristics and user profiles that describe the interests of that user [11]. These techniques can be enhanced with deeper knowledge about the resources. The work in [21] describes a knowledge-intensive approach for recommending learning objects in the computer programming domain. The educational resources are tagged and indexed using an ontology that provides knowledge about the similarity between the concepts that represent the domain topics. Most of online judges only tag their resources with some metadata about the type of the previous knowledge needed to solve it, so we think that these techniques are not suitable in the online judge system context.

Other authors consider that the process of recommending items to users can be considered as a link prediction problem in the user–item bipartite networks [3]. For this reason, we have reviewed some literature in the use of link prediction applied in recommender systems, concentrating our work on the similarity-based methods, which employ different similarity metrics in order to predict new links. Liben-Nowell and Kleinberg [13] systematically compared some neighbour, path and random walk based node similarity indices for link prediction problem in co-authorship networks. These algorithms have been also applied in the user–product bipartite graphs in recommender systems and its performance has been evaluated with a Flickr dataset, outperforming collaborative filtering methods in some cases [3]. The work in [10] also proposes bipartite graph-based algorithms to analyse user–item interactions in order to alleviate the data sparsity problem in collaborative filtering recommenders. They compare CN, JN, AA, PA and two path-based similarity metrics using a book sales dataset and the results show that both path-based and neighbour-based approaches can significantly outperform the standard user-based and item-based algorithms.

Most of the studies on link prediction focus on unweighted networks but ignore the naturally existed link weights. Proximity between nodes can be estimated better by using both graph proximity measures and the weights of existing links. The work in [16] proposed a simple way to extend similarity metrics for binary networks to weighted metrics. However, the latter performed even worse in several real networks. For this reason they introduced a free parameter to control the relative contributions of weak ties to the similarity measure. The experimental study highlighted that the contributions of weak ties can enhance the prediction accuracy in some networks, suggesting that weak ties are not as weak as their weights show.

Other research works transform bipartite graphs into non-bipartite graphs using projections. Our work projects the graph and weigh the edges in a straightforward way using the number of users that resolved a pair of problems. However, this is not the only way to weigh the edges. The work in [25] details a two-step weighting method and a recommendation algorithm that outperforms classical collaborative filtering algorithms in Movielens dataset.

Finally, several works aggregate similarity based methods with another approaches in order to enhance the recommendation. [1] proposes a hybrid similarity measure that combines network similarity with node profile similarity. Profile similarity compares personal data stored in the profile items associated with the users from two different social network. Other works describe alternative link prediction methods based on social theory-based metrics, which enhance well-known neighbour-based metrics with node centrality measures like betweenness, closeness or node degree [14].

7. Conclusions and future work

Online judges are online repositories with hundreds or even thousands of programming exercises. This wide problem availability becomes a challenge for new users who want to choose the next problem to solve depending on their programming knowledge. In some online judges, such as ACR, problems are categorized with semantic labels regarding the programming concepts involved in their solutions. Unfortunately, these labels only describe very general concepts and they are usually not enough for novel users who wants to choose a problem. Besides, most online judges do not even provide these tags.

This problem could be mitigated with the presence of some type of recommendation mechanism to guide those users. Unfortunately, recommender systems are quite uncommon in online judges because users hardly ever rate the problems, they do not express their preferences on their profiles and the meta-information about the problems is nonexistent or very superficial. For these reasons, it is very difficult and ineffective to use classical approaches based on collaborative filtering or content-based techniques to recommend new problems to specific users.

Online judges, however, collect rich records describing which users have solved or tried to solve which problems. In fact, when the submitted solution is not correct, the judge produces different verdicts describing different types of errors. In this work, we consider those user–problem interactions as a social network and we use social network analysis techniques, such as the similarity-based link prediction, for creating similarity metrics between problems. This way, the information regarding which problems are related or similar to each other emerges automatically from the daily use of the system. Our recommendation system takes advantage of this information to recommend similar problems to the ones the user has already solved in the past.

We have represented the user interactions as a problem–problem graph in which two problems are connected by a stronger tie as long as more users solve both problems. Next, we have evaluated the performance of different similarity metrics based on the graph structure to recommend interesting problems to users from two different online judges: ACR and UVa. The analysis has shown that the Edge Weights metric provides the best results consistently in both datasets. However, we must take into account that this similarity metric relies on the existence of an edge between two problem nodes and, therefore, it is not useful to find new relationships between currently unrelated nodes. Note that this situation occurs every time a new problem is added to the judge. We should investigate on feasible solutions to this problem. Additionally, we have found that the problem–problem graph density reduces the quality of the recommendations. For this reason, as part of the future work we would like to include new edge filtering methods to reduce the graph density but preserving the valuable information provided by the edge weights.

The research trend in the link prediction problem is growing and the number of measures and methods employed in this field increases quickly. We are confident that the use of these new similarity measures and approaches to recommend problems in online judges will achieve better results in the short term.

In this work, we have proposed a problem-based approach which recommends the most similar problems to the ones that a user solved before. However, as collaborative filtering proposes, the recommendation process can be reformulated as finding users similar to the current one, in order to recommended the problems solved by these users but not already attempted by the current user. We want to define this new approach and compare the results obtained by both alternatives.

Finally, this work only describes some theoretical recommendation results based on what the user did in two online judges that do not provide any type of recommendation mechanism. That is, maybe some of our recommendations are good but in the evaluations we consider them wrong because the users did not try to solve those problems. In the future, we plan to incorporate our recommendation approach in the ACR judge and carry out some A/B evaluations with users in order to test if these results are aligned with reality

Footnotes

Acknowledgements

This work was supported by Universidad Complutense de Madrid (Group 910494) and Spanish Committee of Economy and Competitiveness (TIN2014-55006-R).

References

C.G.

Akcora,

Carminati and

Ferrari, User similarities on social networks, Social Network Analysis and Mining3(3) (2013), 475–495. doi:10.1007/s13278-012-0090-8.

Avancini and

Straccia, User recommendation for collaborative and personalised digital archives, International Journal of Web Based Communities1(2) (2005), 163–175. doi:10.1504/IJWBC.2005.006061.

Chiluka,

Andrade and

Pouwelse, A link prediction approach to recommendations in large-scale user-generated content systems, in: Advances in Information Retrieval, Springer, 2011, pp. 189–200. doi:10.1007/978-3-642-20161-5_19.

Dooms,

Bellogín,

De Pessemier and

Martens, A framework for dataset benchmarking and its application to a new movie rating dataset, ACM Trans. Intell. Syst. Technol.7(3) (2016), 41:1–41:28. doi:10.1145/2751565.

Drachsler,

H.G.K.

Hummel,

Van den Berg,

Eshuis,

Waterink,

Nadolski,

A.J.

Berlanga,

Boers and

Koper, Effects of the isis recommender system for navigation support in self-organised learning networks, Educational Technology & Society12(3) (2009), 115–126.

Dron,

Mitchell,

Siviter and

Boyne, Cofind – An experiment in n-dimensional collaborative filtering, Journal of Network and Computer Applications23(2) (2000), 131–142. doi:10.1006/jnca.2000.0105.

M.D.

Ekstrand,

J.T.

Riedl,

J.A.

Konstanet al., Collaborative filtering recommender systems, Foundations and Trends® in Human–Computer Interaction4(2) (2011), 81–173. doi:10.1561/1100000009.

Furht, Handbook of Social Network Technologies and Applications, Springer Science & Business Media, 2010.

J.L.

Herlocker,

J.A.

Konstan,

L.G.

Terveen and

J.T.

Riedl, Evaluating collaborative filtering recommender systems, ACM Transactions on Information Systems (TOIS)22(1) (2004), 5–53. doi:10.1145/963770.963772.

10.

Huang,

Li and

Chen, Link prediction approach to collaborative filtering, in: Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries, ACM, 2005, pp. 141–142.

11.

Jannach,

Zanker,

Felfernig and

Friedrich, Recommender Systems: An Introduction, Cambridge University Press, 2010.

12.

Kurnia,

Lim and

Cheang, Online judge, Comput. Educ.36(4) (2001), 299–315. doi:10.1016/S0360-1315(01)00018-5.

13.

Liben-Nowell and

Kleinberg, The link-prediction problem for social networks, Journal of the American Society for Information Science and Technology58(7) (2007), 1019–1031. doi:10.1002/asi.20591.

14.

Liu,

Hu,

Haddadi and

Tian, Hidden link prediction based on node centrality and weak ties, EPL (Europhysics Letters)101(1) (2013), 18004. doi:10.1209/0295-5075/101/18004.

15.

Lü and

Zhou, Link prediction in complex networks: A survey, Physica A: Statistical Mechanics and Its Applications390(6) (2010), 1150–1170. doi:10.1016/j.physa.2010.11.027.

16.

Lü and

Zhou, Link prediction in weighted networks: The role of weak ties, Europhysics Letters89(1) (2010), 18001. doi:10.1209/0295-5075/89/18001.

17.

M.J.

Pazzani, A framework for collaborative, content-based and demographic filtering, Artif. Intell. Rev.13(5–6) (1999), 393–408. doi:10.1023/A:1006544522159.

18.

M.Á.

Revilla,

Manzoor and

Liu, Competitive learning in informatics: The UVa online judge experience, in: A New Learning Paradigm: Competition Supported by Technology,

Verdú,

R.M.

Lorenzo,

M.Á.

Revilla and

L.M.

Regueras, eds, Sello Editorial, 2010, pp. 63–89.

19.

Ricci,

Lior and

Shapira, eds, Recommender Systems Handbook, Springer, 2015.

20.

V.A.

Rohani,

Z.M.

Kasirun,

Kumar and

Shamshirband, An effective recommender algorithm for cold-start problem in academic social networks, Mathematical Problems in Engineering2014 (2014).

21.

Ruiz-Iniesta,

Jimenez-Diaz and

Gomez-Albarran, A semantically enriched context-aware OER recommendation strategy and its application to a computer science OER repository, IEEE Trans. on Educ.57(4) (2014), 255–260. doi:10.1109/TE.2014.2309554.

22.

Said and

Bellogín, Comparative recommender system evaluation, in: Proceedings of the 8th ACM Conference on Recommender Systems – RecSys’14, 2014, pp. 129–136.

23.

M.Á.

Serrano,

Boguná and

Vespignani, Extracting the multiscale backbone of complex weighted networks, Proceedings of the National Academy of Sciences106(16) (2009), 6483–6488. doi:10.1073/pnas.0808904106.

24.

Wang,

B.W.

Xu,

Y.R.

Wu and

X.Y.

Zhou, Link prediction in social networks: The state-of-the-art, Science China Information Sciences58(1) (2014), 1–38. doi:10.1007/s11432-014-5226-1.

25.

Zhou,

Ren,

Medo and

Y.C.

Zhang, Bipartite network projection and personal recommendation, Physical Review E – Statistical, Nonlinear, and Soft Matter Physics76(4) (2007), 1–7.

Similarity metrics from social network analysis for content recommender systems

Abstract

Keywords

1. Introduction

1 https://www.aceptaelreto.com (Spanish only).

4.1. Edge weight

4.2. Common neighbours

4.3. Jaccard neighbours

4.4. Adar/Adamic

4.5. Preferential attachment

5. Experimental setup and evaluation results

5.1. ACR evaluation

7. Conclusions and future work

Footnotes

Acknowledgements

References

¹
https://www.aceptaelreto.com (Spanish only).