Proceedings of the 1st International Workshop on Social Influence Analysis (SocInf 2015) July 27th, 2015 - Buenos Aires, Argentina Influence Maximization in Human-Intervened Social Networks Qiang You, Weiming Hu, Ou Wu National Laboratory of Pattern Recognition Institute of Automation, Chinese Academy of Sciences Beijing 100190, China Abstract 2003]. Therefore, much work has been conducted to solve the approximate guarantees that add necessary prior constraints Recently there has been tremendous research on in- to the original problem (e.g. [Lappas et al., 2010]). To obtain fluence analysis in social networks: how to find ini- better predictions, a large scale of observable data has been tial topics or users to maximize the word-of-mouth extracted for inferring influence models (e.g. [Bakshy et al., effect that may be significant for advertising, vi- 2011]). The previous studies solve the influence maximiza- ral marketing and other applications. Many re- tion problem using the approximate algorithms of greedily searchers focus on the problem of influence max- selecting adopters based on their marginal contribution to the imization on the static structure of the network and influence, and prove that the results are almost satisfactory find a subset of early adopters which activate the with a factor of (1-1/e-ε) providing that the diffusion func- influence diffusion across the network. Despite the tion is submodular. progress in modeling and techniques, how the in- centives improve the network structure to enlarge The influence diffusion models in previous studies mainly the influence diffusion has been largely overlooked. focus on the situation that the network is static and stabilized. In this paper, we introduce a novel problem which With the addition of the viral marketing and advertising, the extends the influence maximization to the situation social networks are not just a place for human interaction and that the network structure can be varied in case of communication. They increasingly become the main battle- some incentives such as fans trading by compen- field for commercial interests. In fact, the networks are con- sating the web users to be fans in social networks. tinually changing since people make new friends or break up Providing that the presented problem is NP-hard, online all the time spontaneously. The work in [Adiga et al., we propose two approximate approaches to solve 2013] is just this kind of situation which models the changes the problem of influence maximization in dynamic as stochastic changes and discusses the effect of stochastic networks. The first is a two-stage approach which changes in the network on influence maximization problems. separates the problem into two sub problems and However, it is still an open question that what changes in solves them respectively. The second is a joint the network mostly help the influence diffusion. Besides the influence diffusion algorithm so as to repair the spontaneous changes in social networks, there are another network structure and find the corresponding ini- kind of changes which are conducted by human intervention. tial subset of the individuals in the repaired social The practical approaches of human intervention in social net- network simultaneously to maximize the influence. works can be outlined as follows. The advertisers may be We performed experiments on social network data willing to pay to the providers of the social network services to provide evidence of the effectiveness of the pro- for connecting web users so as to enlarge the influence of the posed methods. following social advertising . The celebrities are also will- ing to give small flavors such as concert tickets or their au- tographed posters to earn more fans who are not their fans 1 Introduction before so as to market their following concerts or spread their With the social networks emerging and quickly developing in fame. Furthermore, recent statistical and theoretical studies the past few years, information diffusion has attracted consid- involving perturbation of the network show that changes in erable attention by researchers in different kinds of areas such the network structure largely altering the influence dynamics as social advertising, viral marketing, etc. In the studies of in social networks [Adiga et al., 2013]. With the network information diffusion, a central problem that received much changing with human intervention and the changes alter the attention is the influence maximization problem, which speci- influence dynamics, some novel but urgent problems come fies a small subset of individuals in a social network as seeds up: how the influence diffusion dynamics is altered with the that produce a large word-of-mouth effect in the network. As human intervention and how the intervention is carried out so for influence maximization problem, there has been no per- as to help the influence diffusion across the social networks fect method since it is proved to be NP-hard [Kempe et al., to reach the maximum outcome. 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. 9 Proceedings of the 1st International Workshop on Social Influence Analysis (SocInf 2015) July 27th, 2015 - Buenos Aires, Argentina Figure 1: The schema of influence maximization in human-intervened dynamic networks. In this paper, we research how the changes of the net- also theoretically proved that structural changes such as edge work structure alter the influence diffusion. We show that perturbations are largely impact on the stability of the inde- connecting some edges of the network can largely help the pendent cascades and linear threshold models [Adiga et al., influence diffusion process using linear threshold model or 2013] in sparse networks which almost all online social net- independent cascade model. Then we extend the influence works belong to. maximization problem to human guided dynamic networks which can be locally modified with human intervention. Pro- 3 Preliminaries viding that the proposed influence maximization problem is In the following section, as Figure 1 shows, we simply show NP-hard, we introduce two approximate approaches to solve how the human intervention is conducted to modify the struc- the problem in human-intervened dynamic networks. We pro- ture in social networks, and then, we present how these pose a two-stage approach which first repairs the network and changes impact the influence diffusion dynamics. then chooses the early activated adopters to conduct the influ- ence diffusion process with a given budget until the influence 3.1 Human-Intervened Networks maximization is reached as shown in Figure 1. In another ap- The practical approaches of human intervention in social net- proach, we introduce a joint influence diffusion algorithm to works have described in the introduction section. Generally depict the rise of the incentives, the evolution of the network, speaking, the advertisers and the celebrities are willing to pay and the influence diffusion process with respect to the multi- to enlarge their influence on the web. We assume a social ple stages of the evolution procedure, and then solve the influ- network represented by a graph G(V, E). The nodes V cor- ence maximization in the dynamic networks approximately. responding to posts or users can be viewed as adopters to dif- fuse the influence sequentially. There is an edge e ∈ E be- 2 Related Work tween two adopters u, v ∈ V if u has a relation with v. With Given the urgent need of viral marketing, the influence max- the human intervention that the advertisers and the celebrities imization problem has attracted many researchers’ attention are willing to connecting web users, we discuss the human- since it was first released in [Domingos and Richardson, intervened network with connecting node pairs as the new 2001]. The initial researches (e.g. [Kempe et al., 2003], adding edges of the repaired network. [Kempe et al., 2005]) study two basic influence diffusion models in terms of computational approximability and show 3.2 Influence Diffusion in Repaired Networks that the influence maximization problem is NP-hard. They The two basic diffusion models popularly used in previous introduce the approximate algorithms of greedily selecting studies are the linear threshold (LT) model and the indepen- adopters based on their marginal contribution to the influence, dent cascades (IC) model.P In the LT model, a node v is ac- and prove that the results are almost satisfactory with a factor tivated at time step t if u∈Nt (v) wu,v ≥ θv ∈ [0, 1], where of (1-1/e-ε) providing that the object function is submodular. Nt (v) denotes the neighbors of v that are active at time step t, The above studies are all in the same framework that find- wu,v ≥ 0 is a influence weight that the neighbor u imposes on ing submodular influence diffusion models to approximately the node v, and θv a threshold uniformly chosen at random. solve the NP-hard Max-k-Coverage problem [Singer, 2012] While in the IC model, each node v is independently influ- in a whole static network. However, as we have mentioned enced by each neighbor u with some probability pu,v . When in the introduction section, the whole network can be locally the node u is activated at time step t, it has a single chance modified by some incentives conducted by the human inter- to activate each neighbor v with probability pu,v . Besides the vention. two basic models, there is another influence diffusion model, Some researchers begin to study how the network struc- the voter model. Unlike the two basic models where the node tural changes impact on the influence diffusion. As the lit- is always stay active once it is activated, in the voter model, at erature [Lahiri et al., 2008] empirically shows, in real dy- every time step t, the node v always has chance to be activated namic networks the predictions about the relative spreading or deactivated by its neighbors. capacity of individuals and the identity of the top spreaders Assume that we connect k node pairs with respect to the are sensitive even to minimal changes in the network. It is original network with human intervention, how much the 10 Proceedings of the 1st International Workshop on Social Influence Analysis (SocInf 2015) July 27th, 2015 - Buenos Aires, Argentina centrality is maximally changed? We assume the node v is that shows how close one node to all the remaining nodes in the chosen node. The degree centrality of node v could be the graph. We calculate the average distance (the shortest changed from D to D + O(k) if we connect node v with path) Davg of a node vi to the other nodes. The closeness other nodes ai that can be all active at step t. In the next centrality of node vi is defined as Cc (vi ) = Davg1 (vi ) . step t + 1, as for LT, the probability to activate the node v Pk w increases O( i=1 θavi ,v ); while for IC, the probability in- Problem 2 Let B1 be a reparation budget, U the edge set to Pk repair. The network reparation problem is to find the edge creases O( i=1 pai ,v ). Assume that the diameter of part of set S which will the original graph is di and the centroid is Ci . After we con- P maximize the total closeness centrality of all the nodes vi ∈V Cc (vi ) subject to the budget constraint nect node v and Ci , the average distance between the node P e∈S me ≤ B1 . v and part of the original graph becomes quite smaller than before. Thus, the closeness centrality becomes larger, and The Greedy Algorithm the influence starting from the node v can be more quickly to The network reparation problem can be solved by a greedy diffuse to the other nodes. algorithm as follows. 4 The Problem Algorithm 1 The Greedy Algorithm (GA) We assume a social network represented by a graph G(V, E). Input: The edge set U to repair, B1 the reparation budget Given a limited budget B, assume that by compensating the Output: Edge set S two influencers u, v connected together, the cost should be at 1: S := ∅ least cs(u, v). To choose the node v as a early adopter to dif- 2: Br := B1 . the remaining budget fuse the influence, the cost should be at least cs(v). A node at 3: Ur := U . the remaining candidate set each time can only be in one of two state: active or inactive. 4: while Br ≥ 0 and Ur 6= ∅ do We define a state function fi (v) ∈ {1, 0} to show whether the 5: for e ∈ Ur do node is active or not at time step i. Given a target time t, we 6: E ←E∪e want to maximize the influence across the whole graph under 7: G ← G(V, E) . The repaired graph the constraint of budget B. We extends the influence max- 8: . maximize P the closeness centrality of repaired graph imization problem to human-intervened dynamic networks. 9: if vi ∈V Cc (vi ) is maximized then The extended problem can be formalized as follows. 10: Br ← Br − me Problem 1 (Influence Maximization Problem in a Human- 11: Ur ← Ur \e Intervened Dynamic Network) Let G be a graph represent- 12: S ←S∪e 13: end if ing a social network, M ∈ R|V |×|V | a matrix of costs in- 14: end for dicating the cost me = cs(u, v) of connecting u and v to- 15: end while gether, CS ∈ R|V | 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 As for closeness centrality, the time complexity to cal- the edge set S ⊆ E that should be repaired and then find culate all the geodesic distance of the node pairs is O(|V |2 lg |V | + |V ||E|) using the shortest path algorithm im- an assignmentPf0 : V → {0, 1} that will maximize the ex- plementing the minimum priority queue through Fibonacci pectation E P v∈V ft (v) subject to the budget constraint P heap. Thus the time complexity to the greedy algorithm is e∈S m e + v:f0 (v)=1 csv ≤ B. O(l|S|(|V |2 lg |V | + |V ||E|)), where l is the time of itera- As the extended problem is NP-hard, we introduce two tions and S ⊆ U the final edges to repair. approximate solutions. One is a simple two-stage approach which solves the problem with the assumption that the prob- The Centriods Connecting Algorithm lem can be separated into two sub problems. The other intro- The greedy algorithm seems significantly time-consuming. duces a joint influence diffusion algorithm and combines the Inspired by decreasing the geodesic distance between node two stages together. pairs, we perform clustering algorithm on the whole graph and find two centroids, and then we connect the two cen- troids. We repeat the procedure until reaching the budget. 5 The Basic Approach The shortest paths between all the node pairs decrease in ev- The graph can be dynamically changed if we repair it by con- ery iteration, and the responding closeness centrality becomes necting edges, and then the influence diffusion process should larger. be deployed on the repaired network. The procedure of Prob- The graph clustering problem is depicted as follows. Given lem 1 is conducted in two stages according to the time line. the graph weight W with its element wuv representing the So the solution is also separated into two stages. weight between node u and v and the cluster number K, our task is to separate the nodes V into K clusters with nodes 5.1 The Network Reparation in a cluster closely connecting together and nodes in differ- To make the influence diffuse more quickly and widely, the ent clusters should be far away from each other. It can be whole network should be tight, which means the nodes should solved by the iterative algorithm that randomly chooses the be close to each other. Closeness centrality is just an indicator k centroids then repeats it again to renew the centroids or 11 Proceedings of the 1st International Workshop on Social Influence Analysis (SocInf 2015) July 27th, 2015 - Buenos Aires, Argentina the spectral clustering algorithms. More detail of the spectral early adopters. To maximize all the influence diffusion from clustering can be found in [Von Luxburg, 2007]. We follow the other nodes, the early adopters should be close to all the the fast approximate spectral clustering with k-means in [Yan other nodes. et al., 2009] which shows that the time complexity largely Referred to the centroids connecting algorithm (CCA), we decreases from O(|V |3 ) to O(K 3 + Kl|V |) where l is the design a joint influence diffusion algorithm both considering number of iterations in k-means . In our centroids connecting the network reparation and the influence diffusion process. algorithm, we set K = 2 to carefully choose one edge that First, we choose two early adopters u, v to be activated to should be connected with two centroids at a time. The time maximize the influence diffusion in initial graph given the complexity of the algorithm is O(l|S||V |). target time t. We perform clustering algorithm and get two clusters. There are two conditions to consider: (1) if u, v Algorithm 2 The Centriods Connecting Algorithm (CCA) are in one cluster, then we choose the node far from its cen- Input: The edge set U to repair, B1 the reparation budget troid to connect to the other centroid; (2) if u, v are in differ- Output: Edge set S ent clusters, then we choose both the nodes to connect to the 1: S := ∅ other centroid. Second, we maximize the influence diffusion 2: Br := B1 , Ur := U in repaired network and choose two early adopters again. We 3: while Br ≥ 0 and Ur 6= ∅ do perform clustering algorithm again. We repeat the procedure 4: Finding two centroids c1 , c2 by clustering graph G several times until we run out of the entire budget. 5: if e := (c1 , c2 ) ∈ Ur then 6: E ← E ∪ e, G ← G(V, E) . The repaired graph Algorithm 3 The Joint Algorithm 7: Br ← Br − me , Ur ← Ur \e, S ← S ∪ e 8: end if Input: The edge set U to repair, B1 the reparation budget 9: end while Output: Edge set S to connect, early node set N to activate 1: S := ∅, N := ∅ 2: Br := B1 , Ur := U 5.2 The Influence Diffusion Process 3: while Br ≥ 0 and Ur 6= ∅ do 4: Finding two centroids c1 , c2 by clustering graph G After the network reparation, we conduct the influence dif- into C1 , C2 fusion process across the repaired network given the leftover 5: Choosing u, v as early adopters to maximize the in- budget B2 = B − B1 . fluence We know that we should not give the entire budget to the 6: if u, v ∈ C1 then first stage, because the influence diffusion should be started 7: if ShortestPath(u, c1 )>ShortestPath(v, c1 ) then anyway. We repair the edges one by one until the expected 8: if e := (u, c2 ) ∈ / Ur then influence of the graph (the total number of nodes activated) at 9: Choose node cm with the largest degree target time step t does not increase any more. and The basic approach is easy to think about associated with 10: e ← (u, cm ) ∈ Ur the two stages of the problem. However, the influence dif- 11: end if fusion process is not adaptively adjusted with the dynamic 12: E ← E ∪ e, G ← G(V, E) network. The other approximate approach will focus on the 13: Br ← Br − me − cv , Ur ← Ur \e self-adaptive influence diffusion process. 14: S ← S ∪ e, N ← N ∪ v 15: end if 6 The Joint Algorithm 16: end if Unlike the basic approach separating the influence maximiza- 17: The same to the other conditions ... tion problem in dynamic networks into two stages and solv- 18: end while ing the corresponding problems independently, the network reparation and the influence diffusion process are simultane- ously conducted in this model. Apparently, the influence dif- fusion process is the main task that it directly determines how much influence of the graph reaches at the target time. Thus, 7 Experimental Results we design a joint influence diffusion algorithm to adaptively choose the edges to repair to maximize the influence of the We conducted a variety of experiments to evaluate the per- whole network. formance of the presented algorithms with respect to the two A node v in a graph can influence its neighbors in the LT or basic influence diffusion models in social networks. In LT IC model. Given that the network can be repaired with a cost, model, for each of the node v’s neighbors u, the influence the other nodes can also be influenced by v if we connect v weight wu,v = d−1 v , where dv was drawn independently at and the other nodes together. As for v, given the neighbor random from an estimated degree distribution of the social node set N and the other node set F , how can we choose graph. While in IC model, the probability of the single chance the node u ∈ F to connect with v to maximize the influence to activate its neighbors was 1% uniformly set. We first con- diffusion from v? The answer is that v should be influenced cisely introduce the experimental setup and then present the as quickly as possible, that is, v should directly connect to the results of the evaluation. 12 Proceedings of the 1st International Workshop on Social Influence Analysis (SocInf 2015) July 27th, 2015 - Buenos Aires, Argentina 7.1 Experimental Setup soc-Epinions1 in LT model soc-Epinions1 in IC model Joint Joint 3000 6000 We download two online social networks from SNAP1 , soc- CCA GA CCA GA Epinions1 and soc-Slashdot0922. The experiments were con- 2500 Static Random 5000 Static Random ducted on a 2.67GHz 4-core i5 machine with 4GB RAM, run- 2000 4000 Influence Influence ning the Windows 7 operating system. The algorithms were 1500 3000 mainly implemented in C++. 1000 2000 500 1000 Table 1: The basic statistics of the data sets 0 0 Data set soc-Epinions1 soc-Slashdot0922 0 20 40 Budget 60 80 100 0 20 40 Budget 60 80 100 #Nodes 75879 82168 #Edges 508837 948464 Figure 2: soc-Epinions influence vs. budget Avg. cluster coeff. 0.1378 0.0603 Diameter 14 11 soc-Epinions1 in LT model soc-Epinions1 in IC model 6000 8000 Joint Joint CCA 7000 CCA 5000 GA GA 6000 7.2 Results 4000 Static Random Static Random 5000 Influence Influence In this subsection, first we study how the budget B1 which 3000 4000 is used in network reparation imposes on the influence diffu- 2000 3000 sion, and then we conduct two experiments to compare differ- 2000 ent algorithms with respect to the influence according to two 1000 1000 important hyper parameters: the budget and the target time. 0 0 5 10 15 20 0 0 5 10 15 20 After that, we compare the time complexity of the three al- Target Time Target Time gorithms which solve our maximization problem in dynamic Figure 3: soc-Epinions influence vs. target time networks. Influence Diffusion w.r.t the Reparation Budget Compare Influence vs. Target Time The reparation budget B1 is a very important factor we con- In the previous experiment, we fix the target time while cerned in our framework. Our heuristic method is simple just changing the budget. Now we fix the total budget to 50, and as follows. We increasingly set the reparation budget up un- get the influence diffusion vs. target time from 0 to 20. From til the maximum influence is arrived given the target time t the experimental result as shown in Figure 3, the influence and the total budget B. Providing the cost to repair the net- diffusion quickly increases as the target time becomes larger. work and activate the initial adopters is missing, we stipulate When the target time exceeds a threshold, the influence in- that every cost is 1 uniformly. Now the total budget becomes creases slowly. It can be explained that the in a social network the sum of the number of the edges to repair and the number there are only several seeds to conduct the influence diffusion of the initial nodes to activate, where the reparation budget process. Once the neighbors are activated, they further acti- equals to the number of edges to repair. As shown in Table 2, vate their neighbors. Gradually, the world-of-mouth effect is when B1 = B/10, the number of nodes to be activated is the formed. When almost all the nodes could be activated is acti- largest. In the following experiments, we choose B1 = B/10 vated, the influence diffusion goes to the period of stagnation. uniformly. We also conduct the experiments on the soc-Slashdot0922 Compare Influence vs. Total Budget which leads to similar conclusion as we get above with the Let the target time t be fixed, we get the influence diffusion soc-Epinions1 dataset. Due to space constraints we do not vs. budget from 10 to 100. We compare the influence vs present the similar results in this paper. budget with respect to the greedy algorithm (GA), the centri- Compare Time Complexity ods connecting algorithm (CCA), the joint algorithm (Joint), In this paper, we introduce two approaches and three algo- the influence diffusion on the static network (Static) and the rithms to approximately solve the influence maximization in random algorithm as baseline. As shown in Figure 2, we find dynamic networks. Next, we simply compare the time com- that it performed nearly the same trend based on the two basic plexity of each algorithm on the two datasets. As shown in influence diffusion models LT and IC. Throughout the exper- Table 3, though the joint algorithm does not perform the best iment, we find that the formal three algorithms achieved very according to the experimental results listed above. It beats close result, which largely outperformed the static method the other two in terms of running time. In summary, the joint that does not repair the network. Generally speaking, the per- algorithm consumes much less time while the performance formance rank of formal three algorithms in soc-Epinions is does not decrease fiercely. GA ≈ CCA > Joint, respectively. While the performance difference between the joint algorithm and the other two al- gorithms is really small. 8 Conclusions and Future Work In this paper, we have studied the influence maximization 1 http://snap.stanford.edu/data/index.html problem in dynamic networks which can be changed with hu- 13 Proceedings of the 1st International Workshop on Social Influence Analysis (SocInf 2015) July 27th, 2015 - Buenos Aires, Argentina Table 2: The ratio (%) of nodes activated by early adopters given the reparation budget B1 where B = 50 and t = 10 Data set soc-Epinions1 soc-Slashdot0922 Algorithm GA CCA Joint GA CCA Joint Diffusion Model LT IC LT IC LT IC LT IC LT IC LT IC B1 = 0 (No reparation) 2.493 4.301 2.493 4.301 2.493 4.301 3.154 4.459 3.154 4.459 3.154 4.459 B1 = 2 2.948 4.960 2.875 4.812 2.692 4.623 3.630 5.083 3.524 4.984 3.444 4.774 B1 = 5 3.334 6.095 3.252 6.017 3.011 5.792 4.049 6.002 3.979 5.941 3.654 5.734 B1 = 10 3.148 5.494 2.812 5.366 2.817 5.174 3.178 4.823 3.088 4.656 2.845 4.415 B1 = 20 2.510 4.375 2.419 4.202 2.244 4.101 2.975 4.050 2.939 3.952 2.592 3.777 B1 = 40 1.125 2.975 1.096 2.952 1.010 2.655 1.287 3.003 1.245 2.727 1.134 2.429 [Bakshy et al., 2011] E. Bakshy, J.M. Hofman, W.A. Mason, Table 3: The running time for three algorithms and D.J. Watts. Everyone’s an influencer: quantifying in- Data set soc-Epinions1 soc-Slashdot0922 fluence on twitter. In Proceedings of the fourth ACM inter- Algorithm GA CCA Joint GA CCA Joint national conference on Web search and data mining, pages Time(min) 546 138 25 683 220 48 65–74, 2011. [Domingos and Richardson, 2001] P. Domingos and man intervention. Given a limited budget and a target time, M. Richardson. Mining the network value of customers. we can both repair the network structure and choose early In Proceedings of the seventh ACM SIGKDD international adopters to maximize the influence diffusion. We have per- conference on Knowledge discovery and data mining, formed two approximate approaches to solve the problem. pages 57–66, 2001. One is a two-stage approach which splits the original prob- [Kempe et al., 2003] D. Kempe, J. Kleinberg, and É. Tardos. lem into two sub problems according to the time line. Corre- Maximizing the spread of influence through a social net- spondingly, we have solved the sub problems one by one. The work. In Proceedings of the ninth ACM SIGKDD interna- other is a joint algorithm which simultaneously considers the tional conference on Knowledge discovery and data min- two stages. Our experimental results show that the structure ing, pages 137–146, 2003. reparation of social networks can largely encourage the influ- ence diffusion. In combination, the joint algorithm performs [Kempe et al., 2005] David Kempe, Jon Kleinberg, and Éva well enough while the time cost is much less than the other Tardos. Influential nodes in a diffusion model for social two algorithms in the two-stage approach. networks. In ICALP, 2005. Though we propose the extended problem of the influence [Lahiri et al., 2008] Mayank Lahiri, Arun S Maiya, Raj- maximization problem and give two approximate solutions, monda Sulo, Tanya Y Berger Wolf, et al. The impact of there are still many issues not presented in this paper. The structural changes on predictions of diffusion in networks. datasets have no actual cost information, so we conduct all the In IEEE International Conference on Data Mining Work- experiments with the assumption that the cost to connect one shops, 2008. ICDMW’08, pages 939–948, 2008. node to another and to incentive the node to be early adopter [Lappas et al., 2010] T. Lappas, E. Terzi, D. Gunopulos, and uniformly equals to 1. While the Amazon’s Mechanical Turk H. Mannila. Finding effectors in social networks. In Platform begins to use in real life, the cost can be collected Proceedings of the 16th ACM SIGKDD international con- specifically. We will study how the compensation in social ference on Knowledge discovery and data mining, pages networks change the network structure and how the influence 1059–1068, 2010. diffuses in a self-adaptively dynamic network further. [Singer, 2012] Y. Singer. How to win friends and influence people, truthfully: influence maximization mechanisms Acknowledgments for social networks. In Proceedings of the fifth ACM inter- This work is partly supported by the 973 basic research pro- national conference on Web search and data mining, pages gram of China (Grant No. 2014CB349303), the Natural 733–742, 2012. Science Foundation of China (Grant No. 61472421, No. [Von Luxburg, 2007] Ulrike Von Luxburg. A tutorial on 61379098), and the National 863 High-Tech R&D Program spectral clustering. Statistics and computing, 17(4):395– of China (Grant No. 2012AA012504). 416, 2007. [Yan et al., 2009] Donghui Yan, Ling Huang, and Michael I References Jordan. Fast approximate spectral clustering. In Proceed- [Adiga et al., 2013] Abhijin Adiga, Chris Kuhlman, Hen- ings of the 15th ACM SIGKDD international conference ning S Mortveit, and Anil Kumar S Vullikanti. Sensitivity on Knowledge discovery and data mining, pages 907–916, of diffusion dynamics to network uncertainty. In Twenty- 2009. Seventh AAAI Conference on Artificial Intelligence, pages 2–8, 2013. 14