Influencer identification in dynamical complex systems

Abstract

The integrity and functionality of many real-world complex systems hinge on a small set of pivotal nodes, or influencers. In different contexts, these influencers are defined as either structurally important nodes that maintain the connectivity of networks, or dynamically crucial units that can disproportionately impact certain dynamical processes. In practice, identification of the optimal set of influencers in a given system has profound implications in a variety of disciplines. In this review, we survey recent advances in the study of influencer identification developed from different perspectives, and present state-of-the-art solutions designed for different objectives. In particular, we first discuss the problem of finding the minimal number of nodes whose removal would breakdown the network (i.e. the optimal percolation or network dismantle problem), and then survey methods to locate the essential nodes that are capable of shaping global dynamics with either continuous (e.g. independent cascading models) or discontinuous phase transitions (e.g. threshold models). We conclude the review with a summary and an outlook.

Keywords: influencer identification; k-core percolation; optimal percolation; spreading dynamics; threshold models.

Fig. 1.

Simulations of epidemic processes initiated from different origins. We use a susceptible-infected-removed (SIR) model to simulate epidemic outbreaks in a patient-to-patient contact network from multiple Swedish hospitals [18]. Given the same set of epidemiological parameters (infectious rate and recover rate ), outbreaks initiated from two origins have dramatically different outcomes. In (a) and (b), the epidemic sources have the same number of connections, but the source in (a) locates in a more central region with a higher k-core index. The colour of each node indicates the probability of infection during 1,000 independent realizations of the SIR model.

Fig. 2.

Phase transition in percolation process. (a) The continuous transition of the GC size after the removal of fraction of nodes. and are the critical values for random and optimal percolation, respectively. Insets show illustrations of a connected and fragmented clusters. Red nodes are removed influencers. (b) The discontinuous transition of k-core size after the removal of fraction of nodes. The critical values for random and optimal k-core percolation are marked by and . Left inset shows the k-core of . After the removal of the red node, 3-core collapses and only 2-core is left, as shown in the right inset.

Fig. 3.

An example of k-core decomposition. The highlighted blue and yellow nodes have the same degree , but with different values. Figure is adapted from [17] under permission from Springer Nature.

Fig. 4.

Performance of CI in large-scale real social networks. GCs for a Twitter network (a) and a social network of mobile phone users in Mexico (b) computed using CI, HDA (high degree adaptive), PR (PageRank), HD (high degree) and k-core strategies are compared. Figure is reused from [20] permitted by Springer Nature.

Fig. 5.

Performance of the BPD algorithm in ER and RR networks. Fraction of removed nodes to break ER random networks of mean degree (a) and regular random networks of degree (b). Diamonds show the results obtained from CI. Crosses represent results of the replica-symmetric (RS) mean-field theory. Plus symbols in (b) show the mathematical lower bound (LB) on the minimum size of target nodes. Figure reuse from [48] is permitted by American Physical Society.

Fig. 6.

Performance of the Min-Sum algorithm in an ER network. Relative size of the largest component as a function of the fraction of nodes removed from an ER network (size = 78,125 and average degree ). Comparisons are performed for the Min-Sum algorithm (MS), random (RND), adaptive largest degree (DEG), adaptive eigenvector centrality (EC), adaptive CI and simulated annealing (SA). Figure reuse from [21] is permitted by National Academy of Sciences.

Fig. 7.

Performance of the EI algorithm in an ER network. Relative size of the largest clusters after fraction of nodes are removed from ER networks with size and average degree . The red dashed curve is obtained by EI with score . The black continuous curve is obtained with for (). The blue dotted line is the result of CI. The inset shows the relationship between and . The dotted line is the result for random strategy. Figure reuse from [49] is permitted by American Physical Society.

Fig. 8.

Performance of the CI-TM algorithm in ER and SF networks. (a) Size of active GC as a function of the fraction of seed for ER networks (, ). The CI-TM algorithm is compared with high degree adaptive (HDA), high degree (HD), PageRank (PR), k-core adaptive (KsA), Random and the Max-Sum (MS) algorithm. Inset shows the critical values identified by HDA and CI-TM for different mean degrees. (b) Results for scale-free networks (, ). Inset presents the critical values for different power-law exponents . Figure reuse from [188] is permitted by Springer Nature.