Introduction and Related Work Many people today participate in more than one social network on a daily basis; such networks can be seen as dynamic environments containing knowledge about their members. From a KR perspective, these environments are complex in many dimensions; for instance, it is not clear how to treat news being communicated through the network, especially when it contradicts a user's own knowledge, or when contradicting news is received from di erent sources. We are interested in reasoning about the di usion of beliefs in social media. Given the variety of platforms, the underlying communication structure can be seen as a complex network|the potential to integrate many di erent data sources is enormous. The complex network is represented by a graph, and users have access to a stream of news items that are produced by others. Local revisions are performed rst, where each user responds to news items that show up in their feeds; since each local revision is carried out in parallel, the result of this stage could violate global integrity constraints. A global revision process is then carried out in order to return to a consistent state. In this paper we focus solely on local revisions. Related Work. Networks have been used to model di usion processes in realworld domains [4]; more ad hoc models have also been central to world events like the US elections and the Brexit vote [7, 1]. Our research continues the work of [6], where the authors propose a general formalism to model complex networks. Whereas their work focuses on cascading processes, they do not contemplate individual knowledge bases for each agent. Our end goal is to build on the rst steps|modelling local revisions|to eventually model the combination of these processes as they give rise to cascades. This work is also part of the research line started in [2], where we proposed a model called Social Knowledge Bases.
EP \ Pred = ;. Vertex predicates have arity 1, and edge predicates have arity 2; we use LV (resp., LE ) to denote literals over VP (resp., EP ).
De nition 1 ([
De nition 2 ([
We enrich networks with a set of constraints that condition and relate the
structural part and users' KBs; satisfaction and consistency are de ned as expected.
De nition 3 ([
The network belief dynamics problem arises when the epistemic input is
comprised of a set of what we call news items coming from the neighbor nodes.
De nition 4 ([
We assume that all sets of news items are consistent; function changes news items into canonical form without ips|each ip is changed to add. We denote with N KB the universe of NKBs, and P the universe of news items. Given NKB = (V; E; lvert; ledge; K), set of news items P = fp1; :::; png, v 2 V , we use Pv = fp = ho; l; di 2 P j (o; v) 2 Eg to refer to the set of news items seen by v. Given p = ho; l; di 2 P, let src(p) = o, lit(p) = l, and dec(p) = d. Posts made by users are seen by all their connections; when this occurs, each user adopts a position regarding the information that they receive from their friends. Users generally have many possible sources of information that can make mutually inconsistent posts, or posts that contradict their own local belief base. Postulates for Local NKB Belief Revision De nition 5. Local BR operators are functions ~ : N KB V 2P ! N KB.
Let v 2 V , ~ be a local NKB revision operator, and nkb0 = ~(nkb; v; P ) = (V 0; E0; lv0ert; le0dge; K0). We propose a set of postulates as reasonable properties for local NKB revision; note that not all postulates are meant to hold for all operators|we will discuss this further below.
Inclusion: K0(v) Weak Success: lit (Pv)
K(v)[lit (Pv).
Success: lit (Pv)
K0(v) when lit (Pv) is consistent. Consistency: K0(v) 0?.
Vacuity 1: If l 2= K(v); lit (p) = l implies dec(p) = r, for all p 2 Pv, then l 2= K0(v). Vacuity 2: If l 2 K(v); lit (p) = :l implies dec(p) = r, for all p 2 Pv, then l 2 K0(v). Weak Vacuity 1: If l 2= K(v) and lit (p) 6= l for all p 2 Pv, then l 2= K0(v). Weak Vacuity 2: If l 2 K(v) and lit (p) 6= :l for all p 2 Pv, then l 2 K0(v). Strong Congruence: Let Pv be a set of news item and nkb = ~(nkb; v; Pv ) = (V ; E ; lvert ; ledge ; K ), if (Pv) = (Pv ) then K0(v) = K (v).
Weak Congruence: Let P + = fp 2 (P ) j dec(p) = ag be a set of all positive/added news items of (P ), P = fp 2 P j dec(p) = rg be a set of all negative/removed news items of P and let Pv be a set of news item and nkb = ~(nkb; v; Pv ) = (V ; E ; lvert ; ledge ; K ). If Pv+ = Pv +, and Pv Pv then K (v) K0(v). Majority: Let Pro = fp 2 P j lit (p) = l; dec(p) 6= rg Pv and Con = fp 2 Pv j lit (p) = :l; dec(p) 6= rg Pv. Given l 2 L s.t. l 2= K(v) and :l 2= K(v), if jProj > jConj then :l 2= K0(v), and if jProj < jConj then l 2= K0(v).
Local E ect: 8w 2 V s.t. w 6= v; K0(w) = K(w).
Structural Preservation: V = V 0; E = E0; lvert = lv0ert ; and ledge = le0dge . Weighted Majority: For NKBs that have one label per edge, given l 2= K(v) and :l 2= K(v), let sumWPos and sumWNeg be two values calculated as follows: sumWPos = P sumWNeg = Pe2I weight (e); where I = fe 2 E j e = (v; src(p)); lit (p) = l; p 2 Pg.
e2J weight (e); where J = fe 2 E j e = (v; src(p)); lit (p) = :l; p 2 Pg.
If sumWPos > sumWNeg then :l 2= K0(v); if sumWPos < sumWNeg then l 2= K0(v). The following de nition characterizes di erent types of local revisions. De nition 6. A local NKB revision operator is basic if it satis es Structural Preservation, Local E ect, Consistency, Uniformity, and Inclusion. Let ~ be a basic local NKB revision operator: ~ is restrained if it satis es Strong Congruence, Vacuity 1, and Vacuity 2. ~ is weakly restrained if it satis es W. Congruence, and W. Vacuity 1 and 2. ~ is social if it satis es Weak Success, and either Majority or Weighted Majority. Towards Constructions based on User Types. We now brie y discuss how the operator types presented above could be used, along with characterizations of di erent user types, to construct concrete operators. Though the actual constructions are not discussed here, we take an important rst step in the next section by showing how di erent user types can be detected in real-world datasets. Credulous users adopt all new knowledge that they see in their feeds, even if it contradicts their previously-held beliefs.
Incredulous users are reluctant to incorporate new knowledge appearing in their feeds, regardless of whether it has any relation with their previously-held beliefs. Users with herd behavior accept new information as long as there are enough other users adopting it.
Blind followers accept new knowledge being shared by their contacts, as long as such contacts have a close enough relation to them. Cautious users do not adopt new knowledge unless a selected group of their connections do.
Self-con dent users assign more value to their previously-held beliefs, making it di cult for them to incorporate new information that contradicts them. Combining operator and user types, we can in theory arrive at 18 di erent kinds of operators. In future work, we will formally characterize their construction. 3
Experimental Evaluation The dataset is a subset of the Twitter network, with 184,654 users connected by 66,827,454 follow relationships, and 18,292,721 tweets. Hashtags are present in 5,107,986 tweets, and there are 136,809 distinct hashtags. Our objective is to show that by analyzing information ow in a social network, one can build a map of users based on how they behave|the goal is to inform the construction of local NKB revision operators as discussed above. We used hashtags as proxies for news items; to obtain the sentiment associated with the use of each hashtag, we used PHPInsight. We identi ed the 100 most prevalent hashtags and selected 12 users. For each one, we analyzed the sentiment of the tweet via which each hashtag reached their feed (either positive, negative, or neutral), and then analyzed how they reacted|either tweet using the hashtag (again, with positive, negative, or neutral sentiment) or to not use that hashtag in any of their subsequent tweets.
Results are shown in Figure 1; we averaged the sentiment distribution of the tweets seen by each user, yielding 29% positive, 19% negative, and 52% neutral. We summarize users' reactions as an average over all hashtags seen. Users u1{u3, and u10 can be seen as self-con dent, as they almost never reuse hashtags with the same sentiment when receiving them with positive or negative. Users u4, u7, u9 behave similarly, but more for positive tweets, either reusing positive tweets or changing the sentiment of negative ones; u8 is a dual case. User u10 tends to change the sentiment of what they receive when its positive or negative. This analysis also detects \dead end" users such as u5, u6, u11, u12.
Acknowledgments. We thank support from CONICET, Universidad Nacional del Sur, ONR (grant N00014-15-1-2742), and V.S. Subrahmanian for the Twitter dataset.