8.1 Information Propagation Cascades

With the advent of online social networks, humans are able to volunteer free observations about the physical world at scale, as well as communicate and share their observations with each other in a prompt and efficient way. As individuals choose to propagate information, their observations spread through the underlying social networks that connect them. We call such information spread on social networks information propagation cascades as the propagated information will eventually reach a larger population in a similar way as epidemic cascades (ECs) [117]. Information cascades happen naturally within social networks (e.g., Twitter) where individuals are given the option to forward messages or follow behaviors of other people in the network. The properties of information propagation cascades have been well studied in different types of online social networks such as Twitter [118], Facebook [119], Flickr [120], Digg [121], and YouTube [122].

In this chapter, we review the work that address two important problems: (i) How will the information propagation cascades on social network affect the performance of the social sensing model discussed in the previous chapters? (ii) How to further generalize the basic maximum likelihood estimation (MLE) model to consider the information propagation properties? Twitter is a good platform to study the information propagation cascades, especially during the process of natural disasters and emergency events where a lot of warnings, news, and rumors are generated and propagated on Twitter [123]. In particular, Twitter allows users to send short messages through various devices and broadcasts messages to a large population. In particular, Twitter has the option that allows users to follow each other. When a user posts a tweet, that tweet is immediately visible to all of his/her followers. Twitter also has the function called Retweet, which allows users to easily forward tweets from other users. Follower-followee relationship and the Retweet function make it easy and fast for the information propagation cascades to occur on Twitter.

The reader must be cautioned that social networks carry a lot of extraneous information as well, such as subjective opinions (e.g., “It is an inspiring day!”) and personal emotions (e.g., “I am depressed”). These are not the topic of this chapter. Instead, we are interested in objective claims in social sensing that describe external physical state. In the aftermath of important events, many microblog entries offer physical descriptions of the event (e.g., “Shooting erupts on Liberty Square!”). Such reporting is an act of sensing of the physical environment that is external to the human observers. In this case, the physical environment has a unique state, leading to a unique ground truth, according to which these descriptions are either true or false (e.g., either there was shooting on Liberty Square or not). It is this category of claims about the physical environment that this chapter is concerned with. The reviewed work has developed tools to collect such claims from online social media in large-scale disaster and unrest events [124].

8.2 A Binary Model of Human Sensing

In this section, we review a model that takes humans as sources of (i) unknown reliability, generating (ii) binary observations of (iii) uncertain provenance [105]. Of these three features, the first is perhaps the most intuitive. Unlike physical sensors whose characteristics, calibration, and failure modes are known, we do not, in general, know the reliability of human observers and hence cannot assume it in the problem formulation. In the following subsections, we explain the remaining two model features; namely, binary observations and uncertain provenance.

8.3 Inferring the Social Network

In this section, we discuss possible methods that can be used to infer the social network with a focus on Twitter. In order to have a holistic view of the entire system, we put such discussion in the context of the solution architecture. To enable reconstruction of ground truth information from data reported by human sources, a solution needs to (i) collect data from the “humans as a sensor network,” (ii) structure the data for analysis, (iii) understand how sources are related, and (iv) use this collective information to estimate the probability of correctness of individual observations. These steps are described in the following subsections, respectively. The reviewed solution focused on Twitter as the underlying “humans as a sensor network.”

8.4 A Social-Aware Algorithm

It remains to show how to cast the problem of computing the probability of correctness of claims as a MLE problem when sources have unknown reliability and data has uncertain provenance. This section presents a social-aware algorithm that solves this problem. Let m be the total number of sources in the system from which we have data. Let us describe each source (i.e., “sensor”), S_i, 1 ≤ i ≤ m, by two parameters; the likelihoods of true positives, a_i = P(S_iC_j = 1|C_j = 1) and the likelihoods of false positives, b_i = P(S_iC_j = 1|C_j = 0), neither of which are known in advance. d is denoted as the unknown expected ratio of correct claims in the system, d = P(C_j = 1). The vector θ is defined to be the vector of the above unknowns:

$\begin{array}{l}\hfill \theta =[a_1,\dots ,a_m,b_1,\dots ,b_m,d]\end{array}$

A MLE finds the values of the unknowns that maximize the probability of observations, SC, given the social network SD. Hence, the goal is to find θ that maximizes P(SC|SD, θ). The probability P(SC|SD,θ) depends on which claims are true and which are false. Let us therefore introduce the vector Z where element z_j = 1 if C_j is true and zero otherwise. Using the total probability theorem, the expression to maximize, namely P(SC|SD, θ), can be rewritten as follows:

$\begin{array}{l}\hfill P(SC|SD,\theta )=\sum _{z}P(SC,z|SD,\theta )\end{array}$

This problem can be solved by using the expectation maximization (EM) algorithm [93, 126]. The current work explicitly models the source dependency and uncertain data provenance in the MLE and presents an enhanced EM algorithm to address these challenges. The EM scheme starts with some initial guess for θ, say θ₀ and iteratively updates it using the formula:

$\begin{array}{l}\hfill {\theta }_{n+1}=arg{max}_{\theta }\{E_{z|SC,{\theta }_n}\{lnP(SC,z|SD,\theta )\}\}\end{array}$

The above breaks down into three quantities that need to be derived:

• The log likelihood function, $lnP(SC,z|SD,\theta )$

• The expectation step, $Q_{\theta }=E_{z|SC,{\theta }_n}\{lnP(SC,z|SD,\theta )\}$

• The maximization step, ${\theta }_{n+1}=arg{max}_{\theta }\{Q_{\theta }\}$

Note that, the latter two steps are computed iteratively until the algorithm converges. The above functions are derived below.

8.4.1 Deriving the Likelihood

The key contribution of the social-aware EM scheme lies in incorporating the role of uncertain provenance into the MLE algorithm. To compute the log likelihood, the function P(SC,z|SD, θ) needs to be computed first. The source claim graph SC can be divided into subsets, SC_j, one per claim C_j. The subset describes which sources espoused the claim and which did not. Since claims are independent, we have:

$\begin{array}{l}\hfill P(SC,z|SD,\theta )=\prod _{j=1}^{N}P(S{C}_j,z_j|SD,\theta )\end{array}$

  (8.5)

which can in turn be re-written as:

$\begin{array}{l}\hfill P(SC,z|\theta )=\prod _{j=1}^{N}P(S{C}_j|SD,\theta ,z_j)P(z_j)\end{array}$

  (8.6)

where P(SC_j|SD, θ, z_j) is the joint probability of all observations involving claim C_j. Unfortunately, in general, the sources that make these observations may not be independent since they may be connected in the social network leading to a possibility that one expressed the observation of another. Let p_ik = P(S_iC_j|S_kC_j) be the probability that source S_i makes claim C_j given that his parent S_k (in the social dissemination network) makes that claim. p_ik is referred to as repeat ratio and can be approximately computed from graph SC, for pairs of nodes connected in graph SD, as follows:

$\begin{array}{l}\hfill p_{ik}=\frac{\text{number of times}{S}_i\text{and}{S}_k\text{make same claim}}{\text{number of claims}{S}_k\text{makes}}\end{array}$

  (8.7)

Hence, the joint probability that a parent S_p and its children S_i make the same claim is given by $P(S_p{C}_j){\prod }_{i}P(S_i{C}_j|S_p{C}_j)$ which is $P(S_p{C}_j){\prod }_i{p}_{ip}$. This probability accounts for the odds of one source repeating claims by another. Note that the model assumes that a child will not independent make the same claim as a parent. For illustration, let us now consider the special case of social network topology SD, where the network is given by a forest of two-level trees.* Hence, when considering claim C_j, sources can be divided into a set M_j of independent subgraphs, where a link exists in subgraph g ∈ M_j between a parent and child only if they are connected in the social network and the parent claimed C_j. The link implies source dependency as far as the claim in question is concerned. The intuition is that if the parent does not make the claim, then the children act as if they are independent sources. If the parent makes the claim, then each child repeats it with a given repeat probability. The assumed repeat probability determines the degree to which the algorithm accounts for redundant claims from dependent sources. The higher it is, the less credence is given to the dependent source. Two scenarios are illustrated by the two simple examples in Figure 8.1, showing the situation where source S₁, who has children S₂, S₃, and S₄, makes claim C₁ and when it does not make it, respectively. Note the differences in the computed probabilities of its children making claim C₁. In general, let S_g denote the parent of subgraph g and c_g denote the set of its children, if any. Equation (8.6) can then be rewritten as follows:

$\begin{array}{l}\hfill P(SC,z|SD,\theta )=\prod _{j=1}^{N}P(z_j)\times \left\{\prod _{g\in M_j}P(S_g{C}_j|\theta ,z_j)\prod _{i\in c_g}P(S_i{C}_j|S_g{C}_j)\right\}\end{array}$

  (8.8)

where

$\begin{array}{ll}\hfill P(z_j)& =\left\{\begin{array}{cc}d& z_j=1\\ (1-d)& z_j=0\\ \end{array}\right.\hfill \\ \hfill P(S_g{C}_j|\theta ,z_j)& =\left\{\begin{array}{cc}{a}_g& z_j=1,S_g{C}_j=1\\ (1-a_g)& z_j=1,S_g{C}_j=0\\ b_g& z_j=0,S_g{C}_j=1\\ (1-b_g)& z_j=0,S_g{C}_j=0\\ \end{array}\right.\hfill \\ \hfill P(S_i{C}_j|S_g{C}_j)& =\left\{\begin{array}{cc}{p}_{ig}& S_g{C}_j=1,S_i{C}_j=1\\ 1-p_{ig}& S_g{C}_j=1,S_i{C}_j=0\\ a_i& S_g{C}_j=0,S_i{C}_j=1,z_j=1\\ (1-a_i)& S_g{C}_j=0,S_i{C}_j=0,z_j=1\\ b_i& S_g{C}_j=0,S_i{C}_j=1,z_j=0\\ (1-b_i)& S_g{C}_j=0,S_i{C}_j=0,z_j=0\\ \end{array}\right.\hfill \end{array}$

  (8.9)

8.5 Evaluation

In this section, we review the evaluation of the social-aware algorithm through three real world case studies based on Twitter. Evaluation results show the viability of predominantly correct ground truth reconstruction from social sensing data. In the evaluation, the social-aware MLE algorithm, Apollo-social, is compared to three baselines from current literature. The first baseline is voting, where data credibility is estimated by the number of times the same cluster of tweets is collected from the human network. The larger the repetition, the more credibility is attributed to the content. Considering possible retweets on Twittter, two versions of the voting scheme are considered: one that counts both retweets and original tweets as full votes (called regular Voting) and one that only counts the original tweets (called Voting-NoRT). The second baseline is the basic EM algorithm we reviewed in Chapter 5 [100]. We henceforth call it regular EM. The algorithm differs from the social-ware EM in that it assumes that all sources constitute independent observers. The regular EM was shown to outperform four current information ranking schemes. The last baseline is the social data cleaning scheme suggested in [127], which extends regular EM with admission control. The admission controller is designed to improve source independence by simply removing dependent sources using some heuristic approaches from social networks. The winning admission control scheme in [127] called Beta-1 is used.

To compare these algorithms, they were implemented inside Apollo. Three datasets were composed by Apollo by using its keyword and geographic filtering mechanism. The first was collected by Apollo during and shortly after hurricane Sandy, from around New York and New Jersey in October/November 2012. The second was collected during hurricane Irene, one of the most expensive hurricanes that hit the Northeastern United States in August 2011. The third one was collected from Cairo, Egypt during the violent events that led to the resignation of the former president in February 2011. These traces are summarized in Table 8.2.

The Apollo tool operated over each data trace above, while executing each one of the compared filtering algorithms. The output of filtering was manually graded in each case to determine match with ground truth. Due to man-power limitations, only the 150 top ranked claims were manually graded by each algorithm using the following rubric:

• True claims: Claims that describe a physical or social event that is generally observable by multiple independent observers and corroborated by sources external to the experiment (e.g., mainstream news media).

• Unconfirmed claims: Claims that do not meet the definition of true claims.

Note that, the unconfirmed claims contain the false claims and some possibly true claims that cannot be independently verified by external sources. Hence, the evaluation presents a pessimistic performance estimates, taking all unconfirmed claims as false.

Figure 8.2 shows the result for the Hurricane Sandy trace. We observe that Apollo-social (i.e., the social-aware EM) generally outperformed the regular EM schemes in providing more true claims and suppressing the unconfirmed claims. This is achieved by incorporating the source dependency into the analytical framework of expectation maximization to better handle non-independent sources and their claims. The performance advantage of Apollo-social compared to regular EM is significant (nearly 20%) if the combined social network information (i.e., RT+FF social network) constructed from follower-followee and retweet relationship between users was used. We observed that the performance of the Apollo-social using ECs to estimate the social network is between Apollo-social using RT and FF social network. The reason is the RT social network is generated from the retweet relationship from current data interval and is very dynamic to reflect current source dependency and while FF social network is generated from the follower-followee relationship independently from the data traces and is relatively static. The dynamics of source dependency of EC social network is between RT and FF social network.

We also observe the regular EM schemes with admission control perform slightly worse than the one without admission control. The reason is: since the social network in the Sandy trace is relatively dense, the admission controller dropping some sources reduces the amount of useful information by sources that are tweeting when their parents are silent. In contrast, the Apollo-social scheme is shown to handle the social links in a more appropriate way. We also note the voting scheme has a reasonable performance on this trace. The reason is: a set of concrete key words (e.g., gas, station, fuel, etc.) were used for data collection, which results in a relatively “clean” input with less irrelevant information. As we shall see, the performance of voting drops significantly when the input tweet trace has more noise (e.g., Egypt trace as we will discuss later).

Note that, the exact recall may be of less interest, since we are usually interested in only the milestones and key moments of an event as opposed to every possible detail. Experiments were carried to evaluate an approximate recall metric. Specifically, 5 important events reported by media during Sandy were independently collected and checked to see if they are captured in the top claims. The top ranked claims for each of the algorithms were scanned to find these events. Results for selected baselines are shown in Table 8.3. We observed that all five events were covered by the top claims from the Apollo-social scheme, while two of them were missing from the top claims returned from the regular EM scheme.

The above precision and recall experiments were repeated on the Irene tweet trace and Egypt tweet trace. The precision results for Irene are shown in Figure 8.3. In Figure 8.3, we consistently observe that Apollo-social achieves non-trivial performance gain in reducing the number of unconfirmed claims and providing more useful information by using the social network information. Similar results are shown for the Egypt trace in Figure 8.4. For recall, collecting 10 media events on each case, we observed that Apollo-social found all 10 of them in the case of Irene and 9 in Egypt, compared to 7 and 7 by regular EM. Detailed results are shown in Tables 8.4 and 8.5.

Note that, in the experiments above, the number of claims that were verified to be false (i.e., false positives) was not reported. This is because it is easier to verify that an event occurred than it is to verify that it did not. Prominent events that are true would typically be reported in the media. Obscure events would not be. It is therefore hard to verify if they really happened or not.

There was one exception to the above. Namely, in the Sandy example, it was possible for the authors to collect ground truth on gas availability at a subset of New York and New Jersey gas stations at different points in time. This data was mainly obtained from two sources: (i) GasBuddy.com, which recruited spotters to go out and report the status of gas stations in New York and New Jersey during the gas shortage event in the aftermath of hurricane Sandy [128], and (ii) NYC_GAS_Finder, which generated updates on NYC gas stations serving gas based on credit card transaction data [129].

In order to match claims with the ground truth, tweets from the top claims were selected to meet the following criteria: (i) unambiguously mention fuel status, and (ii) explicitly describe a gas station location that matches one of the gas stations for which we have ground truth on the day of the claim. The claim is considered to be true if it matched ground truth status. Otherwise it was false. Thirty (30) of the top ranked Apollo claims could be verified this way. Of these, 29 were true matches, which is 97%. Hence, it is reasonable to hypothesize that the number of unverified claims in other data sets actually contains many true claims.

Finally, we review the analysis of the average running time for the entire Apollo system (with different algorithms) to process and analyze data collected over a one hour window in each of three data traces. The running time is measured from the point when the first tweet of the hour is processed to the point when the results for the hour window are available. The processing times are shown in Table 8.6. We observe that the processing time depends mainly on the size of the trace. The Voting scheme did exhibit the fastest run-time, as might one expect, at the cost of more error in classifying claims correctly. The running speed of Apollo-social is quite comparable to the regular EM scheme. We also note that the running time of Apollo-social and other baselines is well below one hour, which verified the real-time feature of the Apollo system on the real-world data traces.

Note that, the values reported in Table 8.6 include the time taken for computing distance functions, clustering, and running the chosen estimation algorithm (i.e., Voting, Regular EM, or Apollo-social). This explains why voting comes so close to the other two algorithms in run-time, despite the fact that they involve multiple iterations, while voting does not. A more detailed examination reveals that the bottleneck in Apollo lies in computing the distance functions between pairs of observations (as mentioned in Section 8.3). Hence, in total terms, the iterative expectation maximization algorithm described in this paper does not add too much overhead.

8.6 Discussion and Limitations

The chapter reviews encouraging results demonstrating that the accuracy of claims made by social sources can be estimated predominantly correctly even when such sources have unknown reliability and when data has uncertain provenance.

Interestingly, it was observed that the social-aware EM scheme tended to reduce the number of introspective (e.g., emotional and opinion) tweets, compared to tweets that presented descriptions of an external world. This was serendipitously quite appropriate of a “sensor network” that is not supposed to have emotions and opinions, but rather convey observations. Looking into the problem further, it was noticed that emotions and slogans tended to be retweeted along social network topology pathways and hence, tended to be suppressed by the social aware algorithm. In contrast, external facts (such as gas availability at a given location) were often observed independently by multiple sources, and hence not suppressed.

The observation offers many questions and opportunities for improvement, especially when it comes to modeling information propagation. The FF, RT, and RT+FF only provide an approximation of the actual latent social network of how sources are influencing each other. They can be improved by building information propagation models that account for topic (e.g., sensational, emotional, and other news might propagate along different models), expertise, relationship reciprocity, mutual trust, and personal bias (e.g., the claim that “police is beating up innocent demonstrators,” versus “demonstrators are attacking the police”). Note that distortions and biases of human sensors are quite persistent in terms of direction and amplitude, unlike white noise distortions. In a sense, humans exaggerate information in predictable ways. Understanding more about the community of sources can help better quantify the distortion and bias, leading to more accurate formulations of the maximum likelihood model.

The source node behavior model deserves more investigation. The work presented in this chapter only considers the social network structure that can be represented by a forest of two level trees. It also assumes the child node will not independently make the same claim as its parent. Those assumptions might not hold in many real world applications. For example, the twitter user could independently tweet about a popular event with very similar content as its parent. Therefore, it is necessary to develop more comprehensive models to accurately characterize the social network structure in a more general form. The key challenge is how to integrate the new node behavior model with the maximum likelihood framework we reviewed in this chapter.

In this chapter, the social-aware EM scheme focused on a binary claim model. It is shown to be a reasonable model to represent the physical events that are either true or false. However, there is also a large number of real world applications where observations from participants are non-binary (e.g., on-line review systems). It is possible to generalize the fact-finding method that accounts for multiple mutually exclusive values (see Chapter 7) to incorporate the social network model. Furthermore, it is also interesting to generalize the estimation model to better handle claims that have continuous values. Probabilistic, Subjective, or Fuzzy logics could be good modeling techniques to apply in this case.

A separate problem is to deal with dynamics. When the network changes over time, how best to account for it in MLE? A better formulation is needed that puts less weight on older data. Deception and malicious users also need to be addressed. Of particular interest are sources that gain advantage by acting reliably then change their behavior to deceive the system. It is also interesting to understand the impact of distance functions inside Apollo on the accuracy of estimation results. Distance function assess how close two tweets are. Current functions are based on lexicology only (i.e., they compare words without interpreting them). How much benefit is attained by syntactic and semantic analysis of different levels of sophistication? How does that benefit depend on the properties of the trace? These issues provide directions for future work.

Finally, we should note that the human sensor model and the estimation framework reviewed in this chapter is not limited to the applications that are based on Twitter. It can also be applied to a much broader set of crowdsourcing and mobile sensing applications, where the data are collected from both human sources and the devices on their behalf. Examples include traffic condition prediction using data from in-vehicle GPS devices and geo-tagging applications using participant’s smartphones. In these applications, humans or their devices represent the sources and measurements they report represent claims. The reviewed estimation approach can be used to address similar data reliability and uncertain data provenance challenges in these applications.