=Paper=
{{Paper
|id=Vol-1398/SocInf2015_Paper2
|storemode=property
|title=Influence Maximization in Human-Intervened Social Networks
|pdfUrl=https://ceur-ws.org/Vol-1398/SocInf2015_Paper2.pdf
|volume=Vol-1398
|dblpUrl=https://dblp.org/rec/conf/ijcai/YouHW15
}}
==Influence Maximization in Human-Intervened Social Networks==
https://ceur-ws.org/Vol-1398/SocInf2015_Paper2.pdf
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