An Abstract Argumentation Framework (AF), or System, as introduced in the seminal paper by Dung [5], is simply a pair A, R consisting of a set A whose elements are called arguments, and of a binary relation R on A, called "attack" relation. Several different semantics (i.e., extensions) can be obtained over arguments by considering subsets of arguments with specific properties. An AF has an obvious representation as a directed graph where nodes are arguments and edges are drawn from attacking to attacked arguments.
The main aim of this work is to better understand this kind of systems under the perspective of their computational performance, in terms of networks with different properties and size. Indeed, existent and future applications [9] exploiting AFs need to efficiently behave and scale over "large" networks with properties close to real-world ones. In fact, in complex discussions it is not hard to find 50-100 arguments at least, especially if we consider on-line open fora, or discussion groups. When we make these digital tribunes correspond to well-known social networks, as Twitter or Facebook, but also to more structured debate-friendly tools, as DebateGraph 4 , then the number of arguments can further increase due to the a high number of users participating to a discussion. The different intrinsic nature of these graphs leads to find more or less extensions of some kind, e.g., stable ones [5]. In our tests we adopt two different types of small-world networks (Kleinberg [11] and Watts-Strogatz [13]), one class of scale-free networks (Barabasi [1]), and Erdős-Rényi [8] networks (see Sec. 3.2).
Our main goal is to compare three different tools that are more oriented to a straight computation of extensions, than on providing support to negotiation or decision-making. These tools correspond to ASPARTIX, ConArg, and Dung-O-Matic, introduced in Sec. 3.
In [5], Dung has proposed an abstract framework for argumentation in which the focus is on the definition of the argument status. Definition 1. An Argumentation Framework (AF) is a pair A, R of a set A of arguments and a binary relation R on A called the attack relation. ∀a i , a j ∈ A, a i R a j means that a i attacks a j . An AF may be represented by a directed graph (the interaction graph) whose nodes are arguments and edges represent the attack relation. A set of arguments B attacks an argument a if a is attacked by an argument of B. A set of arguments B attacks a set of arguments C if there is an argument b ∈ B which attacks an argument c ∈ C.
Dung gave several semantics to "acceptability". These various semantics produce none, one or several acceptable sets of arguments, called "extensions". In Def. 2 we define the concepts of conflict-free and stable extensions: An admissible set of arguments according to Dung must be a conflict-free set which defends all its elements. Formally:
Besides the stable semantics, three more semantics refining admissibility have been introduced in [5]: Definition 5. Given a A, R , a preferred extension is a maximal (w.r.t. set inclusion) admissible subset of A. An admissible B ⊆ A is a complete extension iff each argument which is defended by B is in B. The least (w.r.t. set inclusion) complete extension is the grounded extension.
In the following of this section we describe our benchmark environment. We organize the content into two subsections: Sec. 3.1 concerns a more detailed description of the three tools we used in our comparison, while Sec. 3.2 describes in detail the random networks we generated as benchmark.
ASPARTIX. The ASPARTIX5 system [7,6] is an ASP-based tool for computing acceptable extensions for a broad range of formalizations of Dung's AFs and generalisations, e.g., value-based AFs [2]. ASPARTIX relies on a fixed disjunctive Datalog program (ASP also includes default negation) which takes an instance of an argumentation framework as input, and uses an ASP solver (as DLV) for computing the type of extension specified by the user. ASPARTIX is able to solve admissible, stable, complete, grounded, preferred, semi-stable, ideal, stage, cf2, resolution-based grounded and stage2 extensions. ConArg. ConArg6 [4, 3] is a constraint-based tool based on the Java Constraint Programming solver7 (JaCoP ), a Java library that provides the Java user with a Finite Domain Constraint Programming paradigm [12]. All the properties describing conflict-free, admissible, complete, stable, grounded and preferred extensions have been modeled and implemented with constraints. In this paper we consider a (faster) command-line version of ConArg. To model all the semantics presented in Sec. 2 we used MiniZinc8 , which is a medium-level constraint modelling language that can be mapped onto different existing solvers. Dung-O-Matic. Dung-O-Matic9 is an abstract argument computation engine implemented by the javaDungAF Java class. Dung-O-Matic supports Dung's AFs and several of their semantics, namely admissible, complete, eager, grounded, ideal, preferred, semi-stable, and finally stable. In order to find each of the proposed extensions, this tool implements a different algorithm presented in literature; for instance, the grounded semantics is computed with the original algorithms presented by Dung in [5].
Due to the lack of well-established benchmarks using real interaction graphs, we decided to randomly generate our test networks. To generate random graphs we adopted two different tools. The first one is Java Universal Network/Graph Framework (JUNG, http://jung.sourceforge.net), which is a Java software library for the modeling, generation, analysis and visualization of graphs. With JUNG we generated Barabasi [1] and Kleinberg [11] networks. The second library we used is named NetworkX (http://networkx.github.io), and it consists of a Python software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks. With this tool we were able to generate Erdős-Rényi [8] and Watts-Strogatz [13]. We use two different libraries because of their different capabilities: with JUNG we are able to randomly generate directed Barabasi and Kleinberg networks, while NetworkX does not cover Kleinberg networks at all, and only provides undirected Barabasi ones. On the other side, NetworkX offers both Watts-Strogatz and Erdős-Rényi networks (not present in JUNG). Four examples of these networks are represented in Fig. 1. Our attention is more focused on testing small-world networks because we consider real large interaction-graphs as coming from social networks [10,9].
In Fig. 2 and Fig. 3 we show a first comparison among the three systems presented in Sec. 3.1, testing complete and stable extensions respectively. On the x-axis we report the exact number of nodes of each set of networks we use: in each set, we considered 50 random networks for each of the four classes reported in Sec. 3.2, for a total of 200 networks. On the y-axis we report the average CPU time to compute all the complete/stable extensions on that given set of networks. These first tests show that ConArg performs better than the other two systems, even if ASPARTIX has comparable results.
Performance has been collected using an Intel(R) Core(TM) i7 2.4Ghz processor, with 16Gb of RAM. To run ASPARTIX, we have used the last version of DLV (December 2012) with Gringo v3.0.5 and ClaspD v1.1.4 as extensions.
In this work we have commenced a study on the computational efficiency of nowadays tools dealing with AFs [5]. Our will is to extend this study under several lines. First, we will show tests on more computationally-demanding semantics (e.g., preferred extensions), we will test hard problems in Argumentation (e.g., deciding if a set is a preferred extension is CO-NP-complete), and, finally, we will better define the link with small-world networks, by finding the most appropriate random-network model. At last, we will test these tools over larger networks (e.g., 1, 000 arguments), to check how feasible it is to use them in a real application, as, for instance, large-scale agreements via microdebates [9].