Formulating Semantics of Probabilistic Argumentation by Characterizing
  Subgraphs: Theory and Empirical Results
  In existing literature, while approximate approaches based on Monte-Carlo
simulation technique have been proposed to compute the semantics of
probabilistic argumentation, how to improve the efficiency of computation
without using simulation technique is still an open problem. In this paper, we
address this problem from the following two perspectives. First, conceptually,
we define specific properties to characterize the subgraphs of a PrAG with
respect to a given extension, such that the probability of a set of arguments E
being an extension can be defined in terms of these properties, without (or
with less) construction of subgraphs. Second, computationally, we take
preferred semantics as an example, and develop algorithms to evaluate the
efficiency of our approach. The results show that our approach not only
dramatically decreases the time for computing p(E^\sigma), but also has an
attractive property, which is contrary to that of existing approaches: the
denser the edges of a PrAG are or the bigger the size of a given extension E
is, the more efficient our approach computes p(E^\sigma). Meanwhile, it is
shown that under complete and preferred semantics, the problems of determining
p(E^\sigma) are fixed-parameter tractable.
