Revealing the microstructure of the giant component in random graph ensembles

How social network structure impacts the ability of zealots to promote weak opinions

Social networks are often permeated by agents who promote their opinions without allowing for their own mind to be changed. Understanding how these so-called "zealots" act to increase the prevalence of their promoted opinion over the network is important for understanding opinion dynamics. In this work, we consider these promoted opinions to be "weak" and therefore less likely to be accepted relative to the default opinion in the network. We show how the proportion of zealots in the network, the relative strength of the weak opinion, and the structure of the network impact the long-term proportion of those in the network who subscribe to the weak opinion.

Distribution of shortest path lengths on trees of a given size in subcritical Erdős-Rényi networks

In the subcritical regime Erdős-Rényi (ER) networks consist of finite tree components, which are nonextensive in the network size. The distribution of shortest path lengths (DSPL) of subcritical ER networks was recently calculated using a topological expansion [E. Katzav, O. Biham, and A. K. Hartmann, Phys. Rev. E 98, 012301 (2018)2470-004510.1103/PhysRevE.98.012301]. The DSPL, which accounts for the distance ℓ between any pair of nodes that reside on the same finite tree component, was found to follow a geometric distribution of the form P(L=ℓ|L<∞)=(1-c)c^{ℓ-1}, where 0 Collapse

Key Words Collapse

MESH Headings Collapse

Grants Collapse

Affiliation(s)

Barak Budnick Racah Institute of Physics, The Hebrew University, Jerusalem 9190401, Israel
Ofer Biham Racah Institute of Physics, The Hebrew University, Jerusalem 9190401, Israel
Eytan Katzav Racah Institute of Physics, The Hebrew University, Jerusalem 9190401, Israel

Collapse

Degree correlations in graphs with clique clustering

Correlations among the degrees of vertices in random graphs often occur when clustering is present. In this paper we define a joint-degree correlation function for vertices in the giant component of clustered configuration model networks which are composed of clique subgraphs. We use this model to investigate, in detail, the organization among nearest-neighbor subgraphs for random graphs as a function of subgraph topology as well as clustering. We find an expression for the average joint degree of a neighbor in the giant component at the critical point for these networks. Finally, we introduce a novel edge-disjoint clique decomposition algorithm and investigate the correlations between the subgraphs of empirical networks.

Fate of articulation points and bredges in percolation

We investigate the statistics of articulation points and bredges (bridge edges) in complex networks in which bonds are randomly removed in a percolation process. Because of the heterogeneous structure of a complex network, the probability of a node to be an articulation point or the probability of an edge to be a bredge will not be homogeneous across the network. We therefore analyze full distributions of articulation point probabilities as well as bredge probabilities, using a message-passing or cavity approach to the problem. Our methods allow us to obtain these distributions both for large single instances of networks and for ensembles of networks in the configuration model class in the thermodynamic limit, through a single unified approach. We also evaluate deconvolutions of these distributions according to degrees of the node or the degrees of both adjacent nodes in the case of bredges. We obtain closed form expressions for the large mean degree limit of Erdős-Rényi networks. Moreover, we reveal and are able to rationalize a significant amount of structure in the evolution of articulation point and bredge probabilities in response to random bond removal. We find that full distributions of articulation point and bredge probabilities in real networks and in their randomized counterparts may exhibit significant differences even where average articulation point and bredge probabilities do not. We argue that our results could be exploited in a variety of applications, including approaches to network dismantling or to vaccination and islanding strategies to prevent the spread of epidemics or of blackouts in process networks.

p-adic numbers encode complex networks

The Erdős-Rényi (ER) random graph G(n, p) analytically characterizes the behaviors in complex networks. However, attempts to fit real-world observations need more sophisticated structures (e.g., multilayer networks), rules (e.g., Achlioptas processes), and projections onto geometric, social, or geographic spaces. The p-adic number system offers a natural representation of hierarchical organization of complex networks. The p-adic random graph interprets n as the cardinality of a set of p-adic numbers. Constructing a vast space of hierarchical structures is equivalent for combining number sequences. Although the giant component is vital in dynamic evolution of networks, the structure of multiple big components is also essential. Fitting the sizes of the few largest components to empirical data was rarely demonstrated. The p-adic ultrametric enables the ER model to simulate multiple big components from the observations of genetic interaction networks, social networks, and epidemics. Community structures lead to multimodal distributions of the big component sizes in networks, which have important implications in intervention of spreading processes.

Heterogeneity in outcomes of repeated instances of percolation experiments

We investigate the heterogeneity of outcomes of repeated instances of percolation experiments in complex networks using a message-passing approach to evaluate heterogeneous, node-dependent probabilities of belonging to the giant or percolating cluster, i.e., the set of mutually connected nodes whose size scales linearly with the size of the system. We evaluate these both for large finite single instances and for synthetic networks in the configuration model class in the thermodynamic limit. For the latter, we consider both Erdős-Rényi and scale-free networks as examples of networks with narrow and broad degree distributions, respectively. For real-world networks we use an undirected version of a Gnutella peer-to-peer file-sharing network with N=62568 nodes as an example. We derive the theory for multiple instances of both uncorrelated and correlated percolation processes. For the uncorrelated case, we also obtain a closed-form approximation for the large mean degree limit of Erdős-Rényi networks.

Structure of percolating clusters in random clustered networks

We examine the structure of the percolating cluster (PC) formed by site percolation on a random clustered network (RCN) model. Using the generating functions, we formulate the clustering coefficient and assortative coefficient of the PC. We analytically and numerically show that the PC in the highly clustered networks is clustered even at the percolation threshold. The assortativity of the PC depends on the details of the RCN. The PC at the percolation threshold is disassortative when the numbers of edges and triangles of each node are assigned by Poisson distributions, but assortative when each node in an RCN has the same small number of edges, most of which form triangles. This result seemingly contradicts the disassortativity of fractal networks, although the renormalization scheme unveils the disassortative nature of a fractal PC.

Statistical analysis of edges and bredges in configuration model networks

A bredge (bridge-edge) in a network is an edge whose deletion would split the network component on which it resides into two separate components. Bredges are vulnerable links that play an important role in network collapse processes, which may result from node or link failures, attacks, or epidemics. Therefore, the abundance and properties of bredges affect the resilience of the network to these collapse scenarios. We present analytical results for the statistical properties of bredges in configuration model networks. Using a generating function approach based on the cavity method, we calculate the probability P[over ̂](e∈B) that a random edge e in a configuration model network with degree distribution P(k) is a bredge (B). We also calculate the joint degree distribution P[over ̂](k,k^{'}|B) of the end-nodes i and i^{'} of a random bredge. We examine the distinct properties of bredges on the giant component (GC) and on the finite tree components (FC) of the network. On the finite components all the edges are bredges and there are no degree-degree correlations. We calculate the probability P[over ̂](e∈B|GC) that a random edge on the giant component is a bredge. We also calculate the joint degree distribution P[over ̂](k,k^{'}|B,GC) of the end-nodes of bredges and the joint degree distribution P[over ̂](k,k^{'}|NB,GC) of the end-nodes of nonbredge edges on the giant component. Surprisingly, it is found that the degrees k and k^{'} of the end-nodes of bredges are correlated, while the degrees of the end-nodes of nonbredge edges are uncorrelated. We thus conclude that all the degree-degree correlations on the giant component are concentrated on the bredges. We calculate the covariance Γ(B,GC) of the joint degree distribution of end-nodes of bredges and show it is negative, namely bredges tend to connect high degree nodes to low degree nodes. We apply this analysis to ensembles of configuration model networks with degree distributions that follow a Poisson distribution (Erdős-Rényi networks), an exponential distribution and a power-law distribution (scale-free networks). The implications of these results are discussed in the context of common attack scenarios and network dismantling processes.

Generating random networks that consist of a single connected component with a given degree distribution

We present a method for the construction of ensembles of random networks that consist of a single connected component with a given degree distribution. This approach extends the construction toolbox of random networks beyond the configuration model framework, in which one controls the degree distribution but not the number of components and their sizes. Unlike configuration model networks, which are completely uncorrelated, the resulting single-component networks exhibit degree-degree correlations. Moreover, they are found to be disassortative, namely, high-degree nodes tend to connect to low-degree nodes and vice versa. We demonstrate the method for single-component networks with ternary, exponential, and power-law degree distributions.

Large deviations of random walks on random graphs

We study the rare fluctuations or large deviations of time-integrated functionals or observables of an unbiased random walk evolving on Erdös-Rényi random graphs, and construct a modified, biased random walk that explains how these fluctuations arise in the long-time limit. Two observables are considered: the sum of the degrees visited by the random walk and the sum of their logarithm, related to the trajectory entropy. The modified random walk is used for both quantities to explain how sudden changes in degree fluctuations, similar to dynamical phase transitions, are related to localization transitions. For the second quantity, we also establish links between the large deviations of the trajectory entropy and the maximum entropy random walk.

Distribution of shortest path lengths in subcritical Erdős-Rényi networks

Networks that are fragmented into small disconnected components are prevalent in a large variety of systems. These include the secure communication networks of commercial enterprises, government agencies, and illicit organizations, as well as networks that suffered multiple failures, attacks, or epidemics. The structural and statistical properties of such networks resemble those of subcritical random networks, which consist of finite components, whose sizes are nonextensive. Surprisingly, such networks do not exhibit the small-world property that is typical in supercritical random networks, where the mean distance between pairs of nodes scales logarithmically with the network size. Unlike supercritical networks whose structure has been studied extensively, subcritical networks have attracted relatively little attention. A special feature of these networks is that the statistical and geometric properties vary between different components and depend on their sizes and topologies. The overall statistics of the network can be obtained by a summation over all the components with suitable weights. We use a topological expansion to perform a systematic analysis of the degree distribution and the distribution of shortest path lengths (DSPL) on components of given sizes and topologies in subcritical Erdős-Rényi (ER) networks. From this expansion we obtain an exact analytical expression for the DSPL of the entire subcritical network, in the asymptotic limit. The DSPL, which accounts for all the pairs of nodes that reside on the same finite component (FC), is found to follow a geometric distribution of the form P_{FC}(L=ℓ|L<∞)=(1-c)c^{ℓ-1}, where c<1 is the mean degree. Using computer simulations we calculate the DSPL in subcritical ER networks of increasing sizes and confirm the convergence to this asymptotic result. We also obtain exact asymptotic results for the mean distance, 〈L〉_{FC}, and for the standard deviation of the DSPL, σ_{L,FC}, and show that the simulation results converge to these asymptotic results. Using the duality relations between subcritical and supercritical ER networks, we obtain the DSPL on the nongiant components of ER networks above the percolation transition.