Bi-objective influence maximization with consideration of node burden

Yuhui Shi, Mingyang Feng, Qi Zhao, Shan He, Yuhui Shi 0001

TL;DR

Traditional influence maximization focuses solely on finding "super-spreaders" to reach the most people, but it ignores the physical strain placed on those seed nodes. This paper introduces a bi-objective approach that maximizes total influence while minimizing the variance of "node burden," ensuring that no single node is overwhelmed by the demands of its followers.

What Problem Does This Paper Address?

Influence Maximization (IM) is a classic problem in network science: if you can only pick $k$ "seed" nodes to start a trend or share a file, which ones do you choose to reach the maximum number of people?

While most research focuses purely on reach, the authors argue that in many real-world scenarios—like Device-to-Device (D2D) communication networks or social programs for homeless youth—the seed nodes have limited resources. In a D2D network, a seed device might provide cached content to its neighbors. If one "super-node" is responsible for hundreds of neighbors while others serve only five, that super-node will suffer from memory shortages and communication congestion, potentially crashing the network.

The authors define this as Node Burden. The gap they fill is the lack of a model that balances high influence with a fair distribution of load across the chosen seeds.

Methods

The authors propose two primary algorithms to solve this bi-objective problem (maximizing influence vs. minimizing burden variance):

  1. IM-B-RR (Reverse Reachable Sampling): This is a fast, constructive algorithm. It uses the standard "Reverse Reachable" sampling method to rank nodes by influence and then selects sets of nodes sequentially to find a stable, local optimum. It’s designed for speed and stability.
  2. IM-B-MA (Memetic Algorithm): This is a more sophisticated evolutionary approach. It uses a population of solutions that "evolve" over generations. The secret sauce here is a novel meme search operator. Instead of random mutations, the algorithm uses two specific indicators:
  3. rm: Identifies nodes that provide high influence with low overlap.
  4. rn: Identifies nodes that help balance the variance of the burden.

By intelligently swapping nodes using these indicators, the algorithm explores the "Pareto front"—the set of optimal trade-offs where you can't improve influence without making the burden more imbalanced.

Datasets

The researchers evaluated their algorithms on both synthetic and real-world networks:

  • Synthetic: Traditional Barabási–Albert (BA) scale-free networks, which mimic the "rich-get-richer" structure of many real systems.
  • Real-World (from SNAP):
    • Facebook: Social circles.
  • GRQC: A collaboration network of researchers in General Relativity.
  • Gnutella: A peer-to-peer file-sharing network.
  • Wiki: A network of Wikipedia users voting on adminship.

Key Insights and Ideas

  • The Conflict is Real: The authors empirically prove that influence and burden variance are conflicting objectives. Because social networks follow a power-law distribution (a few nodes have massive connections), the most influential nodes almost always create the most imbalanced burdens.
  • Burden vs. Cost: The paper distinguishes "burden" from "cost." While "cost" (like an advertising fee) is something a decision-maker chooses to pay, "burden" is a natural property with a hard ceiling. If the burden exceeds a node's capacity, the system fails.
  • Smart Swapping: The Memetic Algorithm's success hinges on the idea that you shouldn't just delete a node because it's "weak." Instead, you should delete the node that has the most overlapping influence with others, as it contributes the least unique value to the set.

Key Results

  • Superior Pareto Fronts: IM-B-MA consistently achieved a higher hypervolume (a metric for multi-objective optimization quality) than standard algorithms like NSGA-II, MOEA/D, and IS-MOPSO+. This means it found better trade-offs between reach and load balancing.
  • Efficiency: The memetic search operator significantly accelerated convergence. IM-B-MA reached high-quality solutions in fewer generations than traditional evolutionary strategies.
  • Stability: The IM-B-RR algorithm, while less flexible than the memetic approach, provided extremely fast and stable results with zero standard deviation, making it a viable "quick-and-dirty" tool for large-scale networks.

Limitations and Future Work

The current study assumes a static network—the connections between nodes don't change over time. In reality, social and D2D networks are highly dynamic. The authors acknowledge this and suggest that future work should integrate these bi-objective strategies into dynamic network models where nodes join and leave the system frequently. Additionally, while "variance" is a good proxy for burden, future models might incorporate specific hardware constraints (like exact battery life or RAM) into the objective function.

Summary updated

Abstract

<title>Abstract</title> Influence maximization aims at finding a set of nodes with the maximum influence in a network. Apart from the influence, the burden of nodes is worth considering as an objective but has been neglected in the literature. Herein, the burden refers to the capacity of a node to serve its influenced nodes, e.g., the storage of a device in the device-to-device networks. In this paper, we propose a new bi-objective influence maximization problem that jointly maximizes the influence of seed nodes and minimizes the variance of the burden of seed nodes, called Influence Maximization with Burden. We provide intuitive and empirical evidence to demonstrate the feasibility and necessity of the proposed problem. Furthermore, we develop two algorithms to solve the proposed influence maximization problem. One is a fast suboptimal algorithm based on the reverse reachable sampling method. The other is a memetic algorithm with a novel meme operator to identify promising nodes. The results of the experiments on synthesis and real networks illustrate that the proposed algorithms perform more effectively and efficiently than other existing algorithms. We published our codes on GitHub: https://github.com/fmyzckj.
BibTeX
@article{shi2025bi,
  author = {Yuhui Shi and Mingyang Feng and Qi Zhao and Shan He and Yuhui Shi},
  title = {{Bi-objective influence maximization with consideration of node burden}},
  journal = {Memetic Comput},
  year = {2025},
  doi = {10.1007/s12293-025-00452-8},
}
Figure