PaperlayerView exact revision on arXiv

Source-linked AI summary

On Budgeted Influence Maximization in Social Networks

Huy Nguyen, Rong Zheng

arXiv:1204.4491v3cs.SIphysics.soc-ph

TL;DR

The paper studies budgeted influence maximization, where node-specific costs constrain seed selection while the goal is to maximize influence spread. It proposes an approximation-guaranteed seed-selection method and Bayesian-network-inspired heuristics for estimating spread. The algorithm guarantees (1 - 1/sqrt(e)) (∼0.394), while experiments report superior performance with moderate computation costs and reveal effects of graph structure.

  • Problem

    Budgeted influence maximization selects seed nodes with arbitrary costs under a fixed budget to maximize the number of influenced nodes, while influence-spread computation is #P-complete.

  • Method

    The paper combines a BIM greedy seed-selection algorithm with belief-propagation-based spread estimation and two DAG-construction heuristics for general graphs.

  • Results

    The seed-selection algorithm guarantees an approximation ratio of (1 - 1/sqrt(e)) (∼0.394), and experiments report superior performance with moderate computation costs.

  • Takeaways & Limitations

    Synthetic networks provide insights into how graph structures affect algorithm performance and the trade-off between computation complexity and attainable spread.

Abstract

from arXiv · show

Given a budget and arbitrary cost for selecting each node, the budgeted influence maximization (BIM) problem concerns selecting a set of seed nodes to disseminate some information that maximizes the total number of nodes influenced (termed as influence spread) in social networks at a total cost no more than the budget. Our proposed seed selection algorithm for the BIM problem guarantees an approximation ratio of (1 - 1/sqrt(e)). The seed selection algorithm needs to calculate the influence spread of candidate seed sets, which is known to be #P-complex. Identifying the linkage between the computation of marginal probabilities in Bayesian networks and the influence spread, we devise efficient heuristic algorithms for the latter problem. Experiments using both large-scale social networks and synthetically generated networks demonstrate superior performance of the proposed algorithm with moderate computation costs. Moreover, synthetic datasets allow us to vary the network parameters and gain important insights on the impact of graph structures on the performance of different algorithms.

I. INTRODUCTION

The paper generalizes influence maximization to budgeted seed selection, develops an approximation-guaranteed algorithm, and addresses the #P-complexity of influence-spread computation with Bayesian-network-based heuristics.

  • I. INTRODUCTION: BIM selects individually costly seed nodes within a fixed budget to maximize the number of influenced nodes, whereas direct simple greedy selection can have an unbounded performance gap.
  • I. INTRODUCTION: The proposed BIM seed-selection algorithm guarantees an approximation ratio of (1 - 1/sqrt(e)) (∼0.394).
  • I. INTRODUCTION: Influence spread is #P-complete to compute exactly, so the paper links it to Bayesian-network belief propagation and develops approximation methods for efficient estimation.
  • I. INTRODUCTION: For general graphs, two heuristics construct DAGs that capture the bulk of influence spread, while localizing candidate evaluation to regions affected by selected seeds improves scalability.
  • I. INTRODUCTION: Experiments on real and synthetic networks study algorithm performance, computation–spread trade-offs, and the effects of graph structures.

III. THE BUDGETED INFLUENCE MAXIMIZATION PROBLEM

The BIM problem selects seed nodes under arbitrary costs and a fixed budget to maximize expected influence spread. The paper shows that naive cost-benefit greedy selection can be unbounded, while an improved greedy algorithm achieves a constant approximation guarantee.

  • Problem formulation: The BIM objective is to choose a seed set whose total node cost stays within budget while maximizing expected influence spread under the IC model.Influence spread is the expected number of activated nodes.
  • Naive Greedy: Naive Greedy can have an unbounded approximation ratio because its best spread-cost choice may block a much better feasible seed.In the construction, Naive Greedy achieves spread 1 while the optimum achieves l, yielding approximation ratio l.
  • Improved Greedy: Algorithm 2 compares the Naive Greedy solution with the single node having maximum influence before returning a seed set.This modification follows an adaptation of an algorithm proposed by Khuller et al.
  • Improved Greedy: Algorithm 2 guarantees a (1 −1/√e)-approximation for BIM, whereas the unmodified greedy approach is unbounded.The paper contrasts this guarantee with CELF’s looser bound of 1/2(1 −1/e) (∼0.316).
  • Computational cost: The seed-selection procedures require repeated influence-spread evaluations, motivating efficient approximation algorithms for σ(.).The stated running time is O(n2T), where T is the maximum time needed to calculate σ(S).

IV. DETERMINING INFLUENCE SPREAD ON DAG

Computing influence spread remains #P-complete even on DAGs, but the paper relates it to marginal-probability computation in Bayesian networks. Belief propagation therefore provides a framework for estimating spread from node activation probabilities.

  • Hardness of computing influence spread on DAGs: Under the IC model, influence spread can be represented through live-edge reachability, with active nodes reached from the seed set by live paths.This representation supports the connection between influence spreading and Bayesian-network inference.
  • Belief propagation formulation: Naively computing the required marginal probabilities is exponential in network treewidth, matching the #P-completeness of marginalization on DAGs.The paper uses this correspondence to explain the computational difficulty of exact spread calculation.
  • Hardness of computing influence spread on DAGs: Computing σ(S) for a seed set on a DAG is #P-complete.The result establishes hardness even under the restricted DAG setting.
  • Belief propagation formulation: A Bayesian-network formulation computes influence spread by estimating each node’s active marginal probability and summing those probabilities.Each influence-spreading node has active and inactive states in the belief-propagation formulation.

C. A Single Pass Belief Propagation Heuristic for σ(·) Estimation

The paper introduces SPBP to estimate influence spread faster by ignoring parent-activation correlations in multiply connected DAGs. This heuristic is exact for singly connected graphs and runs in O(n0d).

  • C. A Single Pass Belief Propagation Heuristic for σ(·) Estimation: LBP is highly accurate but remains slow on multiply connected graphs because parent activations can be correlated.The joint distribution of a node’s parents must otherwise be accounted for.
  • C. A Single Pass Belief Propagation Heuristic for σ(·) Estimation: SPBP ignores parent-activation correlations when estimating σ(.), trading exactness on general DAGs for faster computation.The heuristic is exact when the graph is singly connected.
  • C. A Single Pass Belief Propagation Heuristic for σ(·) Estimation: SPBP starts from seed nodes and processes nodes in topological order to propagate activation probabilities through the DAG.Its total complexity is O(n0d).
  • A. Localizing Influence Spread Region: The method constructs DAG-based local influence regions because general social networks are usually not DAGs.The paper proposes selectively pruning edges while retaining edges where influence is likely to travel.
  • A. Localizing Influence Spread Region: MIOA(G, u, θ) is a thresholded union of maximum-influence paths from seed u, providing a tunable local region for spread estimation.It can be computed from a Dijkstra tree using edge weights −log(p(u, v)).

B. Building DAGs from a Seed Set

The paper constructs DAG approximations from a seed set using MIOA-based topology and rank ordering, with two procedures that differ in edge construction and pruning.

  • Algorithm 4: Algorithm 4 builds a singly connected DAG from a super-root MIOA, then retains additional graph edges directed from lower- to higher-ranked nodes.The super root connects to every seed with probability 1; removing it yields D1, and rank increases with shortest-path distance from the root.
  • Algorithm 5: Algorithm 5 unions the MIOAs of all seed nodes, then removes edges that do not go from lower- to higher-ranked nodes to break cycles.The resulting D2(S) is guaranteed to be a DAG after rank-based pruning.
  • Relationship between constructions: For a fixed influence threshold, both constructions contain the same vertices, while Algorithm 5 retains a subset of Algorithm 4’s edges.Formally, VD1 = VD2 and ED2 ⊆ ED1.
  • Complexity: DAG 1 and DAG 2 require O(n0 log n0) and O(n0) computation respectively, excluding the initial all-node MIOA construction needed by DAG 2.The initialization for all MIOAs costs O(nn0 log n0).

VI. OPTIMIZATION OF SEED SELECTION

The proposed BIM optimizer reduces seed-selection cost by restricting candidate updates to overlapping influence regions while combining cost-aware greedy selection with efficient spread estimation.

  • Seed selection: The optimizer selects nodes by maximum incremental spread-cost ratio, where δ(v) = (σ(S ∪ v) − σ(S))/c(v), subject to the budget.The initial ratio is σ(v)/c(v) when the seed set is empty.
  • Peer-seed optimization: If two seeds’ MIOAs share no vertex, adding one does not change the other’s spread increment, so only overlapping influence regions require re-evaluation.Peer Seeds are nodes whose MIOAs intersect the MIOA of a given vertex and can be computed once at initialization.
  • Proposed algorithm: The proposed algorithm combines peer-seed re-evaluation, CELF-style candidate restriction, and cost-aware selection under the remaining budget.MIOAs and peer-seed sets are constructed during initialization, and the resulting procedure is summarized in Algorithm 6 and Figure 3.
  • Complexity: The proposed approach is more efficient when the resulting DAG is small and sparse, with smaller n0 and in-degree d, conditions likely in social networks with sparse propagation.Its complexity depends on n0 and d, and the DAG2–SPBP combination is identified as the fastest.

VII. EVALUATION

The evaluation compares DAG constructions, inference methods, and seed-selection algorithms on real and synthetic networks to assess performance and structural effects.

  • Evaluation scope: Experiments cover illustrative inference comparisons, implementation details, real-world social networks, and synthetic graphs with varied structures.The evaluation explicitly examines performance on real networks and the impact of network structures using synthetic graphs.

A. An Illustrative Example

The experiment setup compares four DAG–inference combinations with established baselines across real and synthetic networks under multiple propagation-probability models.

  • Illustrative example: DAG 1 retains more edges than DAG 2, producing higher LBP activation probabilities for nodes B and C in the illustrative network.The difference is attributed to DAG 2 omitting the large A-to-B influence; SPBP probabilities tend to be larger when parent-state correlations are ignored.
  • Compared algorithms: The study evaluates DAG1–LBP, DAG1–SPBP, DAG2–LBP, and DAG2–SPBP alongside PMIA, Greedy/CELF, and Weighted Degree.Greedy/CELF estimates each spread value using 10,000 simulation rounds; PMIA uses θ = 1/160.
  • Illustrative example: Figure 4 compares real active probabilities with LBP and SPBP inference results on two DAG models, using green, blue, and red encodings respectively.The panels distinguish real probabilities from inference on DAG 1 and DAG 2.
  • Datasets: The real-network datasets span an email network, p2p-Gnutella, soc-Slashdot, and Amazon, covering scales from thousands to millions of edges.The datasets represent research-lab email, peer-to-peer connections, social links, and product co-purchasing.
  • Datasets: Synthetic scale-free networks vary density and node out-degree distributions to study how graph structure and network properties affect algorithm performance.The networks were generated by modifying DIGG source code.

C. Real Social Networks

Experiments on real networks compare the proposed DAG-based methods with established baselines under unit and general node costs. The proposed methods achieve strong influence spread, while their speed depends on the DAG and belief-propagation choices.

  • Unit-cost BIM: DAG1–LBP matches Greedy on Email, while the proposed methods outperform PMIA and Weighted Degree; on sparser datasets, their spread is identical and matches Greedy on p2p-Gnutella.The comparison uses influence spread from seed sets selected across four datasets, with spread estimated by 10,000 Monte Carlo simulations.
  • Unit-cost BIM: Weighted Degree is fastest, whereas among the proposed methods DAG2–SPBP is fastest and DAG1–LBP is slowest; DAG2–SPBP is 30–40% slower than PMIA in most cases.The proposed methods’ running-time ordering is DAG2–SPBP, DAG2–LBP, DAG1–SPBP, then DAG1–LBP.
  • Unit-cost BIM: Influence spread on Amazon grows linearly with seed-set size, consistent with small seed sets having largely nonoverlapping influence regions.The passage attributes this pattern to the network’s sheer scale.
  • General-cost BIM: DAG1–SPBP is several orders of magnitude faster than Greedy/CELF on random-cost experiments and outperforms it on p2p-Gnutella.DAG1 generally performs better than DAG2, while Weighted Degree is fastest but performs poorly on dense Email.
  • DAG comparison: DAG1 is denser than DAG2, and its denser structure yields smaller activation-probability RMSE; combining DAG1 with LBP gives the best inference result at higher computational complexity.LBP is slightly better than SPBP because SPBP ignores correlations among node states.

D. Synthetic Networks

Synthetic experiments vary density, propagation models, and degree distributions to expose when each algorithm performs well. The proposed methods generally surpass alternatives, while network structure determines the spread–complexity trade-off.

  • Impact of network density: As network density increases, the performance gap between the proposed algorithms and existing methods, including CELF, increases.CELF requires more simulation rounds on dense networks to estimate spread accurately, increasing its computational burden.
  • Impact of probability generation model: All propagation models give similar performance except Weighted Degree under WC, where it performs worst because local degree cannot capture strong ties involving low-in-degree nodes.The comparison uses RA, TV, PL, and WC on a synthetic network with 5,000 nodes and 50,000 edges.
  • Impact of node out-degree distribution: As the power-law exponent β increases, performance gaps reduce because high-out-degree hubs become nearly certain strong seed candidates when costs do not prevent their selection.The synthetic networks contain about 50,000 edges and vary β from 0.5 to 2.0.
  • Summary: The proposed schemes surpass the other algorithms across all experimented datasets, with DAG1–LBP suited to static networks and DAG2–SPBP suited to rapidly changing communities.The paper frames this as application flexibility along a computation-complexity versus performance trade-off.
  • Summary: Weighted Degree has the best spread/complexity efficiency but degrades significantly on dense networks or heavier-tailed power-law graphs; PMIA is faster yet offers little spread improvement except under WC.These conclusions are drawn from the real and synthetic experiments together.

APPENDIX

The appendix develops approximation and complexity results for budgeted influence maximization and DAG-based influence computation. It also formalizes reductions used to establish #P-completeness.

  • Hardness results: S-SET CONNECTEDNESS on a DAG counts subgraphs in which every designated vertex is reachable from a source, while S-T CONNECTEDNESS counts subgraphs containing a directed source-to-target path.These counting problems are used as formal components of the appendix’s complexity argument.
  • Hardness results: The appendix reduces SAT′ to S-T CONNECTEDNESS on DAGs by constructing a layered directed acyclic graph encoding variable assignments and clause occurrences.The construction uses variable and complementary-variable nodes, clause nodes, and edges ordered so that all paths follow increasing indices.
  • DAG properties: The DAG constructions contain the same vertices, while DAG2’s edge set is a subset of DAG1’s; some DAG1 edges are absent from every seed-originating MIOA in DAG2.The proof also states that limiting spread from one node prevents another node’s activation probabilities from being affected by adding the first node to the seed set.
  • Approximation analysis: The approximation proof analyzes cases based on whether a high-spread node exists and whether the current seed-set cost is below or above half the budget.The argument uses submodularity and a lemma adapted from budgeted maximum coverage and generalized to submodular functions.
Loading 1204.4491v3…