{'fraction_non_alphanumeric': 0.044916320917439745, 'fraction_numerical': 0.012633443662300126, 'mean_word_length': 3.9071257005604485, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Effector Detection in Social Networks

In a social network, influence diffusion is the process of spreading innovations from user to user. An activation state identifies who are the active users who have adopted the target innovation. Given an activation state of a certain diffusion, effector detection aims to reveal the active users who are able to best explain the observed state. In this paper, we tackle the effector detection problem from two perspectives. The first approach is based on the influence distance that measures the chance that an active user can activate its neighbors. For a certain pair of users, the shorter the influence distance, the higher probability that one can activate the other. Given an activation state, the effectors are expected to have short influence distance to active users while long to inactive users. By this idea, we propose the influence-distance-based effector detection problem and provide a 3-approximation. Second, we address the effector detection problem by the maximum likelihood estimation (MLE) approach. We prove that the optimal MLE can be obtained in polynomial time for connected directed acyclic graphs. For general graphs, we first extract a directed acyclic subgraph that can well preserve the information in the original graph and then apply the MLE approach to the extracted subgraph to obtain the effectors. The effectiveness of our algorithms is experimentally verified via simulations on the real-world social network.


I. INTRODUCTION
S OCIAL networks serve as important platforms for information propagation as they allow efficient and effective communications between participants. In the sense of online social networks, e.g., Flicker, Facebook, and Twitter, new topics may spread rapidly through the networks via the friendship relation. In the context of viral marketing, companies employ P2P advertising to achieve the increase in brand awareness and sales. At the same time, risks from rumors or viruses also propagate through the Internet or local area network. During the last two decades, the problems regarding influence diffusion has been extensively studied in many domains, such as economics, epidemiology, and social media.
For a social network with a certain influence diffusion, an activation state shows the users who have been influenced. The effectors are the nodes that can best explain the observed activation state. That is, once selected as seed nodes, the effectors are able to activate exactly the active nodes specified by the given activation state. It has been shown that the identification of effectors is of great significance in understanding the dynamics of influence diffusion. On one hand, effectors play as the critical nodes that encourage or halt the spread of new ideas and technologies. On the other hand, effectors may be interpreted as the source of the influence propagation, and thus effector detection helps in identifying the users who are the inventors of novel ideas or the culprits initiating rumors or infections. Nevertheless, measuring the quality of effector is not a trivial problem. Suppose there is one effector. For the activation state shown in Fig. 1(a), the circled node can be a good effector since it is the only node that is able to activate all other active nodes. However, for the second activation state shown in Fig. 1(b), determining the best effector from the active nodes requires more investigation. In fact, the criteria for selecting effectors depend on not only the pattern of the activation state but also on the diffusion model. We will formally define our problem in Section III.
The problem of identifying propagation sources in networks has been widely investigated by Jiang et al. [1], while effector detection has received much less attention. It is worthy to note that these two problems are, although similar, not identical. The propagation source identification problem assumes that the given activation state is a spreading result caused by a certain seed set, while the activation state in the effector problem does not necessarily have this property. For example, assuming the budget is one, the activation state shown in Fig. 1(c) is not a valid input for the propagation source identification problem since there is no node that can result such an influence pattern. However, we can still solve the effector detection problem on this activation state as there always exists the node that can produce an activation state that is the most similar to the given one. Furthermore, the solutions to these problems may not be the same for the same input. Consider the example shown in Fig. 1(d). Suppose associated with each directed edge (u, v) there is a weight w(u, v) ∈ [0, 1], which denotes the probability that u can activate v after becoming active. For this activation state, the source of the influence should be node u, but node v is actually a better choice for selecting effector. One can check that for the four active nodes in Fig. 1(d), u activates 1.02 of them on average, while v brings three active nodes for sure. Therefore, techniques designed for identifying influence sources may not be applicable for detecting good effectors. Furthermore, most of the prior works are focused on epidemic models such as susceptible-infected (SI) model, SI-susceptible (SIS) model, and SI-recovery (SIR) model, and a few works have considered the information-propagation models for social networks. In this paper, we consider a classic information-propagation model, namely, independent cascade (IC) model.
Lappas et al. [2] are among the first who studied the effector detection problem for an IC model. In particular, they propose the effector problem from the perspective of combinatorial optimization and prove that their problem is NP-hard to be solved optimally or efficiently approximated. As expected, the formulation of the problem determines the computational difficulty. In this paper, following their work, we consider the IC model but formulate the effector detection problem from different views.

A. Our Contribution
In a social network, influence distance is a metric that measures the distance between users with respect to information propagation. That is, information is more easily to spread from one user to another if the influence distance is short. Therefore, given an activation state, the influence distance between the effectors and active (also inactive) nodes should be short (also long). As shown in the experiments, given an activation state, for a user set S, there is a clear negative (also positive) correlation between the effector quality of S and the influence distance between S and active (also inactive) nodes. According to that, we introduce the influence-distance-based effector detection problem. For this problem, we first show a 3-approximation and then provide an efficient heuristic. Our second method for selecting effectors employs the approach of maximum likelihood estimation (MLE). One can see that the nodes that, if selected as seed nodes, are able to maximize the probability of observing the given activation state are naturally to be good effectors. For the directed acyclic graphs (DAGs), we show that the optimal MLE can be obtained in polynomial. For general graphs, we proceed in two steps. We first extract a DAG subgraph that maximally preserves the information in the original graph with respect to entropy and then apply the MLE approach to the extracted DAG to detect effectors. By the results of the experiments conducted on the real social network, both of our approaches can produce high-quality effectors and perform better than the state-of-art method.
The rest of this paper is organized as follows. Section II reviews the related work. In Section III, we introduce the IC model and formally define the metric of effector quality. The proposed two approaches are provided in Sections IV and V, respectively. In Section VI, we experimentally evaluate our methods using the Facebook network. Section VII concludes this paper.
II. RELATED WORK Lappas et al. [2] proposed the effector detection problem for the IC model. According to their formulation, the optimal solution is obtainable on tree graphs in polynomial time, while the general graphs are hard to handle. They also propose several heuristics and explore their performance via experiments. We are not aware of any other work addressing this problem for social networks, but there has been a huge body of works regarding the identification of influential nodes or propagation sources.
The topics regarding selecting important users in social networks have been considered for different application domains. Domingos and Richardson [9] first studied the influential customers in viral marketing. Motivated by [9], Kempe et al. [10] propose the well-known influence maximization problem that aims to select the seed users that can maximize the influence. Following their framework, many relevant problems in social network have been studied [11]- [14]. In the influence maximization problem, the goal is to influence the nodes as many as possible while the effector detection problem focuses on achieving a certain activation state. It has been shown that the influence maximization problem can be taken as a special case of the effector detection problem. In the context of immunization, the important nodes are the best for removal to halt the spread of epidemics [15]- [17]. One can see that the immunization problem is the opposite problem to the influence maximization problem, and, in fact, the effector detection problem is somehow the combination of these two problems. We will later discuss this in Section III. Rusmevichientong et al. study the problem of finding the consumers who tend to purchase products earlier than others. According to their formulation, the early buyers correspond to the nodes with large difference between the weights of the outgoing and incoming edges. Different from our setting, their network is constructed based on the purchase information and they do not consider the influence dynamics.
A series of methods for identifying propagation sources has been proposed for epidemic models, e.g., SI, SIR, and SIS models. In such models, the nodes are initially susceptible and may later switch states among susceptible, infected, or recovery. In the SI model, a node never changes its state once becoming infected, while in the SIR or SIS mode, the infected node can later become recovery or susceptible again. Shah and Zaman [3] study the problem of detecting sources of computer viruses in the SI model based on the concept of rumor centrality. Dong et al. [4] consider the single source detection problem by constructing the maximum a posteriori estimator. The similar methods have also been applied to SIS and SIR models [5], [6]. Most of the initial works focus on the tree-like networks to obtain theoretical results. Techniques for general graphs appear in recent years. Prakash et al. [7] consider the generic network topology and propose the NETSLEUTH method for the SI model. Later, Altarelli et al. [8] study several Bayesian inference problems for irreversible stochastic epidemic models, namely, the SIR model. In another issue, the propagation sources can be detected by injecting sensors. When the sensors are injected into networks, they act as normal users while collecting the propagation information including states, transition time, and infection directions. As mentioned in Section I, the propagation source detection problem is not identical to the effector detection problem. The effectors are the nodes that can result in the activation state similar to the one given, while the sources are the nodes initiating the influence diffusion.

III. PROBLEM
In this section, we give the preliminaries regarding the IC model and discuss the issue on defining good effectors. In this section, we give the preliminaries regarding the IC model and discuss the issue on defining good effectors. The notations that are frequently used in the rest of this paper are listed in Table I. A social network is represented by a directed graph where N is the number of users in G. In order to initiate the influence diffusion, we first activate a set of seed users who will potentially activate their friends. We speak of each user as being either active or inactive. In the IC model, associated with each edge e = (u, v), there is a Pr[e] ∈ [0, 1], which is the propagation probability from u to v. An active node u has only one chance to activate its inactive neighbor v with the probability of Pr [(u, v)]. If u successfully activates v via edge (u, v), we call edge (u, v) a live edge. After the activation of seed users, the process of influence diffusion goes round by round and terminates when there is no user can be further activated. An activation state A = (a 1 , . . . , a N ) is a vector of {0, 1} N , where a i = 1 (also a i = 0) if user i is active (also inactive). Given an activation state A, we denote the set of active (also inactive) nodes in A by X A 1 (also X A 0 ). For a node set S that is selected as seed set, we denote by A S the activation state when the influence diffusion terminates. Note that A S is a random vector since the IC model is a probabilistic model. Given an integer B, the B-effector detection problem is defined as follows.
Given a target activation state A * , we aim to find a subset 1 S of X A * 1 with B nodes, which is able to result an activation state A S similar to A * .
Since the given state A * is fixed, in the rest of this paper, we will refer to X A * 1 (also X A * 0 ) as X 1 (also X 0 ). Let N 1 = |X 1 | be the number of nodes in X 1 . Let · be the L 1 -norm and E[·] be the expected value of a random variable. In this paper, we consider the following metrics to measure the quality of a node set S. The first measure is given by 1 Since the effectors are naturally active, they are limited in X A * 1 . which is the expected difference between the target activation state A * and the one resulted by S. Let α(S, u) be the probability that node u can be activated when S is selected as the seed set. The second measure is defined as follows: where E[A S ] = (α(S, u 1 ), . . . , α(S, u n )) is the expected activation state resulted by S. Note that when A * = (1, . . . , 1), our problem reduces to the influence maximization problem, which aims to find a set of seed users to maximize the number of final active users. As shown in [2], it is NP-hard to minimize (1) or (2) and we cannot even obtain an α-approximation for α > 1 unless NP = P. In this paper, we present two techniques to find a node set S, S ⊆ X 1 , with small f 1 (S) and f 2 (S).

IV. INFLUENCE-DISTANCE-BASED EFFECTOR DETECTION
Our first approach is designed based on the concept of influence distance. Generally speaking, for two users u and v, the influence distance d(u, v) measures the chance that the influence can be spread to v from u. The larger the value of d(u, v), the lower the probability with which u can activate v. Therefore, given the activation state A * , the nodes in X 1 (also X 0 ) are expected to have short (also long) distance to the effectors. From this perspective, we formulate the effector detection problem as an optimization problem and provide a 3-approximation algorithm.
We start by discussing how to extract the influence distance from the IC model. A path pp uv from node u to v is a set of edges and its propagation probability Pr[ pp uv ] is defined as e∈ pp uv Pr[e]. Intuitively, u can activate v via path pp uv with the probability of Pr[ pp uv ]. Let pp G uv be the path in G that has the maximum path propagation probability from u to v and we call pp G uv the maximum diffusion path from u to v. Clearly, pp G uv cannot completely capture the influence diffusion from u to v as there are many alternative joint paths. However, if we take the correlation of all the paths into consideration and calculate α({u}, v) precisely, we will encounter a new problem that is #P-hard [18]. We herein develop the kth influence distance d k (u,v) that considers the k independent paths from u to v that have the largest propagation probability. For two users u and v, the kth influence distance is induced by the k-max path set P k uv defined as follows: where G k is a series of instances of IC model and V (G) and E(G), respectively, denote the vertex set and edge set of G.
Recall that pp is the maximum diffusion path from u to v in G k . In the above process, we successively find the maximum diffusion path in G k and G k+1 is obtained from By the construction of P k uv , the paths in P k uv are edge disjoint and thus u activates v independently through these paths. Therefore, 1 − pp uv ∈ P k uv (1 − Pr[ pp uv ]) represents the probability that u can activate v through the paths in P k uv .
is a lower bound of α({u}, v) and it is more closer to α({u}, v) when k is large. One can also see that a small d k (u,v) implies the high propagation probability between u and v. For a node set V and a node u, the kth influence distance d k (V ,u) between V and u is defined as v∈V d k (v,u) and for two sets V 1 and V 2 , (v,u) as we consider the directed graph. Now let us go back to the effector detection problem. Given an activation state A * , we expect a set S of effectors such that the influence distance between S and u is small (also large) if u is active (also inactive) in A * . Thus, the solution to the following problem serves as a good effector set: where λ ∈ [0, 1] is an adjustable parameter. The terms u∈S v∈X 1 \S d k (u,v) and u∈S v∈X 0 d k (u,v) are the distance from S to active and inactive nodes, respectively. If λ is close to 1, it implies that making the nodes in X 1 active is a prime consideration and it is not important whether the nodes in X 0 are inactive. In all four graphs, the y-axis and x-axis denote the objective value and the score of the quality metric of the generated effectors, respectively. Each graph gives four curves plotting the influence spread under four seeding strategies, respectively.
Given X 0 , X 1 , and S, the whole network is partitioned into three parts, X 0 , X 1 \ S, and S. Since and d k (X 1 ,X 0 ) is fixed, the above problem is identical to the following one.
Problem 1 (k-IDBED): S ⊆ X 1 . We denote the above problem by the kth influencedistance-based effector detection (k-IDBED) problem. Before discussing how to solve this problem, we first show the relationship between the objective value g k (S) and the quality of effectors according to f 1 (S) and f 2 (S). The simulation results evince that for a node set S, a small g k (S) implies a high quality of S. We employ the Facebook network [19], which contains 4036 nodes and 176 468 edges. The influence propagation probability for an edge (u, v) is set as 1/deg(u), where deg(u) is the out-degree of node u. Here we set λ to be 0.5. We generate 1000 activation states where each activation state is generated by randomly selecting ten seed nodes and simulating the diffusion process. We set k to be 1 and 3, respectively. For each activation state, we randomly generate an effector set S with ten nodes and calculate g k (S), f 1 (S) and f 2 (S). The scatter diagrams are plotted in Fig. 2. Since small f 1 (S) or f 2 (S) implies high effector quality, the results strongly support that the node set S with small g k (S) can be good effectors.
In the following, we study the cases for k = 1 and k > 1, respectively.

A. 1-IDBSD Problem
In this section, we present a 3-approximation algorithm for Problem 1 when k = 1. In particular, the 1-IDBSD problem is stated as follows.
1) Triangle Inequality: has the following property.
Lemma 1: For every three nodes u, v, and w in V Thus The above triangle inequality allows us to design efficient approximation algorithms for Problem 2. As shown later in this section, the perfect matching problem plays an important role in solving Problem 2.
2) Bipartite Minimum Perfect Matching Problem: Given a weighted complete bipartite graph G = (V 1 , V 2 , E) with a weight w(e) on each edge e ∈ E, the problem asks for a perfect matching with the minimum weight. It is well known that this problem can be solved in polynomial time via linear programming. We assume there is a solver denoted by BMPM(G) whenever we need to solve this problem.
For an ordered pair (u, v) of two nodes u and v in X 1 , we construct a complete bipartite graph as follows.
3) Bipartite Graph Construction: Given two nodes u, v ∈ X 1 , we construct a weighted complete bipartite graph Construction (G, X 1 , u, v, N 1 , B) 1: Input: G = (V, E), X 1 , u i ∈ X i , u j ∈ X j , B and λ. 2: Output: A complete bipartite graph (V 1 , V 2 , E) with a weight function w(·). 3: N 1 := |X 1 |; 4: X 0 := V \ X 1 ; 5: V 1 := X 1 ; 6: V 2 := {v 1 2 , . . . , v N 1 2 }; 7: for each w ∈ V 1 do 8: for i = 1 : N 1 do 9: if i ≤ B then 10: Set ., X 1 ), the weight function is defined as follows: The above construction is formally shown in Algorithm 1. For a perfect matching of G uv , each node in V 1 is matched to one node in V 2 , and thus there are exactly B nodes matched to the For each pair of nodes u and v in G, let E uv be the edge set of the minimum perfect matching of G uv , V uv be the set of the nodes matched to {v 1 2 , . . . , v B 2 } ⊆ V 2 in the minimum perfect matching, and W (E uv ) be the total weight of the edges in E uv . By the construction of G uv Now we are ready to solve Problem 2. Consider the algorithm shown in Algorithm 2, named the matching-based effector detection (MBED) algorithm. In this algorithm, for each pair of nodes u, v ∈ X 1 , we first construct a bipartite graph G uv according to Algorithm 1 and then calculate its minimum perfecting matching. In this way, associated with each pair of nodes u and v in X 1 , there is a node set V uv and an edge set E uv given by the minimum perfect matching of G uv . Finally, we select the V uv such that Suppose the output of MBED is V u * v * corresponding to a certain pair of nodes u * and v * in X 1 . In the following, we show that V u * v * is a 3-approximation of Problem 2.
Lemma 2: For any V ⊆ X 1 with B nodes and any pair of Algorithm 2 Matching-Based Effector Detection 1: Input: G = (V, E), X 1 , N 1 , B and λ. 2: Output: A subset of X 1 with B nodes. 3: N 1 := |X 1 |. 4: for each ordered pair of (u, v) ∈ X 1 , u = v, do 5: G uv := Bipartite-construction (G, X 1 , u, v, B, λ); 6: run BMPM(G uv ) to obtain E uv and V uv ; 7: Return the V uv with the smallest is a function defined on the triple (V , u, v). Proof: According to (8) and the construction of Consider the bipartite graph G u,v constructed according to Algorithm 1. By the selection of u * and v * Let E be the matching of G u,v such that each node in V is matched to a node in {v 1 2 , . . . , v B 2 } ⊆ V 2 . Since E uv is the minimum perfect matching of G uv The above inequalities yields , the right side of the above inequality is h (V , u, v). Lemma 2 thus follows.
Theorem 1: V u * ,v * is a 3-approximation of Problem 2. Proof: We simply denote V u * v * by S and let V * be the optimal solution to Problem 2. Thus By Lemma 2, for every v ∈ V * and u ∈ Adding up the above inequality for all u ∈ V * and v ∈ X 1 \V * , the left side of the summation is and the right side is As shown in Theorem 2, MBED is a polynomial algorithm with respect to N.
Theorem 2: MBED algorithm runs in O(N 2 ). Proof: For each w ∈ V , the first influence distance from w to other nodes can be derived in O(N 2 ) by the classic shortest path algorithm. 2 Note that we only need to calculate the d (w,v) , where w ∈ V 1 . Therefore, the calculation of the influence distance totally requires (N 1 · N 2 ). Given the values of d (w,v) , Algorithm 1 takes O (N 1 (B + (N 1 − B)(N − N 1 ))) where calculating d 1 (w,X 0 ) costs O(N − N 1 ). Furthermore, for each G uv , the bipartite minimum perfect matching problem can be solved in O(N 3 1 ) due to Munkres [20]. Putting these together, Algorithm 2 totally takes In fact, MBED is sufficiently fast because N 1 is very small compared with N. We will later discuss the selection of λ.

B. k-IDBSD Problem for k > 1
In this section, we show a flow-based heuristic for k > 1. We start by transforming Problem 1 to the size-constrained minimum cut problem. In particular, given an IC network G with a target activation state, let us consider a weighted complete graph, denoted by G * , where V (G * ) = X 1 and the weight function is defined as follows: Similarly, for a node u ∈ X 1 and two subsets V 1 , V 2 ⊆ X 1 , we define that w(u, V 1 ) = v∈V 1 w(u, v) and w(V 1 , V 2 ) = u∈V 1 v∈V 2 w(u, v). For an edge set E , W (E ) = e∈E w(e). For any two sets V 1 and V 2 such that V 1 ∩V 2 = ∅ and V 1 ∪ V 2 = X 1 , we denote by cut(V 1 , V 2 ) the set of cut 2 In practice, we adopt the implementation provided by http://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html. edges from V 1 to V 2 . Given an effector set S of size B, it follows that: Therefore, to solve the k-IDBSD problem, it is equivalent to finding a subset S of V (G * ) with B nodes such that W (cut(S, V (G * )/S) is minimized. Note that if the size restriction on S is removed, it becomes the classic minimum cut problem, which can be efficiently solved by the mincut max-flow theory. However, if we require that |S| = B, it becomes NP-hard. In the following, we provide an efficient algorithm that can produce a node set S with a small W (cut(S, V (G * )/S). Our algorithm proceeds in two steps.
Step 1: We first obtain the minimum cut of G * , 3 denoting the corresponding partition of V (G * ) by (S 1 , S 2 ). Because (S 1 , S 2 ) may not satisfy the size restriction, we next move the nodes from one set to the other until |S 1 | = B. In particular, if |S 1 | < B, we keep moving the node u from S 2 to S 1 such that W (cut(S 1 ∪ {u}, S 2 \ {u})) is the minimal among all the u in S 2 , until |S 1 | = B. We do the same if |S 1 | > B. 4 By doing this, we now have a new partition (S 1 , S 2 ), where |S 1 | = B.
Step 2: The second step is to exchange the nodes between S 1 and S 2 such that the objective value is further reduced. In order to show the details, we introduce the following notations. For a pair of nodes (u 1 , u 2 ), where u ∈ S 1 and v ∈ S 2 , let Define the gain by exchanging u 1 and u 2 by Note that g(S 1 , S 2 , u 1 , u 2 ) can be negative, which means the current partition cannot be improved by exchanging a single pair of nodes. Thus, a naive approach is to successively exchange a pair of nodes and update the partition until the gain is nonpositive for any pair of nodes. In the following, we show a better searching strategy. We first select the pair of nodes (u 1 1 , u 1 2 ) with a gain g 1 such that g 1 is maximized among all the choices. Then we repeat this process for S 1 (u 1 , u 2 ) and S 2 (u 2 , u 1 ) where the nodes are selected from S 1 (u 1 , u 2 ) \{u 2 } and S 2 (u 2 , u 1 )\{u 1 }. The nodes that have been selected in the past rounds will never be considered again. Thus, the process terminates after k = min(|S 1 |, |S 2 |) steps and we will obtain a series of pairs of nodes with the gains g 1 , . . . , g k . Clearly, if we exchange the first i pairs of nodes, the total gain is i j =1 g j . Let k * be the index such that k * j =1 g j is maximized. If k * j =1 g j is larger than zero, we exchange the first k * pairs 3 We can use either the classic Ford-Fulkerson algorithm or the randomized algorithm by Karger and Stein [21]. 4 That is, we move the node from S 1 to S 2 .  7: let S 1 and S 2 be the partition corresponding to the minimum cut of G * ; 8: if |S 1 | > B then 9: while |S 1 | > B do 10: u := arg min u∈S 1 W (cut(S 1 \ {u}, S 2 ∪ {u}));  25: if gai n(i ) > gai nmax then 26: gai nmax = gai n(i ), maxi ndex = i ; 27: if maxi ndex > 0 then 28: for i = 1 : maxi ndex do 29: 30: break; return S 1 of nodes and repeat the whole process by treating the resulting partition as the initial (S 1 , S 2 ), until k * j =1 g j is less or equal to zero. The partition produced by this step actually reaches the local optimal. The whole process is formally shown in Algorithm 3 named the flow-based effector detection (FBED) algorithm.

V. MAXIMUM LIKELIHOOD ESTIMATION
In this section, we show how to detect the effectors by the MLE approach. That is, searching the node subset that is able to maximize the likelihood of the observed activation state. Let Pr(A * |S) denote the probability of observing A * for a given seed set S. Therefore, our problem is to find an S * such that It is not surprising that given A * and S, finding such an S * is an NP-hard problem in general and even calculating the value of Pr(A * |S) is #P-hard. In the following, we first show that the MLE can be derived on DAGs in polynomial time, and then discuss the case for general graph.

A. Directed Acyclic Graph
We start by discussing the case when the social network forms a DAG and X 1 is connected. Given an activation state A * and an effector set S, we will give a closed form of Pr(A * |S) in the following. Since X 1 is connected, it must also form a DAG. For a node set V , without causing any confusion, we also refer to V (also V ) as the event that the nodes in V are active (also inactive). Then Pr(A * |S) = Pr(X 1 , X 0 |S) = Pr(X 0 |X 1 , S) · Pr(X 1 |S) (15) where Pr(X 0 |X 1 , S) is the probability that the nodes in X 0 are not active on the condition that the nodes in X 1 are active for the given seed set S. It is easy to verify that where X out 1 = {(u, v)|u ∈ X 1 , v ∈ X 0 }. In order words, given that all the nodes in X 1 are activated, nodes in X 0 are not activated if and only if all the edges in X out 1 are not live. Because Pr(X 0 |X 1 , S) is independent of S according to (16), we hence only need to consider the value of Pr(X 1 |S) for maximizing Pr(A * |S). For a node u in X 1 , we denote the set of the parents of u in X 1 by Par(u). Now let us consider a collection of subsets of X 1 returned by Algorithm 4. Let F 0 , . . . , F m be the output of Algorithm 4. We will in the following show that F 0 , . . . , F m actually forms a partition of X 1 . Clearly, F i ∩ F j = ∅ for i = j , and thus, it is sufficient to prove the following lemma, which implies ∪ m i=0 F i = X 1 . Lemma 3: For each loop from line 6 to 9 in Algorithm 4, if V = ∅ then F i = ∅.
Proof: For contradiction, suppose V = ∅ but F i = ∅. That is, each node in V has at least one parent in V . We arbitrarily choose a node in V , namely, u 0 . Since u 0 has at least one parent in V , we arbitrarily select one of them, namely, u 1 . Since u 1 ∈ V and u 1 has at least one parent in V , we again select one of its parents in V , namely, u 2 . By repeating this process, we obtain a sequence of nodes {u i }. Since the nodes in X 1 are finite, there must be two nodes in {u i } that are the same, which implies that there is a directed cycle in X 1 . Thus, the proof of Lemma 3 has been proved.
Since {F 0 , . . . , F m } forms a partition of X 1 , Pr(X 1 |S) can be decomposed as follows: For the nodes in F i , their parents are in ∪ i−1 j =0 F j , and therefore, given the events F 0 , . . . , F i−1 and S, the nodes in F i are activated independently from each other. Thus For a node u ∈ F i It follows that: and by (17) Pr(X 1 |S) = Now it is clear that to maximize Pr(X 1 |S) is to find an S that minimizes u∈S  (1 − Pr[(v, u)])) and it is sufficient to select the nodes that have the smallest value of Therefore, F 0 must be a subset of the optimal solution. This is intuitive because the nodes in F 0 have no parent and thus can only be activated as seed nodes. The above analysis can be easily generalized to the case when X 1 is not connected and consists of isolated DAGs.

B. General Graph
Generally, the input graph may not be a DAG. For an arbitrary graph, we can first extract a DAG for each connected part of X 1 and then apply the above approach to find the maximum likelihood effector set. To avoid introducing new notations, we assume that X 1 is connected.
A DAG contained in X 1 can be obtained by removing a certain set of edges in X 1 . It is preferred to extract the DAG that preserves the influence information as much as possible. To this end, we employ the maximum entropy principle. Entropy is widely used as a metric of the volume of information contained in a probabilistic system [22]. For an IC model, the entropy H (D) of a DAG D = (X 1 , E) is defined as follows:  12: Suppose the entropy of E L is larger than that of E R ; 13: while E R = ∅ do 14: Let (u, v) be the edge in E R with the largest entropy; 15: if E L ∪ (u, v) is acyclic then 16: 17: return the subgraph corresponding to E L ; Thus, we aim to remove a set of edges from X 1 such that the remaining subgraph forms a DAG that has the maximum entropy according to (18). We call this subproblem the DAG extracting problem. Unfortunately, the DAG extracting problem is NP-hard. Actually, by assigning each edge (u, v) the same propagation probability, it is equivalent to the minimum feedback arc set problem that is to find a set of edges with minimum size that, when removed, leaves a DAG. In this paper, we employ the following approximation algorithm for the DAG extracting problem.
1) Permutation-Based DAG Extraction [23]: We first assign an arbitrarily total order (i.e., decide a permutation) of the nodes in X 1 . Then construct two subgraphs L = (X 1 , E L ) and R = (X 1 , E R ), where E L = {(u, v)|u > v} and E R {(u, v)|u < v}. Without loss of generality, assume L has larger entropy. Now we move the edge from R to L such that L remains acyclic until no such edge exists and output L. When moving edge from R to L, we first check the edge that has the largest value of −Pr[e] · ln Pr[e]. We denote this algorithm by the permutation-based DAG extraction (PBDE) algorithm, which is described in Algorithm 5.
Theorem 3: The PBDE algorithm finds a DAG in X 1 that has an entropy at least half of that of the optimal DAG.
Proof: First, there is no directed cycle in L because u > v for each edge (u, v) in L. Second, the entropy of L is at least half of the optimal solution because where D opt is the optimal solution.
As mentioned earlier, the nodes that have no parent in X 1 must be the effectors, for otherwise Pr(X 1 |S) = 0. Thus, the last step of PBDE algorithm is important as it is can guarantee such nodes to be included in the extracted DAG. Other sophisticated algorithms for the DAG extracting problem can be obtained from [23] and [24] regarding the minimum feedback arc set problem. We denote the above approach by the maximum-likelihood-based effector detection (MLBED) algorithm. Note that the MLBED approach also can be used to solve the influence source detection problem.

VI. EXPERIMENTS
In this section, we experimentally evaluate the proposed methods for effector detection.

A. Experimental Setup
We use the Facebook network [19], which has been widely adopted for studying social networks [25]- [27]. The selected Facebook network includes 4039 users and 88234 undirected edges. We replace each edge with two directed edges to make the graph directed. We consider two popular settings of propagation probability. 1) Uniform Setting: Pr[(u, v)] = 0.01 for each edge. Such a setting represents the case when we lack the knowledge of the given social network. 5 where deg(v) is the number of nodes connected to v. As mentioned in [10], the high degree nodes are too influential under the uniform setting, and the weighed cascade setting balances the degree and the propagation probability. For each activation state, we obtain the effectors according to the algorithms and calculate f 1 (S) via Monte Carlo simulations. 6 By Hoeffding's inequality, the produced f 1 (S) can be as accurate as possible when a sufficient number of simulations have been performed. We herein set the number of iterations as 10 000. The considered effector detection algorithms are as follows.
1) MBED: This is the effector detection algorithm designed in Section IV-A. MBED searches good effectors by solving Problem 2 formulated based on the first influence distance. 2) FBED: This is the effector detection algorithm designed in Section IV-B. FBED searches good effectors by solving Problem 1 formulated based on the kth influence distance. In particular, we set k = 3. 3) MLBED: This is the effector detection algorithm designed in Section V. MLBED searches the effectors that can maximize the likelihood of the target activation state. 4) OutDegree: This is a heuristic algorithm proposed in [2] that selects effectors with the highest out-degree in the influence tree. The details of this algorithm can be found in [2]. 5) Random: This is a baseline algorithm that randomly selects effectors from the active nodes. Note that the other methods proposed in [2] are not included in our experiment because their performances are similar to that of OutDegree as shown there.

B. Result
In this section, we show the results of the two experiments with different methods for generating activation states.
1) First Experiment: In this experiment, given the budget B, we first randomly select B nodes as seed nodes and then generate activation states by simulating the diffusion process.
First, we briefly discuss the selection of λ. According to the formulation, the selection of λ intuitively depends on N 1 (i.e., the number of active nodes in A * ). However, we observe that as long as λ is less than 1, the performance of MBED does not vary much. For a fixed activation state, we apply MBED tuning λ. Fig. 3 shows several results for different N 1 . For the first two cases shown in Fig. 3(a) and (b), the performance is slightly better when λ is close to 0.5. However, when N 1 is further increased, the performances of MBED are in the same level with different λ less than 1.
Second, let us discuss the effectiveness of the considered effector detection methods. First, we consider the case of single effector, i.e., B = 1. As shown in Table II, in most cases, MBED and FBED have better performance than MLBED and Random. Recall that the small f 1 (S) implies the high quality of the effectors. However, the difference of the metric score between the effectors produced by different algorithms is not significant because one seed node cannot result in many active nodes, i.e., N 1 is small. Next, we set λ to be 0.5 and collect the results for larger N 1 . The results under the uniform setting and weighted cascades are shown in Fig. 4(a) and (b), respectively. The details of the result in Fig. 4(a) are shown in Table III in Appendix. From Fig. 4, the following can be observed.
1) MBED provides the best performance in most cases.
2) FBED and MLBED perform slightly worse than MBED does. 3) MBED, FBED, and MLBED are superior to OutDegree by a significant gap. Now, let us discuss the intuitions behind those results. The MBED is highly effective because it is able to minimize g 1 (S) with a theoretical guarantee and g 1 (S) is linearly correlated to f 1 (S) as shown in Fig. 2. Although FBED does not have an approximation ratio for minimizing g k (S), it can utilize the kth influence distance that captures more information of the influence diffusion between the nodes. Because MLBED finds the seed nodes with the maximum likelihood, it is suitable for the activation states that are generated by the seed nodes. Therefore, MLBED also performs well in this experiment. According to Table II and Fig. 4(a), the OutDegree algorithm is comparable to other algorithms only if |X 1 | is small. It is worth noting that none of the considered algorithms can strictly dominate others, implying that a combination of the proposed methods can be a good choice in practice.
Another important observation is that the quality of the effector heavily depends on the pattern of the activation state, and one can imagine that there exists some activation state such that no effector set can have high quality. Consider the illustration graph shown in Fig. 5. Suppose the number of effector is one. Such an activation state is somehow elusive for finding effector because each active node has a low probability to activate its active neighbors but a high probability to activate its inactive neighbor. Therefore, it is not possible to identify  good effectors solely based on the network topology. Such a scenario explains that why OutDegree may have the same degree of effect as that of MBED for a certain activation state.
2) Second Experiment: In the second experiment, we first set the value of |X 1 | and then select the nodes for X 1 from V in random. The budget B is randomly selected from 0.1 · |X 1 | to 0.2 · |X 1 |. The experimental results are shown in Fig. 6(a) and (b). Not surprisingly, the pattern of the scatter plots is similar to that of the first experiment and the proposed algorithms are still effective. An important observation is that the MLBED algorithm does not perform so well as it does in the first experiment. For the uniform setting, the performances of MLBED and MBED are very close to each other in the first experiment as shown in Fig. 4(a) and Table III in Appendix, while MBED is clearly better than MLBED in the second experiment as shown in Fig. 6(b). Similarly, the difference in the performances between MLBED and MBED in this experiment becomes larger than it is in the first experiment. This is because the MLBED algorithm is designed mainly based on the idea of finding the influence source, but the activation states in this experiment may not be a valid input for the influence source detection problem. Such an observation also implies that the influence source detection methods are feasible but may not perform well for solving the effector detection problem.

VII. CONCLUSION
In this paper, we have considered the problem of finding effectors in social networks. We first design an effector detection framework based on the idea of influence distance. Specifically, we show how to extract the kth influence distance from the IC model and then provide a 3-approximation algorithm for k = 1 and a heuristic for k ≥ 1, respectively. Then we show how the effectors can be detected by the MLE. For DAG graphs, we provide an algorithm that finds the  FIG. 4(a) optimal MLE in polynomial time. For general graphs, we extract the DAG subgraph based on the maximum entropy principle and then apply the MLE approach. For the future work, we plan to analyze the effector detection problem for other information-propagation models such as a linear threshold model. As discussed in Section VI, for some activation states, it is not possible to find good effectors. Thus, it is interesting to investigate whether a meaningful effector exists for a given activation state.

APPENDIX DETAILED EXPERIMENTAL RESULTS
See Table III.