Efficient Approximation Algorithms for Adaptive Seed Minimization
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 155 | |
| Author | ||
| License | CC Attribution 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/43075 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
SIGMOD 2019149 / 155
34
37
44
116
120
122
144
148
155
00:00
Adaptive behaviorData managementMagneto-optical driveAlgorithmApproximationLine (geometry)Computer networkRankingFacebookOnline chatSound effectIndependence (probability theory)Linear mapThresholding (image processing)Endliche ModelltheorieVertex (graph theory)Process (computing)Modul <Datentyp>ApproximationsalgorithmusEstimationMaxima and minimaGraph (mathematics)Duality (mathematics)StapeldateiFeedbackSample (statistics)Product (business)Expected valueCollaborationismEndliche ModelltheorieCASE <Informatik>PolynomialMaxima and minimaFacebookInferenceNumberStapeldateiAlgorithmServer (computing)Structural loadTheory of relativitySet (mathematics)WaveInformationBranch (computer science)Poisson-KlammerBenutzerhandbuchApproximationsalgorithmusDivision (mathematics)Thermodynamisches SystemWage labourSocial classOffice suiteComputational scienceGroup actionData conversionMotion capturePerturbation theoryCategory of beingSynchronizationSystem administratorAverageUtility softwarePropagatorService (economics)Network topologyMereologyStrategy gameSampling (statistics)Level (video gaming)FeedbackRevision controlComputer fileThresholding (image processing)ReliefProcedural programmingProcess (computing)Multiplication signFreewareSurface of revolutionState of matter1 (number)State observerHand fanExpected valueWordTerm (mathematics)2 (number)Sound effectLinearizationIndependence (probability theory)Mobile appStochastic processObservational studyLecture/ConferenceComputer animation
09:04
Software frameworkAdaptive behaviorEstimationErreichbarkeitsmengeReverse engineeringBinary fileVertex (graph theory)Range (statistics)MultiplicationRootGraph (mathematics)Thresholding (image processing)Pairwise comparisonTheoryExtension (kinesiology)StapeldateiKolmogorov complexityPerformance appraisalAlgorithmNumberAbstract syntax treeASCIIDistribution (mathematics)Data modelSample (statistics)Distribution (mathematics)Pattern languageEstimatorSet (mathematics)outputThresholding (image processing)Multiplication signTerm (mathematics)InferenceMachine visionSolitonTable (information)Different (Kate Ryan album)MathematicianResultantStructural loadArmRevision controlMatching (graph theory)PlotterDigital electronicsAdditionTheorySystem callNumerical analysisLimit (category theory)Social classWeightSelectivity (electronic)FeedbackRootMereologySoftware frameworkPhysical lawFigurate numberVertex (graph theory)Direction (geometry)Saddle pointAlgorithmState observerStapeldateiPairwise comparisonMaxima and minimaNetwork topologyField (computer science)Theory of relativityNumberProof theoryProcedural programmingCASE <Informatik>PropagatorBranch (computer science)Form (programming)Observational studyKey (cryptography)Reverse engineeringGraph (mathematics)Sampling (statistics)GradientComputer animation
Transcript: English(auto-generated)
00:02
I'm Qing Tang from the National University of Singapore, so our collaborators are also from the Nanyang Technological University and the University of British Columbia. So I believe you guys are quite familiar with these social network apps.
00:21
I believe every day you use the social network apps. So according to the statistics, just on Facebook, there are more than two billion users. So due to such kind of huge amount of social network users, we can do a lot of things. The thing today I want to talk about is viral marketing.
00:44
So what is viral marketing? It leverages the word of mouth effects among social network users. For example, suppose you are one of the social network user, you are on Facebook, you saw several status from your fans say, okay, SIGMOD is the best conference in computer science.
01:06
So what we do, probably you are influenced by these guys, say, okay, SIGMOD is the best. Then post the similar status on your Facebook, Twitter, whatever. Then you will continuous influence your labels, your fans on Facebook, Twitter, and whatever.
01:28
So this is the viral marketing in social networks. And there are two commonly used models to describe the information diffusion through social networks, including the independent cascade linear threshold models.
01:42
So based on these models, we define the influence spread as the expected number of users influenced by the city users. Note that the influence diffusion is a stochastic process. And there are two important properties for influence spread.
02:04
The first one says sub-module. It captures the diminishing returns in economics. So this property is very good. This says we can design approximation algorithms for the related problem.
02:20
However, the second property is rather bad. It says we cannot compute the influence spread in polynomial time. So we can only estimate the influence spread using some sampling techniques or some other techniques to estimate the influence spread. Based on the influence spread, in this work, we study the city minimization problem
02:46
that we want to find the minimum number of nodes to influence required number of users in social networks. So this problem is the dual problem of the influence minimization, very classical one.
03:02
And the conventionally, the city minimization algorithms look at the long-adapted setting. That is, these algorithms, they select the city nodes in one batch. They do not use any knowledge, any information of the actual propagation of the information
03:22
diffusion. So they just find the solution in one batch. However, we claim that long-adapted is not good enough. For example, suppose we want to influence four people in Facebook.
03:41
However, due to some reasons, we select some city users under certain realizations, possible words. We find that this city set just influence three people. So this is, of course, a case of under-qualified case. And on the other hand, for some other cases, the city users may influence more than four
04:08
people, maybe eight people, much more than the required four people. So this is kind of waste. Maybe we select too much user. Suppose in this case, we select two users.
04:20
Maybe we just need one user is enough so we can save our costs, save our budget by selecting less users. So to address these issues, we consider the city minimization in adaptive setting. That is, we select the load one by one and using the feedback, using the observations
04:46
from previous sitting results. So we stop sitting as long as we observe that, okay, right now there are already a number of ETA users have been activated or influenced.
05:03
So by doing this, we can guarantee that no matter which realization is, we can always influence at least a required number of users ETA. And the second, for some realizations, we can save costs.
05:21
We can stop earlier once we observe that. Okay, the required number of users have reached. So here is a procedure. First, we find the user to sit this guy, maybe give this user a free sample.
05:44
Then we observe who are influenced by this guy in actual propagation. After that, based on these observations, we see the next user. Then we continue observing who will be influenced.
06:02
We repeat this procedure until we find, okay, the required number of users are influenced. So this is a very standard way for adaptive algorithms, right? Now, questions. What's the standard?
06:20
What's the criteria? We decide to select the user based on our observation. Intuitively, we want to maybe select the load to maximize the expected influence spread. It's a very natural way. A lot of researchers, a lot of studies related to influence maximization, they use this
06:43
strategy. However, we claim that this strategy does not work for adaptive CD minimization. The reason is that the influence spread in excess of the threshold has no value. Consider a case. There are two realizations with probability 15 to 15, okay?
07:05
Our target is to influence 20 people. Then there is a guy, Alex, say, okay, I can influence 100 people on one realization and influence another 10 people in another realization.
07:24
So the average is 55, right? Meanwhile, there is another guy, Bob, say, I can influence 30 people on one realization and another 26 in another.
07:40
So which one is better? In terms of expected influence spread, Alex can influence 55 in average and Bob can influence 28 in average. Of course, we should choose Alex, right? However, we find that with probability 50%, Alex fails to influence a required number
08:08
of users, 20. On the second realization with probability 50%, only 10 people are influenced. So this may be not good.
08:21
Based on this observation, we've tried, we think, okay, we need to maximize the truncated influence spread. The truncated influence spread is the small one between the influence spread and the threshold, eta. So in this case, the Alice can only influence the truncated influence spread is 15.
08:45
And for Bob, the truncated influence spread is 20. So now we should choose Bob. Then no matter which realization, realization one or realization two, we don't know which one we are happening actually.
09:01
So but no matter which one is, Bob can always guarantee that at least 20 people are influenced. So of course, Bob is bad. So here is our framework. We first start, select the seed user to maximize the truncated influence spread.
09:27
Then we observe how many people are influenced by the seed user. If enough people are influenced, then stop, finish, quite easy. Otherwise, we update our graph based on the observations, based on the feedbacks.
09:46
Then we select the next seed user to maximize the truncated influence spread. So we just repeat this procedure until the requirement is satisfied.
10:01
Here is the challenge. To our knowledge, there is no research, no work starting the truncated influence maximization. The key challenge is how can we estimate the truncated influence spread? Maybe people may say, okay, can we use the vanilla diverse reachable set to estimate
10:26
the truncated influence spread? And truthfully, we find that it's not okay for truncated influence spread. The other set is inaccurate. So to address this problem, we propose a new sampling method called multi-root reverse
10:46
reachable set, or say MR set. The key difference of MR set and R set is that we randomly select a set of K loads
11:00
as the C and the root loads. Then we generate a realization. Then we find all the loads at least can reach one of the K loads and the MR sets. So we can prove that the MR set can estimate the truncated influence spread accurately.
11:25
Here is how can we generate MR set. Suppose that this is a probabilistic graph with six nodes. And then maybe this is one of the realization of the graph.
11:43
And suppose we want to activate three people. Our target is to influence three users. Then based on our sampling technique, we randomly select two loads. Here, maybe node four and node five.
12:02
And then we identify all the loads can reach any of the node four or node five. So in this case, V1, V3, V4, V5 forms the MR set. For comparison, our MR set generalize the vanilla R set.
12:28
MR set can be used to estimate both the truncated influence spread and the influence spread. We also extend our adaptive algorithms to a batch version.
12:46
That is, we select, in each one, we select a batch of B loads. And if we select more loads in one batch, then we observe the actual propagation of
13:02
the batch of loads. Then the procedure will be faster. However, there is a trade-off. Maybe the results can be less accurate. Through a complicated proof, we show that our algorithms have strong theoretical guarantees
13:24
and they can run in quasi-linear time. Okay, the proof is a little bit complicated, so I just skip it. Interesting, maybe you can leave our papers for the details.
13:40
And to evaluate our proposed methods, we use some real data sets, real-world data sets with up to millions of nodes. And we compare several adaptive algorithms proposed in our paper and against the non-adaptive
14:02
algorithm. The key observation is that the non-adaptive algorithms, the blue sky line with a square marker, it says the non-adaptive algorithm selects much more nodes than our adaptive
14:25
algorithms. Of course, this is because we use the feedback, the non-adaptive algorithm does not use any observation, any knowledge of the feedback. So of course, it performs worse. In particular, we show that in this table, we show that the improvement ratio over the
14:46
non-adaptive algorithm. We can see that the improvement is very significant. In particular, on opinion's data set, the improvement is more than 60%.
15:05
And this table, this figure shows the results of running time by different algorithms. As we claimed, if we select more nodes in one batch, then our algorithms will run faster.
15:23
So the ASTI 2, ASTI 4, ASTI 8 means we select two nodes in one batch, four nodes in one batch, and eight nodes in one batch. And finally, we plot the spread distribution over 20 realizations that have data set
15:47
to verify our conjecture that the non-adaptive algorithm cannot reach the threshold for some realizations and can produce much higher spread than the required in some realizations.
16:07
For example, in this figure, in the left-hand side, we can see that among the 20 realizations, there are four realizations,
16:22
the non-adaptive algorithms cannot reach the threshold. And for another four realizations, the non-adaptive algorithms produce much higher inference grade than the required more than 50%. So this verifies the quantified or over-quantified situation of longer-adaptive algorithm.
16:51
So to summarize, in this work, we propose the first practical algorithms for a W-seeding realization with strong theoretical guarantees.
17:02
Our algorithms are based on truncated inference maximization. So this is the first work to study truncated inference maximization. And we propose a multitude reverse reachable set to estimate the truncated inference spread.
17:21
It generalizes the asset, and our experiment results show that the improvement is significant, even more than 60% for certain data sets. So we also remarked that our algorithms still need several hours to finish on some
17:42
big data sets, like LiveJournal data set. So a future direction on this topic can be to further improve the efficiency of the adaptive algorithms. That's all. Thank you. Thank you.
Recommendations
Series of 8 media