In a recent work we have developed an argumentative approach for discovering relevant opinions in Twitter. A Twitter discussion is modeled as a weighted argument graph where each node denotes a tweet, each edge denotes a criticism relationship between a pair of tweets of the discussion and each node is attached with a weight that denotes the social relevance of the corresponding tweet in the discussion. In the social network Twitter, a tweet always refers to previous tweets in the discussion, so the obtained underlying argument graph is acyclic. Based on this structural feature, in this work, we introduce a distributed algorithm for computing the set of globally accepted opinions of a Twitter discussion. The set of accepted opinions is extracted by mapping the weighted argument graph into a valued argumentation framework and it is computed as the biggest set of tweets of the discussion that satis es that it is consistent.
In order to understand what are the major accepted and rejected opinions in
di erent domains by Twitter users, in a recent work [
The system architecture has two main components: a discussion retrieval and
a reasoning system. The discussion retrieval component allows us to move from
a discussion in Twitter (a set of tweets) in natural language to a weighted graph
which is computed taking into account criticism relationships between tweets
and three di erent attributes of a tweet: the number of followers of the author,
the number of retweets and the number of favorites. The reasoning system
component maps the weighted graph into a weighted argumentation framework and
the set of socially accepted tweets in the discussion is evaluated from the weight
assigned to each tweet and the criticism relationships between the tweets of the
discussion, and it is computed as the ideal semantics [
In abstract argumentation [
The system developed in [
Based on the fact that the graphs we obtain are acyclic, in this work, we introduce and investigate a distributed implementation of the skeptical approach based on the ideal semantics of a valued abstract argumentation framework. A tweet defeats a second one if it criticizes the second one and it has at least the same social relevance as the second one. The ideal semantics for valued abstract argumentation guarantees that the set of tweets in the solution is the maximal set of tweets that satis es that it is consistent, in the sense that there are no defeaters among them. But the solution also satis es that it defends against defeaters from the tweets outside the solution, in the sense we will see in the formal de nition of ideal semantics.
The social relevance is measured with a social valuation function that for each tweet considers di erent information sources from the social network, such as the number of followers of the author, the number of retweets and the number of favorites. The distributed approach can be of special relevance for assessing Twitter discussions that involve a large number of tweets and the system can be applied in elds where identifying groups of tweets globally compatible or consistent, but at the same time that are widely accepted, is of particular interest, such as for instance for the assistance and guidance of marketing and policy makers.
After this introduction, in the next section, we formalize the structure to model Twitter discussions and, in Section 3, we de ne the reasoning model for computing their solutions. Then, in Section 4, we present a novel distributed strategy for the implementation of the reasoning model based on the ideal semantics for a valued abstract argumentation framework. We end the paper with some conclusions and a discussion of future work. As far as we know, this is the rst distributed algorithm presented to solve such problem. 2
Following the approach proposed in [
De nition 1. (Twitter Discussion) A Twitter discussion is a non-empty set of tweets. A tweet t 2 is a tuple t = (m; a; ; r; fv), where m is the up to 140 characters long message of the tweet, a is the author's identi er of the tweet, r 2 N is the number of retweets and fv 2 N is the number of favorites. Let t1 = (m1; a1; 1; r1; fv1) and t2 = (m2; a2; 2; r2; fv2) be a pair of tweets of a Twitter discussion . We say that t1 answers t2 i t1 is a reply to the tweet t2 or t1 mentions (refers to) tweet t2.
De nition 2. (Discussion Graph) The Discussion Graph (DisG) for a Twitter discussion is the directed graph (T; E) such that { for every tweet in there is a node in T and { if tweet t1 = (m1; a1; 1; r1; fv1) answers tweet t2 = (m2; a2; 2; r2; fv2), with a1 6= a2, and m1 criticizes the claim expressed in m2, there is a directed edge (t1; t2) in E.
Only the nodes and edges obtained by applying this process belong to T and E, respectively.
Although our system allows us to analyze any discussion in Twitter (set of tweets), in this work we deal with discussions where a tweet answers previous tweets in the discussion. Moreover, in our approach, (t1; t2) 2 E i t1 answers t2 and the message of tweet t1 does not agree with the claim expressed in the message of tweet t2. So, the answers between tweets whose messages are not classi ed as criticisms, do not give rise to edges and, therefore, some nodes (tweets) of a discussion graph can be disconnected. Thus, we can nd nodes for which the input or the output degree, or both, is zero.
Since the social network we are considering in this work is Twitter, every tweet of a discussion can reply at most one tweet, but can mention many tweets, and all of them are prior in the discussion. So, every tweet can answer and, in turn, can criticize many prior tweets of the discussion, and thus, every tweet can criticize many prior tweets from a same author and from di erent authors.
From an implementation point of view, in order to check if a tweet criticizes
another tweet, we can use some of the components we have developed in [
On the other hand, to check if a tweet does not agree with the claim expressed in a di erent tweet, the system uses an automatic labeling system based on Support Vector Machines (SVM). Our SVM model for labeling relations between tweets considers di erent attributes obtained from the tweets of an answer (t1; t2). On the one hand, we have attributes that count the number of occurrences of relevant words in the tweets t1 and t2. We have considered two kinds of words: regular words and stopwords. We have considered the inclusion of stopwords as attributes because the typical tweet is very short and the fraction of stopwords that can be giving information about the kind of answer could be relevant. For example, in the next tweet the stopwords ... and !!! give information about the sentiment associated to the tweet.
On the other hand, we also consider attributes that have to be computed
from the text and from the additional information that comes with the tweets.
In particular, for each tweet these attributes are the number of images and the
number of URLs mentioned in the tweet, the number of positive and negative
emoticons and the sentiment expressed by the tweet. Our labeling system
incorporates a sentiment analysis computation module [
Since SVM follows a supervised learning approach, we rst have to train a model from an already labeled data set of answers. To this aim, we have collected a set of several Twitter discussions, on the Spanish language, and we have manually labeled the answers in the discussions to be able to train a SVM labeling model for Spanish discussions.
The training collection contains 12 discussions and a total of 582 pairs of
tweets (answers). We have considered the creation of SVM models with di erent
number of regular words (w) and di erent number of stopwords (s). The words
in the collection are sorted by number of occurrences, and for an SVM model
with w regular words, we select the rst w most frequent regular words. The
stopwords have been obtained from the natural language toolkit (NLTK) [
Using this training collection, we have trained four models with di erent
values for w and s, in order to get a good labeling model. In order to compute
the sentiment for the tweets in this collection, we have taken the AFINN data3
used in [
Regarding the implementation, we instantiate the set of ordered values R to the natural numbers N and, for each node with tweet t = (m; a; ; r; fv), we consider the following weighting scheme:
W (t) = blog2( + 20 r + 40 fv + 1)c;
which takes into account not only the number of followers of the author, but
also the number of retweets and favorites. This function allows us to quantify
the orders of magnitude of the social relevance of tweets following the statistics
about tweets and retweets de ned in [
Figure 1 shows a WDisG graph instance for a Twitter discussion obtained from the political domain using the fl1r20fv40 weighting scheme. Each tweet is represented as a node and each criticism answer as an edge. The root tweet of the discussion is labeled with 0 (the tweet that starts the discussion) and the other nodes are labeled with consecutive identi ers according to the temporal generation order of the tweets in the social network. The nodes that appear disconnected in the graph correspond to tweets that have participated in the discussion in response to other tweets, but have not been classi ed as criticisms answers (nodes 3 and 5). The discussion has a simple structure, possibly one of the most frequent in Twitter. A root tweet starts the discussion and some answers criticize it, and there are not many criticisms between non-root tweets. The discussion contains 13 tweets and 14 criticisms answers. Nodes are colored 3 http://www2.compute.dtu.dk/~faan/data/AFINN.zip in blue scale, where the darkness of the color is directly proportional to its weight with respect to the maximum value in the discussion.
Since our reasoning model de nes the set of socially accepted tweets of a discussion as a set of tweets without e ective con icts, the solution is mainly de ned by tweets that generate or receive criticism of other tweets and it is presented in next section.
Once we have introduced our formal representation model of Twitter discussions
with criticism relationships between pairs of tweets, the next key component is
the de nition of the reasoning model used to obtain the set of socially accepted
tweets. To this end, we use a valued abstract argumentation framework [
A valued argumentation framework (VAF) is a tuple hA; attacks; R; Val; Valprefi where A is a set of arguments, attacks is an irre exive binary relation on A, R is a nonempty set of values, Val is a valuation function Val : A ! R that assigns to each argument in A a weight value in R, and Valpref R R is a preference relation on R (transitive, irre exive and asymmetric), re ecting the value preferences of arguments.
Given a Twitter discussion and its WDisG graph G =hT; E; N; fl1r20fv40i based on the weighting scheme fl1r20fv40 : T ! N, the VAF for G is the tuple F = hT; E; N; fl1r20fv40;>i, where each tweet in T results in an argument of F , each criticism answer in E results in an attack between the arguments of F , N is the set of valuations or weights of the arguments, the weighting scheme fl1r20fv40 is the weighting valuation function of F , and the order relation > of N is the preference relation between the valuations or weights of the arguments; i.e. a tweet t2 is more valued than a tweet t1 whenever fl1r20fv40(t2) > fl1r20fv40(t1).
Then, a defeat relation (or e ective attack relation) between tweets (arguments) is de ned as follows: defeats = f(t1; t2) 2 E j fl1r20fv40(t2) 6> fl1r20fv40(t1)g.
Moreover, a set of tweets (arguments) S T is con ict-free if for all t1; t2 2 S; (t1; t2) 62 defeats, and a con ict-free set of tweets S T is maximally admissible if for all t1 62 S, S [ ft1g is not con ict-free and, for all t2 2 S, if (t1; t2) 2 defeats then there exists t3 2 S such that (t3; t1) 2 defeats. Finally, the set of socially accepted tweets of , referred as the solution of , is computed as the largest admissible con ict-free set of tweets S T in the intersection of all maximally admissible con ict-free sets. Remark that the tweets of a discussion that do not generate nor receive criticism, are always part of the solution.
Figure 2 shows the VAF solution for the WDisG graph instance of Figure 1. The nodes colored in blue are the tweets in the solution and the nodes colored in gray are the rejected tweets, where the darkness of the color is directly proportional to its weight. According to the fl1r20fv40 valuation function, the tweets of the discussion are strati ed in three levels denoting their relevance in the discussion. For each level, we nd the following sets of tweets: level 0: f3; 2; 4; 5; 9; 10; 11g, level 1: f6; 7; 8; 12g, level 2: f0; 1g, being level 0 the lowest level and level 2 the highest one. The solution contains 7 tweets (Tweets 1, 4, 7, 8, 9, 11 and 12) of the 13 tweets of the discussion, and 6 tweets are rejected (Tweets 0, 2, 3, 5, 6 and 10). On the one hand, Tweet 1 defeats the root tweet, since Tweet 1 attacks the root tweet and both have the same weight. The same happens with Tweets 3, 5, 6 and 10, since Tweet 4 attacks Tweet 3, Tweet 11 attacks Tweets 5 and 10, and Tweets 7 and 12 attack Tweet 6. On the other hand, Tweet 8 defeats Tweet 2, since Tweet 8 attacks Tweet 2 and Tweet 8 is heavier than Tweet 2. Finally, Tweets 1, 4, 7, 8, 9, 11 and 12 are accepted since they do not have any defeater in the solution. Notice that in this discussion with high controversy around Tweets 0 and 6 (with a high number of attacks), we end up rejecting both tweets due to the weight they get during the discussion.
In [
Now in this work, we de ne a distributed strategy for implementing the underlying reasoning algorithm for computing the ideal extension for a VAF. The algorithm takes a WDisG graph of a Twitter discussion and outputs the set of accepted tweets based on the valuation function, the preference relation and the computation of the largest admissible con ict-free set of tweets according to the defeat relation. 4
We design a distributed strategy for computing the solution of a WDisG graph
using the distributed model of computation of Pregel [
Within each superstep the nodes compute their state in parallel, executing a speci c function that computes the new state of the node taking into account the possible messages sent by the nodes' neighbors in the previous superstep. Then, as a byproduct of the computation of the node state, some messages may be sent to some of the nodes' neighbors, that they will be processed in the next superstep. The idea is that the messages are used by nodes to indicate some change in their state, that could have some in uence on the state of their neighbors in the next superstep. The superstep nishes when every node has computed its state and has sent the necessary messages to its neighbors.
In the computation model of Pregel, the input can be any directed graph. However, the algorithm we present here works only with discussion graphs that are acyclic, such that it allows us to solve discussions of big size with an e cient polynomial time distributed algorithm, where the state of each node depends only on the state of its attacking nodes. Observe that in the case of Twitter, where a tweet only answers previous tweets, the discussion graphs are always acyclic, so restricting the algorithm to consider only acyclic discussion graphs is not a real restriction for Twitter.
For the distributed computation of the solution (ideal extension) for a discussion acyclic graph, we propose a Pregel algorithm where each node can be in two states: accepted or not accepted (rejected), but a node also stores a defeaters count, to keep track of the number of accepted defeaters the node has, to actually compute its acceptance state. Initially, every node starts in the rejected state and with its defeaters counter equal to zero.
Algorithm 1 Compute the acceptance state for a node a 1: procedure a.CompAcceptance(i) . Update acceptance state of a at superstep i 2: a.storeCurrentAcceptanceState() 3: for all msg 2 a.received(i-1) do . Check defeaters count update 4: if (msg.type == attacker) then a.updateDefeaters( msg.value ) 5: a.updateAcceptanceState() 6: if ( a.StateChanged() ) then . a changed to accepted or to not accepted 7: sendToAllNeighbors( msg( attacker, (a.weight(), a.isAccepted() ) ) ) 8: else 9: a.VoteToHalt() . Vote to nish distributed computation
Algorithm 1 shows the pseudocode of the function used by each node a to compute its state in a superstep i. 4 It works as follows. In the superstep i, a node a checks if its state has to be changed after updating its defeaters counter. The node a updates its defeaters counter based on the received messages (from the previous superstep i 1) from any nodes v connected with a with an incoming edge (v; a). These messages are processed in the for loop of lines 3 and 4. There are two possible changes that every message can produce on the defeaters counter of a. On the one hand, if in the previous superstep a node v, and such that (v; a) is an edge of the graph, changed its state to accepted then v sent a message to a of type attacker and with value (v:weight(); +1), indicating to a that its defeaters counter should be increased by one but only if v is a defeater of a (if v:weight() a:weight()). On the other hand, such node v could instead have changed its state to not accepted, so in that case the message sent to a will be also of type attacker but with value (v:weight(); 1), indicating that its defeaters counter should be decreased by one if v is a defeater of a. The possible addition or subtraction to its defeaters counter, caused by a message msg sent by a node v is checked (and performed when needed) by calling the function a:updateDef eaters(msg:value), where the value has the format indicated previously. Then, after updating the defeaters counter the state 4 The pseudocode is written using object oriented notation, as the Pregel API is written in C++. However, our actual implementation is based on the Pregel implementation found on the Spark distributed programming framework, graphX, that is written in Scala. of a is updated calling the function a:updateAcceptanceState(), that checks if the updated defeaters counter is greater than zero. Finally, we call the function a:StateChanged() (in line 6) to check whether the state of a changed (from not accepted to accepted or viceversa). If it changed, a sends an attacker message to all its outgoing neighbors with value (a:weight(); a:isAccepted()), where the function a:isAccepted() will return either +1 or -1 depending on whether the state of a is accepted or not accepted. These sent messages will be processed by the outgoing neighbors of a when the next superstep begins. If the state of a did not change, then a votes towards nishing the distributed computation of the solution (line 9), but only when all the nodes agree to nish, in a same superstep, will the algorithm nish.
Consider the execution of the algorithm when solving the example discussion we have presented in Section 2, and whose solution is shown on Figure 2: 1. Before the rst superstep, all the nodes start in the not accepted state and with defeaters counter equal to zero, so in the rst superstep, as there are no incoming messages for any node, all of them will change their state to accepted. Then, any node with outgoing edges (all except 3 and 0), sends a message to its attacked nodes with value (node:weight(); +1). Observe that nodes 4; 7; 8; 9; 11 and 12 will remain accepted for the rest of the execution of the algorithm, as they will never receive any messages. 2. In the second superstep, the received messages produce that nodes 0; 1; 2; 3; 5; 6 and 10 change to not accepted, as they receive messages from attacking accepted nodes that defeat them, so each one of these nodes (except 0 and 3) will send a message with value (node:weight(); 1). Nodes 2; 3; 5; 6 and 10 will remain not accepted for the rest of the execution of the algorithm. 3. In the third superstep, the messages sent in the previous superstep produce that nodes 0 and 1 change to accepted, and so node 1 will send a message to node 0 with value (1:weight(); +1). Node 1 will remain accepted for the rest of the execution. 4. Finally, in the fourth superstep the message received by node 0 from 1, as 1 is a defeater for 0, will change the state of 0 to rejected, being this its nal state and the end of the execution of the algorithm as no more messages are sent by any nodes.
Observe that the number of supersteps is equal to the maximum path length of the discussion graph, and although one can think about variants of this algorithm where less messages are sent, it seems that in the worst case it is not possible the have less supersteps than the maximum path length of the discussion graph. So, for typical Twitter discussions, where one has many branches in the discussion graph but not too deep, this algorithm may solve big discussions.
We have started to evaluate the performance of this algorithm on real Twitter discussions of di erent sizes, working with a small Spark cluster with ve computers working with Linux. A table with preliminary results for a test set of Twitter discussions can be found at the URL: https://www.dropbox.com/ s/u4yrz5an78d6dfw/lasttable.pdf?dl=0. 5
In this paper we introduce a distributed system for mining the set of globally accepted tweets of a Twitter discussion. We model discussions with a weighted argumentation graph, where each node denotes a tweet, each edge denotes a criticism relationship between a pair of tweets of the discussion and each node is attached with a weight, that denotes the social relevance of the corresponding tweet in the discussion and it is computed from some tweet's attributes, such as the number of followers of the author, the number of retweets and the number of favorites.
The set of accepted tweets is de ned following an skeptical approach based on the ideal semantics of a valued argumentation framework. The ideal semantics for valued argumentation guarantees that the set of tweets in the solution is the maximal set of tweets that satis es that it is consistent, in the sense that there are no defeaters among them, and that all of the tweets outside the solution are defeated by a tweet within the solution.
Our distributed strategy is based on the distributed computation model of Pregel which is appropriate for our problem, because the input for a Pregel algorithm is a directed graph, where the nodes can be in di erent states, and the goal is to compute the state of each node based on the state of the nodes' neighbors.
In our system each node (tweet) can be in two states, accepted or not accepted (rejected), and the algorithm works only with discussion graphs that are acyclic, such that it allows us to solve discussions of big size with an e cient polynomial time distributed algorithm, where the state of each node depends only on the state of its attacking nodes. As far as we know, the system is the rst distributed implementation of an argumentative reasoning algorithm for social network analysis.
As future work, we plan to extend the representation model to consider support relationships between tweets and also to explore an e cient implementation of a distributed algorithm for bipartite graphs.