Propagation History Ranking in Social Networks: A Causality-Based Approach

If $\mathrm{\Gamma }$ is the selected contingency set for edge $t$ , $\mathrm{\Gamma }$ must satisfy two constraints: (a) after removing all edges in $\mathrm{\Gamma }$ , the diffusion remains but the removal of $t$ would make the diffusion fail; and (b) $\mathrm{\Gamma }$ must be the minimum set satisfying ${\bigcup }_{x\in \mathrm{\Gamma }}\text{sc}(x)=\mathrm{\Phi }-\text{sc}(t)$ . Based on these two constraints, we propose a greedy algorithm named Appresp; the main aspects of this algorithm are as follows:

(1) Get the covered set $\text{SA}=\text{sc}(t,\mathrm{\Phi })$ and the uncovered set $\text{ST}=\mathrm{\Phi }-\text{SA}$ .

(2) Choose edge $x\in T-\mathrm{\Gamma }$ which satisfies these two rules: (a) $\text{sc}(x,\text{ST})$ contains as many as possible of the sets in ST, and (b) $\text{SA}\ne \text{sc}(x,\text{SA})$ .

(3) Add $x$ to $\mathrm{\Gamma }$ , remove $\text{sc}(x,\text{SA})$ from SA, and remove $\text{sc}(x,\text{ST})$ from ST.

(4) Repeat Steps (2) and (3) until ST gets empty, and compute the responsibility of $t$ .

The key aspects of our algorithm are the two rules listed in Step 2. The first rule is a heuristic for ranking the edges to be added to the contingency set. The second rule is a constraint to ensure that $t$ is still a cause of the diffusion (in accordance with Definition 3) after removing the calculated contingency set. This selection guarantees a feasible solution, provided that the propagation history contains no redundancy (Redundancy is defined by Ref. [ 21 ], i.e., a propagation trace $t^i$ is redundant if there exists another trace $t^j$ whose edge set is a subset of $t^i$ ’s edge set. After removing all redundancies, the remaining edges are causes (Definition 3). This is also the PTIME solution for the causality checking problem in propagation histories). We formalize this property in Proposition 4 and present the pseudo code in Algorithm 1.

Proposition 4 Appresp guarantees a feasible solution, provided that the propagation history contains no redundancy.

Proof We continue with the definitions of $\mathrm{\Phi }$ , $T$ , $\mathrm{\Gamma }$ , sc, ST, and SA from Algorithm 5.2. Suppose the propagation history does not contain any redundant traces. We calculate the responsibility of edge $t$ as an example.

Case A (If Appresp returns a contingency set $\mathrm{\Gamma }$ ). Suppose we get the initial covered set $\text{SA}=\text{sc}(t,\mathrm{\Phi })$ and the uncovered set $\text{ST}=\mathrm{\Phi }-\text{SA}$ . In this case, ST is covered by ${\bigcup }_{x\in \mathrm{\Gamma }}\text{sc}(x,\mathrm{\Phi })$ . For simplicity, here "the removal of edge $t$ " refers to removing all sets in $\text{sc}(t,\mathrm{\Phi })$ from both SA and ST. In accordance with our constraint rule, the removal of $\mathrm{\Gamma }$ makes ST empty but cannot render SA empty. In addition, if we first remove all edges from $\mathrm{\Gamma }$ , the further removal of $t$ renders SA empty. Consequently, according to Definition 3, $\mathrm{\Gamma }$ is a feasible contingency set for $t$ .

Case B (If Appresp cannot find a contingency set). Suppose we have gotten temporary results ${\mathrm{\Gamma }}^{\prime }$ , ${\text{SA}}^{\prime }$ , and ${\text{ST}}^{\prime }$ , when no edge satisfies our constraint rule, i.e., for each left edge $x\in T-{\mathrm{\Gamma }}^{\prime }$ , we get ${\text{SA}}^{\prime }=\text{sc}(x,{\text{SA}}^{\prime })$ . Suppose $c_t$ is the edge set of trace $t^t$ in ${\text{ST}}^{\prime }$ and $c_a$ is the edge set of trace $t^a$ in ${\text{SA}}^{\prime }$ . For each edge $x$ in $c_t$ , we will find $\text{sc}(x,{\text{SA}}^{\prime })$ contains $c_a$ . Thus, we get $c_t\subseteq c_a$ , i.e., $t^a$ is redundant. This is opposite to our hypothesis of non-redundancy.

Therefore, Appresp guarantees a feasible solution for a propagation history without redundancy.

Complexity of Appresp. Suppose the propagation history has $N$ traces and $M$ edges, the average length of traces is $L$ , and the corresponding contingency set size is $k$ . On average, the time complexity of Appresp is $O(k\times (L\times N+M))$ . Note that, both $k$ and $L$ are usually small numbers, i.e., Appresp has linear time complexity (We verify the small values of $k$ in our experiments, and $L$ is also small according to the concept of six degrees of separation^{[ 24 ]}).

Proof Given the input edge $t$ , to calculate its responsibility we need to loop the following steps $k$ times.

(1) Line 6 of Algorithm 1 performs two tasks. Firstly, it calculates $\text{sc}(x,\text{ST})$ for each edge $x$ ; we can use an inverted index to speed up this calculation (the time complexity is $O(L\times N)$ ). It then selects edge $x$ , which satisfies the two rules (the time complexity is at most $O(M)$ , since SA is usually small).

(2) Line 9 removes all sets in $\text{sc}(x,\text{ST})$ from ST. The time complexity is $O(N/k)$ , since on average we need to repeat this removal $k$ times to empty ST.

(3) Line 10 does a similar task on SA to that performed on ST in Line 9. Therefore, the time complexity is also $O(N/k)$ .

Therefore, the overall time complexity is $O(k\times (L\times N+M+2\times N/k))$ = $O(k\times (L\times N+M))$ .

Example 8 (Example of Algorithm 1). Continuing with the same propagation history $\mathrm{\Phi }$ in Example 1, we use edge $B$ as an example and employ Algorithm 1 to compute its responsibility. We first get the covered set $\text{SA}=\text{sc}(B,\mathrm{\Phi })=\{c_1\}$ and the uncovered set $\text{ST}=\{c_2,c_3\}$ . Then, we find that $A$ cannot be selected because $\text{sc}(A,\text{SA})=\text{SA}$ . We can select either of $C$ or $D$ , since both satisfy our constraint rule and have the same priority according to our heuristic rule. Suppose we choose $C$ first and then choose $D$ in the next round. Finally, we get the contingency set $\{C,D\}$ , so the responsibility of $B$ is $1/3$ .

Unlike the approach of our Appresp method, Qin et al.^{[ 27 ]} directly adopted a greedy strategy to solve the corresponding SCP problem, i.e., they ignore the constraint rule in our method. However, without this rule, the greedy strategy cannot guarantee a feasible solution for the responsibility problem (as shown in Example 7). We will show this property and compare the two methods in presenting the results of our experiments.

We first review Pearl’s definition of Probability of Necessity and Sufficiency (PNS)^{[ 14 ]}, which has been proved to consider causal effects from both the necessity and sufficiency aspects. We then prove Proposition 1 by showing that PNS and DCE are equivalent in the scenario of propagation history ranking.

Definition 6 (PNS). Suppose the propagation history of a diffusion is $\mathrm{\Phi }$ , and $X$ is a participant edge. Let $x$ and $x^{\prime }$ stand for the propositions " $X$ non-failed" and " $X$ failed" , respectively. The probability of the necessity and sufficiency of edge $X$ for diffusion $\mathrm{\Phi }$ is defined as the expression:

(3) $$\mathrm{PNS}\triangleq P({\mathrm{\Phi }}_x=\text{true},{\mathrm{\Phi }}_{x^{\prime }}=\text{false})$$

In this definition, ${\mathrm{\Phi }}_x=\text{true}$ stands for that enabling edge $X$ leads to a successful information transmission, and ${\mathrm{\Phi }}_{x^{\prime }}=\text{false}$ stands for the removal of $X$ makes this transmission fail. Thus, PNS considers causal effects from both the necessity and sufficiency aspects; a rigorous proof can be found in Ref. [ 14 ].

Proof of Proposition 1 We continue with the same definitions of $\mathrm{\Phi }$ , $X$ , $x$ , and $x^{\prime }$ in Definition 6. Let set $S$ contain all propagation traces which go through edge $X$ , with the rest of the traces is put into another set (denoted as $\bar{S}$ ). Let $s$ and $\bar{s}$ stand for the cases that $S$ and $\bar{S}$ , respectively, can successfully transmit the information, and let $s^{\prime }$ and ${\bar{s}}^{\prime }$ denote their complements. We first get the following two properties.

Property 1 X does not affect $\bar{s}$ and ${\bar{s}}^{\prime }$ :

$P({\bar{s}}_x)=P({\bar{s}}_{x^{\prime }})=P(\bar{s})$ and $P(\bar{s}_{\prime }^x)=P(\bar{s}_{\prime }^{x^{\prime }})=P({\bar{s}}^{\prime })$ .

Property 2 Since all traces in $S$ go through $X$ , we have $P(s_{x^{\prime }})=0$ .

Consider the definition of DCE (Definition 2):

Consider the definition of PNS (Definition 6):

Combining the above two results, we get the following equation:

(4) $$\mathrm{ }\mathrm{DCE}(X)=\mathrm{PNS}(X)=P({\mathrm{\Phi }}_x=\text{true})-P({\mathrm{\Phi }}_{x^{\prime }}=\text{true})$$

Note that a similar equation has also been proved by Pearl^{[ 14 ]}, when an elaborate complex assumption (exogeneity and monotonicity) holds true. As an extension, we prove it from the viewpoint of information propagation.

As shown in Eq. ( 4 ), PNS and DCE can be seen as the same causal measure in the problem of propagation history ranking. Therefore, we successfully prove Proposition 1.

We first review Pearl’s definition of Probability of Necessity and Sufficiency (PNS)^{[ 14 ]}, which has been proved to consider causal effects from both the necessity and sufficiency aspects. We then prove Proposition 1 by showing that PNS and DCE are equivalent in the scenario of propagation history ranking.

Definition 6 (PNS). Suppose the propagation history of a diffusion is $\mathrm{\Phi }$ , and $X$ is a participant edge. Let $x$ and $x^{\prime }$ stand for the propositions " $X$ non-failed" and " $X$ failed" , respectively. The probability of the necessity and sufficiency of edge $X$ for diffusion $\mathrm{\Phi }$ is defined as the expression:

(3) $$\mathrm{PNS}\triangleq P({\mathrm{\Phi }}_x=\text{true},{\mathrm{\Phi }}_{x^{\prime }}=\text{false})$$

In this definition, ${\mathrm{\Phi }}_x=\text{true}$ stands for that enabling edge $X$ leads to a successful information transmission, and ${\mathrm{\Phi }}_{x^{\prime }}=\text{false}$ stands for the removal of $X$ makes this transmission fail. Thus, PNS considers causal effects from both the necessity and sufficiency aspects; a rigorous proof can be found in Ref. [ 14 ].

Proof of Proposition 1 We continue with the same definitions of $\mathrm{\Phi }$ , $X$ , $x$ , and $x^{\prime }$ in Definition 6. Let set $S$ contain all propagation traces which go through edge $X$ , with the rest of the traces is put into another set (denoted as $\bar{S}$ ). Let $s$ and $\bar{s}$ stand for the cases that $S$ and $\bar{S}$ , respectively, can successfully transmit the information, and let $s^{\prime }$ and ${\bar{s}}^{\prime }$ denote their complements. We first get the following two properties.

Property 1 X does not affect $\bar{s}$ and ${\bar{s}}^{\prime }$ :

$P({\bar{s}}_x)=P({\bar{s}}_{x^{\prime }})=P(\bar{s})$ and $P(\bar{s}_{\prime }^x)=P(\bar{s}_{\prime }^{x^{\prime }})=P({\bar{s}}^{\prime })$ .

Property 2 Since all traces in $S$ go through $X$ , we have $P(s_{x^{\prime }})=0$ .

Consider the definition of DCE (Definition 2):

Consider the definition of PNS (Definition 6):

Combining the above two results, we get the following equation:

(4) $$\mathrm{ }\mathrm{DCE}(X)=\mathrm{PNS}(X)=P({\mathrm{\Phi }}_x=\text{true})-P({\mathrm{\Phi }}_{x^{\prime }}=\text{true})$$

Note that a similar equation has also been proved by Pearl^{[ 14 ]}, when an elaborate complex assumption (exogeneity and monotonicity) holds true. As an extension, we prove it from the viewpoint of information propagation.

As shown in Eq. ( 4 ), PNS and DCE can be seen as the same causal measure in the problem of propagation history ranking. Therefore, we successfully prove Proposition 1.

We first review Pearl’s definition of Probability of Necessity and Sufficiency (PNS)^{[ 14 ]}, which has been proved to consider causal effects from both the necessity and sufficiency aspects. We then prove Proposition 1 by showing that PNS and DCE are equivalent in the scenario of propagation history ranking.

Definition 6 (PNS). Suppose the propagation history of a diffusion is $\mathrm{\Phi }$ , and $X$ is a participant edge. Let $x$ and $x^{\prime }$ stand for the propositions " $X$ non-failed" and " $X$ failed" , respectively. The probability of the necessity and sufficiency of edge $X$ for diffusion $\mathrm{\Phi }$ is defined as the expression:

(3) $$\mathrm{PNS}\triangleq P({\mathrm{\Phi }}_x=\text{true},{\mathrm{\Phi }}_{x^{\prime }}=\text{false})$$

In this definition, ${\mathrm{\Phi }}_x=\text{true}$ stands for that enabling edge $X$ leads to a successful information transmission, and ${\mathrm{\Phi }}_{x^{\prime }}=\text{false}$ stands for the removal of $X$ makes this transmission fail. Thus, PNS considers causal effects from both the necessity and sufficiency aspects; a rigorous proof can be found in Ref. [ 14 ].

Proof of Proposition 1 We continue with the same definitions of $\mathrm{\Phi }$ , $X$ , $x$ , and $x^{\prime }$ in Definition 6. Let set $S$ contain all propagation traces which go through edge $X$ , with the rest of the traces is put into another set (denoted as $\bar{S}$ ). Let $s$ and $\bar{s}$ stand for the cases that $S$ and $\bar{S}$ , respectively, can successfully transmit the information, and let $s^{\prime }$ and ${\bar{s}}^{\prime }$ denote their complements. We first get the following two properties.

Property 1 X does not affect $\bar{s}$ and ${\bar{s}}^{\prime }$ :

$P({\bar{s}}_x)=P({\bar{s}}_{x^{\prime }})=P(\bar{s})$ and $P(\bar{s}_{\prime }^x)=P(\bar{s}_{\prime }^{x^{\prime }})=P({\bar{s}}^{\prime })$ .

Property 2 Since all traces in $S$ go through $X$ , we have $P(s_{x^{\prime }})=0$ .

Consider the definition of DCE (Definition 2):

Consider the definition of PNS (Definition 6):

Combining the above two results, we get the following equation:

(4) $$\mathrm{ }\mathrm{DCE}(X)=\mathrm{PNS}(X)=P({\mathrm{\Phi }}_x=\text{true})-P({\mathrm{\Phi }}_{x^{\prime }}=\text{true})$$

Note that a similar equation has also been proved by Pearl^{[ 14 ]}, when an elaborate complex assumption (exogeneity and monotonicity) holds true. As an extension, we prove it from the viewpoint of information propagation.

As shown in Eq. ( 4 ), PNS and DCE can be seen as the same causal measure in the problem of propagation history ranking. Therefore, we successfully prove Proposition 1.

We first review Pearl’s definition of Probability of Sufficiency^{[ 14 ]}. Then, we show how to calculate it from the propagation history.

Definition 8 (PS).  Continuing with the same definitions of $\mathrm{\Phi }$ , $X$ , $x$ , and $x^{\prime }$ in Definition 6 in Appendix A, the probability of the sufficiency of edge $X$ for diffusion $\mathrm{\Phi }$ is defined as the expression:

$$\mathrm{PS}\triangleq P({\mathrm{\Phi }}_x=\text{true}\mid X=\text{false},\mathrm{\Phi }=\text{false}).$$

Proposition 6 Continuing with the same definitions of $\mathrm{\Phi }$ , $X$ , $x$ , $x^{\prime }$ , $s$ , $\bar{s}$ , $s^{\prime }$ , and ${\bar{s}}^{\prime }$ in the proof of Proposition 1 in Appendix A, the PS value of edge X (for diffusion $\mathrm{\Phi }$ ) can be estimated as the expression:

(6) $$\mathrm{PS}=P\left({\bar{s}}^{\prime }(s|x)x^{\prime }\right)/P({\bar{s}}^{\prime }{x}^{\prime })$$

Proof To calculate PS, we need to find a situation where $X=\text{false}$ and $\mathrm{\Phi }=\text{false}$ shows up at first, but where changing $x^{\prime }\to x$ would produce $\mathrm{\Phi }=\text{true}$ . This situation corresponds to $s^{\prime }{\bar{s}}^{\prime }\Lambda x^{\prime }$ , i.e., $X=\text{false}$ and $\mathrm{\Phi }=\text{false}$ both occur. Then, we change $x^{\prime }\to x$ , and cause $\mathrm{\Phi }=\text{false}\to \mathrm{\Phi }=\text{true}$ . So we get

According to the definition of intervention^{[ 14 ]}, $P(y_x)$ equals $P(y|x)$ in the causal model of propagation history, because each participant edge $X$ is not affected by any other cause. Consequently, we could get

$$\mathrm{PS}=P\left({\bar{s}}^{\prime }{x}^{\prime }(s|x)\right)/P({\bar{s}}^{\prime }{x}^{\prime }).$$