Iterated tabu search for identifying community structure in complex networks

A biologically inspired immunization strategy for network epidemiology

Well-known immunization strategies, based on degree centrality, betweenness centrality, or closeness centrality, either neglect the structural significance of a node or require global information about the network. We propose a biologically inspired immunization strategy that circumvents both of these problems by considering the number of links of a focal node and the way the neighbors are connected among themselves. The strategy thus measures the dependence of the neighbors on the focal node, identifying the ability of this node to spread the disease. Nodes with the highest ability in the network are the first to be immunized. To test the performance of our method, we conduct numerical simulations on several computer-generated and empirical networks, using the susceptible-infected-recovered (SIR) model. The results show that the proposed strategy largely outperforms the existing well-known strategies.

•

We study an efficient, bio-inspired immunization strategy for network epidemiology.

•

Inspiration stems from a single-celled, ameba-like organism, Physarum polycephalum.

•

Our strategy goes beyond the node degree in selecting targets for immunization.

•

The strategy performs considerably better than several well-known competitors.

Immunization strategy based on the critical node in percolation transition

The problem of finding a better immunization strategy for controlling the spreading of the epidemic with limited resources has attracted much attention since its great theoretical significance and wide application. In this letter, we propose a novel and successful targeted immunization strategy based on percolation transition. Our strategy repeatedly looks for the critical nodes for immunizing. The critical node, which leads to the emergence of the giant connected component as the degree threshold increases, is determined when the maximal second-largest connected component disappears. To test the effectiveness of the proposed method, we conduct the experiments on several artificial networks and real-world networks. The results show that the proposed method outperforms the degree centrality strategy, the betweenness centrality strategy and the adaptive degree centrality strategy with 18% to 50% fewer immunized nodes for same amount of immunization.

Overlapping community detection via network dynamics

The modular structure of a network is closely related to the dynamics toward clustering. In this paper, a method for community detection is proposed via the clustering dynamics of a network. The initial phases of the nodes in the network are given randomly, and then they evolve according to a set of dedicatedly designed differential equations. The phases of the nodes are naturally separated into several clusters after a period of evolution, and each cluster corresponds to a community in the network. For the networks with overlapping communities, the phases of the overlapping nodes will evolve to the interspace of the two communities. The proposed method is illustrated with applications to both synthetically generated and real-world complex networks.

Multilevel local search algorithms for modularity clustering

Modularity is a widely used quality measure for graph clusterings. Its exact maximization is NP-hard and prohibitively expensive for large graphs. Popular heuristics first perform a coarsening phase, where local search starting from singleton clusters is used to compute a preliminary clustering, and then optionally a refinement phase, where this clustering is improved by moving vertices between clusters. As a generalization, multilevel heuristics coarsen in several stages, and refine by moving entire clusters from each of these stages, not only individual vertices.

This article organizes existing and new single-level and multilevel heuristics into a coherent design space, and compares them experimentally with respect to their effectiveness (achieved modularity) and runtime. For coarsening by iterated cluster joining, it turns out that the most widely used criterion for joining clusters (modularity increase) is outperformed by other simple criteria, that a recent multistep algorithm [Schuetz and Caflisch 2008] is no improvement over simple single-step coarsening for these criteria, and that the recent multilevel coarsening by iterated vertex moving [Blondel et al. 2008] is somewhat faster but slightly less effective (with refinement). The new multilevel refinement is significantly more effective than the conventional single-level refinement or no refinement, in reasonable runtime.

A comparison with published benchmark results and algorithm implementations shows that multilevel local search heuristics, despite their relative simplicity, are competitive with the best algorithms in the literature.