Recently there has been tremendous research on influence analysis in social networks: how to find initial topics or users to maximize the word-of-mouth effect that may be significant for advertising, viral marketing and other applications. Many researchers focus on the problem of influence maximization on the static structure of the network and find a subset of early adopters which activate the influence diffusion across the network. Despite the progress in modeling and techniques, how the incentives improve the network structure to enlarge the influence diffusion has been largely overlooked. In this paper, we introduce a novel problem which extends the influence maximization to the situation that the network structure can be varied in case of some incentives such as fans trading by compensating the web users to be fans in social networks. Providing that the presented problem is NP-hard, we propose two approximate approaches to solve the problem of influence maximization in dynamic networks. The first is a two-stage approach which separates the problem into two sub problems and solves them respectively. The second is a joint influence diffusion algorithm so as to repair the network structure and find the corresponding initial subset of the individuals in the repaired social network simultaneously to maximize the influence. We performed experiments on social network data to provide evidence of the effectiveness of the proposed methods.
With the social networks emerging and quickly developing in
the past few years, information diffusion has attracted
considerable attention by researchers in different kinds of areas such
as social advertising, viral marketing, etc. In the studies of
information diffusion, a central problem that received much
attention is the influence maximization problem, which
specifies a small subset of individuals in a social network as seeds
that produce a large word-of-mouth effect in the network. As
for influence maximization problem, there has been no
perfect method since it is proved to be NP-hard [Kempe et al.,
Copyright c 2015 for the individual papers by the papers’ authors.
Copying permitted for private and academic purposes. This volume
is published and copyrighted by its editors.
2003]. Therefore, much work has been conducted to solve the
approximate guarantees that add necessary prior constraints
to the original problem
The influence diffusion models in previous studies mainly focus on the situation that the network is static and stabilized. With the addition of the viral marketing and advertising, the social networks are not just a place for human interaction and communication. They increasingly become the main battlefield for commercial interests. In fact, the networks are continually changing since people make new friends or break up online all the time spontaneously. The work in [Adiga et al., 2013] is just this kind of situation which models the changes as stochastic changes and discusses the effect of stochastic changes in the network on influence maximization problems. However, it is still an open question that what changes in the network mostly help the influence diffusion. Besides the spontaneous changes in social networks, there are another kind of changes which are conducted by human intervention. The practical approaches of human intervention in social networks can be outlined as follows. The advertisers may be willing to pay to the providers of the social network services for connecting web users so as to enlarge the influence of the following social advertising . The celebrities are also willing to give small flavors such as concert tickets or their autographed posters to earn more fans who are not their fans before so as to market their following concerts or spread their fame. Furthermore, recent statistical and theoretical studies involving perturbation of the network show that changes in the network structure largely altering the influence dynamics in social networks [Adiga et al., 2013]. With the network changing with human intervention and the changes alter the influence dynamics, some novel but urgent problems come up: how the influence diffusion dynamics is altered with the human intervention and how the intervention is carried out so as to help the influence diffusion across the social networks to reach the maximum outcome.
In this paper, we research how the changes of the network structure alter the influence diffusion. We show that connecting some edges of the network can largely help the influence diffusion process using linear threshold model or independent cascade model. Then we extend the influence maximization problem to human guided dynamic networks which can be locally modified with human intervention. Providing that the proposed influence maximization problem is NP-hard, we introduce two approximate approaches to solve the problem in human-intervened dynamic networks. We propose a two-stage approach which first repairs the network and then chooses the early activated adopters to conduct the influence diffusion process with a given budget until the influence maximization is reached as shown in Figure 1. In another approach, we introduce a joint influence diffusion algorithm to depict the rise of the incentives, the evolution of the network, and the influence diffusion process with respect to the multiple stages of the evolution procedure, and then solve the influence maximization in the dynamic networks approximately. 2
Given the urgent need of viral marketing, the influence
maximization problem has attracted many researchers’ attention
since it was first released in [Domingos and Richardson,
2001]. The initial researches
Some researchers begin to study how the network structural changes impact on the influence diffusion. As the literature [Lahiri et al., 2008] empirically shows, in real dynamic networks the predictions about the relative spreading capacity of individuals and the identity of the top spreaders are sensitive even to minimal changes in the network. It is also theoretically proved that structural changes such as edge perturbations are largely impact on the stability of the independent cascades and linear threshold models [Adiga et al., 2013] in sparse networks which almost all online social networks belong to. 3
In the following section, as Figure 1 shows, we simply show how the human intervention is conducted to modify the structure in social networks, and then, we present how these changes impact the influence diffusion dynamics.
The practical approaches of human intervention in social networks have described in the introduction section. Generally speaking, the advertisers and the celebrities are willing to pay to enlarge their influence on the web. We assume a social network represented by a graph G(V; E). The nodes V corresponding to posts or users can be viewed as adopters to diffuse the influence sequentially. There is an edge e 2 E between two adopters u; v 2 V if u has a relation with v. With the human intervention that the advertisers and the celebrities are willing to connecting web users, we discuss the humanintervened network with connecting node pairs as the new adding edges of the repaired network.
The two basic diffusion models popularly used in previous studies are the linear threshold (LT) model and the independent cascades (IC) model. In the LT model, a node v is activated at time step t if Pu2Nt(v) wu;v v 2 [0; 1], where Nt(v) denotes the neighbors of v that are active at time step t, wu;v 0 is a influence weight that the neighbor u imposes on the node v, and v a threshold uniformly chosen at random. While in the IC model, each node v is independently influenced by each neighbor u with some probability pu;v. When the node u is activated at time step t, it has a single chance to activate each neighbor v with probability pu;v. Besides the two basic models, there is another influence diffusion model, the voter model. Unlike the two basic models where the node is always stay active once it is activated, in the voter model, at every time step t, the node v always has chance to be activated or deactivated by its neighbors.
Assume that we connect k node pairs with respect to the original network with human intervention, how much the centrality is maximally changed? We assume the node v is the chosen node. The degree centrality of node v could be changed from D to D + O(k) if we connect node v with other nodes ai that can be all active at step t. In the next step t + 1, as for LT, the probability to activate the node v increases O(Pik=1 wavi;v ); while for IC, the probability increases O(Pk
i=1 pai;v). Assume that the diameter of part of the original graph is di and the centroid is Ci. After we connect node v and Ci, the average distance between the node v and part of the original graph becomes quite smaller than before. Thus, the closeness centrality becomes larger, and the influence starting from the node v can be more quickly to diffuse to the other nodes. 4
We assume a social network represented by a graph G(V; E). Given a limited budget B, assume that by compensating the two influencers u; v connected together, the cost should be at least cs(u; v). To choose the node v as a early adopter to diffuse the influence, the cost should be at least cs(v). A node at each time can only be in one of two state: active or inactive. We define a state function fi(v) 2 f1; 0g to show whether the node is active or not at time step i. Given a target time t, we want to maximize the influence across the whole graph under the constraint of budget B. We extends the influence maximization problem to human-intervened dynamic networks. The extended problem can be formalized as follows. Problem 1 (Influence Maximization Problem in a HumanIntervened Dynamic Network) Let G be a graph representing a social network, M 2 RjV j jV j a matrix of costs indicating the cost me = cs(u; v) of connecting u and v together, CS 2 RjV j a vector of costs indicating the cost csv = cs(v) of setting f0(v) = 1, B a budget, and t a target time. The influence maximization problem is to find the edge set S E that should be repaired and then find an assignment f0 : V ! f0; 1g that will maximize the expectation E Pv2V ft(v) subject to the budget constraint Pe2S me + Pv:f0(v)=1 csv B.
As the extended problem is NP-hard, we introduce two approximate solutions. One is a simple two-stage approach which solves the problem with the assumption that the problem can be separated into two sub problems. The other introduces a joint influence diffusion algorithm and combines the two stages together. 5
The graph can be dynamically changed if we repair it by connecting edges, and then the influence diffusion process should be deployed on the repaired network. The procedure of Problem 1 is conducted in two stages according to the time line. So the solution is also separated into two stages. 5.1
To make the influence diffuse more quickly and widely, the whole network should be tight, which means the nodes should be close to each other. Closeness centrality is just an indicator that shows how close one node to all the remaining nodes in the graph. We calculate the average distance (the shortest path) Davg of a node vi to the other nodes. The closeness 1 centrality of node vi is defined as Cc(vi) = Davg(vi) . Problem 2 Let B1 be a reparation budget, U the edge set to repair. The network reparation problem is to find the edge set S which will maximize the total closeness centrality of all the nodes Pvi2V Cc(vi) subject to the budget constraint Pe2S me B1.
The network reparation problem can be solved by a greedy algorithm as follows.
Input: The edge set U to repair, B1 the reparation budget Output: Edge set S 1: S := ; 2: Br := B1 . the remaining budget 3: Ur := U . the remaining candidate set 4: while Br 0 and Ur 6= ; do 5: for e 2 Ur do 6: E E [ e 7: G G(V; E) . The repaired graph 8: . maximize the closeness centrality of repaired graph 9: if PBvri2V Cc(vi) is maximized then 10: Br me 11: Ur Urne 12: S S [ e 13: end if 14: end for 15: end while
As for closeness centrality, the time complexity to calculate all the geodesic distance of the node pairs is O(jV j2 lg jV j + jV jjEj) using the shortest path algorithm implementing the minimum priority queue through Fibonacci heap. Thus the time complexity to the greedy algorithm is O(ljSj(jV j2 lg jV j + jV jjEj)), where l is the time of iterations and S U the final edges to repair.
The greedy algorithm seems significantly time-consuming. Inspired by decreasing the geodesic distance between node pairs, we perform clustering algorithm on the whole graph and find two centroids, and then we connect the two centroids. We repeat the procedure until reaching the budget. The shortest paths between all the node pairs decrease in every iteration, and the responding closeness centrality becomes larger.
The graph clustering problem is depicted as follows. Given the graph weight W with its element wuv representing the weight between node u and v and the cluster number K, our task is to separate the nodes V into K clusters with nodes in a cluster closely connecting together and nodes in different clusters should be far away from each other. It can be solved by the iterative algorithm that randomly chooses the k centroids then repeats it again to renew the centroids or the spectral clustering algorithms. More detail of the spectral clustering can be found in [Von Luxburg, 2007]. We follow the fast approximate spectral clustering with k-means in [Yan et al., 2009] which shows that the time complexity largely decreases from O(jV j3) to O(K3 + KljV j) where l is the number of iterations in k-means . In our centroids connecting algorithm, we set K = 2 to carefully choose one edge that should be connected with two centroids at a time. The time complexity of the algorithm is O(ljSjjV j).
Algorithm 2 The Centriods Connecting Algorithm (CCA) Input: The edge set U to repair, B1 the reparation budget Output: Edge set S 1: S := ; 2: Br := B1; Ur := U 3: while Br 0 and Ur 6= ; do 4: Finding two centroids c1; c2 by clustering graph G 5: if e := (c1; c2) 2 Ur then 6: E E [ e; G G(V; E) . The repaired graph 7: Br Br me; Ur Urne; S S [ e 8: end if
5.2
After the network reparation, we conduct the influence diffusion process across the repaired network given the leftover budget B2 = B B1.
We know that we should not give the entire budget to the first stage, because the influence diffusion should be started anyway. We repair the edges one by one until the expected influence of the graph (the total number of nodes activated) at target time step t does not increase any more.
The basic approach is easy to think about associated with the two stages of the problem. However, the influence diffusion process is not adaptively adjusted with the dynamic network. The other approximate approach will focus on the self-adaptive influence diffusion process. 6
Unlike the basic approach separating the influence maximization problem in dynamic networks into two stages and solving the corresponding problems independently, the network reparation and the influence diffusion process are simultaneously conducted in this model. Apparently, the influence diffusion process is the main task that it directly determines how much influence of the graph reaches at the target time. Thus, we design a joint influence diffusion algorithm to adaptively choose the edges to repair to maximize the influence of the whole network.
A node v in a graph can influence its neighbors in the LT or IC model. Given that the network can be repaired with a cost, the other nodes can also be influenced by v if we connect v and the other nodes together. As for v, given the neighbor node set N and the other node set F , how can we choose the node u 2 F to connect with v to maximize the influence diffusion from v? The answer is that v should be influenced as quickly as possible, that is, v should directly connect to the early adopters. To maximize all the influence diffusion from the other nodes, the early adopters should be close to all the other nodes.
Referred to the centroids connecting algorithm (CCA), we design a joint influence diffusion algorithm both considering the network reparation and the influence diffusion process. First, we choose two early adopters u; v to be activated to maximize the influence diffusion in initial graph given the target time t. We perform clustering algorithm and get two clusters. There are two conditions to consider: (1) if u; v are in one cluster, then we choose the node far from its centroid to connect to the other centroid; (2) if u; v are in different clusters, then we choose both the nodes to connect to the other centroid. Second, we maximize the influence diffusion in repaired network and choose two early adopters again. We perform clustering algorithm again. We repeat the procedure several times until we run out of the entire budget.
Input: The edge set U to repair, B1 the reparation budget Output: Edge set S to connect, early node set N to activate 1: S := ;; N := ; 2: Br := B1; Ur := U 3: while Br 0 and Ur 6= ; do 4: Finding two centroids c1; c2 by clustering graph G into C1; C2 5: Choosing u; v as early adopters to maximize the influence 6: if u; v 2 C1 then 7: if ShortestPath(u; c1)>ShortestPath(v; c1) then 8: if e := (u; c2) 2= Ur then 9: Choose node cm with the largest degree and 10: e (u; cm) 2 Ur 11: end if 12: E E [ e; G G(V; E) 13: Br Br me cv; Ur 14: S S [ e; N N [ v 15: end if 16: end if 17: The same to the other conditions ... 18: end while Urne 7
We conducted a variety of experiments to evaluate the performance of the presented algorithms with respect to the two basic influence diffusion models in social networks. In LT model, for each of the node v’s neighbors u, the influence weight wu;v = d 1
v , where dv was drawn independently at random from an estimated degree distribution of the social graph. While in IC model, the probability of the single chance to activate its neighbors was 1% uniformly set. We first concisely introduce the experimental setup and then present the results of the evaluation.
3000 JCoCinAt 2500 SGtAatic
Random 2000 cen eu1500 lfI1000 n 500 00 6000 5000 4000 e c lfen3000 u n I2000 1000 00
Joint CCA GA Static Random 6000 JCoCinAt 5000 SGtAatic
Random 4000 cen eu3000 lIf2000 n 1000
00 8000 7000 6000 e5000 c lfen4000 u In3000 2000 1000 00
Joint CCA GA Static
Random soc-Epinions1 in LT model soc-Epinions1 in IC model 20 We download two online social networks from SNAP1, socEpinions1 and soc-Slashdot0922. The experiments were conducted on a 2.67GHz 4-core i5 machine with 4GB RAM, running the Windows 7 operating system. The algorithms were mainly implemented in C++. In this subsection, first we study how the budget B1 which is used in network reparation imposes on the influence diffusion, and then we conduct two experiments to compare different algorithms with respect to the influence according to two important hyper parameters: the budget and the target time. After that, we compare the time complexity of the three algorithms which solve our maximization problem in dynamic networks.
The reparation budget B1 is a very important factor we concerned in our framework. Our heuristic method is simple just as follows. We increasingly set the reparation budget up until the maximum influence is arrived given the target time t and the total budget B. Providing the cost to repair the network and activate the initial adopters is missing, we stipulate that every cost is 1 uniformly. Now the total budget becomes the sum of the number of the edges to repair and the number of the initial nodes to activate, where the reparation budget equals to the number of edges to repair. As shown in Table 2, when B1 = B=10, the number of nodes to be activated is the largest. In the following experiments, we choose B1 = B=10 uniformly.
Let the target time t be fixed, we get the influence diffusion vs. budget from 10 to 100. We compare the influence vs budget with respect to the greedy algorithm (GA), the centriods connecting algorithm (CCA), the joint algorithm (Joint), the influence diffusion on the static network (Static) and the random algorithm as baseline. As shown in Figure 2, we find that it performed nearly the same trend based on the two basic influence diffusion models LT and IC. Throughout the experiment, we find that the formal three algorithms achieved very close result, which largely outperformed the static method that does not repair the network. Generally speaking, the performance rank of formal three algorithms in soc-Epinions is GA CCA > Joint, respectively. While the performance difference between the joint algorithm and the other two algorithms is really small.
5
In the previous experiment, we fix the target time while changing the budget. Now we fix the total budget to 50, and get the influence diffusion vs. target time from 0 to 20. From the experimental result as shown in Figure 3, the influence diffusion quickly increases as the target time becomes larger. When the target time exceeds a threshold, the influence increases slowly. It can be explained that the in a social network there are only several seeds to conduct the influence diffusion process. Once the neighbors are activated, they further activate their neighbors. Gradually, the world-of-mouth effect is formed. When almost all the nodes could be activated is activated, the influence diffusion goes to the period of stagnation.
We also conduct the experiments on the soc-Slashdot0922 which leads to similar conclusion as we get above with the soc-Epinions1 dataset. Due to space constraints we do not present the similar results in this paper.
In this paper, we introduce two approaches and three algorithms to approximately solve the influence maximization in dynamic networks. Next, we simply compare the time complexity of each algorithm on the two datasets. As shown in Table 3, though the joint algorithm does not perform the best according to the experimental results listed above. It beats the other two in terms of running time. In summary, the joint algorithm consumes much less time while the performance does not decrease fiercely. 8
In this paper, we have studied the influence maximization problem in dynamic networks which can be changed with hu
IC 4.459 4.774 5.734 4.415 3.777 2.429 man intervention. Given a limited budget and a target time, we can both repair the network structure and choose early adopters to maximize the influence diffusion. We have performed two approximate approaches to solve the problem. One is a two-stage approach which splits the original problem into two sub problems according to the time line. Correspondingly, we have solved the sub problems one by one. The other is a joint algorithm which simultaneously considers the two stages. Our experimental results show that the structure reparation of social networks can largely encourage the influence diffusion. In combination, the joint algorithm performs well enough while the time cost is much less than the other two algorithms in the two-stage approach.
Though we propose the extended problem of the influence maximization problem and give two approximate solutions, there are still many issues not presented in this paper. The datasets have no actual cost information, so we conduct all the experiments with the assumption that the cost to connect one node to another and to incentive the node to be early adopter uniformly equals to 1. While the Amazon’s Mechanical Turk Platform begins to use in real life, the cost can be collected specifically. We will study how the compensation in social networks change the network structure and how the influence diffuses in a self-adaptively dynamic network further.
This work is partly supported by the 973 basic research program of China (Grant No. 2014CB349303), the Natural Science Foundation of China (Grant No. 61472421, No. 61379098), and the National 863 High-Tech R&D Program of China (Grant No. 2012AA012504).