Search

In this paper, we describe the challenges in the realization of a semantic search engine, suited to help law enforcements in the fight against the online drug marketplaces, where new psychoactive substances are sold. This search engine has been developed under the Semantic Illegal Content Hunter (SICH) Project, with the financial support of the Prevention of and Fight Against Crime Programme ISEC 2012 European Commission. The SICH Project-specific objective is to develop new strategic tools and assessment techniques, based on semantic analysis on texts, to support the dynamic mapping and the automatic identification of illegal content over the Net. In particular, a Web search engine can be roughly divided into three main components: (a) the crawler that is in charge of collecting the Web pages to be indexed, (b) the indexer that parses and stores the collected data and (c) the query processor that interacts with the user parsing a query and returning the relevant document; in this paper, we detail each of these components of the SICH search engine, highlighting the differences from a traditional Web search engine. [ABSTRACT FROM AUTHOR]

Just as ordinary hypergraphs are a generalization of graphs, directed hypergraphs (DH) are a natural generalization of digraphs. A DH consists of a set of vertices V and a set of hyperarcs H , where a hyperarc is a pair < S , v > , S non empty subset of V and v ∈ V . DHs have a variety of applications: they have been used to represent functional dependency in databases, Horn formulae in propositional logic, and–or graphs, context free grammars etc. In the paper, after providing a brief historical introduction on the notion of DH and some relevant applications, various problems regarding DHs are surveyed and analyzed. In particular we consider the complexity of the reachability problem (together with its application in the related satisfiability problem for Horn CNF formulae) and the computation of transitive closure and transitive reduction of directed hypergraphs (together with its application to the computation of minimum coverings for a set of functional dependencies). Finally a short introduction to the problem of computing shortest hyperpaths in directed hypergraphs is provided. [ABSTRACT FROM AUTHOR]

Abstract: Given a directed graph , an edge is a strong bridge if its removal increases the number of strongly connected components of . Similarly, we say that a vertex is a strong articulation point if its removal increases the number of strongly connected components of . In this paper, we present linear-time algorithms for computing all the strong bridges and all the strong articulation points of directed graphs, solving an open problem posed in Beldiceanu et al. (2005) . [Copyright &y& Elsevier]

Given a directed graph, two vertices v and w are 2- vertex-connected if there are two internally vertex-disjoint paths from v to w and two internally vertex-disjoint paths from w to v . In this paper, we show how to compute this relation in O ( m + n ) time, where n is the number of vertices and m is the number of edges of the graph. As a side result, we show how to build in linear time an O ( n ) -space data structure, which can answer in constant time queries on whether any two vertices are 2-vertex-connected. Additionally, when two query vertices v and w are not 2-vertex-connected, our data structure can produce in constant time a “witness” of this property, by exhibiting a vertex or an edge that is contained in all paths from v to w or in all paths from w to v . [ABSTRACT FROM AUTHOR]

Abstract: We introduce the notion of a -path within Petri nets, and propose to adopt the model of directed hypergraphs in order to determine properties of nets; in particular, we study the relationships between -paths and firable sequences of transitions. Let us consider a Petri net  and the set of places with a positive marking in , i.e., . If we regard the net as a directed graph, the existence of a simple path from any place in to a transition is, of course, a necessary condition for the potential firability of . This is sufficient only if the net is a state machine, where for all . In this paper we show that the existence of a -path from any subset of to a transition is a more restrictive condition and is, again, a necessary condition for the potential firability of . But, in this case: (a) if  is a conflict-free Petri net, this is also a sufficient condition, (b) if  is a general Petri net, is potentially firable by increasing the number of tokens in . For conflict-free nets (CFPN) we consider the following problems: (a) determining the set of firable transitions, (b) determining the set of coverable places, (c) determining the set of live transitions, (d) deciding the boundedness of the net. For all these problems we provide algorithms requiring linear space and time, i.e., , for a net . Previous results for this class of networks are given by Howell et al. (1987) , providing algorithms for solving problems in conflict-free nets in time and space. Given a Petri net and a marking , the well-known coverability problem consists in finding a reachable marking such that ; this problem is known to be EXPSPACE hard (Rackoff (1978)). For general Petri nets we provide a partial answer to this problem. is coverable by augmentation if it is coverable from an augmented marking of the initial marking : and, for all , if . We solve this problem in linear time. The algorithms for computing -paths are incremental: it is possible to modify the network (adding new places, transitions, arcs, tokens), and update the set of potentially firable transitions and coverable places without recomputing them from scratch. This feature is meaningful when used during the interactive design of a system. [Copyright &y& Elsevier]

Abstract: We investigate the complexity of finding Nash equilibria in which the strategy of each player is uniform on its support set. We show that, even for a restricted class of win–lose bimatrix games, deciding the existence of such uniform equilibria is an -complete problem. Our proof is graph-theoretical. Motivated by this result, we also give -completeness results for the problems of finding regular induced subgraphs of large size or regularity, which can be of independent interest. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

Let $$G=(V,E)$$ be a directed graph. A vertex $$v\in V$$ (respectively an edge $$e\in E$$ ) is a strong articulation point (respectively a strong bridge) if its removal increases the number of strongly connected components of $$G$$ . We implement and engineer fast algorithms for computing all the strong articulation points and all the strong bridges of a directed graph, based on the linear-time algorithms presented in Italiano et al. (Theor Comput Sci 447:74-84, ). Our implementations are tested against real-world graphs taken from several application domains, including social networks, communication graphs, web graphs, peer2peer networks and product co-purchase graphs. The algorithms implemented turn out to be very efficient in practice, and are able to run on large scale graphs, i.e., on graphs with ten million vertices and half billion edges. Our experiments on such graphs highlight some properties of strong articulation points, which might be of independent interest. [ABSTRACT FROM AUTHOR]

Abstract: We study the usefulness of lookahead in on-line server routing problems: if an on-line algorithm is not only informed about the requests released so far, but also has a limited ability to foresee future requests, what is the improvement that can be achieved in terms of the competitive ratio? We consider several on-line server routing problems in this setting, such as the on-line traveling salesman and the on-line traveling repairman problem. We show that the influence of lookahead can change considerably depending on the particular objective function and metric space considered. [Copyright &y& Elsevier]

We describe Leonardo Web, a collection of tools for building animated presentations that can be useful for teaching, disseminating, and e-learning. Presentations can be created via the combined use of a visual editor and a Java library. The library allows it to generate animations in a batch fashion directly from Java code according to an imperative specification style. Batch-generated animations can then be refined and customized using the editor. Presentations can be finally viewed with a simple Java player, which ships both as a stand-alone application for off-line deployment and as a Java applet embedded in a Web page. The player supports step-by-step and continuous execution, reversibility, speed selection, and smooth animation. [Copyright &y& Elsevier]

Machine learning has been used for distinct purposes in the science field but no applications on illegal drug have been done before. This study proposes a new web-based system for cocaine classification, profiling relations and comparison, that is capable of producing meaningful output based on a large amount of chemical profiling's data. In particular, the Profiling Relations In Drug trafficking in Europe (PRIDE) system, offers several advantages to intelligence actions across Europe. Thus, it provides a standardized, broad methodology which uses machine learning algorithms to classify and compare drug profiles, highlight how similar drug samples are, and how probable it is that they share a common origin, batch, or preparation process. We evaluated the proposed algorithms using precision and recall metrics and analyzed the quality of predictions performed by the algorithms, with respect to our gold standard. In our experiments, we reached a value of 88% for F0.5-measure, 91% for precision, and 78% for recall, confirming our main hypothesis: machine learning can learn and be applied to have an automatic classification of cocaine profiles. [ABSTRACT FROM AUTHOR]