•A method by weighted overlapped community, local diffusion, and probability of global diffusion.•Remove weak communities and periphery nodes to a get a near-linear time complexity.•Generating ...candidate influential nodes using the probability of global diffusion.•Select seed set from candidates based on diffusion and overlapping capability.
Influence maximization is the process of identifying a small set of influential nodes from a complex network to maximize the number of activation nodes. Due to the critical issues such as accuracy, stability, and time complexity in selecting the seed set, many studies and algorithms has been proposed in recent decade. However, most of the influence maximization algorithms run into major challenges such as the lack of optimal seed nodes selection, unsuitable influence spread, and high time complexity. In this paper intends to solve the mentioned challenges, by decreasing the search space to reduce the time complexity. Furthermore, It selects the seed nodes with more optimal influence spread concerning the characteristics of a community structure, diffusion capability of overlapped and hub nodes within and between communities, and the probability coefficient of global diffusion. The proposed algorithm, called the FIP algorithm, primarily detects the overlapping communities, weighs the communities, and analyzes the emotional relationships of the community’s nodes. Moreover, the search space for choosing the seed nodes is limited by removing insignificant communities. Then, the candidate nodes are generated using the effect of the probability of global diffusion. Finally, the role of important nodes and the diffusion impact of overlapping nodes in the communities are measured to select the final seed nodes. Experimental results in real-world and synthetic networks indicate that the proposed FIP algorithm has significantly outperformed other algorithms in terms of efficiency and runtime.
The different communications of users in social networks play a key role in effect to each other. The effect is important when they can achieve their goals through different communications. Studying ...the effect of specific users on other users has been modeled on the influence maximization problem on social networks. To solve this problem, different algorithms have been proposed that each of which has attempted to improve the influence spread and running time than other algorithms. Due to the lack of a review of the meta-heuristic algorithms for the influence maximization problem so far, in this paper, we first perform a comprehensive categorize of the presented algorithms for this problem. Then according to the efficient results and significant progress of the meta-heuristic algorithms over the last few years, we describe the comparison, advantages, and disadvantages of these algorithms.
The influence maximization problem has gained particular importance in viral marketing for large-scale spreading in social networks. Developing a fast and appropriate algorithm to identify an ...optimized seed set for the diffusion process on social networks is crucial due to the fast growth of networks. Most fast methods only focus on the degree of nodes while ignoring the strategic position of nodes in the networks. These methods do not have the required quality in finding a seed set in most networks. On the other hand, many other methods have acceptable quality, but their computational overhead is significant. To address these issues, the main concentration of this paper is to propose a fast and accurate method for the influence maximization problem, which uses a local traveling for labeling of nodes based on the influence power, called the LMP algorithm. In the proposed LMP algorithm, first, a travel starts from a node with the lowest influence power to assign a ranking-label for this node and its neighbor nodes in each step based on their diffusion capability and strategic position. The LMP algorithm uses node labeling steps to reduce search space significantly. Three ranking-labels are used in the proposed algorithm, and nodes with the highest ranking-label are selected as candidate nodes. This local and fast step strictly reduces the search space. Finally, the LMP algorithm selects seed nodes based on the topology features and the strategic position of the candidate and connector. The performance of the proposed algorithm is benchmarked with the well-known and recently proposed seed selection algorithms. The experimental results are performed on real-world and synthetic networks to validate the efficiency and effectiveness. The experiments exhibit that the proposed algorithm is the fastest in comparison with other state-of-the-art algorithms, and it has linear time complexity. In addition, it can achieve a good tradeoff between the efficiency and time complexity in the influence maximization problem.
•To propose a fast and accurate method for the influence maximization problem.•A local traveling is used to select candidate nodes for node labeling based on their diffusion capability.•The LMP algorithm uses node labeling step to reduce significantly search space.•Seed nodes are selected from the candidate and specially connector nodes based on the topology features and the specific position.•The proposed algorithm has the best stability, accuracy and running time than other well-known and fast algorithms.•The proposed algorithm does not use any adjustable parameters in steps of algorithms.
Influence maximization is a classic optimization problem to find a subset of seed nodes in a social network that has a maximum influence with respect to a propagation model. This problem suffers from ...the overlap of seed nodes and the lack of optimal selection of seed nodes. Kempe et al. have shown that this problem is an NP-hard problem, and the objective function is submodular. Therefore, some heuristic and greedy algorithms have been proposed to find a near-optimal solution. However, the greedy algorithm may not satisfy the accuracy of a given solution and high time-consuming problem. To overcome these problems, the TI-SC algorithm is proposed for the problem of influence maximization. The TI-SC algorithm selects the influential nodes by examining the relationships between the core nodes and the scoring ability of other nodes. After selecting each seed node, the scores are updated to reduce the overlap in selecting the seed nodes. This algorithm has efficient performance in high Rich-Club networks. The Rich-Club phenomenon causes overlapping of the influence spread among the seed nodes in most of the other methods so that the TI-SC algorithm reduces this overlapping. Furthermore, the discovered communities with low expansion are not considered in the seed node selection phase, and this is useful for reducing computational overhead. Experimental results on both synthetic and real datasets show that the proposed TI-SC algorithm significantly outperforms the state-of-the-art algorithms in terms of efficiency in both small and large-scale datasets.
•A new fast module extraction method is presented to select important modules.•Optimal module pruning is proposed reduces the search space for IM problem.•A new criterion is defined for calculating ...node’s influence to identify candidate nodes.•A new measure is defined to select final seed set from candidate nodes.•The classic IC model is improved based on real-world information diffusion and different capabilities of nodes.
In this paper, we explore influence maximization, one of the most widely studied problems in social network analysis. However, developing an effective algorithm for influence maximization is still a challenging task given its NP-hard nature. To tackle this issue, we propose the CSP (Combined modules for Seed Processing) algorithm, which aim to identify influential nodes. In CSP, graph modules are initially identified by a combination of criteria such as the clustering coefficient, degree, and common neighbors of nodes. Nodes with the same label are then clustered together into modules using label diffusion. Subsequently, only the most influential modules are selected using a filtering method based on their diffusion capacity. The algorithm then merges neighboring modules into distinct modules and extracts a candidate set of influential nodes using a new metric to quickly select seed sets. The number of selected nodes for the candidate set is restricted by a defined limit measure. Finally, seed nodes are chosen from the candidate set using a novel node scoring measure. We evaluated the proposed algorithm on both real-world and synthetic networks, and our experimental results indicate that the CSP algorithm outperforms other competitive algorithms in terms of solution quality and speedup on tested networks.
With the development of science and technology through social networks, the process of diffusion has become a controversial subject. In social networks, the process of diffusion is transmitted from ...one individual to another. The influence maximization problem, in which at least k nodes are chosen as the initial nodes of the spreader in the smallest amount of time, is one of the most critical aspects of the diffusion process. Furthermore, the initial nodes in the social network should generate the most influence on the other nodes in the network. However, in the algorithms proposed to solve the problem of influence maximization, the real-world factors which affect the influence probability in diffusion models are ignored for example, the influence probability is determined randomly. This problem causes influence maximization algorithms based on diffusion models to face the challenge of time-consuming Monte Carlo simulation. So, the RIM algorithm presented in this article which this method selects the initial nodes of the spreader according on their local reachability. In addition, Due to privacy in social networks, complete information about people such as gender, education, etc. is not available. For this reason, in the RIM algorithm, using the graph structure in social networks, the influence probability is calculated in the new DBT diffusion model. In addition, the RIM algorithm exhibits stable performance in the selection of the spreader's initial nodes in terms of influence spread, and execution time.
Influence maximization techniques emphasize selecting a set of influential nodes in order to maximize influence. Because the algorithms presented in this field ignore the topology of cliques for ...diffusion, there are two major challenges in influence maximization algorithms: optimal diffusion and computational overhead reduction. As a result, the CDP algorithm is presented in this article to address these issues. This algorithm first selects suitable cliques for diffusion based on their position and strategy in social networks. Furthermore, for each clique, a score is calculated based on the topological criteria of the clique, and suitable cliques are selected for diffusion by applying a threshold limit. The seed nodes are chosen from the cliques in the second step. To avoid the rich club phenomenon, only a few nodes from each clique are chosen as seed candidate nodes. Finally, the seed nodes are chosen based on the node's topology and the strength of the node's level one neighbor. In the experiment section, the CDP algorithm significantly outperforms the best algorithms presented in recent years in terms of influence spread rate and execution time.
Identify influential nodes is essential to the immunization and propagation process on complex networks that this node selects based on the influence maximization problem. However, most of the ...previous strategies face many challenges, such as accuracy and efficiency. To solve these challenges, in this paper, we propose a novel influence maximization algorithm, named NFIM (Node filtering in influence maximization), which is based on deleting a maximal independent set and creating a subgraph. First, the search space for selecting seed nodes is reduced in the NFIM algorithm Then, seed nodes are selected by examining independent paths and clustering coefficient. Experiment results present that the NFIM algorithm performs better than PHG, LIR, CI, and ProbDegree on influence spread and faster than PHG, LIR, and CI.
The strength of information diffusion on social networks depends on many factors, including the selected influential nodes. The problem of finding such nodes in the network is modeled by influence ...maximization problem, which faces two essential challenges: (1) inadequate selection of the seed nodes due to the lack of focus on the rich-club phenomenon and (2) high running time due to the lack of focus on pruning the graph nodes and localization. To solve these challenges, a computational localization-based RLIM algorithm is presented here to prevent the rich-club phenomenon. In this algorithm, the graph nodes are pruned based on the eigenvector centrality to reduce the computational overhead, and then the computations are performed locally using localization criteria. After that, influential nodes are selected by avoiding the rich-club phenomenon. In the RLIM algorithm, the seed nodes provided a better influence spread than the other algorithms. Experimental results on the synthetic and real-world datasets shows that the RLIM algorithm can verify the high effectiveness and efficiency than the comparable algorithms for an influence maximization problem.
Influence maximization is a problem based on diffusion and probability in social networks with the aim of finding the least k node with the most influence. These nodes play an essential role in the ...diffusion process. However, the influence maximization problem faces two essential challenges of time efficiency and optimal selection of the seed nodes. To solve these challenges, we proposed an algorithm based on the properties of the graph topology structure and centrality, called IMT (Influence Maximization based on the Topology) algorithm. This algorithm selects the seed nodes from the dense part of the graph that can access more nodes in the shortest distance. Finally, experiments showed that the proposed algorithm outperformed the other algorithms in terms of influence spread and running time.
