Search

As introduced by Bollobás, a graph G$$ G $$ is weakly H$$ H $$‐saturated if the complete graph Kn$$ {K}_n $$ is obtained by iteratively completing copies of H$$ H $$ minus an edge. For all graphs H$$ H $$, we obtain an asymptotic lower bound for the critical threshold pc$$ {p}_c $$, at which point the Erdős–Rényi graph 풢n,p is likely to be weakly H$$ H $$‐saturated. We also prove an upper bound for pc$$ {p}_c $$, for all H$$ H $$ which are, in a sense, strictly balanced. In particular, we improve the upper bound by Balogh, Bollobás, and Morris for H=Kr$$ H={K}_r $$, and we conjecture that this is sharp up to constants. [ABSTRACT FROM AUTHOR]

Let F be a family of r -uniform hypergraphs. The random Turán number ex (G n , p r , F) is the maximum number of edges in an F -free subgraph of G n , p r , where G n , p r is the Erdős-Rényi random r -graph with parameter p. Let C ℓ r denote the r -uniform linear cycle of length ℓ. For p ≥ n − r + 2 + o (1) , Mubayi and Yepremyan showed that ex (G n , p r , C 2 ℓ r) ≤ max ⁡ { p 1 2 ℓ − 1 × n 1 + r − 1 2 ℓ − 1 + o (1) , p n r − 1 + o (1) }. This upper bound is not tight when p ≤ n − r + 2 + 1 2 ℓ − 2 + o (1). In this paper, we close the gap for r ≥ 4. More precisely, we show that ex (G n , p r , C 2 ℓ r) = Θ (p n r − 1) when p ≥ n − r + 2 + 1 2 ℓ − 1 + o (1). Similar results have recently been obtained independently in a different way by Mubayi and Yepremyan. For r = 3 , we significantly improve Mubayi and Yepremyan's upper bound. Moreover, we give reasonably good upper bounds for the random Turán numbers of Berge even cycles, which improve previous results of Spiro and Verstraëte. [ABSTRACT FROM AUTHOR]

We study the weak Ks ${K}_{s}$‐saturation number of the Erdős–Rényi random graph G(n,p) ${\mathbb{G}}(n,p)$, denoted by wsat(G(n,p),Ks) $\text{wsat}({\mathbb{G}}(n,p),{K}_{s})$, where Ks ${K}_{s}$ is the complete graph on s $s$ vertices. In 2017, Korándi and Sudakov proved that the weak Ks ${K}_{s}$‐saturation number of Kn ${K}_{n}$ is stable, in the sense that it remains the same after removing edges with constant probability. In this paper, we prove that there exists a threshold for this stability property and give upper and lower bounds on the threshold. This generalizes the result of Korándi and Sudakov. A general upper bound on wsat(G(n,p),Ks) $\text{wsat}({\mathbb{G}}(n,p),{K}_{s})$ is also provided. [ABSTRACT FROM AUTHOR]

Let G$$ G $$ be a d$$ d $$‐regular graph on n$$ n $$ vertices. Frieze, Gould, Karoński, and Pfender began the study of the following random spanning subgraph model H=H(G)$$ H=H(G) $$. Assign independently to each vertex v$$ v $$ of G$$ G $$ a uniform random number x(v)∈[0,1]$$ x(v)\in \left[0,1\right] $$, and an edge (u,v)$$ \left(u,v\right) $$ of G$$ G $$ is an edge of H$$ H $$ if and only if x(u)+x(v)≥1$$ x(u)+x(v)\ge 1 $$. Addressing a problem of Alon and Wei, we prove that if d=o(n/(logn)12)$$ d=o\left(n/{\left(\log n\right)}^{12}\right) $$, then with high probability, for each nonnegative integer k≤d$$ k\le d $$, there are (1+o(1))n/(d+1)$$ \left(1+o(1)\right)n/\left(d+1\right) $$ vertices of degree k$$ k $$ in H$$ H $$. [ABSTRACT FROM AUTHOR]

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree. [ABSTRACT FROM AUTHOR]

Varimax factor rotations, while popular among practitioners in psychology and statistics since being introduced by Kaiser (1958) , have historically been viewed with skepticism and suspicion by some theoreticians and mathematical statisticians. Now, work by Rohe & Zeng (2023) provides new, fundamental insight: varimax rotations provably perform statistical estimation in certain classes of latent variable models when paired with spectral-based matrix truncations for dimensionality reduction. We build on this new-found understanding of varimax rotations by developing further connections to network analysis and spectral methods rooted in entrywise matrix perturbation analysis. Concretely, this paper establishes the asymptotic multivariate normality of vectors in varimax-transformed Euclidean point clouds that represent low-dimensional node embeddings in certain latent space random graph models. We address related concepts including network sparsity, data denoising and the role of matrix rank in latent variable parameterizations. Collectively, these findings, at the confluence of classical and contemporary multivariate analysis, reinforce methodology and inference procedures grounded in matrix factorization-based techniques. Numerical examples illustrate our findings and supplement our discussion. [ABSTRACT FROM AUTHOR]

In this note, we consider the width of a supercritical random graph according to some commonly studied width measures. We give short, direct proofs of results of Lee, Lee and Oum, and of Perarnau and Serra, on the rank‐ and tree‐width of the random graph G(n,p) $G(n,p)$ when p=1+ϵn $p=\frac{1+\epsilon }{n}$ for ϵ>0 $\epsilon \gt 0$ constant. Our proofs avoid the use of black box results on the expansion properties of the giant component in this regime, and so as a further benefit we obtain explicit bounds on the dependence of these results on ϵ $\epsilon $. Finally, we also consider the width of the random graph in the weakly supercritical regime, where ϵ=o(1) $\epsilon =o(1)$ and ϵ3n→∞ ${\epsilon }^{3}n\to \infty $. In this regime, we determine, up to a constant multiplicative factor, the rank‐ and tree‐width of G(n,p) $G(n,p)$ as a function of n $n$ and ϵ $\epsilon $. [ABSTRACT FROM AUTHOR]

Exploration in complex networks has surged. Centrality measures play a pivotal role in pinpointing essential components within these networks. Previous work focus on nodes with the highest Betweenness centrality through extensive simulations. This paper analyzes the attack and/or defense strategy using one more centrality metric, bridging centrality and Bridging-Betweenness Fusion Attack (combination of both betweenness and bridging centrality). Our two-fold contribution is (1) Using high centrality removal as an attacking strategy and inspired by the dynamic node removal process, recalculated node method after each node removal is proposed. (2) In our defense techniques, new nodes are added to existing lower centrality nodes. They are added after attacks to restore the graph's connectivity according to proposed defense strategies. Note that some attacks and defense techniques were already introduced while others are presented first time, e.g., the combination of two centrality measures for attack and a bridging-based defense strategy. This innovative approach presents a promising advancement in enhancing the resilience and fortification of complex networks against potential attacks, signifying a notable advantage of this work. [ABSTRACT FROM AUTHOR]

We consider a large random network, in which the performance of a node depends upon that of its neighbours and some external random influence factors. This results in random vector valued fixed-point (FP) equations in large dimensional spaces, and our aim is to study their almost-sure solutions. An underlying directed random graph defines the connections between various components of the FP equations. Existence of an edge between nodes i, j implies the i-th FP equation depends on the j-th component. We consider a special case where any component of the FP equation depends upon an appropriate aggregate of that of the random 'neighbour' components. We obtain finite dimensional limit FP equations in a much smaller dimensional space, whose solutions aid to approximate the solution of FP equations for almost all realizations, as the number of nodes increases. We use Maximum theorem for non-compact sets to prove this convergence.We apply the results to study systemic risk in an example financial network with large number of heterogeneous entities. We utilized the simplified limit system to analyse trends of default probability (probability that an entity fails to clear its liabilities) and expected surplus (expected-revenue after clearing liabilities) with varying degrees of interconnections between two diverse groups. We illustrated the accuracy of the approximation using exhaustive Monte-Carlo simulations.Our approach can be utilized for a variety of financial networks (and others); the developed methodology provides approximate small-dimensional solutions to large-dimensional FP equations that represent the clearing vectors in case of financial networks. [ABSTRACT FROM AUTHOR]

The biclique partition number of a graph G = (V , E) , denoted b p (G) , is the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that b p (G) ≤ n − α (G) , where α (G) is the maximum size of an independent set of G. Erdős conjectured in the 80's that for almost every graph G equality holds; i.e., if G = G n , 1 / 2 then b p (G) = n − α (G) with high probability. Alon showed that this is false. We show that the conjecture of Erdős is true if we instead take G = G n , p , where p is constant and less than a certain threshold value p 0 ≈ 0.312. This verifies a conjecture of Chung and Peng for these values of p. We also show that if p 0 < p < 1 / 2 then b p (G n , p) = n − (1 + Θ (1)) α (G n , p) with high probability. [ABSTRACT FROM AUTHOR]

Networks (graphs) permeate scientific fields such as biology, social science, economics, etc. Empirical studies have shown that real-world networks are often heterogeneous, that is, the degrees of nodes do not concentrate on a number. Recently, the Rényi index was tentatively used to measure network heterogeneity. However, the validity of the Rényi index in network settings is not theoretically justified. In this paper, we study this problem. We derive the limit of the Rényi index of a heterogeneous Erdös–Rényi random graph and a power-law random graph, as well as the convergence rates. Our results show that the Erdös–Rényi random graph has asymptotic Rényi index zero and the power-law random graph (highly heterogeneous) has asymptotic Rényi index one. In addition, the limit of the Rényi index increases as the graph gets more heterogeneous. These results theoretically justify the Rényi index is a reasonable statistical measure of network heterogeneity. We also evaluate the finite-sample performance of the Rényi index by simulation. [ABSTRACT FROM AUTHOR]

For graphs G and H , let G ⟶ k H signify that any k -edge coloring of G contains a monochromatic H as a subgraph. Let G (K 2 (N) , p) be random graph spaces with edge probability p , where K 2 (N) is the complete N × N bipartite graph. Let C 2 n be a cycle of length 2 n and let k = 2 , 3. It is shown for any ϵ > 0 , there exists T = T (ϵ) > 0 such that if n p > T , then Pr [ G (K 2 ((k + ϵ) n) , p) ⟶ k C 2 n ] → 1 as n → ∞ , for which the proof relies heavily on the sparse regularity lemma for multipartite graphs. [ABSTRACT FROM AUTHOR]

We describe a robust methodology, based on the martingale argument of Nachmias and Peres and random walk estimates, to obtain simple upper and lower bounds on the size of a maximal component in several random graphs at criticality. Even though the main result is not new, we believe the material presented here is interesting because it unifies several proofs found in the literature into a common framework. More specifically, we give easy-to-check conditions that, when satisfied, allow an immediate derivation of the above-mentioned bounds. [ABSTRACT FROM AUTHOR]

We prove that the size of the maximum induced forest (of bounded and unbounded degree) in the binomial random graph for with an arbitrary fixed is concentrated in an interval of size . We also show 2-point concentration for the size of the maximum induced forest (and tree) of bounded degree in for p = const. [ABSTRACT FROM AUTHOR]

Many real-world networks exhibit the phenomenon of edge clustering,which is typically measured by the average clustering coefficient. Recently,an alternative measure, the average closure coefficient, is proposed to quantify local clustering. It is shown that the average closure coefficient possesses a number of useful properties and can capture complementary information missed by the classical average clustering coefficient. In this paper, we study the asymptotic distribution of the average closure coefficient of a heterogeneous Erdős–Rényi random graph. We prove that the standardized average closure coefficient converges in distribution to the standard normal distribution. In the Erdős–Rényi random graph,the variance of the average closure coefficient exhibits the same phase transition phenomenon as the average clustering coefficient. [ABSTRACT FROM AUTHOR]

In this paper we study acyclic colouring in the random subgraph G of the complete graph Kn on n vertices where each edge is present with probability p, independent of the other edges. We show that unlike the ordinary chromatic number, the acyclic chromatic number exhibits a phase transition from sub-linear to linear growth as the edge probability increases, even in the sparse regime and obtain estimates for the critical exponent. We show that allowing for a small relaxation in the acyclic colouring condition allows for sub-linear growth for all values of the edge probability exponent. We also study a generalization of unique colourings where we impose the condition that at least one vertex in any copy of a given tree has a unique colour and obtain bounds for the minimum number of colours needed for such a colouring. [ABSTRACT FROM AUTHOR]

Abstract Exploration in complex networks has surged. Centrality measures play a pivotal role in pinpointing essential components within these networks. Previous work focus on nodes with the highest Betweenness centrality through extensive simulations. This paper analyzes the attack and/or defense strategy using one more centrality metric, bridging centrality and Bridging-Betweenness Fusion Attack (combination of both betweenness and bridging centrality). Our two-fold contribution is (1) Using high centrality removal as an attacking strategy and inspired by the dynamic node removal process, recalculated node method after each node removal is proposed. (2) In our defense techniques, new nodes are added to existing lower centrality nodes. They are added after attacks to restore the graph’s connectivity according to proposed defense strategies. Note that some attacks and defense techniques were already introduced while others are presented first time, e.g., the combination of two centrality measures for attack and a bridging-based defense strategy. This innovative approach presents a promising advancement in enhancing the resilience and fortification of complex networks against potential attacks, signifying a notable advantage of this work.

AbstractThis article revisits the classical concept of network modularity and its spectral relaxations used throughout graph data analysis. We formulate and study several modularity statistic variants for which we establish asymptotic distributional results in the large-network limit for networks exhibiting nodal community structure. Our work facilitates testing for network differences and can be used in conjunction with existing theoretical guarantees for stochastic blockmodel random graphs. Our results are enabled by recent advances in the study of low-rank truncations of large network adjacency matrices. We provide confirmatory simulation studies and real data analysis pertaining to the network neuroscience study of psychosis, specifically schizophrenia. Collectively, this article contributes to the limited existing literature to date on statistical inference for modularity-based network analysis. Supplemental materials for this article are available online. [ABSTRACT FROM AUTHOR]

In the edge-triangle model with edge density close to 1/2 and triangle density below 1/8 we prove that the unique entropy-maximizing graphon is symmetric bipodal. We also prove that, for any edge density e less than e 0 = (3 − 3) / 6 ≈ 0.2113 and triangle density slightly less than e 3, the entropy-maximizing graphon is not symmetric bipodal. We also discuss the implications for an old idea of Landau for using symmetry to give an intrinsic difference between solid and fluid phases of matter. [ABSTRACT FROM AUTHOR]

Summary statistics play an important role in network data analysis. They can provide us with meaningful insight into the structure of a network. The Randić index is one of the most popular network statistics that has been widely used for quantifying information of biological networks, chemical networks, pharmacologic networks, etc. A topic of current interest is to find bounds or limits of the Randić index and its variants. A number of bounds of the indices are available in literature. Recently, there are several attempts to study the limits of the indices in the Erdős–Rényi random graph by simulation. In this paper, we shall derive the limits of the Randić index and its variants of an inhomogeneous Erdős–Rényi random graph. Our results charaterize how network heterogeneity affects the indices and provide new insights about the Randić index and its variants. Finally we apply the indices to several real-world networks. [ABSTRACT FROM AUTHOR]

This paper studies the magnitude homology of graphs focusing mainly on the relationship between its diagonality and the girth. The magnitude and magnitude homology are formulations of the Euler characteristic and the corresponding homology, respectively, for finite metric spaces, first introduced by Leinster and Hepworth–Willerton. Several authors study them restricting to graphs with path metric, and some properties which are similar to the ordinary homology theory have come to light. However, the whole picture of their behaviour is still unrevealed, and it is expected that they catch some geometric properties of graphs. In this article, we show that the girth of graphs partially determines the magnitude homology, that is, the larger girth a graph has, the more homologies near the diagonal part vanish. Furthermore, applying this result to a typical random graph, we investigate how the diagonality of graphs varies statistically as the edge density increases. In particular, we show that there exists a phase transition phenomenon for the diagonality. [ABSTRACT FROM AUTHOR]

In this paper we relate a fundamental parameter of a random graph, its degree sequence, to a simple model of nearly independent binomial random variables. As a result, many interesting functions of the joint distribution of graph degrees, such as the distribution of the median degree, become amenable to estimation. Our result is established by proving an asymptotic formula conjectured in 1990 for the number of graphs with given degree sequence. In particular, this gives an asymptotic formula for the number of d-regular graphs for all d, as n→∞. The key to our results is a new approach to estimating ratios between point probabilities in the space of degree sequences of the random graph, including analysis of fixed points of the associated operators. [ABSTRACT FROM AUTHOR]

We revisit an old topic in algorithms, the deterministic walk on a finite graph which always moves toward the nearest unvisited vertex until every vertex is visited. There is an elementary connection between this cover time and ball-covering (metric entropy) measures. For some familiar models of random graphs, this connection allows the order of magnitude of the cover time to be deduced from first passage percolation estimates. Establishing sharper results seems a challenging problem.

For reaction networks arising in systems biology, the capacity for two or more steady states, that is, multistationarity, is an important property that underlies biochemical switches. Another property receiving much attention recently is absolute concentration robustness (ACR), which means that some species concentration is the same at all positive steady states. In this work, we investigate the prevalence of each property while paying close attention to when the properties occur together. Specifically, we consider a stochastic block framework for generating random networks and prove edge-probability thresholds at which, with high probability, multistationarity appears and ACR becomes rare. We also show that the small window in which both properties occur only appears in networks with many species. Taken together, our results confirm that, in random reversible networks, ACR and multistationarity together, or even ACR on its own, is highly atypical. Our proofs rely on two prior results, one pertaining to the prevalence of networks with deficiency zero and the other "lifting"" multistationarity from small networks to larger ones. [ABSTRACT FROM AUTHOR]

We consider a random geometric hypergraph model based on an underlying bipartite graph. Nodes and hyperedges are sampled uniformly in a domain, and a node is assigned to those hyperedges that lie within a certain radius. From a modelling perspective, we explain how the model captures higher-order connections that arise in real data sets. Our main contribution is to study the connectivity properties of the model. In an asymptotic limit where the number of nodes and hyperedges grow in tandem, we give a condition on the radius that guarantees connectivity. [ABSTRACT FROM AUTHOR]

In this note, we give a precise description of the limiting empirical spectral distribution for the non-backtracking matrices for an Erdős-Rényi graph $G(n,p)$ assuming $np/\log n$ tends to infinity. We show that derandomizing part of the non-backtracking random matrix simplifies the spectrum considerably, and then, we use Tao and Vu's replacement principle and the Bauer-Fike theorem to show that the partly derandomized spectrum is, in fact, very close to the original spectrum. [ABSTRACT FROM AUTHOR]

A fundamental organizing principle of real-world complex networked systems is modularity, where networks have interactions at different levels. In this paper we consider a modular graph G having modules with arbitrary intraconnections and random interconnections between activated vertices in different modules. The vertices in different modules are activated with probability r and linked by an interconnecting edge with probability p independently. We present results regarding the Cheeger constant, robustness, algebraic connectivity as well as the smallest eigenvalue for the Dirichlet Laplacian matrix of G with high probability. Our results suggest that r = (ln n) / n is a potential scaling for the recently observed external field-like phenomena of modular networks in statistical mechanics. [ABSTRACT FROM AUTHOR]

Let G = (V (G) , E (G)) be a graph and let k be an integer. A vertex subset S ⊆ V (G) is called a k -extended dominating set if every vertex u of G satisfies one of the following conditions: the distance between u and S is at most one or there are at least k different vertices s 1 , s 2 , ... , s k ∈ S such that the distance between u and s i (i ∈ [ k ]) is two. The k -extended domination number γ e k (G) of G is the minimum size over all k -extended dominating sets in G. When k = 2 , they are called the extended dominating set and the extended domination number of G , respectively. In this paper, we mainly study the bounds of the extended domination numbers of graphs. First, we obtain the exact values of the extended domination numbers for paths and cycles. And then the Nordhaus–Gaddum bounds for the extended domination numbers are provided. Additionally, we give some bounds of the extended domination numbers for planar graphs with small diameters. Finally, we consider the k -extended domination numbers in Random graphs. [ABSTRACT FROM AUTHOR]

A bi-block graph is a connected graph in which all blocks are complete bipartite graphs. Labeled bi-block graphs and bridgeless bi-block graphs are enumerated exactly and asymptotically by the number of vertices. It is proved that almost all labeled connected bi-block graphs have no bridges. In addition, planar bi-block graphs are enumerated, and an asymptotic estimate is found for the number of such graphs. [ABSTRACT FROM AUTHOR]

Tolerance graphs were introduced in 1982 by M. C. Golumbic and C. L. Monma as a generalization of interval graphs. In this paper, we introduce tolerance fuzzy graphs as a generalization of tolerance graphs, and apply them to a modeling of a transmission of airborne diseases. [ABSTRACT FROM AUTHOR]

We analyze the existence and the size of the giant component in the stationary state of a Markovian model for bipartite multigraphs, in which the movement of the edge ends on one set of vertices of the bipartite graph is a zero-range process, the degrees being static on the other set. The analysis is based on approximations by independent variables and on the results of Molloy and Reed for graphs with prescribed degree sequences. The possible types of phase diagrams are identified by studying the behavior below the zero-range condensation point. As a specific example, we consider the so-called Evans interaction. In particular, we examine the values of a critical exponent, describing the growth of the giant component as the value of the dilution parameter controlling the connectivity is increased above the critical threshold. Rigorous analysis spans a large portion of the parameter space of the model exactly at the point of zero-range condensation. These results, supplemented with conjectures supported by Monte Carlo simulations, suggest that the phenomenological Landau theory for percolation on graphs is not broken by the fluctuations. [ABSTRACT FROM AUTHOR]

We prove that for n \in \mathbb N and an absolute constant C, if p \geq C\log ^2 n / n and L_{i,j} \subseteq [n] is a random subset of [n] where each k\in [n] is included in L_{i,j} independently with probability p for each i, j\in [n], then asymptotically almost surely there is an order-n Latin square in which the entry in the ith row and jth column lies in L_{i,j}. The problem of determining the threshold probability for the existence of an order-n Latin square was raised independently by Johansson [ Triangle factors in random graphs , 2006], by Luria and Simkin [Random Structures Algorithms 55 (2019), pp. 926–949], and by Casselgren and Häggkvist [Graphs Combin. 32 (2016), pp. 533–542]; our result provides an upper bound which is tight up to a factor of \log n and strengthens the bound recently obtained by Sah, Sawhney, and Simkin [ Threshold for Steiner triple systems , arXiv: 2204.03964 , 2022]. We also prove analogous results for Steiner triple systems and 1-factorizations of complete graphs, and moreover, we show that each of these thresholds is at most the threshold for the existence of a 1-factorization of a nearly complete regular bipartite graph. [ABSTRACT FROM AUTHOR]

A simple but powerful network model with n$$ n $$ nodes and m$$ m $$ partly overlapping layers is generated as an overlay of independent random graphs G1,...,Gm$$ {G}_1,\dots, {G}_m $$ with variable sizes and densities. The model is parameterized by a joint distribution Pn$$ {P}_n $$ of layer sizes and densities. When m$$ m $$ grows linearly and Pn→P$$ {P}_n\to P $$ as n→∞$$ n\to \infty $$, the model generates sparse random graphs with a rich statistical structure, admitting a nonvanishing clustering coefficient together with a limiting degree distribution and clustering spectrum with tunable power‐law exponents. Remarkably, the model admits parameter regimes in which bond percolation exhibits two phase transitions: the first related to the emergence of a giant connected component, and the second to the appearance of gigantic single‐layer components. [ABSTRACT FROM AUTHOR]

The continuum limit provides a useful tool for analyzing coupled oscillator networks. Recently, Medvedev (Commun Math Sci 17(4):883–898, 2019) gave a mathematical foundation for such an approach when the networks are defined on single graphs which may be dense or sparse, directed or undirected, and deterministic or random. In this paper, we consider coupled oscillator networks depending on multiple graphs, and extend his results to show that the continuum limit is also valid in this situation. Specifically, we prove that the initial value problem (IVP) of the corresponding continuum limit has a unique solution under general conditions and that the solution becomes the limit of those to the IVP of the networks in some adequate meaning. Moreover, we show that if solutions to the networks are stable or asymptotically stable when the node number is sufficiently large, then so are the corresponding solutions to the continuum limit, and that if solutions to the continuum limit are asymptotically stable, then so are the corresponding solutions to the networks in some weak meaning as the node number tends to infinity. These results can also be applied to coupled oscillator networks with multiple frequencies by regarding the frequencies as a weight matrix of another graph. We illustrate the theory for three variants of the Kuramoto model along with numerical simulations. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Let be the centered and normalized number of cycles of fixed length contained in a generalized random graph with vertices. We obtain a Höffding-type exponential inequality for the tail probability of . [ABSTRACT FROM AUTHOR]

The paper considers the NP-hard problem of calculation the reliability of a network, which elements are subject to accidental failures. As network reliability, we mean the probabilistic connectivity of a random graph with unreliable edges. To evaluate the reliability of a network, a parallel Monte Carlo method is used, improved by checking the connectivity of a particular graph realization simultaneously with the generation of this realization. Based of multi-agent simulation, we study the scalability of this algorithm and tune the parameters for an execution using high-performance supercomputers. [ABSTRACT FROM AUTHOR]

In this paper, we perform analytical and statistical studies of Revan indices on graphs $ G $: $ R(G) = \sum_{uv \in E(G)} F(r_u, r_v) $, where $ uv $ denotes the edge of $ G $ connecting the vertices $ u $ and $ v $, $ r_u $ is the Revan degree of the vertex $ u $, and $ F $ is a function of the Revan vertex degrees. Here, $ r_u = \Delta + \delta - d_u $ with $ \Delta $ and $ \delta $ the maximum and minimum degrees among the vertices of $ G $ and $ d_u $ is the degree of the vertex $ u $. We concentrate on Revan indices of the Sombor family, i.e., the Revan Sombor index and the first and second Revan $ (a, b) $-$ KA $ indices. First, we present new relations to provide bounds on Revan Sombor indices which also relate them with other Revan indices (such as the Revan versions of the first and second Zagreb indices) and with standard degree-based indices (such as the Sombor index, the first and second $ (a, b) $-$ KA $ indices, the first Zagreb index and the Harmonic index). Then, we extend some relations to index average values, so they can be effectively used for the statistical study of ensembles of random graphs.

In this paper, we propose a procedure to test the independence of bivariate censored data, which is generic and applicable to any censoring types in the literature. To test the hypothesis, we consider a rank-based statistic, Kendall's tau statistic. The censored data defines a restricted permutation space of all possible ranks of the observations. We propose the statistic, the average of Kendall's tau over the ranks in the restricted permutation space. To evaluate the statistic and its reference distribution, we develop a Markov chain Monte Carlo (MCMC) procedure to obtain uniform samples on the restricted permutation space and numerically approximate the null distribution of the averaged Kendall's tau. We numerically compare the power of our procedure to existing state of the art procedures in the literature under various censoring types. We apply the procedure to three real data examples with different censoring types, and compare the results with those by existing methods. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , a dominating set is a subset D ⊆ V such that every vertex in V \ D is adjacent with at least one vertex in D. The domination number of G, denoted by γ (G) , is the minimum cardinality of a dominating set in G. Assuming that the graph G = (V , E) is connected, a subset D ⊆ V is said to be a connected dominating set if it is a dominating set and the subgraph G[D] induced by D is connected. The minimum cardinality of a connected dominating set is termed the connected domination number, denoted by γ c (G) . Comparing γ (G) and γ c (G) for a random graph with constant edge probability p, we obtain that the two parameters are asymptotically equal with probability tending to 1 as the number of vertices gets large. We also consider nonconstant edge probability p n tending to zero (where n is the number of vertices). Among other results, we extend an asymptotic formula of Gilbert on the probability of connectivity. [ABSTRACT FROM AUTHOR]

We study Turing bifurcations on one-dimensional random ring networks where the probability of a connection between two nodes depends on the distance between them. Our approach uses the theory of graphons to approximate the graph Laplacian in the limit as the number of nodes tends to infinity by a nonlocal operator---the graphon Laplacian. For the ring networks considered here, we employ center manifold theory to characterize Turing bifurcations in the continuum limit in a manner similar to the classical partial differential equation case and classify these bifurcations as sub-/super-/transcritical. We derive estimates that relate the eigenvalues and eigenvectors of the finite graph Laplacian to those of the graphon Laplacian. We are then able to show that, for a sufficiently large realization of the network, with high probability the bifurcations that occur in the finite graph are well approximated by those in the graphon limit. The number of nodes required depends on the spectral gap between the critical eigenvalue and the remaining ones; the smaller this gap is, the more nodes are required to guarantee that the graphon and graph bifurcations are similar. We demonstrate that if this condition is not satisfied, then the bifurcations that occur in the finite network can differ significantly from those in the graphon limit. [ABSTRACT FROM AUTHOR]

Consider two independent Erdős–Rényi G (N , 1 / 2) graphs. We show that with probability tending to 1 as N → ∞ , the largest induced isomorphic subgraph has size either ⌊ x N − ε N ⌋ or ⌊ x N + ε N ⌋ , where x N = 4 log 2 ⁡ N − 2 log 2 ⁡ log 2 ⁡ N − 2 log 2 ⁡ (4 / e) + 1 and ε N = (4 log 2 ⁡ N) − 1 / 2. Using similar techniques, we also show that if Γ 1 and Γ 2 are independent G (n , 1 / 2) and G (N , 1 / 2) random graphs, then Γ 2 contains an isomorphic copy of Γ 1 as an induced subgraph with high probability if n ≤ ⌊ y N − ε N ⌋ and does not contain an isomorphic copy of Γ 1 as an induced subgraph with high probability if n > ⌊ y N + ε N ⌋ , where y N = 2 log 2 ⁡ N + 1 and ε N is as above. [ABSTRACT FROM AUTHOR]

The celebrated canonical Ramsey theorem of Erdős and Rado implies that for a given graph H, if n is sufficiently large then any colouring of the edges of K n gives rise to copies of H that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions of this result and the threshold at which the random graph G(n,p) inherits the canonical Ramsey properties of K n. Our main result here pins down this threshold when we focus on colourings that are constrained by some prefixed lists. This result is applied in an accompanying work of the authors on the threshold for the canonical Ramsey property (with no list constraints) in the case that H is an even cycle. [ABSTRACT FROM AUTHOR]

We consider a specific random graph which serves as a disordered medium for a particle performing biased random walk. Take a two-sided infinite horizontal ladder and pick a random spanning tree with a certain edge weight c for the (vertical) rungs. Now take a random walk on that spanning tree with a bias β > 1 to the right. In contrast to other random graphs considered in the literature (random percolation clusters, Galton–Watson trees) this one allows for an explicit analysis based on a decomposition of the graph into independent pieces. We give an explicit formula for the speed of the biased random walk as a function of both the bias β and the edge weight c. We conclude that the speed is a continuous, unimodal function of β that is positive if and only if β < β c (1) for an explicit critical value β c (1) depending on c. In particular, the phase transition at β c (1) is of second order. We show that another second order phase transition takes place at another critical value β c (2) < β c (1) that is also explicitly known: For β < β c (2) the times the walker spends in traps have second moments and (after subtracting the linear speed) the position fulfills a central limit theorem. We see that β c (2) is smaller than the value of β which achieves the maximal value of the speed. Finally, concerning linear response, we confirm the Einstein relation for the unbiased model ( β = 1 ) by proving a central limit theorem and computing the variance. [ABSTRACT FROM AUTHOR]

The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g. to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence, ES-MC carries out a large number of small changes, called edge switches, to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate uniform samples. In this work, we study the problem of executing edge switches in parallel. We discuss parallelizations of ES-MC, but find that this approach suffers from complex dependencies between edge switches. For this reason, we propose the Global Edge Switching Markov Chain (G-ES-MC), an ES-MC variant with simpler dependencies. We show that G-ES-MC converges to the uniform distribution and design shared-memory parallel algorithms for ES-MC and G-ES-MC. In an empirical evaluation, we provide evidence that G-ES-MC requires not more switches than ES-MC (and often fewer), and demonstrate the efficiency and scalability of our parallel G-ES-MC implementation. • We propose a new switch Markov Chain for sampling simple undirected graphs. • This Markov Chain exhibits more parallelism due to less dependencies between steps. • We present a shared-memory parallel algorithm for our Markov Chain. • Our parallelization is exact by accounting for all dependencies between steps. • We empirically investigate the mixing time, efficiency and scalability of our solution. [ABSTRACT FROM AUTHOR]

If we pick n random points uniformly in [0, 1] d and connect each point to its c d log n-nearest neighbors, where d ≥ 2 is the dimension and c d is a constant depending on the dimension, then it is well known that the graph is connected with high probability. We prove that it suffices to connect every point to c d,1 log log n points chosen randomly among its c d,2 log n-nearest neighbors to ensure a giant component of size n - o(n) with high probability. This construction yields a much sparser random graph with ~ n log log n instead of ~ n log n edges that has comparable connectivity properties. This result has nontrivial implications for problems in data science where an affinity matrix is constructed: instead of connecting each point to its k nearest neighbors, one can often pick k' ≪ k random points out of the k nearest neighbors and only connect to those without sacrificing quality of results. This approach can simplify and accelerate computation; we illustrate this with experimental results in spectral clustering of large-scale datasets.