Knowledge assessment in online platforms is widely based on multiple-choice questions (MCQs). In this paper we describe our proposal for a NLP-based system designed to support the management of large repositories of MCQs. Indeed, within large repositories of MCQs, it is common to have similar if not almost duplicated questions, and coping with them is a time consuming and error prone task. We propose an approach, based on Natural Language Processing (NLP), that i) computes the similarity between the items and ii) checks the similarity between the questions and, if available, the areas of the syllabus. The results of the analysis are also displayed in a graph (i.e. network) based view, providing a clear picture to the user.

Let G = (V, E) be a strongly connected directed graph. The edge connectivity λ of G is the minimum number of edges whose deletion leaves a graph that is not strongly connected. Computing the edge connectivity of a graph is a classical subject in graph theory, and is an important notion in several application areas, such as transportation, communication, production, scheduling, and power engineering. In this paper we explore the design space of efficient algorithms for computing the edge connectivity of a directed graph in practice. In particular, we present efficient implementations of Gabow's algorithm, which is based on matroid intersection and packing spanning trees, as well as algorithms based on recent “local search” algorithms for minimum-cut. We conduct a thorough empirical study to highlight the merits and weaknesses of each technique.

The visualization of large graphs in interactive applications, specifically on small devices, can make harder to understand and analyze the displayed information. We show as simple topological properties of the graph can provide an efficient automatic computation of features which improves the "readibility" of a large graph by a proper selection of the displayed information. The connectivity (existence of a path) is a very intuitive structural property of a network; in this paper we propose an approach to the visualization of a network based on connectivity and related concepts as effective tools for visual analysis. In particular, given a root vertex r and a target vertex t, it is possible to check at a glance if there are some dominators, i.e., mandatory vertices that are on every path from r to t. Furthermore, using a recent graph algorithm from Georgiadis and Tarjan [19], [20], by selecting a target vertex it is possible to see two distinct paths from r to t: the paths are vertex-disjoints if there are no dominators from r to t, otherwise the paths have only the dominators in common. We conclude by presenting, as a relevant case study that motivated our work, as this approach improves a personalized eLearning application. In a framework, presented in [27], for dynamic configuration of paths of learning activities for both individual and group education, we can add visual analysis capabilities for both the final user/learner, and for the administrator of a repository.

In this paper we discuss the use of Analytics in oii-web, an online programming contest training system. We first provide an overview of the challenges in training for programming contests. Then we discuss the data collected in these years using oii-web, a platform devoted to the training of students for the Italian Olympiads in Informatics (Olimpiadi Italiane di Informatica - OII), and analyze them comparing two distinct groups of users in two distinct platforms built on oii-web, one devoted to students and one to their teachers. Most notably, the two groups are more similar than one would expect when dealing with programming contest training.

A flow graph $G=(V,E,s)$ is a directed graph with a distinguished start vertex $s$. The dominator tree $D$ of $G$ is a tree rooted at $s$, such that a vertex $v$ is an ancestor of a vertex $w$ if and only if all paths from $s$ to $w$ include $v$. The dominator tree is a central tool in program optimization and code generation and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low-high order of $G$ is a preorder $δ$ of $D$ that certifies the correctness of $D$ and has further applications in connectivity and path-determination problems. In this paper, we first consider how to maintain efficiently a low-high order of a flow graph incrementally under edge insertions. We present algorithms that run in $O(mn)$ total time for a sequence of $m$ edge insertions in an initially empty flow graph with $n$ vertices.These immediately provide the first incremental certifying algorithms for maintaining the dominator tree in $O(mn)$ total time, and also imply incremental algorithms for other problems. Hence, we provide a substantial improvement over the $O(m^2)$ simple-minded algorithms, which recompute the solution from scratch after each edge insertion. We also show how to apply low-high orders to obtain a linear-time $2$-approximation algorithm for the smallest $2$-vertex-connected spanning subgraph problem (2VCSS). Finally, we present efficient implementations of our new algorithms for the incremental low-high and 2VCSS problems and conduct an extensive experimental study on real-world graphs taken from a variety of application areas. The experimental results show that our algorithms perform very well in practice.

Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly, not much has been investigated for directed graphs. In this article, we study 2-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices v and w are 2- edge-connected if there are two edge-disjoint paths from v to w and two edge-disjoint paths from w to v . This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the undirected case, those blocks do not correspond to the 2-edge-connected components of the graph. The main result of this article is an algorithm for computing the 2-edge-connected blocks of a directed graph in linear time. Besides being asymptotically optimal, our algorithm improves significantly over previous bounds. Once the 2-edge-connected blocks are available, we can test in constant time if two vertices are 2-edge-connected. Additionally, when two query vertices v and w are not 2-edge-connected, we can produce in constant time a “witness” of this property by exhibiting an edge that is contained in all paths from v to w or in all paths from w to v . We are also able to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has O ( n ) edges and maintains the same 2-edge-connected blocks as the input graph, where n is the number of vertices.

Graph connectivity is a fundamental concept in graph theory with numerous practical applications. Very recently, various notions of 2-connectivity in directed graphs (digraphs) have been introduced. In particular, 2-connectivity revealed to have a much richer and more complicated structure in directed graphs than in undirected graphs. In this paper we consider the computation of the 2-connected components and the 2-connected blocks of a digraph in practice, in the case of both edge and vertex connectivity. Specifically, we present efficient implementations of previously proposed and of new algorithms for computing the 2-vertex-connected components and the 2-vertex-connected blocks, the 2-edge-connected components and the 2-edge-connected blocks, and evaluate their performance experimentally on large digraphs taken from a variety of application areas. To the best of our knowledge, this is the first empirical study for these problems. Our extensive experimental study sheds light on the relative difficulty of computing these notions of 2-connectivity in digraphs in practice. Furthermore, our experimental results suggest that the 2-vertex- and 2-edge-connected components of digraphs that arise in many practical applications can be found efficiently, despite the fact that currently the best known asymptotical bound for their computation is O(mn).

Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study 2-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices v and w are 2-edge-connected if there are two edge-disjoint paths from v to w and two edge-disjoint paths from w to v. This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the undirected case, those blocks do not correspond to the 2-edge-connected components of the graph. The main result of this paper is an algorithm for computing the 2-edge-connected blocks of a directed graph in linear time. Besides being asymptotically optimal, our algorithm improves significantly over previous bounds. Once the 2-edge-connected blocks are available, we can test in constant time if two vertices are 2-edge-connected. Additionally, we also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-edge-connected blocks as the input graph, where n is the number of vertices.

Current route planning algorithms for public transport networks are mostly based on timetable information only, i.e., they compute shortest routes under the assumption that all transit vehicles (e.g., buses, subway trains) will incur in no delays throughout their trips. Unfortunately, unavoidable and unexpected delays often prevent transit vehicles to respect their originally planned schedule. In this paper, we try to measure empirically the quality of the solutions offered by timetabling routing in a real public transport network, where unpredictable delays may happen with a certain frequency, such as the public transport network of the metropolitan area of Rome. To accomplish this task, we take the time estimates required for trips provided by a timetabling-based route planner (such as Google Transit) and compare them against the times taken by the trips according to the actual tracking of transit vehicles in the transport network, measured through the GPS data made available by the transit agency. In our experiments, the movement of transit vehicles was only mildly correlated to the timetable, giving strong evidence that in such a case timetabled routing may fail to deliver optimal or even high-quality solutions.

The betweenness centrality of a node is a measure related to the number of shortest path the node is involved with. It is, indeed, a measure of the importance of the node in the network, and in the recent years has been used intensively for network analysis. The major drawback of this measure is its high computational cost, and thus in the literature several works appeared providing ways of approximating it, thus presenting a trade off between accuracy and speed. The articulation points of a connected network are the nodes whose removal disconnects the network, and the critical nodes are the articulation points of the network core, i.e. the subset of the network obtained by repeatedly pruning the nodes of low (fixed) degree. In [1] Ausiello et al. showed that, in ten years of samples of the Autonomous System (AS) Network, the removal of a single critical node from the network was able to affect hundreds of nodes, that were no longer connected to the main part of the AS Network.

The articulation points and bridges of a connected network are, respectively, the vertices and the edges whose removal disconnects the network. However, not all the articulation points (resp. bridges) are equal: from the graph theoretic perspective, there is no difference whether the removal of a vertex (resp. bridge) disconnects only one vertex from the rest of the network, or it cuts the network in two pieces. But in the monitoring of a huge network, it makes a difference. We present a real-time algorithm, analyzed in the (semi-)streaming model of computation, that is able to identify a core subset of the articulation points (resp. bridges), i.e. the ones whose removal has a big impact on the network: these are the critical nodes (resp. edges) of the network. We complement our work with an experimental evaluation of the algorithm against ten years of samples of the Autonomous System network, that confirms the effectiveness of our approach.

Network clustering is traditionally accomplished by relying just on the topology information, while a traffic-aware clustering approach has been recently proposed. The latter approach employs traffic matrices to take into account the intensity of the relationship between nodes. The extra effort needed to gather the traffic matrices is warranted if the composition of the clusters obtained in the traffic-based approach is significantly different from that obtained under the topology-based approach. In this paper we compare the outcomes of the two approaches, using the Rand Index as a similarity metric. For a variety of established clustering algorithms, and two large datasets, we show that the two approaches provide significantly different results, since the Rand Index lies far below one.

Abstract In this article, we present the first algorithm in the streaming model to characterize completely the biconnectivity properties of undirected networks: articulation points, bridges, and connected and biconnected components. The motivation of our work was the development of a real‐time algorithm to monitor the connectivity of the autonomous systems (AS) network, but the solution provided is general enough to be applied to any network. The network structure is represented by a graph, and the algorithm is analyzed in the datastream framework. Here, as in the on‐line model, the input graph is revealed one item (i.e., graph edge) after the other, in an on‐line fashion; but, if compared to traditional on‐line computation, there are stricter requirements for both memory occupation and per item processing time. Our algorithm works by properly updating a forest over the graph nodes. All the graph (bi)connectivity properties are stored in this forest. We prove the correctness of the algorithm, together with its space (O(nlog n), with n being the number of nodes in the graph) and time bounds. We also present the results of a brief experimental evaluation against real‐world graphs, including many samples of the AS network, ranging from medium to massive size. These preliminary experimental results confirm the effectiveness of our approach. © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012

A typical modern newspaper recognition system operates in distinct phases: i) page segmentation (also called page decomposition or zoning), that is the process of decomposing a page into its structural and logical units (called regions or zones), ii) region (or zone) labeling, where the previously identified units are labeled according to their types (title, text, images, and lines), iii) article identification (or tracking or clustering), in which all the units that belong to a single article are clustered together, and iv) read order identification, in which each item in an article is assigned its reading order inside the article. So far, in the literature, several works appeared describing algorithms and metrics for the first two phases, i.e. page segmentation and region labeling, that indeed play a crucial role in the whole process, however, few results focused on article identification, that is a difficult task mainly due to the rich and complex variety of newspapers layouts. In this paper we propose a methodology to evaluate news-papers article identification algorithms, our approach is based on well-established tools from graph theory: in particular, we reduce the newspaper article clustering problem to a specific graph clustering problem, that is therefore evaluated using the appropriate coverage and performance measures. The advantages of our approach are twofold: on one side, the proposed measures correctly detects that not all the errors are equals, i.e. some errors are worse than others, and the scores are assigned properly. On the other side, we show how to reverse the reduction, in order to exploit the large number of graph clustering algorithm available: indeed, given a graph clustering algorithm, to obtain a full working newspaper article identification algorithm we only need to define a similarity measure between units in the article. We provide some examples, using a specifically designed dataset. Finally, we would like to point out that both our dataset, together with its ground-truth base, and the software tool, that implements the proposed approach, are freely available.

The structural analysis is the very basic tool for understanding the properties of a network. In this paper we present a (customizable) tool, able to compute in real-time the most important connectivity properties of a network, modeled as an undirected graph: connected and biconnected components, articulation points and bridges. The algorithm underlying the tool has been theoretically analyzed in the (semi-)streaming model, and has been tested with graphs up to hundreds of millions nodes and billions edges. The tool, therefore, can be employed to monitor traffic flows in medium and large networks, at real-time, and detect possible anomalies. As an application, we provide results about the structural properties of ten years of samples of the Autonomous System network, obtained from the Univ. of Oregon Route Views project, that (once again) shows the ubiquitous presence of power-law distribution.

While network clustering is traditionally accomplished just relying on the topology of the network, the new traffic-aware clustering approach employs traffic matrices to take into account the intensity of the relationship between nodes. In the context of traffic-aware clustering we propose a new Evolutionary Clustering algorithm and compare it with the Spectral Filtering algorithm. We compare them using both the Modularity and the Traffic-aware Scaled Coverage metrics, and two real-world datasets, each made of 1000 traffic matrices, respectively from Abilene and Géant networks. Our experiments show that Evolutionary Clustering performs better on all traffic matrices, excepting a minor number of traffic matrices in the Abilene network when the Modularity metric is employed.

Network clustering is traditionally approached just relying on the topology of the network, and neglecting the information on the traffic intensity between the nodes. In this paper we propose traffic-aware clustering, whereby networks are clustered on the basis of their traffic matrices. We redefine two clustering metrics for the context of traffic matrices, and perform an exploratory analysis by comparing four well known algorithms against two real-world datasets, each made of 1000 traffic matrices, respectively from Abilene and Géant networks. The Spectral Filtering algorithm appears as the best performer. However, in the Géant network dataset the two metrics provide different rankings for the algorithms under examination, and Newman's algorithm can perform marginally better under one of the two metrics.

Communication-induced checkpointing protocols are mechanisms used to produce checkpoints and communication patterns which enjoy desirable properties, such as No-Z-Cycle (NZC). NZC guarantees that each checkpoint can be part of a global consistent checkpoint. It would be nice to define communication-induced checkpointing protocols that enforce NZC, adding a minimum number of checkpoints to remove all the Z-cycles from the distributed computation. In this paper, we prove that this is impossible by formulating the Minimum Z-Cycle Removal (MinZCR) problem and showing that there are no online competitive protocols for it. Moreover, we prove that the problem of enforcing NZC with an optimal number of checkpoints is difficult even if the whole input instance is known because its decision version is NP-complete. Finally, we also prove that MinZCR is difficult to approximate: it is APX-hard and this implies that no Polynomial Time Approximation Scheme exists for the problem.

In this article we present an experimental study of the properties of webgraphs. We study a large crawl from 2001 of 200M pages and about 1.4 billion edges, made available by the WebBase project at Stanford, as well as several synthetic ones generated according to various models proposed recently. We investigate several topological properties of such graphs, including the number of bipartite cores and strongly connected components, the distribution of degrees and PageRank values and some correlations; we present a comparison study of the models against these measures.Our findings are that (i) the WebBase sample differs slightly from the (older) samples studied in the literature, and (ii) despite the fact that these models do not catch all of its properties, they do exhibit some peculiar behaviors not found, for example, in the models from classical random graph theory.Moreover we developed a software library able to generate and measure massive graphs in secondary memory; this library is publicy available under the GPL licence. We discuss its implementation and some computational issues related to secondary memory graph algorithms.

Leonardo Web is a collection of tools to animate algorithms. Animations can be generated with a visual editor or directly as a trace of an algorithm's execution. They can be visualized via a small Java player, available as an applet or as a standalone application; the player supports bidirectional continuous and step-by-step execution. Furthermore the system allows to export the animations in several formats, including Macromedia Flash, Microsoft PowerPoint and animated GIF.In this paper we discuss the design issues of one of the component of the visual editor of Leonardo Web, called the Builder, that can be used to design an animation from scratch as well as to refine batch-generated ones.