Context-based influence maximization with privacy protection in social networks

In this paper, information diffusion can be described as the propagating procedure of information over some network. A network is usually denoted by a graph G(V,E). Here, V is the node set where each node represents one person or entity, and E is the edge set where each edge represents the relation (cooperation, friends, enemies, and so on) between two nodes. Each node is associated with active or inactive state. Intuitively, the active state means that the node has been affected. The active set of nodes may affect the nodes in inactive set and the influence ratio can describe the strength of that affection. If some inactive node is affected by some active node so much that the inactive becomes active, such a process is called activation. Intuitively, for some node v, the more of the neighbors of v are activated, more likely v will be activated. After then, v will affect more nodes further. As such procedures repeat, more and more nodes will become active. The procedure of activation cannot be reversed: one node can transform from inactive state to active state, but not vice versa. To design proper theoretical model to describe information diffusion in real world, the key is to explain how the interactions between nodes work. Next, we introduce two popular information diffusion models.

Linear threshold model. Given a network G(V,E), let N(v) be the set { u|(u,v)∈E}. For each (u,v)∈E, a threshold value b_uv is utilized to represent the degree of influence from u to v. For each node v, it is satisfied that \(0\leq \sum _{u\in {N(v)}}b_{u,v}\leq {1}\). During the procedure of information diffusion, another threshold value θ_v with respect to each node v is used to control the diffusion of information. In detail, at some instant time, let A(v) be the set of v’s neighbor nodes which have been active. If \(\sum _{u\in {A(v)}}b_{u,v}\geq {\theta _{v}}\), v will become active. In this model, when node u tries to activate its neighbor v and fails, the influence b_u,v is remembered and will be accumulated in the following activating steps. In other words, the influence from u to v will not be ignored, even if the activation is failed. As we will see in the following part, the influence is treated differently in other models. The whole procedure of information diffusion in linear threshold model can be described as follows. First, an initial active node set S₀ will be activated. Then, in the ith step of information diffusion, based on the active nodes in S_i−1, the influence for each node in V∖S_i−1 will be computed. According to the influence computed and the θ_v for each node v, all nodes satisfying \(\sum _{u\in {A(v)}}b_{u,v}\geq {\theta _{v}}\) will be put in S_i. Repeat these steps until no more nodes can become active.

Independent cascade model. Independent cascade model is a probabilistic model. Instead of b_uv in linear threshold model, this model uses p_uv to describe the probability that u can activate v in a single activation. The whole procedure of information diffusion under independent cascade model can be described as follows. First, an initial node set S₀ will be set to be active. Then, in the ith step, every node will try to activate their neighbors. In detail, for each node u∈S_i−1 and node v∈V∖S_i−1, if (u,v)∈E, v will be activated once in probability p_uv. If v indeed becomes active, it will be added to S_i and not be further considered in current step. Repeat this procedure until that no new nodes are added. It should be noted that p_uv is only determined by u and v and is independent with other node pairs. In this model, each edge (u,v) will be considered only one time. Once it fails, this edge will never be considered. In [2], an extended model in which p_uv will be decreased as time goes by.

It has been a huge requirement to protect information privacy, especially in the area of social network. Without privacy protection mechanism, sensitive information of users may be easy to be obtained by illegal applications. More and more operation systems tend to provide core mechanism to protect information privacy when users try to send out data to the network, the protection mechanism is transparent to users. Also, general users learn more and more knowledge about how to protect their privacy by sending only insensitive information.

There have been lots of previous works focusing on the techniques of privacy protection mechanisms, such as perturbation [6], randomization [7], k-anonymity [8], and difference privacy [9]. Most of them have one common feature, that is to hide single user data or answer from other ones. The main intuitive idea is to let the item protected seem to be no difference from other items.

In the procedure of information diffusion in social network, the actions of reposting some message may leak private information of users. In fact, when some user A receives some message M, the actions A taking will answer the query “is A interested in M?.” If A decides to repost M, the answer is yes, otherwise, the answer is no. By collecting such answers, private information (e.g., interests, majors) of A can be obtained using information techniques. Essentially, during this procedure, to provide the privacy protection mechanisms, it needs to modify the answers (the decisions about whether to repost the message received) in certain way such that A will not show obvious difference from other users. Therefore, the privacy protection mechanisms will affect the probability that A can activate other users, that is there are cases A will not repost M to avoid leaking private information even if A has been activated by M. To describe the procedure of diffusing information under privacy protection mechanism, we propose a context -based representation of privacy protection mechanism first, then the corresponding information diffusion model is introduced in the following part.

Here, a context set C={c₁,c₂,…,c_m} is used to specify which kind of class the information belongs to. We consider a privacy protection model as follows. Each user is attached to several contexts; they can represent his interests which can be obtained based on tags labeled by himself. Also, each message is attached with contexts, which can be obtained by getting the tags labeled by the produced user or analyzing it by language processing algorithms. Intuitively, when a user A receives some message M, even if A indeed is interested in M and wishes to share M with other uses in the network, it is very possible that A determines not to repost M because of privacy considerations. There are mainly three kinds of such considerations as follows:

In this part, to integrate privacy protection strategies with the procedure of information diffusion, a context-based information diffusion model (IDC for short) is proposed. In IDC model, the social network can be represented by a graph G=(V,E). Here, V is the node set and E is the directed edge set which represents the influence relationship between nodes in the network. Intuitively, if there is an edge (u,v)∈E, it says that v can be influenced by u. That is, if u has been influenced, v also may be influenced through the edge (u,v).

In the IDC model, a finite context set C={c₁,c₂,…,c_m} is used to represent the context information. Intuitively, to support privacy protection strategies during information diffusion, the relationships between users and messages must be identified. However, it is impossible to build a model for each piece of message, a better solution is to put messages into different categories by analyzing their characteristics. The context information is just used to identify which category the message belongs to. For example, the contexts of a tweet like “LeBron James has agreed to a four year, 154 million dollars contract with Los Angeles Lakers” may be {LeBron James, Los Angeles Lakers, Basketball}. Also, we use context information to represent what kinds of information some node is interested in. For example, in real applications such as tweet, the tags of users can be viewed as the contexts. Ideally, each item in C should be totally different from others, such that we can use a C with minimum size to import context information to the procedure of information diffusion. Each node v in V may be associated with a context set C_v⊆C, which represent v is sensitive or interested those information generated by the contexts in C_v. In IDC model, also, for each special message M, different from general information diffusion models, the information M should also be specified with a context set C_M⊆C, which means that information M is related with all context in C_M.

In general information diffusion model, for each edge (u,v) in the network, a probability or threshold is assigned to represent the influence, which is usually defined to be a function p:E↦[0,1]. Differently, the influence function p is extended to be a function set P={p₁,…,p_m}, where each function corresponds to a special context c and for edge (u,v) the value of \(p^{c}_{uv}\) is the measure of influence of u on v. Therefore, for each two nodes u and v satisfying (u,v)∈E, given special information I, whether v will be influenced by u is determined by the contexts of I, the influence probability functions of different contexts maybe different. For example, suppose A and B are two tweet users, it is a usual case that AtrustsB in IT area but not in music area, so the probability that v is influenced by some IT information re-tweeted by u is much higher than by some music-related information.

Context-based information diffusion model. Formally speaking, in IDC model, an information diffusion model can be described by a 5-tuple 〈G,C,P,U,Θ〉, where U:V↦2^C is defined to be the function to compute the context set for each user and Θ={θ_i|1≤i≤|V|} satisfying 0≤θ_i≤1. The procedure of information diffusion in IDC model can be explained as follows.

In IDC model, given a network G=(V,E), a context set C, two functions P and U, a threshold set Θ, a message I with context set C_I⊆C and a seed node set A, the information diffusion process working in discrete time can be explained as follows. Here, we use t₀, t₁, ⋯, t_n to represent the discrete times. For each node v∈V, there are three different states: inactive, active, and progressive.

The intuitive idea of context-based information diffusion model can be explained as follows. There are several factors affecting the actions of some node on special information, each factor can be abstracted by the relationship between node and information. The relationship is abstracted by context, e.g., tag information in real applications. For special information I, if I is interesting enough on all related contexts to node u, u will accept I and become active. If I is “similar” enough with u and there are enough neighbor users which accept I, u will tend to become progressive and try to activate other users.

Let us consider an example of IDC model shown on the top left corner of Fig. 1. Assume that we have an ID model 〈G,C,P,U,Θ〉 for some network. The network G is shown in Fig. 1, which include five nodes and seven edges. The context set C is

We use c₁, c₂, c₃, and so on to represent them. The function set P={p¹,p²,p³,… } can be represented as follows, without loss of generality, focusing on the first two contexts in this example, we only describe p¹ and p².

The definition of function U is as follows:

The definition of threshold set Θ is as follows:

Given {A} as the seed node set, assume that a message m associated with contexts C_I={c₁,c₂}, an example of information diffusion procedure is shown in Fig. 1. In the first step t₀, node A will be initialized to be active. Then, \(p_{1}(A,m)=\frac {|C_{I}\cap {U(A)}|}{|U(A)|}=\frac {2}{3}\), A will continue to calculate \(f_{1}(A)=\frac {1}{3}\) with probability \(\frac {2}{3}\). Suppose A successes to compute f₁(A), since f₁(A)>θ_A=0.1, A will become progressive in the next step. In the second step t₁, two edges connected with A will be processed. For the edge (A,C), since \(p^{1}_{AC}=0.7\) and \(p^{2}_{AC}=0.8\), node C will be tried to be activated in two steps. Assume that the first random value generated is 0.85, because \(0.85>p^{1}_{AC}=0.7\), C will be activated in the first context. Also, assume that C is also activated in the second context. Then, C will become active. For the edge (A,B), because \(p^{1}_{AB}=0.6\) and \(p^{2}_{AB}=0.9\), the node B will be tried to be activated by two contexts. Assume that the two random values generated for the two contexts are 0.7 and 0.9, the node B will become active also. Then, we have

Assume that B and C are both success in this step. Then, we have

Because f₁(B)<θ_B=0.5, B will stay in active state, and C will become progressive observing that f₁(C)≥θ_C=0.5. In the third step t₂, C will try to activate the node D on two contexts in the probability \(p^{1}_{CD}=0.1\) and \(p^{2}_{CD}=0.9\). Assume that D is activated on the second context, but D will not become active since only one context is activated. Now, since C has been progressive in the last step, we have

Therefore, B will become progressive. In the forth step t₃, the node B will try to activate D and E. Assume that D is activated on the first context, then D will become active. Also, since \(p^{2}_{BE}=0.02\) and \(p^{1}_{BE}=0.8\), assume that only the first context of E is activated. In the fifth step t₄, assume that the node D fails to continue calculate f₁(D), D will stay in the state active in the following steps. Then, E will not be activated. Finally, the nodes {A,B,C,D} are influenced by the seed set {A}.

The goal of the original influence maximization problem is to find a node subset S such that the expected nodes which are influenced by S is maximized. Obviously, to define the influence, a method measuring the benefit obtained by diffusing information over S should be given first. Based on the two classical models of information diffusion, the corresponding procedures of diffusing information are probabilistic. Therefore, the influence maximization problems are usually studied under the semantics of possible worlds.

The space of all possible worlds corresponding to a given IDC model can be determined by the following steps. Let Ω be the set of all different possible worlds of given IDC model. As shown in the section above, each possible world can be defined by a special procedure of information diffusion. That is, even if almost all steps in the information diffusion procedure of IDC model are probabilistic, once fixed series of steps are given, all operations can be determined. Therefore, each unique diffusion procedure is related with a possible world. Then, the probability of the possible world X∈Ω can be represented by Pr(X).

To be simple, each possible world can be represented by a deterministic-induced subgraph of the whole network. According to the information diffusion procedure of IDC model, all probabilistic choices are indeed the operations of tossing coins based on p₁ and {p¹,p²,… } for the contexts. Then, the probability of each possible induced graph \(\hat {G}\) can be calculated by the following formula

where S is the set of edges selected in \(\hat {G}\), and T is the set of nodes selected by the probability p₁(·) in \(\hat {G}\). It can be verified that there exists efficient algorithms to check whether the induced graph \(\hat {G}\) is feasible to obtain in IDC model. For each feasible induced graph, we can determine an information diffusion procedure to conduct it. It should be noted that in IDC model, two different processes may reach the same possible world. Therefore, the probabilities of each single process and possible world are different. Intuitively, we can define a standard information diffusion such that it can be one-to-one mapped to the induced graphs. As shown in the following part, such standard procedure can be simulated efficiently, and the problem can be solved by randomized estimation.

Based on the observations above, we can give the definition of influence function. Usually, we use the function δ(·) to represent the influence range of given seed node set. That is, given seed set A, δ(A) will be the nodes which become active after diffusing the information based A. Observing the above procedure of information diffusion, for each single process, we have δ(A)=Z. In fact, within the example shown above, each possible world G_i is indeed a deterministic single diffusion procedure, and the vertex set of G_i is just Z which can be influenced by A. However, the diffusion process is a probabilistic one, we need a definition based on possible world semantics.

Based on the definition of influence function, we can give the formal definition of influence maximization problem on IDC model.

In the following parts, we will use IM-IDC (influence maximization for information diffusion with contexts) to represent the influence maximization problem on IDC model.

For each node v in the network, as shown in the section above, we use C_v to represent the context information of v. In a practical application, the context information can be collected by selecting the tags of interested topics. For example, most of social applications, such as Tweet, and Sina Weibo, allow users to select interested tags which will be used to do the recommendation, indeed the tags can represent which kind of information will be read and retransmit. Second, the tags can also be obtained by analyzing the profiling information of users. For example, the user profiles in Sina Weibo also contains some important information of users such as living place and age, and the profiles also contain tag information which may affect the information diffusion, one of the key observations is that people usually are interested in things or topics related to their local events; by analyzing some more customized information, such as self-descriptions of users, utilizing techniques of natural language processing, we can also identify the tags which represent the factors affecting the procedure of information diffusion. Finally, the tags for nodes can also be copied from one node to another one. The structural information in social networks can be used to infer the tags of nodes. By finding clusters in the network, we can identify which nodes may contain similar tags. Intuitively, the nodes within one same cluster tend to contain similar tags; if the clustering algorithms take the information related to some special tags into consideration, the clustering result will provide a strong evidence for predicting the tags for nodes.

For information m in the network, such as one tweet, we use C_m to represent the contexts related to m. In real applications, we can obtained the contexts of m by following methods. First, most social platforms allow users to give the highlights or labels for the information produced in the network, for example, Sina Weibo allows users to use special symbols (e.g., #) to add topic labels for the message created by them. Second, a simple strategy is to use the users’ tag for the information produced by them. Finally, the tags can also be generated by analyzing the information by sophisticated synthetic and semantic processing techniques for natural languages.

According to the definition of contexts in the above section, during the procedure of information diffusion, the influence probability functions are different for different contexts. Essentially, general techniques for predicting influence probabilities in social network without context considerations can be utilized here to determine the influence probabilities. Intuitively, for each special context c, it can be done by using the predicting techniques over information diffusing records related to context c. As long as enough data for diffusing information can be collected, the influence probabilities can be predicted accurately. Since the goal of this paper is to design efficient algorithms for the problem of influence maximization, without loss of generality, we assume the influence functions of contexts are given in advance. In fact, even if only the influence functions for a special set of tags are given, when new tags appear, we can still build the influence probabilities for new tag incrementally by analyzing the procedure of information diffusion related to the corresponding tags.

The result above indicates that it is impossible to design algorithms in polynomial time unless P=NP. Therefore, we need heuristic algorithms later. In fact, the problem is much harder than the analysis in Theorem 1. As shown in [1], the problem of computing δ(·) under classic IC model has already been ♯P-hard. That is, to compute an influence measure in a feasible way (e.g., on possible worlds semantics) has been already very hard. Of course, this result is meaningful only when we assume that all algorithms solving the IM-IDC problem will invoke a procedure to solve the subproblem of computing influence measures. Observing that no existing algorithms can avoid computing or estimating the influence measure directly, the result of ♯P-hard indicates that the IM-IDC problem is much harder than we think in usual.

According to Theorem 1, since there are no efficient deterministic algorithms for the IM-IDC problem, therefore, in this part, an approximation algorithm is given. The main idea of this part is to design greedy algorithm with performance guarantees. A popular method is to utilize the monotonicity and submodularity properties of measuring functions. Given a function δ(·):2^V→R, δ is called to be monotone if and only if δ(S₁)≤δ(S₂) for any S₁⊆S₂, it is called to be submodular if δ(S₁∪x)−δ(S₁)≥δ(S₂∪x)−δ(S₂) for any S₁⊆S₂. Informally speaking, suppose we are trying to find an optimal subset S^′⊆S, the optimization goal is measured by a function f, a greedy algorithm has performance guarantee if f is monotone and submodular. In practical, for influence maximization problem, as shown in [2], monotone and submodular properties allow us to develop greedy algorithms to achieve (1−1/e−ε) approximation ratio.

We proposed an algorithm based on greedy idea which can produce approximation algorithms with ratio 1−1/e as shown by [10]. The algorithm is shown as Algorithm 1. The algorithm APPROIM-IDC takes M=〈G=(V,E),P,C,U,Θ〉, an information context set C_I, and integer k>0 as the input parameters. First, two variables S and cur are initialized to be an empty set and 0, respectively, where S is a set for storing the optimal seed nodes, and cur is used to record the influence obtained by the algorithm during the whole procedure (line 2–3). Then, algorithm APPROIM-IDC iterates over the integer k. At each time, APPROIM-IDC selects one node u greedily (line 4–16). Intuitively, APPROIM-IDC tries to maximize the benefit obtained locally by selecting u, which may lose the chance to get the global optimal solution. As shown by the analysis in the following parts, the solution of APPROIM-IDC has approximation performance guarantees. The variable Δ_v is used to represent the influence benefit obtained by adding v to S, that is δ(S∪v)−δ(S). The function CALINF is invoked to calculate the influence (line 8), which will be explained in the following part. Finally, the set S will be returned by APPROIM-IDC as the approximation of optimal seed node set (line 17).

The function CALINF is shown in Algorithm 1 also (line 27–64). In the CALINF procedure, the inputs include the information context set C_I, the seed node set S, and the instance M of IM-IDC model, the task is to compute the expected influence obtained by diffusing information from S in M under possible world semantics. As discussed before, the problem of computing δ(·) is at least ♯P-hard; therefore, we give a randomized algorithm to estimate the value of δ(·). It is easy to verify that the procedure CALINF can give an estimation of δ(·) satisfying the requirements by allowing multiple runs of the randomized algorithm. Thus, our idea is to compute the influence by simulating the information diffusion procedures enough times. First, the variable influence for storing the final result is initialized to be zero (line 28). Then, the randomized estimation method will be ran for n times (line 29–62) (the value of n can be determined according to the method in [2]) and the averaged value of all result influences will be returned (line 63). During each iteration, we use three variables T, L, and R to represent the set which is composed of the active nodes, the progressive nodes, and progressive nodes whose influences have not been calculated, respectively (line 30). Then, S is used to initialize all temporary variables used (line 32–43). Nodes in V are divided into two parts, S and V∖S, and for each node v the variable v.state is used to record the node v is inactive, active, or progressive, and the variable v.con[c] is used to indicate whether v has been influenced by the information over a specified context c. Then, the inactive nodes will be processed one by one, and the node may be influenced during this procedure (line 44–60). The function TOACTIVE is invoked to determine whether node v will be influenced by u (line 51). Because of the privacy considerations, even if v becomes active, it may stop reposting the information, therefore, the function TOPROGRESSIVE is invoked to determine whether v will be progressive (line 54). During the iterations, L is used to maintain the nodes which should be considered in the computation of influence. New nodes becoming progressive in the last iteration will be added into L (line 55), and once one node has been considered, it will be removed from L(line 59). The two functions TOPROGRESSIVE and TOACTIVE are shown in Algorithm 2, which are used to change the state of some node.

In this part, we will show that algorithm APPROIM-IDC has performance guarantee on time complexity and the approximation ratio. The main idea is to show the influence function δ satisfies the properties of monotone and submodular.

First, based on the observation that the main procedure of algorithm APPROIM-IDC is to iterate among all nodes, and the CALINF procedure only enumerates every edge of G, it is easy to verify that algorithm CALINF can be finished in polynomial time. In the function TOPROGRESSIVE, the time costs can be bounded by O(|C|+|V|), where C represents the context set usually with constant size and V is caused by the iteration of N(v). The time cost of function TOACTIVE can be bounded by |C_I|<|C|. In CALINF, the main time cost comes from the procedure of processing each progressive node (line 44–60), it is not hard to verify that the cost can be bounded by O(|E|²)·|C|; therefore, the time cost of CALINF can be bounded by O(n·|E|²·|C|+n·|V|). Combining CALINF with APPROIM-IDC and ignoring the value |C| by treating it to be a constant, the total time cost of APPROIM-IDC can be bounded by O(k·n·|V|·|E|²).

Then, we will give an equivalent form of δ, represented by \(\hat {\delta }\), which is based on the general threshold model defined by [11]. In that model, the influence functions are defined over node sets but not over nodes. In detail, for a special node u, an influence function f_v is defined by mapping the elements in 2^{V} to the range [0,1], a necessary condition is that f_v(∅)=0. A threshold γ_v is given to control whether v will be activated, where v will become active when we have f_v(S)≥γ_v for which S is the neighbors of v active. It is not hard to see that this model can be extended to the setting of context considerations. We can replace f_v with a set of influence functions \(\{f^{\varphi _{c}}_{v}\}\) where φ_c is a corresponding dimension to a special context in C, and let the condition that v becomes active be v is influenced by all contexts, that is we have fvφ_c(S)≥γvφ_c for all contexts.

For the convenience in following this part, we will introduce several useful notations. For an arbitrary active node set \(\hat {S}\), where \(\hat {S}\) may be different from the input parameter S of the problem since \(\hat {S}\) will represent the active set in the network during the whole procedure of information diffusion, let H_u(S) be the probability that u satisfies the constraints defined by p₁(u,I). Obviously, the condition of p₁ depends on the context sets of information and users, it is independent from which users have become active. To be consistent, we still use the parameter S for H_u. For a special information I, we have H_u(S)=|C_u∩C_I|/|C_u|=λ_u.

For an arbitrary active node set \(\hat {S}\) and a node u which has passed the verification of p₁ condition, let \(H^{\prime }_{u}(S)\) be the probability that u satisfies the constraints defined by f₁(u). Actually, the probability can be represented by an indicator function \({I}_{f_{1}(u,S)\geq {\theta _{u}}}(u)\), which is defined to be 1 if f₁(u,S)≥θ_u or 0 if f₁(u,S)<θ_u. Here, f₁(u) can be rewritten with respect to S as \(f_{1}(u,S)=\frac {|N_{u}\cap {S}|+1}{|N_{u}|+1}\), where the value f₁(u,S) only depends on the network structure and the active set S.

Here, the definition of multi-dimensional threshold model is introduced first, which is used in [11] to give general definitions of influence maximization problem for extending linear threshold and independent cascade models. Here, for a special dimension φ, each node is associated with a monotone threshold function \(f_{v}^{\varphi }\) which maps subsets of neighbors of v to a probability value in [0,1], satisfying \(f_{v}^{\varphi }(\emptyset)=0\). Initially, each node v selects a random threshold value \(\theta _{v}^{\varphi }\) uniformly. At each step k, a node v becomes active if and only if for all dimensions the node v has \(f_{v}^{\varphi }(S)\geq \theta _{v}^{\varphi }\) where S is the set of neighbors of v active in the step k−1.

Actually, the proof of Theorem 2 still needs the following three theorems to be complete, since we made an assumption that \(\theta _{u}>\frac {1}{|N_{u}|+1}\) and did not verify the wellness of definition of I^′.

The results obtained in previous part are based on careful analysis about the process of diffusing special information denoted by C_I over IDC model. Theorem 2 only works for the case that a special information has been given and the context set C_I can be obtained in advance. Essentially, given a network G and settings for IDC model, the APPROIM-IDC algorithm shown in Fig. 1 can only output a seed set A which can maximize the expected influence of given information with context set C_I. A more general case is that the context set of some information is randomly selected within a given domain, and it is expected that the APPROIM-IDC algorithm can be simply extended to solve the related influence maximization problem.

First, assume that the information context set C_I is taken from the global context set C, where each context in C is selected by probability α.

It is not hard to check that \(\hat {\delta }_{I}(A)\) also satisfies the submodular property, then, by replacing the procedure of verifying p₁ with checking the value of random variable generated by probability α, the APPROIM-IDC algorithm can be extended to solve the influence maximization problem for general information in IDC model, which also guarantees that the approximation ratio is 1−1/e.

For more, assume that the random information has only context set with fixed size b. Utilizing similar techniques, we can construct the corresponding instance I^′ by letting \(f_{v}^{\varphi _{1}}(S)=\frac {b}{|C|}\). Since \(\mathbf {E}(H_{u}(S))=\frac {C_{|C|-1}^{b-1}}{C_{|C|}^{b}}=\frac {b}{|C|}\), we can obtain similar result.

Compared with classical information diffusion model, the IDC model is more complex, which is mainly caused by the verification of information relativeness and privacy. It appears to have two drawbacks, the first one is we need more computation cost to simulate the procedure of diffusing information in IDC model, the second one is that most of the previous work on optimizing the influence maximization algorithms do not work again since the distributions of active nodes become very different. In general case, it seems that nothing can be done to fix this, since IDC model is more expressive and the drawbacks are the side effects of expressibility. In this part, some special cases are considered, and optimization methods are introduced.

Suppose we know that many information with the same context set C_I is often used to generate the seed set with maximum expected influence. Given an instance I=〈G,C,P,U,Θ〉 of IDC model, we can simplify G and the procedure of diffusing information by preprocessing I to generate another equivalent instance I^′. First, given C_I, obviously, we can eliminate the function set P to \(P_{C_{I}}\) which only includes the functions related to contexts appearing in C_I. Then, for each node v satisfying that C_v∩C_I=∅, the out edges of v can be removed from G. Intuitively, even if v becomes active, it will not try to trigger other nodes further, according to the definition of IDC model. For more, the seed set A can only be considered to be selected within V_G∖v, except for some trivial cases like |V_G|≤k. When the values in Θ have been given, if some node v satisfies that \(\frac {1}{|N_{v}|+1}\geq \theta _{v}\), the verification of the second constraint defined by f₁ can be removed.

In the definition of IDC model, we did not discuss the problem of redundant contexts which are usually viewed in real applications. Obviously, the computation cost of simulating information diffusion procedure will increase much, even if only one extra context is added. Therefore, less contexts will produce efficient algorithms for influence maximization problem.

Redundant contexts need to be identified, which is helpful to improve the efficiency and fill the missing context information using similar ones. To be simple, it is assumed that there is a matrix which contains the information about similarity values between each two contexts. In practical applications, such a matrix can be obtained by learning methods such as embedding algorithms [12] or ranking algorithms such as simrank [13]. Intuitively, since the matrix contains similarity values of every pair of contexts, while the ideal structure we need is actually a clique-based matrix, efficient algorithms are needed to resolve this problem. As shown in algorithm 3, the main idea is a bottom-up method. Two parameters ε₁ and ε₂, are used to preprocess the similarity matrix to eliminate the noises as much as possible. Then, P is initialized to be the most refined partition of all contexts. For each two partitions in P, every time REDUNCONTEXT considers to merge the partitions to build a bigger partition by calculating a value which can be used to measure the closeness of the two partitions (line 15–23). If the two partitions are close enough, they will be merged into one. If there are no partitions, it can be merged further, REDUNCONTEXT stops, and outputs P as the final result. Intuitively, if two contexts are put into the same partition in P, they will be treated as redundant contexts latter.

In this part, one possible solution for obtaining the influence probabilities by learning methods is introduced, which is based on word2vec, a powerful method for learning compressed representations. Word2vec is a group of learning models that are used to produce word embeddings which are usually used to reconstruct linguistic contexts of words, whose detail can be found in [12]. The main idea of word2vec is to take the inputs of a large corpus of text and compute a vector space, where each unique word in the corpus is represented by a corresponding vector in the space. There are two models often utilized, CBOW (continuous Bag-of-Words) and Skip-gram (continuous Skip Gram). A common framework of CBOW is shown in Fig. 2, it is widely used. There are usually three layers: input layer, hidden layer, and output layer. Intuitively, the word2vec method can be used to construct condensed representations for a set of keys. The co-occurrence relationships of keys are considered, which means that those keys appearing at the same time when we try to search the keys within information we take. If we treat the keys as input of the word2vec method, the hidden layer will maintain a matrix which can be used to explain the relations between different keys. The matrix can help us to know which keys are similar, which keys have co-occurrence relations, and so on. Usually, the output will be a key which has highest possibility to appear with all given keys together.

Therefore, one possible solution for determining the influence probabilities for the contexts can be summarized as follows. For each information sequence, suppose that the same techniques are utilized to extract contexts from both users and messages and a bag-of-word model Q is built to learn the probabilities, the sequence will be transformed into a context set sequence. Here, each context set is obtained from the corresponding users in the information sequence. Then, by analyzing the message, another special context set for the message can be produced, and the context set sequence will be associated with each item in the message context set. After that, for each context c, the associated context set sequence will be sent to the model Q, where each context set can be reduced to one unique item, since we do not consider the similarity relation between contexts here. When estimating the influence probability between two nodes u and v on special context c, a certain number of prefix sequences can be generated and concatenated with u. Using the whole sequence as the input of Q, the appearing probability of v after this sequence can be obtained in the output layer. Finally, the influence probability can be estimated efficiently by running the model multiple times and taking the average probability values.

We ran our experiments on two real datasets, DBLP and LiveJournal, which are collected from the SNAP project of Stanford University¹. The DBLP dataset is a large network of research collaboration maintained by Michael Ley. In the network of DBLP, the nodes represent the authors of academic papers, and there exist one edge between two nodes if and only if the two corresponding authors have collaborations. For DBLP, we use the coauthor relationships to compute the influence probability between two authors. The LiveJournal dataset is a free online community with almost 10 million members, a significant fraction of these members are highly active. (For example, according to the statistics of the SNAP project, roughly 300,000 update their content in any given 24-h period.) The members use LiveJournal to maintain information about journals, individual, and group blogs. Also, LiveJournal allows people to declare which other members are their friends they belong, which provides us the social relation between users.

In the experiments, the effects of contexts considerations and the performances of the algorithms are evaluated. The algorithm proposed in the paper is ran over different datasets, by choosing different parameters, we focus on the influence effects, the running time costs, and so on.

One key parameter of the APPROIM-IDC algorithm is the context set C, which actually can be treated to be a constant set in the experiments, since in real applications (e.g., DBLP) the number of contexts is limited. Although the two datasets we used have different properties, the contexts are similar, since both of them are about publications and authors. Therefore, We generated the context sets by first extract contexts from DBLP and LiveJournal by calculating the frequencies of different items, and then combing the two contexts together.

For the two other important parameters U and Θ, the following methods are adopted to generate the parameters. Since not all contexts are equivalent in the aspect of appearing frequencies, we did not obtain the information-related data; therefore, when generating the context sets, we consider the frequencies of contexts in current datasets and try to generate data by similar distributions. For the nodes in the network, besides the context information collected by analyzing the item frequencies, we also generate the contexts based on the context distribution obtained from the data in special probability (0.1 in the experiments), and mix the two sets of contexts together. We do not use the real message in the experiments, since the information diffusion procedure only focuses the context information indeed, random context sets with low, medium, and high cardinalities are generated to represent the real message. For the parameter Θ, in general experiments, it is randomly selected for each node, while it is randomly generated according to the Poisson distribution when the effects of Θ are evaluated. According to the parameter λ = 0.1,0.3,0.5, the corresponding cases can be identified to be IM-IDC-A, IM-IDC-B, and IM-IDC-C, respectively.

Effects of seed set size. The effects of given seed set can be evaluated by the influenced nodes size, that is to verify how many nodes are expected to be influenced in average setting. On the two datasets, we compare the APPROIM-IDC algorithm on different parameters settings of U to distinguish different kinds of information. For each special setting, the seed node set size is changed from low to high, the influence sizes are recorded. The results are shown in Figs. 3 and 4. It can be observed that as the size of seed nodes set increases, the size of influenced nodes increases almost in linear speed. The result is expected since in a network all enough large nodes tend to perform uniformly during the information diffusion. Especially, as discussed in the previous parts, the IDC model has similar representations with the general one which can be obtained by treating each set as the basic considerations of influence sets.

Also, it can be found that when increasing the value of U, that is when we change the context set of users from low to high, the size of influenced nodes set gets smaller. Essentially, when we increase the size of values of U(·), there are mainly two factors which will affect the influence set size. The first is that the probability that each node become progressive from active gets higher; however, in practical, it depends on the tossing coin results not just the probability. Also, the second step about computing f₁ lets the effects of this factor not so obvious. The second factor is that the probability that one user gets active becomes lower. Actually, in real applications, this factor shows the main effect since it causes a main decrease of the influence probabilities, especially when the size of U(·) is relatively small. As shown by the results, when increasing the size of value of U(·), the entire trend of the influence set size shows to get lower and lower. Also, the difference between IM-IDC-H and IM-IDC-M is smaller than the one between IM-IDC-L and IM-IDC-M.

Effects of Θ. As discussed above, the parameter set Θ is a key factor affecting the procedure of information diffusion. In this part, the effect of Θ is evaluated by comparing the influence set size for seed node sets with different sizes on the two datasets. When increasing the seed node size from 1 to 50, we ran APPROIM-IDC on the two datasets for three different λ values for the Poisson distribution generator, the influence sizes are reported. The result is shown in Figs. 5 and 6. It can be observed that as the value of seed node size increases, the size of influenced nodes increases, which are expected and observed in the experiments above also. Comparing the results for IM-IDC-A, IM-IDC-B, and IM-IDC-C, it can be observed that as the increase of the parameter λ, the influence set size decreases when the sizes of seed nodes are the same. As shown in the APPROIM-IDC method, it can be known that the value of λ will determine the values of θ of most nodes. The higher the value is, the larger the corresponding θ value is. Then, during the procedure of information diffusion, it will be harder for the node to become progressive, since it needs more progressive neighbor nodes in that case.

Running time. For the real applications, one key challenge of solving the influence maximization problems is the time cost. That is just the reason that we need approximation algorithms whose performance on running time is better than deterministic algorithms. For the two datasets, we ran the APPROIM-IDC algorithm proposed by this paper on different parameters of seed node size. For the parameters of APPROIM-IDC, we picked six combinations which may represent most settings of APPROIM-IDC and give us an illustration about the performances of APPROIM-IDC under different application settings. The running time results are shown in Fig. 7. It can be found that as the size of seeds set increases the running time cost also increases, when seed node size becomes larger the increase speed of running time cost becomes slow. Also, we can find that the parameters such as context cardinalities and Θ have important affections on the performance of APPROIM-IDC on running time costs. Generally speaking, the higher the context cardinalities are, the more effcient the running time performance is, and the higher the values in Θ are, the running time performances of APPROIM-IDC become much better.