Abstract Locating a set of influential users within a social network, known as the Influence Maximization (IM) problem, can have significant implications for boosting the spread of positive information/news and curbing the spread of negative elements such as misinformation and disease. However, the traditional simulation‐based spread computations under conventional diffusion models render existing algorithms inefficient in finding optimal solutions. In recent years, hop and path‐based approaches have gained popularity, particularly under the cascade models to address the scalability issue. Nevertheless, these existing functions vary based on the considered hop‐distance and provide no guidance on capturing spread sizes beyond two‐hops. In this paper, we introduce Hop‐based Expected Influence Maximization (HEIM), an approach utilizing generalized functions to compute influence spread across varying hop‐distances in conventional diffusion models. We extend our investigation to the Linear Threshold (LT) model, in addition to the Independent Cascade (IC) and Weighted Cascade (WC) models, filling a gap in current literature. Our theoretical analysis shows that the proposed functions preserve both monotonicity and submodularity, and the proposed HEIM algorithm can achieve an approximation ratio of under a limited hop‐measures, whereas a multiplicative ‐approximation under global measures. Furthermore, we show that expected spread methods can serve as a better benchmark approach than existing simulation‐based methods. The performance of the HEIM algorithm is evaluated through experiments on three real‐world networks, and is compared to six other existing algorithms. Results demonstrate that the three‐hop based HEIM algorithm achieves superior solution quality, ranking first in statistical tests, and is notably faster than existing benchmark approaches. Conversely, the one‐hop‐based HEIM offers faster computation while still delivering competitive solutions, providing decision‐makers with flexibility based on application needs.

Uncertainty is ubiquitous in almost every real-life optimization problem, which must be effectively managed to get a robust outcome. This is also true for the Influence Maximization (IM) problem, which entails locating a set of influential users within a social network. However, most of the existing IM approaches have overlooked the uncertain factors in finding the optimal solution, which often leads to subpar performance in reality. A few recent studies have considered only the epistemic uncertainty (i.e., arises from the imprecise data), while ignoring completely the aleatory uncertainty (i.e., arises from natural or physical variability). In this article, we propose a formulation and a novel algorithm for the Robust Influence Maximization (RIM) problem under both types of uncertainties. First, we develop a robust influence spread function under aleatory uncertainty that, in contrast to the existing IM theory, is no longer monotone and submodular. Thereafter, we expand our RIM formulation to incorporate epistemic uncertainty aiming to maximize the robust ratio between the selected worst-case solution and the best-case optimal solution, adopting a conservative approach. Furthermore, using a chance-constraint-based method, we investigated feasibility robustness by accounting for the uncertainties related to constraint functions. Finally, an Evolutionary Algorithm (named EA-RIM) is designed to solve the proposed formulation of the RIM problem. Experimental evaluation results on four empirical datasets show that our proposed formulation and algorithm are more effective in dealing with uncertainties and finding an optimal solution for the RIM problem.

Identification of a set of influential spreaders in a network, called the Influence Maximization (IM) problem, has gained much popularity due to its immense practicality. In real-life applications, not only the influence spread size, but also some other criteria such as the selection cost and the size of the seed set play an important role in selecting the optimal solution. However, majority of the existing works have treated this issue as a single-objective optimization problem, where decision-makers are forced to make their choices regarding other variables in advance despite having a thorough understanding of them. This research formulates a multi-objective version of the IM problem (referred to as MOIMP), which considers three competing objectives while subject to certain practical restrictions. Theoretical analysis reveals that the influence spreading function under the suggested MOIMP framework is no longer monotone, but submodular. We also considered three well-established multi-objective evolutionary algorithms to solve the proposed MOIMP. Since the proposed MOIMP addresses varying-size seeds, all the considered algorithms are significantly modified to fit into it. Experimental results on four real-life datasets, evaluating and comparing the performance of the considered algorithms, demonstrate the effectiveness of the proposed MOIMP.