Evaluating Robustness of Influence Maximization in Presence of Edge Uncertainty
Explore the robustness of influence maximization against edge uncertainty, encompassing discrete and continuous cases, diffusion models, algorithms, and experiments. Edge uncertainty scenarios, algorithmic complexities, submodularity issues, and Greedy Algorithm's role in addressing uncertainties are discussed.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Evaluate the Robustness of Influence Maximization Against Edge Uncertainty 2020 05 25
C O N T E N T Background and Overview Discrete Case: Greedy 01 02 Continuous Case: SGD Experiments 03 04
1 Background and Overview
Influence Maximization Independent Cascade (IC) ?1,?3 try probability ?1,?3independently Linear Thresholds (LT) ?is activated iff ?1+ ?3exceeds a random threshold ?? Diffusion Models Independent Cascade (IC) Linear Thresholds (LT, DLT) to activate with ? Greedy Algorithm repeatedly add an element that gives the maximum marginal gain ?1 ?2 ?1 ? ?2 Submodularity ? ? ? ? ? ?3 ? ? ? 1 1/? Approximation ? ? ?3
Edge Uncertainty Missing Edges (Discrete) Wrong Edge Values (Continuous) Two users register an edge (e.g. friendship relation) in the system, but do not contact each other. Edge value of the real social network is assumed to follow Gaussian distribution, with expectation as the estimated value.
Algorithms Discrete Case Discrete Case: Greedy Algorithm NP-hard under DLT and IC Inapproximable under IC Submodular submodular under DLT and IC under LT, non- Continuous Case: Stochastic Gradient Descent Continuous Case SGD-like algorithm for optimization Experiments: Algorithm Implementation E x p e r i m e n t s Both algorithms are implemented, and the result validates the theorems.
2 Discrete Case: Greedy
NP-hardness Reduction from maximum union/intersection set Maximum union/intersection set Subsets S = {?1, ,??} of ? = {?1, ,??} Picking ? subsets from S, maximize the union/intersection set size ?1 ?1 ?1 ?2 ?2 ?2 Reduced robustness evaluation problem Seeds: Edge probability/weight: ?? ?? ?? DLT: union, IC: intersection ?1 ?? ?? ?? ?? :1 ??:1 ?? , 1/????? (???)
Greedy Algorithm and Submodularity ?1 Greedy Algorithm Repeatedly pick the edge that maximize the number of deactivated nodes ? Objective functions under DLT and IC are not submodular Seeds: ?1,?2 IC: edge probability = 1 DLT: edge weight = 0.5, threshold of ? is 0.1 Only when both edges are removed, ? is deactivated ?2
Greedy Algorithm and Submodularity Objective function under LT is submodular At most one path to ?4in the live-edge graph Prove Submodularity case by case ?1 ?1 ?2 ?2 ?3 ?4 ? ? ? ? ?2 ?3 ?2 ?3 ?2 ?3 ? ? ? ? ? ?1 ?1 ?2 ?1 ?1 ?2 ?1 ?1 ?2 ? ? ? ? ?2 ?3 ?2 ?3 ?2 ?3 ? ? ? ? ? ?1 ?1 ?2 ?1 ?1 ?2 ?1 ?1 ?2
3 Continuous Case: SGD
Regularization Term and SGD Algorithm Objective function minimize ????????? ??????????? subject to ? ? 2 ? 2 minimize ????????? ??????????? + ? ? ? 2 Stochastic gradient descent Gradient descent on the objective Compute gradient via simulation (introduce randomness)
4 Experiments
Greedy Algorithm Baseline: select edge with the largest probability/weight
Greedy Algorithm More simulations contribute to better performance
SGD SGD with Larger ? converges to larger influence expectation Reasonable because ? represents the accuracy of estimated edge values.
SGD We should ensure enough simulations to make the SGD process stable. SGD also works well under IC model.
Contributions and Future Work Discrete Case Continuous Case SGD Algorithm Future Work NP-hardness of LT Algorithms under IC/DLT with theoretical performance guarantee Robust IM against edge uncertainty
T h a n k s
