SpreadRank: A Novel Approach for Identifying Influential Spreaders in Complex Networks

Identifying influential spreaders in complex networks is critical for information spread and malware diffusion suppression. In this paper, we propose a novel influential spreader identification method, called SpreadRank, which considers the path reachability in information spreading and uses its quantitative index as a measure of node spread centrality to obtain the spread influence of a single node. To avoid the overlapping of the influence range of the node spread, this method establishes a dynamic influential node set selection mechanism based on the spread centrality value and the principle of minimizing the maximum connected branch after network segmentation, and it selects a group of nodes with the greatest overall spread influence. Experiments based on the SIR model demonstrate that, compared to other existing methods, the selected influential spreaders of SpreadRank can quickly diffuse or suppress information more effectively.

Agglomerative clustering enhanced GA for optimal seed selection in online social networks

Purpose

The social media revolution has brought tremendous change in business strategies for marketing and promoting the products and services. Online social networks have become prime choice to promote the products because of the large size of online communities. Identification of seed nodes or identifying the users who are able to maximize the spread of information over the network is the key challenge faced by organizations. It is proved as non-deterministic polynomial-time hard problem. The purpose of this paper is to design an efficient algorithm for optimal seed selection to cover the online social network as much as possible to maximize the influence. In this approach, agglomerative clustering is used to generate the initial population of seed nodes for GA.

Design/methodology/approach

In this paper agglomerative clustering based approach is proposed to generate the initial population of seed nodes for GA. This approach helps in creating the initial populations of Genetic algorithm from different parts of the network. Genetic algorithm evolves this population and aids in generating the best seed nodes in the network.

Findings

The performance of of proposed approach is assessed with respect to existing seed selection approaches like k-medoid, k-means, general greedy, random, discounted degree and high degree. The algorithms are compared over networks data sets with varying out-degree ratio. Experiments reveal that the proposed approach is able to improve the spread of influence by 35% as compared to contemporary techniques.

Originality/value

This paper is original contribution. The agglomerative clustering-based GA for optimal seed selection is developed to improve the spread of influence in online social networks. This paper is of immense importance for viral marketing and the organizations willing to promote product or services online via influential personalities.

A New Strategy in Boosting Information Spread

Finding a seed set to propagate more information within a specific budget is defined as the influence maximization (IM) problem. The traditional IM model contains two cardinal aspects: (i) the influence propagation model and (ii) effective/efficient seed-seeking algorithms. However, most of models only consider one kind of node (i.e., influential nodes), ignoring the role of other nodes (e.g., boosting nodes) in the spreading process, which are irrational. Specifically, in the real-world propagation scenario, the boosting nodes always improve the spread of influence from the initial activated seeds, which is an efficient and cost-economic measure. In this paper, we consider the realistic budgeted influence maximization (RBIM) problem, which contains two kind of nodes to improve the diffusion of influence. Facing the newly modified objective function, we propose a novel B-degree discount algorithm to solve it. The novel B-degree discount algorithm which adopts the cost-economic boosting nodes to retweet the influence from the predecessor nodes can greatly reduce the cost, and performs better than other state-of-the-art algorithms in both effect and efficiency on RBIM problem solving.

A Memetic Algorithm for Solving the Robust Influence Maximization Problem on Complex Networks against Structural Failures

Many transport systems in the real world can be modeled as networked systems. Due to limited resources, only a few nodes can be selected as seeds in the system, whose role is to spread required information or control signals as widely as possible. This problem can be modeled as the influence maximization problem. Most of the existing selection strategies are based on the invariable network structure and have not touched upon the condition that the network is under structural failures. Related studies indicate that such strategies may not completely tackle complicated diffusion tasks in reality, and the robustness of the information diffusion process against perturbances is significant. To give a numerical performance criterion of seeds under structural failure, a measure has been developed to define the robust influence maximization (RIM) problem. Further, a memetic optimization algorithm (MA) which includes several problem-orientated operators to improve the search ability, termed RIMMA, has been presented to deal with the RIM problem. Experimental results on synthetic networks and real-world networks validate the effectiveness of RIMMA, its superiority over existing approaches is also shown.

Finding Influential Nodes in Multiplex Networks Using a Memetic Algorithm

In order to find the nodes with better propagation ability, a large body of studies on the influence maximization problem has been conducted. Several influence spreading models and corresponding optimization algorithms have been proposed and successfully identified the infusive seeds in single isolated networks. However, as indicated by some recent studies and online materials, modern networked systems tend to have more complicated structures and multiple layers, which makes it difficult for existing seed determination techniques to deal with these networks. Thus, finding influential nodes in realistic multiplex networks remains open. Therefore, this paper aims to design an extended influence spreading model to simulate the influence diffusion process in multiplex networks, based on which a memetic algorithm is developed to find the seeds that are influential in all network layers. Experimental results on synthetic and real-world networks validate the effectiveness of the proposed algorithm. These results are helpful for identifying potential propagators in multiplex social networks, and provide solutions to analyze and gain deeper insights into networked systems.

Cost-Aware Robust Control of Signed Networks by Using a Memetic Algorithm

The robust controllability (RC) of a complex system tries to select a set of dominating entities for the functional control of this entire system without uncertain disturbances, and the research on RC will help to understand the system's underlying functions. In this article, we introduce the control cost in signed networks and present a cost-aware robust control (CRC) problem in this scenario. The aim of CRC is to minimize the cost to control a set of dominating nodes and transform a set of unbalanced links into balanced ones, such that the signed network can be robustly controlled without uncertain unbalanced factors (like nodes and links). To solve this problem, we first model CRC as a constrained combination optimization problem, and then present a memetic algorithm with some problem-specific knowledge (like the neighbors of nodes, the constraints of CRC, and the fast computation of the cost under each optimization) to solve this problem on signed networks. The extensive experiments on both real social and biological networks assess that our algorithm outperforms several state-of-the-art RC algorithms.

Ant Colony Optimization for the Control of Pollutant Spreading on Social Networks

The rapid development of online social networks not only enables prompt and convenient dissemination of desirable information but also incurs fast and wide propagation of undesirable information. A common way to control the spread of pollutants is to block some nodes, but such a strategy may affect the service quality of a social network and leads to a high control cost if too many nodes are blocked. This paper considers the node selection problem as a biobjective optimization problem to find a subset of nodes to be blocked so that the effect of the control is maximized while the cost of the control is minimized. To solve this problem, we design an ant colony optimization algorithm with an adaptive dimension size selection under the multiobjective evolutionary algorithm framework based on decomposition (MOEA/D-ADACO). The proposed algorithm divides the biobjective problem into a set of single-objective subproblems and each ant takes charge of optimizing one subproblem. Moreover, two types of pheromone and heuristic information are incorporated into MOEA/D-ADACO, that is, pheromone and heuristic information of dimension size selection and that of node selection. While constructing solutions, the ants first determine the dimension size according to the former type of pheromone and heuristic information. Then, the ants select a specific number of nodes to build solutions according to the latter type of pheromone and heuristic information. Experiments conducted on a set of real-world online social networks confirm that the proposed biobjective optimization model and the developed MOEA/D-ADACO are promising for the pollutant spreading control.

Influential Nodes Identification in Complex Networks via Information Entropy

Identifying a set of influential nodes is an important topic in complex networks which plays a crucial role in many applications, such as market advertising, rumor controlling, and predicting valuable scientific publications. In regard to this, researchers have developed algorithms from simple degree methods to all kinds of sophisticated approaches. However, a more robust and practical algorithm is required for the task. In this paper, we propose the EnRenew algorithm aimed to identify a set of influential nodes via information entropy. Firstly, the information entropy of each node is calculated as initial spreading ability. Then, select the node with the largest information entropy and renovate its l-length reachable nodes’ spreading ability by an attenuation factor, repeat this process until specific number of influential nodes are selected. Compared with the best state-of-the-art benchmark methods, the performance of proposed algorithm improved by 21.1%, 7.0%, 30.0%, 5.0%, 2.5%, and 9.0% in final affected scale on CEnew, Email, Hamster, Router, Condmat, and Amazon network, respectively, under the Susceptible-Infected-Recovered (SIR) simulation model. The proposed algorithm measures the importance of nodes based on information entropy and selects a group of important nodes through dynamic update strategy. The impressive results on the SIR simulation model shed light on new method of node mining in complex networks for information spreading and epidemic prevention.