Abstract
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.
Introduction: The Challenge of Node Burden
Traditional Influence Maximization (IM) focuses on identifying "super-spreaders"—a small set of $k$ seed nodes that can trigger the largest possible cascade of information or influence across a network. However, this singular focus on reach often ignores the physical or operational strain placed on those seed nodes.
In practical scenarios like Device-to-Device (D2D) communication or social support networks, seed nodes are not just conduits; they are resource providers. For instance, in a D2D network, a seed device might cache content for its neighbors. If a single "super-node" is tasked with serving hundreds of neighbors while others serve only a few, that node faces significant "Node Burden"—leading to memory exhaustion, battery drain, or communication congestion.
The authors argue that a fair distribution of load is critical for network stability. They define a new bi-objective problem: maximizing total influence while simultaneously minimizing the variance of the burden across the chosen seeds.
Methodology: Balancing Reach and Load
To address this bi-objective optimization, the researchers developed two distinct algorithmic approaches:
1. IM-B-RR (Reverse Reachable Sampling)
This algorithm is designed for speed and stability. It leverages the "Reverse Reachable" (RR) sampling method, a state-of-the-art technique for estimating influence. By iteratively selecting nodes that offer the best marginal gain in influence while considering the resulting burden distribution, IM-B-RR provides a fast, constructive solution suitable for large-scale networks.
2. IM-B-MA (Memetic Algorithm)
For more complex optimization, the authors proposed a memetic algorithm—a population-based evolutionary strategy enhanced by local search operators. The core innovation is a "meme search operator" that uses two specific indicators to guide the evolution of solutions:
- Influence Indicator ($rm$): Identifies nodes that provide high influence with minimal overlap with other seeds.
- Burden Indicator ($rn$): Identifies nodes that help balance the overall variance of the burden.
By intelligently swapping nodes based on these indicators, the algorithm explores the "Pareto front"—the set of solutions where no objective can be improved without degrading the other.
Experimental Evaluation
The algorithms were tested against synthetic Barabási–Albert (BA) scale-free networks and real-world datasets from the SNAP repository, including Facebook social circles, Gnutella peer-to-peer networks, and Wiki-Vote networks.
Key Insights
- Objective Conflict: Empirical results confirm that influence and burden variance are naturally conflicting. Because real-world networks often follow power-law distributions, the most influential nodes are almost always the most heavily burdened.
- Superior Optimization: IM-B-MA consistently outperformed standard multi-objective algorithms (like NSGA-II and MOEA/D) in terms of "hypervolume," meaning it found a more diverse and higher-quality set of trade-offs between influence and load balancing.
- Efficiency and Stability: While the memetic approach offers the best Pareto fronts, the IM-B-RR algorithm provides a highly efficient alternative with zero standard deviation, making it ideal for scenarios requiring rapid decision-making.
Conclusion and Future Directions
This research shifts the focus of influence maximization from pure reach to sustainable network operation. By accounting for node burden, the proposed models ensure that the "super-spreaders" of a network are not overwhelmed by their own success.
Future work will look to extend these bi-objective strategies to dynamic networks where node connections change over time. Additionally, the authors suggest incorporating more granular hardware constraints, such as specific battery life or bandwidth limits, to further refine the definition of node burden in specialized environments.
Summary updated