{'fraction_non_alphanumeric': 0.03905110423010978, 'fraction_numerical': 0.009954704813573202, 'mean_word_length': 4.0671680497925315, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Least Cost Influence Maximization Across Multiple Social Networks

Recently in Online Social Networks (OSNs), the Least Cost Influence (LCI) problem has become one of the central research topics. It aims at identifying a minimum number of seed users who can trigger a wide cascade of information propagation. Most of existing literature investigated the LCI problem only based on an individual network. However, nowadays users often join several OSNs such that information could be spread across different networks simultaneously. Therefore, in order to obtain the best set of seed users, it is crucial to consider the role of overlapping users under this circumstances. In this article, we propose a unified framework to represent and analyze the influence diffusion in multiplex networks. More specifically, we tackle the LCI problem by mapping a set of networks into a single one via lossless and lossy coupling schemes. The lossless coupling scheme preserves all properties of original networks to achieve high quality solutions, while the lossy coupling scheme offers an attractive alternative when the running time and memory consumption are of primary concern. Various experiments conducted on both real and synthesized datasets have validated the effectiveness of the coupling schemes, which also provide some interesting insights into the process of influence propagation in multiplex networks.


I. INTRODUCTION
In the recent decade, the popularity of online social networks, such as Facebook, Google+, Myspace and Twitter etc., has created a new major communication medium and formed a promising landscape for information sharing and discovery. On average [1], Facebook users spend 7 hours and 45 minutes per person per month on interacting with their friends ; 3.2 billion likes and comments are posted every day on Facebook; 340 million tweets are sent out everyday on Twitter. Such engagement of online users fertilizes the land for information propagation to a degree which has never been achieved before in the mass media. More importantly, OSNs also inherit one of the major properties of real social networks -the word-of-mouth effect, in which personal opinion or decision can be reshaped or reformed through influence from friends and colleagues. Recently, motivated by the significant effect of viral marketing, OSNs have been the most attractive platforms to increase brand awareness of new products as well as strengthen the relationship between customers and companies. In general, the ultimate goal is to find the least advertising cost set of users which can trigger a massive influence.
Along with the fast development of all existing OSNs, there have been quite a number of users who maintain several accounts simultaneously, which allow them to propagate information across different networks. For example, Jack, a user of both Twitter and Facebook, knew a new book from Twitter. After reading it, he found it very interesting and shared this book with friends in Facebook as well as Twitter. This can be done by configuring both of the accounts to allow automatically posting across different social networks. As a consequence, the product information is exposed to his friends and further spreads out on both networks. If we only focus on an individual network, the spread of the information is estimated inaccurately. As shown in Fig. 1, the fraction of overlapping users is considerable. Therefore considering the influence only in one network fails to identify the most influential users, which motivates us to study the problem in multiplex networks where the influence of users is evaluated based on all OSNs in which they participate.
Related works. Nearly all the existing works studied different variants of the least cost influence problem on a single network. Kempe et al. [10] first formulated the influence maximization problem which asks to find a set of k users who can maximize the influence. The influence is propagated based on a stochastic process called Independent Cascade Model (IC) in which a user will influence his friends with probability proportional to the strength of their friendship. The author proved that the problem is NP-hard and proposed a greedy algorithm with approximation ratio of (1−1/e). After that, a considerable number of works studied and designed new algorithms for the problem variants on the same or extended models such as [6], [14], [15], [17]. There are also works on the linear threshold (LT) model for influence propagation in which a user will adopt the new product when the total influence of his friends surpass some threshold. Dinh et al [7] proved the inapproximability as well as proposed efficient algorithms for this problem on a special case of LT model. In their model, the influence between users is uniform and a user is influenced if a certain fraction ρ of his friends are active.
Recently, researchers have started to explore multiplex networks with works of Yagan et al. [16] and Liu et al. [11] which studied the connection between offline and online networks. The first work investigated the outbreak of information using the SIR model on random networks. The second one analyzed networks formed by online interactions and offline events. The authors focused on understanding the flow of information and network clustering but not solving the least cost influence problem. Additionally, these works did not study any specific optimization 3 problem of viral marketing. Shen et al. [14] explored the information propagation in multiplex online social networks taking into account the interest and engagement of users. The authors combined all networks into one network by representing an overlapping user as a super node. This method cannot preserve the individual networks' properties.
In this article, we studies the LCI problem which aims at finding a set of users with minimum cardinality to influence a certain fraction of users in multiplex networks. Due to the complex diffusion process in multiplex networks, it is difficult to develop the solution by directly extending previous solutions in a single network. Additionally, studying the problem in multiplex networks introduces several new challenges: (1) how to accurately evaluate the influence of overlapping users; (2) in which network, a user is easier to be influenced; (3) which network propagates the influence better. To answer above questions, we first introduce a model representation to illustrate how information propagate in multiplex networks via coupling schemes. By mapping multiple networks into one network, different coupling schemes can preserve partial or full properties of the original networks. After that, we can exploit existing solutions on a single network to solve the problem in multiplex networks. Moreover, through comprehensive experiments, we have validated the effectiveness of the coupling schemes, and also provide some interesting insights into the process of influence propagation in multiplex networks. Our main contributions are summarized as follows: • Propose a model representation via various coupling schemes to reduce the problem in multiplex networks to an equivalent problem on a single network. The proposed coupling schemes can be applied for most popular diffusion models including: linear threshold model, stochastic threshold model and independent cascading model. • Provide a scalable greedy algorithm to solve the LCI problem. Especially, the improvement factor scales up with the size of the network which allows the algorithm to run on very large networks with millions of nodes. • Conduct extensive experiments on both real and synthesized datasets. The results show that considering multiplex networks instead of a single network can effectively choose the most influential users. The rest of the paper is organized as follows. In Section II, we present the influence propagation model in multiplex networks and define the problem. The lossless and lossy coupling schemes are introduced in Section IV and Section V. A scalable greedy algorithm is proposed in Section VI. Section VII shows the experimental results on the performance of different algorithms and coupling schemes. Finally, Section VIII concludes the paper.

A. Graph notations
We consider k networks G 1 , G 2 , . . . , G k , each of which is modeled as a weighted directed The vertex set V i = {u's} represents the participation of n i = |V i | users in the network G i , and the edge set E i = {(u, v)'s} contains m i = |E i | oriented connections (e.g., friendships or relationships) among network users. W i = {w i (u, v)'s} is the (normalized) weight function associated to all edges in the i th network. In our model, weight w i (u, v) can also interpreted as the strength of influence (or the strength of the relationship) a user u has on another user v in the i th network. The sets of incoming and outgoing neighbors of vertex u in network G i are denoted by N i− u and N i+ u , respectively. In addition, each user u is associated with a threshold θ i (u) indicating the persistence of his opinions. The higher θ i (u) is, the more unlikely that u will be influenced by the opinions of his friends. Furthermore, the users that actively participate 4 in multiple networks are referred to as overlapping users and can be identified using methods in [3], [9] (Note that identifying overlapping users is not the focus of this paper). Those users are considered as bridge users for information propagation across networks. Finally, we denote by G 1...k the system consisting of k networks, and by U the exhaustive set of all users U = ∪ k i=1 V i .

B. Influence Propagation Model
We first describe the Linear Threshold (LT) model [7], a popular model for studying information and influence diffusion in a single network, and then discuss how LT model can be extended to cope with multiplex networks. In the classic LT model, each node u can be either active or inactive: u is in an active state if it is selected into the seed set, or the total influence from the in-degree neighbors exceeds its threshold θ(u), i.e, v∈N (u) w(v, u) ≥ θ(u). Otherwise, u is in an inactive state.
In multiplex network system, given a number of k networks, the information is propagated separately in each network and can only flows to other networks via the overlapping users. The information starts to spread out from a set of seed users S i.e. all users in S are active and the remaining users are inactive. At time t, a user u becomes active if the total influence from its active neighbors surpasses its threshold in some network i.e. there exists i such that: where A is the set of active users after time (t − 1).
In each time step, some of inactive users become activated and try to influence other users in the next time step. The process terminates until no more inactive users can be activated. If we limit the propagation time to d, then the process will stop after t = d time steps. The set of active users in time d is denoted as A d (G 1...k , S). Note that d is also the number of hops up to which the influence can be propagated from the seed set, so d is called the number of propagation hops.

C. Problem definition
In this paper, we address the fundamental problem of viral marketing in multiplex networks: the Least Cost Influence problem. The problem asks to find a seed set of minimum cardinality which influences a large fraction of users. Definition 1. (Least Cost Influence (LCI) Problem) Given a system of k networks G 1...k with the set of users U, a positive integer d, and 0 < β ≤ 1, the LCI problem asks to find a seed set S ⊂ U of minimum cardinality such that the number of active users after d hops according to LT model is at least β fraction of users i.e. |A d (G 1...k , S)| ≥ β|U|.
When k = 1, we have the variant of the problem on a single network which is NP-hard to solve [5], Dinh et al. [7] proved the inapproximability and proposed an algorithm for a special case when the influence between users is uniform and a user is activated if a certain fraction ρ of his friends are active. In the following sections, we will present different coupling strategies to reduce the problem in multiplex networks to the problem in a single network in order to utilize the algorithm design. 5 III. COUPLING SCHEME A coupling scheme is an approach to project multiple networks to a single network, which can preserve important network information and reproduce the diffusion process from each individual network. Such a scheme will facilitate researchers to study various optimization problems that relate to the diffusion of information on multiple networks. In general, we can mitigate these problems to the one defined on single network and apply existing solutions to solve them. Next we specify the requirements for such schemes and the general framework.

A. Coupling scheme general framework
Our goal is to map multiple networks into a single network such that a diffusion process on multiple networks can be simulated by a process on the projected network. Two most important points are: (1) which user is active and (2) when a user is activated. Formally, a coupling scheme that maps a system of networks G 1...k with the set of users U to a network G = (V, E) needs to satisfy following requirements: (1) There exists a set of nodes U ⊆ V and bijection function that maps users to nodes in the coupled network: F : U → U.
(2) There exists a time mapping function T : N → N.
The first constraint reserves the identity of users in the coupled network. The second constraint allows us the know when a user is activated. The last constraint guarantees that the diffusion process is preserved, i.e., the diffusion of information on the set of user U is the same on the set of nodes U. This is the core part of the couple scheme and may be difficult to achieve. Since the main goal is to construct a solution to the studied problem on multiple networks from the solution on single network, we can relax the last condition such as u ∈ U is activated at time t on G 1...k if F (u) is activated at time T (t) on G. In this case, the diffusion information is not totally reserved. The coupling scheme is called lossless coupling scheme if the last condition is satisfied and lossy coupling scheme otherwise.
Since our main concern is the diffusion of information among users, such coupling scheme reserve most of the properties of the diffusion process. It helps to answer following questions: • When a node becomes active? • How many nodes are activated at a specific time?
• Who are top influencers in the multiple networks? Another important aspect of the coupling scheme is the activation state of nodes in V \ U. In some optimization problems, the fraction of active nodes plays an important role. Thus, it is desirable for the coupling scheme to reserve the fraction of active nodes or the scale-up property.

B. General framework to solve some optimization problems
With the coupling scheme, if we only consider the set of users and its mapped set on the coupled network, the diffusion process is the same on these two sets. Thus, we can design algorithms to solve various information diffusion optimization problems on multiple networks such as Influence Maximization problem [10], Limiting the misinformation problem [4], Minimum Influential Node Selection problem [18], etc, by the following framework: (1) Create a coupled 6 network following a coupling scheme, (2) Use an algorithm for the studied problem on single networks to identify the set of selected nodes, (3) Use the F function to determine the set of selected users from the set of selected nodes on the coupled network.

Algorithm 1 General Framework
Input: A set of users U, a system of networks G 1...k , and an algorithm A.
IV. LOSSLESS COUPLING SCHEMES In this section, we present the lossless scheme to couple multiple networks into a new single network with respect to the influence diffusion process on each participant network. A notable advantage of this newly coupled graph is that we can use any existing algorithm on a single network to produce the solution in multiplex networks with the same quality.

A. Clique lossless coupling scheme
In LT-model, the first issue is solved by introducing dummy nodes for each user u in networks that it does not belong to. These dummy nodes are isolated. Now the vertex set V i of i th network can be represented by In the new representation, there is an edge from u i p to u i q if u p and u q are connected in G i . Now we can union all k networks to form a new network G. The approach to overcome the second challenge is to allow nodes u 1 , u 2 , . . . , u k of a user u to influence each other e.g. adding edge (u i , u j ) with weight θ(u j ). When u i is influenced, u j is also influenced in the next time step as they are actually a single overlapping user u, thus the information is transferred from network G i to G j . But an emerged problem is that the information is delayed when it is transferred between two networks. Right after being activated, u i will influence its neighbors while u j needs one more time step before it starts to influence its neighbors. It would be better if both u i and u j start to influence their neighbors in the same time. For this reason, new gateway vertex u 0 is added to G such that both u i and u j can only influence other vertices through u 0 . In particular, all edges (u i , v i ) ((u j , z j )) will be replaced by edges (u 0 , v i ) ((u 0 , z j )). In addition, more edges are added between u 0 , u i , and u j to let them influence each other, since the connection between gateway and representative vertices of the same user forms a clique, so we call it clique lossless coupling scheme. After forming the topology of the coupled network, we assign edge weights and vertex thresholds as following: Vertex thresholds. All dummy vertices and gateway vertices have the threshold of 1. Any remaining representative vertex u i p has the same threshold as u p in G i , i.e., θ(u i p ) = θ i (u p ). Edge weights. If there is an edge between user u and v in G i , then the edge (u 0 , v i ) has weight w(u 0 , v i ) = w i (u, v). The edges between gateway and representative vertices of the same user u are assigned as w(u i , u j ) = θ(u j ), ∀ 0 ≤ i, j ≤ k, i = j to synchronize their state together.
A simple example of the clique lossless coupling scheme is illustrated in Fig. 2.  Next we will show that the propagation process in the original multiplex networks and the coupled network is actually the same. Influence is alternatively propagated between gateway and representative vertices, so the problem with d hops in the multiplex networks is equivalent to the problem with 2d hops in the coupled network. Proof. Suppose that a gateway vertex u 0 is the first gateway vertex that is activated at the odd hops 2d + 1. u 0 must be activated by some vertex u i and u i is the first activated vertex among vertices u 1 , u 2 , . . . , u k . It means that u i is activated in hop 2d. Since all incoming neighbors of u i are gateway vertices, some gateway vertex becomes active in hop 2d − 1 (contradiction).

Lemma 2.
Suppose that the propagation process on G 1...k and G starts from the same seed set S, then following conditions are equivalent: (1) User u is active after d propagation hops in G 1...k .
(2) There exists i such that u i is active after 2d − 1 propagation hops in G.
(3) Vertex u 0 is active after 2d propagation hops in G.
Proof. We will prove this lemma by induction. Suppose it is correct for any 1 ≤ d ≤ t, we need 8 to prove it is correct for d = t + 1. Denote A 1...k (t) and A(t) as the set of active users and active vertices after t propagation hops in G 1...k and G, respectively.
(1) ⇒ (2): If user u is active at time t + 1 in G 1...k , it must be activated in some network G j . We have: Due to the induction assumption, for each v ∈ A 1...k (t), we also have v 0 ∈ A(2t) in G. Thus: It means that u j is active after (2(t + 1) − 1) propagation hops.
(2) ⇒ (3): If there exists i such that u i is active after 2(t + 1) − 1 propagation hops on G, then u i will activate u 0 in hop 2(t + 1) (3) ⇒ (1): Suppose that u 0 / ∈ S is active after 2(t + 1) propagation hops in G, then there exists u j which activates u 0 before. This is equivalent to: For each v ∈ A(2t), we also have v ∈ A 1...k (t). Replace this into the above inequality we have: Thus, u is active in network G j after t + 1 hops.
Next, we will show that the number of influenced vertices in the coupled network is (k + 1) times the number of influenced users in multiplex networks as stated in Theorem 1.
Theorem 1. Given a system of k networks G 1...k with the user set U, the coupled network G produced by the lossless coupling scheme, and a seed set S = {s 1 , s 2 , . . . , s p }, if A d (G 1...k , S) = {a 1 , a 2 , . . . , a q } is the set of active users caused by S after d propagation hops in multiplex networks, then A 2d (G, S) = {a 0 1 , a 1 1 , . . . , a k 1 , . . ., a 0 q , a 1 q , . . . , a k q } is the set of active vertices caused by S after 2d propagation hops in the coupled network.
Proof. For each user a i ∈ A d (G 1...k , S) i.e. a i is active after d hops in G 1...k , then there exists a j i which is active after 2d − 1 hops in G according to the Lemma 2. As a result, all a 0 i , a 1 i , . . . , a k i are active after 2d hops. So B = {a 0 1 , a 1 1 , . . . , a k 1 , . . ., a 0 q , a 1 q , . . . , a k q } ⊆ A 2d (G, S). Let consider a vertex of A 2d (G, S) which is: Case 1. A gateway vertex u 0 which is active after 2d hops in G, so vertex u must be active after d hops in G 1...k . This implies u ∈ A d (G 1...k , S), thus u 0 ∈ B.
Case 2. An representative vertex u i . If u i is active after 2d − 1 hops, then u must be active after d hops due to Lemma 2, thus u ∈ A d (G 1...k , S). Otherwise, u i is activated at hop 2d , it must be activated by some vertex u j , j > 0 since all gateway vertices only change their state at even hops. Again, u ∈ A d (G 1...k , S). This results in u i ∈ B. 9 From two above cases, we also have A 2d (G, S) ⊆ B. So that A 2d (G, S) = B, the proof is completed.
Theorem 1 provides the basis to derive the solution for LCI in multiplex networks from the solution on a single network. It implies an important algorithmic property of the lossless coupling scheme regarding the relationship between the solutions of LCI in G 1...k and G. The equivalence of two solutions is stated below: Size of the coupled network. Each user u has k + 1 corresponding vertices u 0 , u 1 , . . . , u k in the coupled network, thus the number of vertices is |V | = (k + 1)|U| = (k + 1)n. The number of edges equals the total number of edges from all input networks plus the number of new edges for synchronizing. Thus the total number of edges is |E| = k i=1 |E i | + nk(k + 1).

B. Star lossless coupling scheme
In last subsection, we discussed the clique lossless coupling scheme, however, in this scheme, the number of edges to synchronize the state of vertices u 0 , u 1 , . . . , u k is added up to k(k + 1) for each user u, which results in nk(k + 1) extra edges in the coupled network. In real networks, the number of edges is often linear to the number of vertices, while the number of extra edges greatly increases the size of the coupled network, especially when k is large. Therefore, we would like to design another synchronization strategy that has less additional edges. Note that the large volume of extra edges is due to the direct synchronization between each pair of representative vertices of u in clique lossless coupling scheme, so we can reduce it by using indirect synchronization. In the new coupling scheme, we create one intermediate vertex u k+1 with threshold θ(u k+1 ) = 1 and let the active state propagate from any vertex in u 1 , u 2 , . . . , u k via this vertex. Specifically, the synchronization edges are established as follows: w(u i , u k+1 ) = 1 and w(u k+1 , u i ) = θ(u i ) 1 ≤ i ≤ k; w(u k+1 , u 0 ) = w(u 0 , u k+1 ) = 1. The synchronization strategy of star lossless coupling scheme is illustrated in Fig. 3. Now, the number of extra edge for each user is 2(k +1) and the size of the coupled network is reduced as shown in the following proposition.
Proposition 1. When star lossless scheme is used, the coupled network has |V | = (k + 2)|U| = (k + 2)n vertices and |E| = k i=1 |E i | + 2n(k + 1) edges. In star lossless coupling scheme, it takes 2 hops to synchronize the states of representative vertices of each user which leads to delaying the propagation of influence in the coupled network. Due to the similarity between star lossless scheme and clique lossless scheme, we state the following property of star lossless scheme without proof.

C. Reduced lossless schemes
In all above coupling schemes, we create representative vertices in all networks in G 1...k to guarantee that the number of influenced vertices in the coupled network is scaled up from the number of influenced users in the original system of networks. This creates an extraordinary redundant vertices. For example, we have n users and 4 networks with 0.8n, 0.6n, 0.3n, 0.2n users, then the total number of vertices in all network is only 1.9n while the number of vertices created in clique lossless scheme and star lossless scheme are 5n and 6n, respectively. The redundant ratios of these two schemes are 260 % and 315 %. To overcome this redundant, we use assign weight for vertices in the coupled network and guarantee that the total weight of active vertices is scaled from the number of active users in the original system. In particular, we only create representative vertices u i 1 , u i 2 , . . . , u ip for user u where G i 1 , G i 2 , . . . , G ip are networks that u joins in. Each representative vertex is assigned weight 1, and the user vertex is assigned weight k − p. We have reduced clique lossless scheme or reduced star lossless scheme corresponding the method to synchronize the state of user and representative vertices is clique or star type. With this modification, the number of extra vertices is only n and 2n when clique and star synchronization is used, respectively. The number of extra edges now depends on the participants of users.
Proposition 2. When reduced clique lossless scheme or reduced star lossless scheme is used, the coupled network has |V | = k i=1 |V i | + n or |V | = k i=1 |V i | + 2n vertices, respectively. The relation between the a set of active vertices in coupled network and the set of active users in original networks is similar to previous schemes. We state this relation without proof below.

D. Extensions to other diffusion models
In this section, we show that we can design lossless coupling schemes for some other wellknown diffusion models in each component network. As a result, top influential users can be identified under these diffusion models. In particular, we investigate two most popular stochastic diffusion models which are Stochastic Threshold and Independent Cascading models [10].
• Stochastic Threshold model. This model is similar to the Linear Threshold model but the threshold θ i (u i ) of each node u i of G i is a random value in the range [0, Θ i (u i )]. Node u i will be influenced when • Independent Cascading model. In this model, there are only edge weights representing the influence between users. Once node u i of G i is influenced, it has a single chance to influence its neighbor v i ∈ N + (u i ) with probability w i (u i , v i ). For both models, we use the same approach of using gateway vertices, representative vertices and the synchronization edges between gateway vertices and their representative vertices. The weight of edge (u i , u j ), 0 ≤ i = j ≤ k will be Θ(u j ) for Stochastic Threshold model and 1 for Independent Cascading model. Once u i is influenced, u j will be influenced with probability 1 in the next time step. The proof for the equivalence of the coupling scheme is similar to ones for LT-model.

V. LOSSY COUPLING SCHEMES
In the preceding coupling scheme for LT-model, a complicated coupled network is produced with large numbers of auxiliary vertices and edges. It is ideal to have a coupled network which only contain users as vertices. This network provides a compact view of the relationship between users crossing the whole system of networks. The loss of the information is unavoidable when we try to represent the information of multiplex networks in a compact single network. The goal is to design a scheme that minimizes the loss as much as possible i.e. the solution for the problem in the coupled network is very close to one in the original system. Next, we present these schemes based on the following key observations. Observation 1. User u will be activated if there exists i such that: where A is the set of active users. We can relax the condition to activate u with positive parameters α 1 (u), α 2 (u), . . ., α k (u) as follows: Note that sometimes the condition to activate u is met, but the condition (1) still needs more influence from u's friends to satisfy. The more this need for extra influence is, the looser condition (1) is. We can reduce this redundancy by increasing the value of α i (u) proportional to the value In the special case, if v∈N i− u ∩A w i (v, u) > θ i (u) and we choose α i (u) ≫ α j (u), ∀j = i, then there is no redundancy. Unfortunately, we do not know before hand in which network user u will be activated, so we can only choose parameters heuristically.
Observation 2. When user u participates in multiple networks, it is easier to influence u in some network than the others. The following simple case illustrate such situation. Suppose that we have two networks. In network 1, θ 1 (u) = 0.1 and u has 8 in-neighbors, each neighbor v influences u with w 1 (v, u) = 0.1. In network 2, θ 2 (u) = 0.7 and u has 8 in-neighbors, each neighbor v influences u with w 2 (v, u) = 0.1. The number of active neighbors to activate u is 1 and 7 in network 1 and 2, respectively.
Easiness. Intuitively, we can say that u is easier to be influenced in the first network. We quantify the easiness ǫ i (u) that u is influenced in network i as the ratio between the total influence from friends and the threshold to be influenced: . We can use the easiness of a user in networks as the parameters of the condition 1.
Based on above observations, we couple multiplex networks into one using parameters {α i (u)}. The vertex set is the set of users V = {u 1 , u 2 , . . . , u n }. The threshold of vertex u is set to The weight of the edge (v, u) is: Then the set of edges is E = {(v, u)|w(v, u) > 0}. Fig. 4 illustrates the loosy coupled network of networks in Fig. 2.
Besides easiness, other metrics can be used for the same purpose. We enumerate here some other metrics.
Involvement. If a user is surrounded by a group of friends who have high influence on each other, he tends to be influenced. When a few of his friends are influenced, the whole group involving him is likely to be influenced. We estimate involvement of a node v in a network G i by measuring how strongly the 1-hop neighborhood v is connected and to what extent influence can propagate from one node to another in the 1-hop neighborhood. Formally we can define involvement of a node v in network G i as: is the set of all neighbors of v (both in-coming and out-going).
Average. All parameters have the same value α i (u) = 1 Next we show the relationship between the solution for LCI in the lossy coupled network and the original system of networks. As discussed in the above observations, if the propagation process starts from the same set of users in G 1...k and the coupled network G, then the active state of a user in G implies its active state in G 1...k . It means that if the set of users S activates β fraction of users in G, it also activates at least β fraction of users in G 1...k . It implies that if a seed set is a feasible solution in G, it is also a feasible solution in G 1...k . Thus we have the following result.

VI. ALGORITHMS
In this section, we describe a greedy algorithm and its improvement in terms of scalability in large networks. In the state of the art work, Dinh et al. [7] only solved the problem in a special case where the threshold is uniform and the required fraction of active nodes is the same for all nodes. VII. EXPERIMENTS In this section, we show the experimental results to compare the proposed coupling schemes and utilize these coupling schemes to analyze the influence diffusion in multiplex networks. First, we compare lossless and lossy coupling schemes to measure the trade-off between the running time and the quality of solutions. In particular, for those different kinds of lossless coupling methods, all of them can preserve complete information of all networks. As a result, the quality of seeds are the same, the only difference would be the running time which have been theoretically proved in Proposition 1 and Proposition 2. Therefore, we only chose the clique coupling scheme to be evaluated. Second, we investigate the relationship between networks in the information diffusion to address the following questions: (1) What is the role of overlapping users in diffusing the information? (2) What do we miss when considering each network separately? (3) How and to what extent does the diffusion on one network provide a burst of information in other networks?

A. Datasets
Real networks. We perform experiments on two datasets: • Foursquare (FSQ) and Twitter networks [14] • Co-author networks in the area of Condensed Matter(CM) [13], High-Energy Theory(Het) [13], and Network Science (NetS) [12]. The statistics of those networks are described in Table I. The number of overlapping users in the first dataset FSQ-Twitter is 4100 [14]. We examine the in and out-degree of overlapping nodes. For the second dataset, we match overlapping users based on authors' names. The numbers of overlapping users of the network pairs CM-Het, CM-NetS, and Het-NetS are 2860, 517, and 90, respectively. While the edge weights are provided for co-author networks, only the topology is available for Twitter and Foursquare networks. Thus to assign the weight of each edge, we adopt the method in [10], where each edge weight is randomly picked from 0 to 1 and then normalize it so that the total weight of in-coming edges is sum up to 1 for each node. This is suitable since the influence of user u on user v tends to be small if v is under the influence of many friends. Finally, we also adopt the assignment of threshold in [10] where all thresholds are randomly chosen from 0 to 1.
Synthesized networks. We also use synthesized networks generated by Erdos-Renyi random network model [8] to test on networks with controlled parameters. There are two networks with 10000 nodes which are formed by randomly connecting each pair of nodes with probability p 1 = 0.0008 and p 2 = 0.006. The average degrees, 8 and 60, reflect the diversity of network densities in reality. Then, we select randomly f fraction of nodes in two networks as overlapping nodes. We shall refer to 0 ≤ f ≤ 1 as the overlapping fraction. The edge weights and node thresholds are assigned as Twitter.
Setup. We ran all our experiments on a desktop with an Intel(R) Xeon(R) W350 CPU and 12 GB RAM. The number of hops is d = 4 and the influenced fraction β = 0.8, unless otherwise mentioned.

B. Comparison of coupling schemes
We evaluate the impact of the coupling schemes on the running time and the solution quality of the greedy algorithm to solve the LCI problem.
Solution quality. As shown in Figs. 6(a) and 6(b), the greedy algorithm provides larger seed sets but runs faster in lossy coupled networks than lossless coupled networks. In both Twitter-FSQ and the co-author networks, the seed size is smallest when the lossless coupling scheme is used. It is as expected since the lossless coupling scheme reserves all the influence information which is exploited later to solve LCI. However, the seed sizes are only a bit larger using the lossy coupling schemes. In the lossy coupling schemes, the information is only lost at overlapping users which occupy a small fraction the total number of users (roughly 5% in FSQ-Twitter and 7% in co-author networks). Thus, the impact of the lossy coupling schemes on the solution quality is small especially when seed sets are large to influence a large fraction of users.
A closer examination reveals the relative effectiveness of the coupling methods on the seed size. That is when the seed size is significantly small, the lossess coupling outperforms all the lossy methods. For example, when the overlapping fraction f = 0.8, the solution using the lossless coupling is roughly 55% of that in the solution using the (lossy) Easiness, and the solution using Easiness is about 15% smaller than the other two lossy methods ( Fig. 7(a)).
Running time. The greedy algorithm runs much faster in the lossy coupled networks than the lossless ones in general. As shown in Figs. 6(c) and 6(d), using the lossy coupling reduces the running times by a factor of 2 in FSQ-Twitter and a factor 4 in the co-author networks compared to the lossless coupling. The major disadvantages of the lossless coupling scheme are the redundant nodes and edges. Therefore, the lossy coupling schemes works better on networks that are sparse and the number of overlapping users is small.
However, in some other cases, the lossless coupling scheme is more efficient. As shown in Fig.  7(b), the running time in the lossless coupled networks is larger in the beginning, but gradually reduces down and beats other methods at f = 0.4. The larger f is, the larger the ratio between seed size in the lossless and lossy coupled networks is. As the running time depends on the seed size, thus it reduces faster in the lossless coupled network with larger overlapping ratio.
Overall, the lossless coupling scheme returns solution with higher quality, especially when the seed set is small. However, if the constraint of running time and the memory are of priority, the lossy Easiness coupling scheme offers an attractive alternative. To understand the benefit of taking consideration of overlapping users and coupled network, in this part, we are going to compare the seed size with/out using coupled network. In particular, we do two comparisons on: 1) influencing a fraction β of the nodes in all networks by selecting seeds from each network and taking the union to compare with seeds achieved from lossless coupling scheme; 2) influencing a fraction β of the nodes in a particular network by only choosing seeds from that network compare to the seeds obtained from lossless coupling scheme.  The results for the first scenario are shown in Fig. 8. The seed obtained by the lossless coupling method outperforms other methods. The size of the union set is approximately 30% and 47% larger than lossless coupling method in co-author and FSQ-Twitter, respectively. This shows that