Identifying influential spreaders in complex networks is crucial in understanding, controlling and accelerating spreading processes for diseases, information, innovations, behaviors, and so on. Inspired by the gravity law, we propose a gravity model that utilizes both neighborhood information and path information to measure a node’s importance in spreading dynamics. In order to reduce the accumulated errors caused by interactions at distance and to lower the computational complexity, a local version of the gravity model is further proposed by introducing a truncation radius. Empirical analyses of the Susceptible-Infected-Recovered (SIR) spreading dynamics on fourteen real networks show that the gravity model and the local gravity model perform very competitively in comparison with well-known state-of-the-art methods. For the local gravity model, the empirical results suggest an approximately linear relation between the optimal truncation radius and the average distance of the network.

How to identify influential spreaders in complex networks is a topic of general interest in the field of network science. Therefore, it wins an increasing attention and many influential spreaders identification methods have been proposed so far. A significant number of experiments indicate that depending on a single characteristic of nodes to reliably identify influential spreaders is inadequate. As a result, a series of methods integrating multi-characteristics of nodes have been proposed. In this paper, we propose a gravity model that effectively integrates multi-characteristics of nodes. The number of neighbors, the influence of neighbors, the location of nodes, and the path information between nodes are all taken into consideration in our model. Compared with well-known state-of-the-art methods, empirical analyses of the Susceptible-Infected-Recovered (SIR) spreading dynamics on ten real networks suggest that our model generally performs best. Furthermore, the empirical results suggest that even if our model only considers the second-order neighborhood of nodes, it still performs very competitively.

Identification of influential spreaders is still a challenging issue in network science. Therefore, it attracts increasing attention from both computer science and physical societies, and many algorithms to identify influential spreaders have been proposed so far. Degree centrality, as the most widely used neighborhood-based centrality, was introduced into the network world to evaluate the spreading ability of nodes. However, degree centrality always assigns too many nodes with the same value, so it leads to the problem of resolution limitation in distinguishing the real influences of these nodes, which further affects the ranking efficiency of the algorithm. The k-shell decomposition method also faces the same problem. In order to solve the resolution limit problem, we propose a high-resolution index combining both degree centrality and the k-shell decomposition method. Furthermore, based on the proposed index and the well-known gravity law, we propose an improved gravity model to measure the importance of nodes in propagation dynamics. Experiments on ten real networks show that our model outperforms most of the state-of-the-art methods. It has a better performance in terms of ranking performance as measured by the Kendall’s rank correlation, and in terms of ranking efficiency as measured by the monotonicity value.

Community detection has a very important role in data processing and analysis, which is very hot in recent years. However, traditional algorithms have shortcomings in both time complexity and precision. In this paper, we introduce a Modified Genetic Algorithm (MGA) that with alleles encoding and half uniform crossover to detect community structure. In the algorithm, each allele of the chromosome stands for the community index of the corresponding node. At the same time, half uniform crossover can better prevent the elite individuals from destroying. And we choose modularity function as its fitness function. It does not need to know how many communities the network has. In order to identify our algorithm is effective. We use both artificial random network and real networks to test our algorithm. The experimental results show that the MGA algorithm can be applied to community detection, and its accuracy and time complexity can reach the effect of classical algorithms.

Identifying influential spreaders in complex networks is crucial in understanding, controlling and accelerating spreading processes for diseases, information, innovations, behaviors, and so on. We proposed a semi-local-information-based algorithm named the adaptive weighted link model (AWLM), which classifies the links in the subgraph made up of the second-order neighbors of nodes and gives them different weights adaptively. The adaptive weighted link model is completely depends on the semi-local topological structure and thus can be calculated not only faster but also under the case where the global topology is not known, especially when the network is sparse, the time complexity is approximate linear. Empirical analyses of the Susceptible-Infected-Recovered (SIR) spreading dynamics on ten real networks show that the adaptive weighted link model always perform the best in comparison with well-known state-of-the-art methods.