PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Influence Maximization in Dynamic Social Networks

Guangmo Tong, Weili Wu, Shaojie Tang, Ding-Zhu Du

arXiv:1506.06294v1cs.SI

TL;DR

Influence maximization methods often assume static social networks despite uncertain activation, propagation, and topology. This paper introduces the Dynamic Independent Cascade model and adaptive seeding strategies, showing that adaptive methods outperform standard strategies while offering a greedy guarantee and a practical heuristic.

  • Problem

    Existing influence-maximization strategies are limited by static-network assumptions, although real-world diffusion involves uncertain activation, propagation, and changing topology.

  • Method

    The paper models dynamic uncertain diffusion with the DIC model and designs adaptive seeding through an optimal pattern, a greedy strategy, and a heuristic candidate-selection strategy.

  • Results

    Adaptive seeding outperforms Greedy across the tested settings, including 125% improvement on Hep under classic IC and 320% under greater diffusion uncertainty.

  • Takeaways & Limitations

    Adaptive seeding can exploit outcomes from past rounds and provides an effective approach for influence maximization in dynamic social networks.

  • Takeaways & Limitations

    H-Greedy is not effective for all DIC settings, motivating better heuristics for general social networks.

Abstract

from arXiv · show

For the purpose of propagating information and ideas through a social network, a seeding strategy aims to find a small set of seed users that are able to maximize the spread of the influence, which is termed as influence maximization problem. Despite a large number of works have studied this problem, the existing seeding strategies are limited to the static social networks. In fact, due to the high speed data transmission and the large population of participants, the diffusion processes in real-world social networks have many aspects of uncertainness. Unfortunately, as shown in the experiments, in such cases the state-of-art seeding strategies are pessimistic as they fails to trace the dynamic changes in a social network. In this paper, we study the strategies selecting seed users in an adaptive manner. We first formally model the Dynamic Independent Cascade model and introduce the concept of adaptive seeding strategy. Then based on the proposed model, we show that a simple greedy adaptive seeding strategy finds an effective solution with a provable performance guarantee. Besides the greedy algorithm an efficient heuristic algorithm is provided in order to meet practical requirements. Extensive experiments have been performed on both the real-world networks and synthetic power-law networks. The results herein demonstrate the superiority of the adaptive seeding strategies to other standard methods.

1 INTRODUCTION

Influence maximization seeks a limited set of seed users that maximizes information spread, but existing strategies mainly assume static networks. This paper addresses uncertain, dynamic diffusion through adaptive seeding strategies with theoretical and empirical evaluation.

  • Motivation: Influence maximization selects a limited set of seed users to maximize the number of eventual adopters or active nodes.The motivating example is product advertising with a fixed budget of free samples.
  • Motivation: Real-world diffusion is uncertain because seed activation, information transmission, and network topology can all vary.The paper specifically identifies probabilistic activation and propagation alongside changing social ties.
  • Research gap: Existing seeding approaches choose seed users statically before diffusion, making them inapplicable to the Dynamic Independent Cascade model.The DIC setting may require reseeding users who were not successfully activated.
  • Contributions: The paper proposes the DIC model, formalizes adaptive seeding through seeding patterns, and develops adaptive greedy and heuristic strategies.The contributions include a provable adaptive hill-climbing strategy and candidate-set narrowing for efficiency.
  • Evaluation: Experiments compare the proposed adaptive strategies with standard methods on real-world and synthetic power-law networks.The paper reports superiority of adaptive strategies in dynamic social networks.

2 PROBLEM SETTING

The paper models influence diffusion on a directed social graph with uncertain seed activation and propagation, then defines adaptive seeding patterns and strategies under a finite budget. Its setting permits decisions to depend on observed diffusion outcomes.

  • 2.1 DIC Model: A social network is represented as a directed graph whose nodes are individuals and whose edges are social ties.Nodes can become active through neighboring users or direct seeding.
  • 2.1 DIC Model: In the DIC model, seed activation follows node-specific Bernoulli variables, while edge propagation probabilities are random variables revealed during diffusion.Propagation proceeds round by round, and the model allows distributions to vary across nodes and edges.
  • 2.1 DIC Model: The model includes node and edge distributions, an activation budget B ≤ N, and unrevealed edge probabilities until relevant activation occurs.An instance is denoted G = (V, E, F_V, F_E).
  • 2.2 Adaptive Seeding Strategy: A seeding pattern A = (a_1, ..., a_N) specifies how many nodes are seeded at each step, with total seeding constrained by Σa_i ≤ B.A corresponding strategy selects node-sets s_i with |s_i| = a_i; zero entries mean no seeding at that step.
  • 2.2 Adaptive Seeding Strategy: Both seeding patterns and selected node-sets may depend on outcomes from previous diffusion rounds.The objective is the expected final number of active nodes after diffusion ends and the budget is exhausted.
  • 2.2 Adaptive Seeding Strategy: Pattern A0 seeds one node per step until the budget is exhausted, whereas A* waits for diffusion to stop before constructing the next seeding step.The paper identifies A* as optimal because it maximizes information obtained before later seeding decisions.
  • 2.2 Adaptive Seeding Strategy: Adaptive Influence Maximization asks for a pattern and corresponding strategy that maximize expected active nodes under the budget constraint.The framework compares strategies for a given DIC network G.
  • 2.3 An Example: In the example DIC network, seed activation probability is 0.5, edge propagation takes values 0.4 or 0.8, and the budget is three.A strategy may seed the same node again after an unsuccessful activation.

3 GREEDY ALGORITHM

The greedy algorithm selects seeds adaptively using observed diffusion events, supported by an auxiliary-graph transformation that represents repeated seeding and realizations. The resulting strategy uses the optimal pattern A∗ and achieves a (1 − 1/e)-approximation for influence maximization.

  • Greedy rule: The greedy rule selects, at each seeding step, the node maximizing marginal profit conditioned on observed events.The observations include outcomes of past rounds and propagation probabilities between active nodes and their neighbors.
  • Transformation: The DIC network is transformed into an auxiliary graph with node layers for multiple seedings and edges encoding seed activation and propagation-probability states.The construction partitions auxiliary nodes into V0 and Vi layers, with E1c and E2c representing different relationships.
  • Realizations: Full realizations specify determinate edge states, while partial realizations represent intermediate diffusion states with undetermined outcomes.Compatibility defines which full realizations can follow a partial realization, enabling the diffusion process to be represented incrementally.
  • Transformation: The auxiliary construction maps active nodes under a seeding strategy to nodes reachable through live edges, preserving the active-node count of the original network.This correspondence supports expressing expected influence through realizations and the transformed graph.
  • Optimal pattern: Pattern A∗ is optimal because it maximizes information obtained before subsequent seeding decisions and thereby provides more seed-selection options.The paper states this optimality for any DIC network and arbitrary competing pattern.
  • Approximation ratio: The greedy strategy under A∗ is an (1 − 1/e)-approximation of the influence maximization problem.The strategy is within a factor 1 − 1/e of the optimal strategy for pattern A∗, and A∗ is optimal among patterns.

4 HEURISTIC SEEDING STRATEGY

H-Greedy accelerates adaptive seeding by narrowing the candidate seed set before selection, using Monte Carlo estimates and a power-law-inspired threshold.

  • Heuristic design: H-Greedy narrows the candidate seed set before adaptive seeding to reduce computation while preserving influential-node candidates.The approach is motivated by the observed strength gap between influential and other nodes and the power-law structure of real-world networks.
  • Heuristic design: Before seeding, H-Greedy estimates E[H(v)], E[Std[H(v)]], and E[P_v∈V H(v)/N] using Monte Carlo simulation.These estimates characterize single-seed influence and its variation across nodes.
  • Candidate filtering: During seeding, H-Greedy omits node v when E[H(v)] falls below the lower 1-sigma control of the average single-seed influence.The filtering rule is applied while determining each seed node.
  • Efficiency: 1000 to 2000 simulations suffice for candidate narrowing, compared with 10000 to 20000 simulations previously used for accurate estimation.The estimates need only be accurate enough to reduce the candidate set, and the resulting seeding time can be reduced substantially.

5 EXPERIMENT

Experiments compare adaptive and non-adaptive seeding strategies across real-world and synthetic networks under varied propagation and activation settings. A-Greedy consistently outperforms Greedy, while H-Greedy achieves similar performance with reduced candidate evaluation.

  • Experiment Setup: Experiments use Hep and Wiki real-world networks plus a synthetic power-law network, with three propagation-probability distributions and two activation probabilities.The datasets range from about 2,500 to 15,000 nodes, and activation probabilities are 1 and 0.5.
  • Adaptive Seeding Performance: A-Greedy outperforms Greedy under all tested circumstances, including both the classic IC model and the more uncertain DIC model.The adaptive strategy uses outcomes from past rounds, whereas Greedy selects seeds before diffusion.
  • Adaptive Seeding Performance: 125%: A-Greedy’s improvement over Greedy on Hep under the classic IC model with F 1 and Prob[Xu = 1] = 1.Under increased uncertainty, the corresponding Hep improvement rises to 320% when Prob[Xu = 1] = 0.5.
  • Adaptive Seeding Performance: 320%: A-Greedy’s improvement over Greedy on Hep under F 1 when Prob[Xu = 1] = 0.5.For PL under F 1 with Prob[Xu = 1] = 0.5, one seed activates about 2.5 nodes with A-Greedy versus 1.67 with Greedy.
  • Adaptive Seeding Performance: Greedy curves become less stable in the DIC model, so matching A-Greedy’s estimation accuracy requires more simulations.This reflects the greater uncertainty in the diffusion process under DIC.
  • Heuristic Seeding Performance: H-Greedy uses E[H(v)] to narrow the candidate set, and its performance is almost the same as A-Greedy across the tested circumstances.The heuristic uses fewer simulations for this screening step and excludes about half the nodes from consideration.
  • Heuristic Seeding Performance: H-Greedy performs slightly worse than A-Greedy but remains better than Greedy in Fig. 7a and 7b.The comparison omits Random because it performs poorly.

6 CONCLUSION AND FUTURE WORK

The paper models influence maximization in dynamic social networks with uncertain diffusion and develops adaptive strategies for selecting seeds over time. It proves a guarantee for A-Greedy, proposes H-Greedy for efficiency, and identifies limitations involving heuristic scope and round limits.

  • Conclusion: The DIC model captures uncertain diffusion by allowing repeated seeding of a node and varying propagation probabilities between users.Adaptive seeding strategies are formulated through the concept of a seeding pattern.
  • Conclusion: A-Greedy combines the optimal pattern A∗ with hill-climbing and has a performance ratio of (1−1/e).The pattern determines how many budget units to use at each seeding step.
  • Conclusion: H-Greedy is a heuristic adaptive strategy based on A-Greedy and the observation that influential nodes are much more powerful than other nodes.Experiments demonstrate the superiority of the adaptive strategies to prior approaches.
  • Future Work: H-Greedy is not effective for all DIC settings, motivating better heuristic adaptive strategies for general social networks.The authors identify improved heuristics as future work.
  • Future Work: With a round limit, delaying seeding loses a diffusion round, and the objective is no longer submodular, complicating greedy algorithms with provable guarantees.The unrestricted strategy attempts to use budgets as late as possible to obtain more information.
Loading 1506.06294v1…