Search

The best known solutions for k-message broadcast in dynamic networks of size n require Ω (nk) rounds. In this article, we see if these bounds can be improved by smoothed analysis. To do so, we study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every timestep, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (i.e., one random edge added per round), this natural strategy solves k-message broadcast in \(\tilde{O}(n+k^3)\) rounds, with high probability, beating the best known bounds for \(k=o(\sqrt {n})\) and matching the Ω (n+k) lower bound for static networks for k=O(n1/3) (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: Given ℓ-smoothing (i.e., ℓ random edges added per round), this simple strategy terminates in \(O(kn^{2/3}\log ^{1/3}(n)\ell ^{-1/3})\) rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of \(\tilde{O}(k\sqrt {n})\) rounds to solve k-message broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms the intuition that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply tools developed to support our smoothed analysis to prove an optimal result for k-message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the k-message broadcast problem. [ABSTRACT FROM AUTHOR]

The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximalmatching either take polylogarithmic time which is considered inefficient, or require a strictly superlinear space of n1+Ω(1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [15]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition.We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an O(log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved O(log log Δ) round algorithm for 1 + ε approximate matching. All these results can also be implemented in the congested clique model in the same number of rounds. [ABSTRACT FROM AUTHOR]

We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any \(\gamma›0\) and \(k\ge3\), we show that asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform hypergraph \(G^{(k)}\big(n,n^{\gamma-1}\big)\) in which all \((k-1)\)-sets are contained in at least \(\big(\tfrac12+2\gamma\big)pn\) edges has a tight Hamilton cycle. This is a cyclic ordering of the \(n\) vertices such that each consecutive \(k\) vertices forms an edge.Mathematics Subject Classifications: 05C80, 05C35Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience

In this paper, we study the mean Li-Yorke chaotic phenomenon along any infinite positive integer sequence for infinite-dimensional random dynamical systems. To be precise, we prove that if an injective continuous infinite-dimensional random dynamical system (X , ϕ) over an invertible ergodic Polish system (Ω , F , P , θ) admits a ϕ -invariant random compact set K with positive topological entropy, then given a positive integer sequence a = { a i } i ∈ N with lim i → + ∞ ⁡ a i = + ∞ , for P -a.s. ω ∈ Ω there exists an uncountable subset S (ω) ⊂ K (ω) and ϵ (ω) > 0 such that for any two distinct points x 1 , x 2 ∈ S (ω) , one has lim inf N → + ∞ 1 N ∑ i = 1 N d (ϕ (a i , ω) x 1 , ϕ (a i , ω) x 2) = 0 , lim sup N → + ∞ 1 N ∑ i = 1 N d (ϕ (a i , ω) x 1 , ϕ (a i , ω) x 2) > ϵ (ω) , where d is a compatible complete metric on X. To overcome the difficulties arising in the infinite-dimensional random dynamical systems, we use the regularity of measure to construct the expected measurable partitions and to decompose the distance function. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) with n = | V | vertices, the graph coloring problem is defined as Find a color vector C = (c (v)) , where c (v) ∈ { 1 , 2 , ... , n } denotes the color of vertex v ∈ V , such that no monochromatic edge exists in G and the span , the total number of distinct colors in C , is minimized. Since the problem is NP-complete, a greedy coloring is commonly used for solving it. Greedy coloring visits the vertices of G following an order S , and while visiting a vertex v , it puts the minimum color absent in all neighbors of v. We show that the orders producing span ≤ k , where k ≤ n is a positive integer, can be partitioned into disjoint subsets of equivalent orders. Next, we propose a selective search (SS) algorithm, which takes ρ as an input parameter, selects ≥ ρ orders each from a different set of equivalent orders with high probability, applies greedy coloring on them, and returns the color vector with minimum span. We analytically show that SS performs better than greedy coloring with high probability by evaluating the same number of orders. We propose an incremental search heuristic (ISH), which ρ 1 times execute SS with parameter ρ 2 and returns the color vector with minimum span. A parallel version of ISH called PISH is also proposed, executing ρ 1 SS calls in parallel. We show that ISH hits an optimum coloring for a graph G = (V , E) with χ (G) (Δ (G) + 1) ≤ n e in expected O (| V | + | E |) time and space complexities. We have evaluated ISH and PISH on 136 challenging benchmarks and shown that they significantly outperform 10 existing state-of-the-art algorithms. Finally, we validated our theoretical findings by evaluating ISH and greedy coloring on random graphs. [ABSTRACT FROM AUTHOR]

Neuro‐imaging data can often be represented as statistical networks, especially for functional magnetic resonance imaging (fMRI) data, where brain regions are defined as nodes and the functional interactions between those regions are taken as edges. Such networks are commonly divided into classes depending on the type of edges, namely binary or weighted. A binary network means edges can either be present or absent. Whereas the edges of a weighted network are associated with weight values, and fMRI networks belong to weighted networks. Statistical methods are often adopted to analyse such networks, among which, the exponential random graph model (ERGM) is an important network analysis approach. Typically ERGMs are applied to binary networks, and weighted networks often need to be binarised by arbitrarily selecting a threshold value to define the presence of the edges, which can lead to non‐robustness and loss of valuable edge weight information representing the strength of fMRI interaction in fMRI networks. While it is therefore important to gain deeper insight in adopting ERGM on weighted networks, there only exists a few different ERGM frameworks for weighted networks; some of these are not directly implementable on fMRI networks based on their original proposal. We systematically review, implement, analyse and compare five such frameworks via a simulation study and provide guidelines on each modelling framework as well as conclude the suitability of them on fMRI networks based on a range of criteria. We concluded that Multi‐Layered ERGM is currently the most suitable framework. [ABSTRACT FROM AUTHOR]

Ecological interactions among benthic communities are crucial for shaping marine ecosystems. Understanding these interactions is essential for predicting how ecosystems will respond to environmental changes, invasive species, and conservation management. However, determining the prevalence of species interactions at the community scale is challenging. To overcome this challenge, we employ tools from social network analysis, specifically exponential random graph modelling (ERGM). Our approach explores the relationships among animal and plant organisms within their neighbourhoods. Inspired by companion planting in agriculture, we use spatiotemporal co-occurrence as a measure of mixed species interaction. In other words, the variety of community interactions based on co-occurrence defines what we call 'co-occurrence social diversity'. Our objective is to use ERGM to quantify the proportion of interactions at both the simple paired level and the more complex triangle level, enabling us to measure and compare co-occurrence social diversity. Applying our approach to the Spanish coastal zone across eight sites, five depths, and sunlit/shaded aspects, we discover that 80% of sessile communities, consisting of over a hundred species, exhibit co-occurrence social diversity, with 5% of species consistently forming associations with other species. These organism-level interactions probably have a significant impact on the overall character of the site. This article is part of the theme issue 'Connected interactions: enriching food web research by spatial and social interactions'. [ABSTRACT FROM AUTHOR]

Cloud-based computing networks have taken over the digital landscape. From small non-profits to large multinational corporations, more and more entities have been offloading computing effort to the cloud in order to take advantage of the increased cost-efficiency and scalability of cloud computing. One of the new types of cloud that have emerged is P2P cloud, which disengages from a traditional datacenter setup by allowing users to instead share their own computing hardware into a cloud to reap the benefits of cloud computing's advantages at an even lower cost. However, this new paradigm comes with a slew of challenges: (i) security, when operating with the devices of strangers and (ii) fairness when not operating in a market-based system. This paper aims to address these two issues by proposing an algorithm based on social credits for a P2P cloud system that uses a social network to establish its security measures. We implement our new Social Credit algorithm along with two other task-migration-based load-balancing algorithms adapted for a P2P social cloud in "Cloudsim Plus", and the relative gains are shown in terms of fairness and other related metrics. [ABSTRACT FROM AUTHOR]

A rooted tree is balanced if the degree of a vertex depends only on its distance to the root. In this paper we determine the sharp threshold for the appearance of a large family of balanced spanning trees in the random geometric graph G(n,r,d) ${\mathscr{G}}(n,r,d)$. In particular, we find the sharp threshold for balanced binary trees. More generally, we show that all sequences of balanced trees with uniformly bounded degrees and height tending to infinity appear above a sharp threshold, and none of these appears below the same value. Our results hold more generally for geometric graphs satisfying a mild condition on the distribution of their vertex set, and we provide a polynomial time algorithm to find such trees. [ABSTRACT FROM AUTHOR]

This study examines the information diffusion of "Airbnb discrimination" and related digital activism on Twitter. The model-based inferential network analysis shows a hub-and-spoke network that is loosely connected, indicating that the diffusion network of Airbnb discrimination includes various issues (e.g., antisemitism). The retweet network mirrors the existing offline relationship of users (e.g., those who support opinion leaders of antisemitism), demonstrating a core–periphery structure during the information diffusion process. This study not only empirically tested the retweet relationships but also provided theoretical explanations on how these relationships form through the notion of curative logic and two step information flow theory. The findings of this research challenge the widely accepted assumption about social media that "the more users share, the more people will see." [ABSTRACT FROM AUTHOR]

Online travel communities (OTCs) enable users to interact and share travel information voluntarily. Extant research has primarily focused on the content generated through user interactions but neglected how user interactions are structured. This study employed exponential random graph models to examine the formation of user interactions and the outcomes of homophily in terms of network structure across levels (actor, dyad, triad, and network). A dataset of 2,926 posts and 25,854 replies involving 9,712 users in an OTC was used. Results reveal that users' question initiating and replying ties in OTCs exhibit significant positive structural dependencies in terms of reciprocity, activity spread, generalized transitive closure, and multiple connectivity. Homophily serves as the basis of dyadic interactions and homophilous ties evolve after formation. The study advances hospitality and tourism network research and methodology by going beyond traditional dyadic user interactions, and provides insights into user interactions in OTCs from the social network perspective. [ABSTRACT FROM AUTHOR]

Online social networks (OSNs) are an indispensable part of social communication where people connect and share information. Spammers and other malicious actors use the OSN's power to propagate spam content. In an OSN with mutual relations between nodes, two kinds of spammer detection methods can be employed: feature based and propagation based. However, both of these are incomplete in themselves. The feature-based methods cannot exploit mutual connections between nodes, and propagation-based methods cannot utilize the rich discriminating node features. We propose a hybrid model—Markov enhanced graph attention network (MEGAT)—using graph attention networks (GAT) and pairwise Markov random fields (pMRF) for the spammer detection task. It efficiently utilizes node features as well as propagation information. We experiment our GAT model with a smoother Swish activation function having non-monotonic derivatives, instead of the leakyReLU function. The experiments performed on a real-world Twitter Social Honeypot (TwitterSH) benchmark dataset and subsequent comparative analysis reveal that our proposed MEGAT model outperforms the state-of-the-art models in accuracy, precision–recall area under curve (PRAUC), and F1-score performance measures. [ABSTRACT FROM AUTHOR]

We consider random graph models in which the events describing the inclusion of potential edges have to be independent of each other if the corresponding edges are non‐adjacent and ask: what is the minimum probability ρ(n)$$ \rho (n) $$, such that for any distribution 풢 (in this model) on graphs with n$$ n $$ vertices in which each potential edge has a marginal probability of being present at least ρ(n)$$ \rho (n) $$, a graph drawn from 풢 is connected with non‐zero probability? The answer to this question is sensitive to the formalization of the independence condition. We introduce a strict hierarchy of five conditions, which give rise to at least three different functions ρ(n)$$ \rho (n) $$. For each condition, we provide upper and lower bounds for ρ(n)$$ \rho (n) $$. For the strongest condition, the coloring model, we show that ρ(n)→2−ϕ≈0.38$$ \rho (n)\to 2-\phi \approx 0.38 $$ for n→∞$$ n\to \infty $$. In contrast, for the weakest condition, pairwise independence, we show that ρ(n)$$ \rho (n) $$ lies within O(1/n2)$$ O\left(1/{n}^2\right) $$ of the threshold 1−2/n$$ 1-2/n $$ for completely arbitrary distributions. [ABSTRACT FROM AUTHOR]

In [Trans. Am. Math. Soc. 375 (2022), no. 1, 627–668], Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let r⩾3$$ r\geqslant 3 $$ and let n$$ n $$ be divisible by r$$ r $$. Then, in the random r$$ r $$‐uniform hypergraph process on n$$ n $$ vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: at the time that the last vertex joins a copy of the complete graph Kr$$ {K}_r $$, the random graph process contains a Kr$$ {K}_r $$‐factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the s$$ s $$‐uniform hypergraph process (s⩾3$$ s\geqslant 3 $$). [ABSTRACT FROM AUTHOR]

We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given α∈(0,1)$$ \alpha \in \left(0,1\right) $$, the union of any n$$ n $$‐vertex graph with minimum degree αn$$ \alpha n $$ and the binomial random graph G(n,p)$$ G\left(n,p\right) $$. This is known when α>1/2$$ \alpha >1/2 $$ and we determine the exact perturbed threshold probability in all the remaining cases, that is, for each α≤1/2$$ \alpha \le 1/2 $$. We demonstrate that, as α$$ \alpha $$ ranges over the interval (0,1)$$ \left(0,1\right) $$, the threshold performs a countably infinite number of 'jumps'. Our result has implications on the perturbed threshold for two‐universality, where we also fully address all open cases. [ABSTRACT FROM AUTHOR]

We offer an alternative proof, using the Stein-Chen method, of Bollobás' theorem concerning the distribution of the extreme degrees of a random graph. Our proof also provides a rate of convergence of the extreme degree to its asymptotic distribution. The same method also applies in a more general setting where the probability of every pair of vertices being connected by edges depends on the number of vertices. [ABSTRACT FROM AUTHOR]

A network evolution with predicted tail and extremal indices of PageRank and the Max-Linear Model used as node influence indices in random graphs is considered. The tail index shows a heaviness of the distribution tail. The extremal index is a measure of clustering (or local dependence) of the stochastic process. The cluster implies a set of consecutive exceedances of the process over a sufficiently high threshold. Our recent results concerning sums and maxima of non-stationary random length sequences of regularly varying random variables are extended to random graphs. Starting with a set of connected stationary seed communities as a hot spot and ranking them with regard to their tail indices, the tail and extremal indices of new nodes that are appended to the network may be determined. This procedure allows us to predict a temporal network evolution in terms of tail and extremal indices. The extremal index determines limiting distributions of a maximum of the PageRank and the Max-Linear Model of newly attached nodes. The exposition is provided by algorithms and examples. To validate our theoretical results, our simulation and real data study concerning a linear preferential attachment as a tool for network growth are provided. [ABSTRACT FROM AUTHOR]

In a previous work, we defined and studied random walk labelings of graphs. These are graph labelings that are obtainable by performing a random walk on the graph, such that each vertex is labeled upon its first visit. In this work, we calculate the number of random walk labelings of several natural graph families: The wheel, fan, barbell, lollipop, tadpole, friendship, and snake graphs. Additionally, we prove several combinatorial identities that emerged during the calculations. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing the number of full degree vertices in a spanning tree T of a graph G ; that is, the number of vertices whose degree in T equals its degree in G. In cubic graphs, this problem is equivalent to maximizing the number of leaves in T and minimizing the size of a connected dominating set of G. We provide an algorithm that produces (w.h.p.) a tree with at least 0. 4591 n vertices of full degree (and also, leaves) when run on a random cubic graph. This improves the previously best known lower bound of 0. 4146 n. We also provide lower bounds on the number of full degree vertices in the random regular graph G (n , r) for r ≤ 10. [ABSTRACT FROM AUTHOR]

Innovation in peripheral areas relies more on external linkages to overcome peripherality than in core areas. We study how these linkages are formed, especially through the interaction with diverse networks like transport and investment networks that connect the periphery with external areas. Using data from peripheral Zhejiang, China, we construct a four-layer network with co-patenting and three explanatory layers: transport, investment, and university headquarters-branch linkages. We use multilayer exponential random graph modelling to examine factors driving the formation of the co-patent network, specifically cross-layer interactions between co-patenting and the other three networks. Results show a tendency for the periphery to be linked to the core through co-patenting. All the other three layers have a positive association with the co-patent network, and their intersections show a stronger correlation with the network. This is especially true for the university headquarter-branch network and its intersection with the investment network. The main contribution of this paper is expanding the analysis of peripheral innovation by considering broader intercity networks rather than solely focusing on innovation linkages. Our findings also have policy implications for overcoming innovation constraints in peripheral areas and reducing spatial disparities in Zhejiang and similar regions. [ABSTRACT FROM AUTHOR]

Recent work has exposed the idea that interesting quantum-like (QL) probability laws, including interference effects, can be manifest in classical systems. Here, we propose a model for QL states and QL bits. We suggest a way that huge, complex systems can host robust states that can process information in a QL fashion. Axioms that such states should satisfy are proposed. Specifically, it is shown that building blocks suited for QL states are networks, possibly very complex, that we defined based on k -regular random graphs. These networks can dynamically encode a lot of information that is distilled into the emergent states we can use for QL processing. Although the emergent states are classical, they have properties analogous to quantum states. Concrete examples of how QL functions are possible are given. The possibility of a 'QL advantage' for computing-type operations and the potential relevance for new kinds of function in the brain are discussed and left as open questions. [ABSTRACT FROM AUTHOR]

The study of drug–target interaction plays an important role in the process of drug development. The subject of DTI forecasting has advanced significantly in the last several years, yielding numerous significant research findings and methodologies. Heterogeneous data sources provide richer information and comprehensive perspectives for drug–target interaction prediction, so many existing methods rely on heterogeneous networks, and graph embedding technology becomes an important technology to extract information from heterogeneous networks. These approaches, however, are less concerned with potential noisy information in heterogeneous networks and more focused on the extent of information extraction in those networks. Based on this, a potential DTI predictive network model called FBRWPC is proposed in this paper. It uses a fine-grained similarity selection program to first integrate similarity on similar networks and then a bidirectional random walk graph embedding learning method with restart to obtain an updated drug target interaction matrix. Through the use of similarity selection and fine-grained selection similarity integration, the framework can effectively filter out the noise present in heterogeneous networks and enhance the model's prediction performance. The experimental findings demonstrate that, even after being split up into four distinct types of data sets, FBRWPC can still retain great prediction performance, a sign of the model's resilience and good generalization. [ABSTRACT FROM AUTHOR]

Since today's HPC and data center systems can comprise hundreds of thousands of servers and beyond, it is crucial to equip them with a network that provides high performance. New topologies proposed to achieve such performance need to be evaluated under different traffic conditions, aiming to closely replicate real-world scenarios. While most optimizations should be guided by common traffic patterns, it is essential to ensure that no pathological traffic pattern can compromise the entire system. Determining synthetic adversarial traffic patterns for a network typically relies on a thorough understanding of its topology and routing. In this paper, we address the problem of identifying a generic adversarial traffic pattern for low-diameter direct interconnection networks. We first focus on Random Regular Graphs (RRGs), which represent a typical case for these networks. Moreover, RRGs have been proposed as topologies for interconnection networks due to their superior scalability and expandability, among other advantages. We introduce Ant Mill, an adversarial traffic pattern for RRGs when using routes of minimal length. Secondly, we demonstrate that the Ant Mill traffic pattern is also adversarial in other low-diameter direct interconnection networks such as Slimfly, Dragonfly, and Projective networks. Ant Mill is thoroughly motivated and evaluated, enabling future studies of low-diameter direct interconnection networks to leverage its findings. [ABSTRACT FROM AUTHOR]

In the well known planted clique problem, a clique (or alternatively, an independent set) of size k is planted at random in an Erdos-Renyi random G(n, p) graph, and the goal is to design an algorithm that finds the maximum clique (or independent set) in the resulting graph. We introduce a variation on this problem, where instead of planting the clique at random, the clique is planted by an adversary who attempts to make it difficult to find the maximum clique in the resulting graph. We show that for the standard setting of the parameters of the problem, namely, a clique of size k = n planted in a random G (n , 1 2) graph, the known polynomial time algorithms can be extended (in a non-trivial way) to work also in the adversarial setting. In contrast, we show that for other natural settings of the parameters, such as planting an independent set of size k = n 2 in a G(n, p) graph with p = n - 1 2 , there is no polynomial time algorithm that finds an independent set of size k, unless NP has randomized polynomial time algorithms. [ABSTRACT FROM AUTHOR]

We study the mixing time of a random walker who moves inside a dynamical random cluster model on the d-dimensional torus of side-length n. In this model, edges switch at rate μ between open and closed, following a Glauber dynamics for the random cluster model with parameters p, q. At the same time, the walker jumps at rate 1 as a simple random walk on the torus, but is only allowed to traverse open edges. We show that for small enough p the mixing time of the random walker is of order n 2 / μ . In our proof we construct a non-Markovian coupling through a multi-scale analysis of the environment, which we believe could be more widely applicable. [ABSTRACT FROM AUTHOR]

A mathematical procedure enabling the transformation of an arbitrary tessellation of a surface into a bi-colored, complete graph is introduced. Polygons constituting the tessellation are represented by vertices of the graphs. Vertices of the graphs are connected by two kinds of links/edges, namely, by a green link, when polygons have the same number of sides, and by a red link, when the polygons have a different number of sides. This procedure gives rise to a semi-transitive, complete, bi-colored Ramsey graph. The Ramsey semi-transitive number was established as R t r a n s (3 , 3) = 5 Shannon entropies of the tessellation and graphs are introduced. Ramsey graphs emerging from random Voronoi and Poisson Line tessellations were investigated. The limits ζ = lim N → ∞ N g N r , where N is the total number of green and red seeds, N g and N r , were found ζ = 0.272 ± 0.001 (Voronoi) and ζ = 0.47 ± 0.02 (Poisson Line). The Shannon Entropy for the random Voronoi tessellation was calculated as S = 1.690 ± 0.001 and for the Poisson line tessellation as S = 1.265 ± 0.015. The main contribution of the paper is the calculation of the Shannon entropy of the random point process and the establishment of the new bi-colored Ramsey graph on top of the tessellations. [ABSTRACT FROM AUTHOR]

The employment of two‐sample hypothesis testing in examining random graphs has been a prevalent approach in diverse fields such as social sciences, neuroscience, and genetics. We advance a spectral‐based two‐sample hypothesis testing methodology to test the latent position random graphs. We propose two distinct asymptotic normal statistics, each optimally designed for two different models—the elementary Erdős–Rényi model and the more complex latent position random graph model. For the latter, the spectral embedding of the adjacency matrix was utilized to estimate the test statistic. The proposed method exhibited superior efficacy as it accomplished higher power than the conventional method of mean estimation. To validate our hypothesis testing procedure, we applied it to empirical biological data to discern structural variances in gene co‐expression networks between COVID‐19 patients and individuals who remained unaffected by the disease. [ABSTRACT FROM AUTHOR]

The complexity of metropolitan polycentric governance is still challenging scholars and practitioners, who have mostly been engaged in a normative debate in which scant attention has been paid to the coexistence and interdependence of institutional solutions. The ecology of games framework (EGF) can be used to remedy this gap. By incorporating the analysis of institutional variation into EGF propositions about venues' interdependence, this article examines the mechanisms of metropolitan governance configuration resulting from institutional complexity at the inter‐municipal level. Provincial forums, municipal associations, and inter‐municipal agreements are the policy venues studied in the Santiago Metropolitan Region, Chile. Official documents reporting formal agreements in 2017–2021 help to capture the inter‐municipal governance network to which we apply exponential random graph models (ERGMs). The results show the positive effects of mandated provincial venues on inter‐municipal ties and the absence of the effect of self‐organized municipal associations, tendencies that prevail even when incorporating other relevant covariates into the models. These results nourish the EGF debate about interdependencies between coexisting policy venues, emphasizing the role of the different institutional attributes framing the policy venues and the effects of these differences on governance formation. [ABSTRACT FROM AUTHOR]

The random equiprobable mappings of finite set S into itself are considered. The probability that k fixed elements of S belong to the same connected component is studied. The limit of this probability as|S| → ∞ is found. [ABSTRACT FROM AUTHOR]

The formation of congestion on an urban road network is a key issue for the development of sustainable mobility in future smart cities. In this work, we propose a reductionist approach by studying the stationary states of a simple transport model using a random process on a graph, where each node represents a location and the link weights give the transition rates to move from one node to another, representing the mobility demand. Each node has a maximum flow rate and a maximum load capacity, and we assume that the average incoming flow equals the outgoing flow. In the approximation of the single-step process, we are able to analytically characterize the traffic load distribution on the single nodes using a local maximum entropy principle. Our results explain how congested nodes emerge as the total traffic load increases, analogous to a percolation transition where the appearance of a congested node is an independent random event. However, using numerical simulations, we show that in the more realistic case of synchronous dynamics for the nodes, entropic forces introduce correlations among the node states and favor the clustering of empty and congested nodes. Our aim is to highlight the universal properties of congestion formation and, in particular, to understand the role of traffic load fluctuations as a possible precursor of congestion in a transport network. [ABSTRACT FROM AUTHOR]

We consider dense graph sequences that converge to a connected graphon and prove that the GHP scaling limit of their uniform spanning trees (USTs) is Aldous' Brownian CRT. Furthermore, we are able to extract the precise scaling constant from the limiting graphon. As an example, we can apply this to the scaling limit of the USTs of the Erdös–Rényi sequence (G(n,p))n≥1$$ {\left(G\left(n,p\right)\right)}_{n\ge 1} $$ for any fixed p∈(0,1]$$ p\in \left(0,1\right] $$, and sequences of dense expanders. A consequence of GHP convergence is that several associated quantities of the spanning trees also converge, such as the height, diameter and law of a simple random walk. [ABSTRACT FROM AUTHOR]

For a graph G$$ G $$ and p∈[0,1]$$ p\in \left[0,1\right] $$, we denote by Gp$$ {G}_p $$ the random sparsification of G$$ G $$ obtained by keeping each edge of G$$ G $$ independently, with probability p$$ p $$. We show that there exists a C>0$$ C>0 $$ such that if p≥C(logn)1/3n−2/3$$ p\ge C{\left(\log n\right)}^{1/3}{n}^{-2/3} $$ and G$$ G $$ is an n$$ n $$‐vertex graph with n∈3ℕ$$ n\in 3\mathbb{N} $$ and δ(G)≥2n3$$ \delta (G)\ge \frac{2n}{3} $$, then with high probability Gp$$ {G}_p $$ contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of C$$ C $$, are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corrádi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to p=1$$ p=1 $$ in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in G(n,p)$$ G\left(n,p\right) $$ (corresponding to G=Kn$$ G={K}_n $$ in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least 2n3$$ \frac{2n}{3} $$ which gets close to the truth. [ABSTRACT FROM AUTHOR]

For two independent Erdős–Rényi graphs G(n,p)$$ \mathbf{G}\left(n,p\right) $$, we study the maximal overlap (i.e., the number of common edges) of these two graphs over all possible vertex correspondence. We present a polynomial‐time algorithm which finds a vertex correspondence whose overlap approximates the maximal overlap up to a multiplicative factor that is arbitrarily close to 1. As a by‐product, we prove that the maximal overlap is asymptotically n2α−1$$ \frac{n}{2\alpha -1} $$ for p=n−α$$ p={n}^{-\alpha } $$ with some constant α∈(1/2,1)$$ \alpha \in \left(1/2,1\right) $$. [ABSTRACT FROM AUTHOR]

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 N be the number of triangles in an Erdős–Rényi graph G (n , p) on n vertices with edge density p = d / n , where d > 0 is a fixed constant. It is well known that N weakly converges to the Poisson distribution with mean d 3 / 6 as n → ∞ . We address the upper tail problem for N, namely, we investigate how fast k must grow, so that P (N ≥ k) is not well approximated anymore by the tail of the corresponding Poisson variable. Proving that the tail exhibits a sharp phase transition, we essentially show that the upper tail is governed by Poisson behavior only when k 1 / 3 log k < (3 2 - o (1)) 2 / 3 log n (sub-critical regime) as well as pin down the tail behavior when k 1 / 3 log k > (3 2 + o (1)) 2 / 3 log n (super-critical regime). We further prove a structure theorem, showing that the sub-critical upper tail behavior is dictated by the appearance of almost k vertex-disjoint triangles whereas in the supercritical regime, the excess triangles arise from a clique like structure of size approximately (6 k) 1 / 3 . This settles the long-standing upper-tail problem in this case, answering a question of Aldous, complementing a long sequence of works, spanning multiple decades and culminating in Harel et al. (Duke Math J 171(10):2089–2192, 2022), which analyzed the problem only in the regime p ≫ 1 n. The proofs rely on several novel graph theoretical results which could have other applications. [ABSTRACT FROM AUTHOR]

Computer simulations are a powerful tool in many fields of research. This also applies to the broadly understood analysis of experimental data, which are frequently burdened with multiple imperfections. Often the underlying imprecision or vagueness can be suitably described in terms of fuzzy numbers which enable also the capture of subjectivity. On the other hand, due to the random nature of the experimental data, the tools for their description must take into account their statistical nature. In this way, we come to random fuzzy numbers that model fuzzy data and are also solidly formalized within the probabilistic setting. In this contribution, we introduce the so-called LR random fuzzy numbers that can be used in various Monte-Carlo simulations on fuzzy data. The proposed method of generating fuzzy numbers with membership functions given by probability densities is both simple and rich, well-grounded mathematically, and has a high application potential. [ABSTRACT FROM AUTHOR]

This research paper presents a methodology for improving wireless sensor network (WSN) performance by leveraging centrality measures, including degree, betweenness, closeness, eigenvector, and Katz centrality. Employing a random walk graph model, this study constructs networks with 30 and 50 nodes to investigate the impact of these centrality metrics on routing decisions to optimize energy efficiency, minimize latency, and enhance overall network reliability. Additionally, the paper provides a comprehensive analysis of the relationships among these centrality measures through various correlation techniques, such as Pearson correlation, Kendall rank correlation, and Spearman correlation, offering insights into how these metrics can effectively improve WSN operations. [ABSTRACT FROM AUTHOR]

This study examines patterns of interorganizational collaboration for hazard mitigation in metropolitan regions. Metropolitan regions whose populations reside in vulnerable places may experience extreme events. Facilitation of collective actions among organizations is critical for building resilient urban communities. Although the literature highlights the importance of interorganizational collaboration in disaster management, patterns of interorganizational collaboration for hazard mitigation in urban settings has been underexamined. Building on an institutional collective action framework, this study argues that hazard mitigation efforts tend to be localized. We tested this hypothesis using survey data collected in the Busan and Ulsan metropolitan regions, where natural disasters are problematic. An exponential random graph model confirmed the presence of a bonding strategy, which builds trust with municipalities and organizations within the region and creates interorganizational collaboration. We found that local public agencies tend to collaborate with organizations in the same jurisdictions or at higher levels of government. Practical Applications: In the context of emergency management, hazard mitigation plays a crucial role in building resilient communities. Public agencies implement hazard mitigation actions by collaborating with other agencies and groups. Local agencies may require financial or logistical support from regional or national governments to effectively implement hazard mitigation actions. Agencies can foster collaborative relationships and strengthen their commitment to hazard mitigation efforts through regular interactions and by forming collaborative groups. Furthermore, collaboration among agencies within a region allows for shared interests in hazard mitigation and the strengthening of commitments. These strategies will help public agencies to implement hazard mitigation actions that utilize resources from a broad range of organizations. [ABSTRACT FROM AUTHOR]

One of the most interesting open problems of a digraph is Seymour's Second Neighborhood Conjecture (SSNC), which asserts that every digraph D has a vertex v satisfying d + + (v) ≥ d + (v) , we called such vertex v a Seymour vertex. Sullivan stated two compromise conjectures on SSNC. Let v ∈ V (D) if d + + (v) ≥ d − (v) , then v is called a Sullivan-1 vertex. If d + + (v) + d + (v) ≥ 2 d − (v) , then v is called a Sullivan-2 vertex. In this paper, we give a condition that the digraph has n Seymour vertices. And we also prove that every random tournament T n has n Sullivan-1 vertices and at least n 2 − n log n Sullivan-2 vertices with high probability. [ABSTRACT FROM AUTHOR]

The increasing institutionalization of regulatory oversight worldwide has not resulted in the creation of numerous formal channels of transnational regulatory oversight cooperation. Despite its puzzling nature, this circumstance has barely attracted scholarly attention. Additionally, the study of cooperation across transgovernmental regulatory networks with actors having low autonomy from central governments remains under‐researched. We fill these literature gaps by applying insights from the policy networks literature to identify drivers of transnational regulatory oversight cooperation. Combining Exponential Random Graph Models with semi‐structured interviews, we show that commonalities in administrative traditions drive cooperation. Innovative bodies become sources of best practices. Conversely, exchanges between countries with similar regulatory oversight settings or preferences are rare, perhaps due to their low independence from their political principals. These results suggest that regulatory oversight actors use relational opportunities and general country features as cues for transnational cooperation, instead of adopting strategic partnerships with better matches. [ABSTRACT FROM AUTHOR]

AbstractThis study explores the impact of prior participation in summer care programs (SCPs) on children’s physical activity (PA) and social connections at the start (T1) and end (T2) of summer. Children aged 8–12 reported their attendance, PA, and social connections (T1: n = 100, T2: n = 77). T-tests and exponential random graph modeling were used to analyze data. Results showed that prior attendance didn’t significantly affect friend count or PA. New connections formed over time were more likely among children with similar PA levels. The study highlights SCPs’ role in integrating new children into social circles without preferential attachment. [ABSTRACT FROM AUTHOR]

We present a renormalization group (RG) analysis of the problem of Anderson localization on a random regular graph (RRG) which generalizes the RG of Abrahams, Anderson, Licciardello, and Ramakrishnan to infinite-dimensional graphs. The RG equations necessarily involve two parameters (one being the changing connectivity of subtrees), but we show that the one-parameter scaling hypothesis is recovered for sufficiently large system sizes for both eigenstates and spectrum observables. We also explain the nonmonotonic behavior of dynamical and spectral quantities as a function of the system size for values of disorder close to the transition, by identifying two terms in the beta function of the running fractal dimension of different signs and functional dependence. Our theory provides a simple and coherent explanation for the unusual scaling behavior observed in numerical data of the Anderson model on RRG and of many-body localization. [ABSTRACT FROM AUTHOR]

In efforts to address the far-reaching effects of climate change and associated impacts in communities, research on environmental philanthropy suggests that more resources are being allocated to environmental societal challenges. However, understandings about which environmental nonprofits benefit from these funding flows is limited. This study integrates resource dependency theory with elitism and pluralism perspectives to analyze a network of environmental nonprofits and their funders in Texas. Resource dependency and a network-analytic approaches share underlying relationality principles, and we connect those dots by conceptualizing the funding dynamics in Texas as a network of funder-grantee relations. Drawing on statewide survey data (n = 114), we use a network analysis technique – exponential random graph modeling (ERGM) – to analyze funding allocations in Texas through the organizational attributes of environmental nonprofits, their funder-grantee relations, and their community context. We specifically observe elitism in funding allocations in Texas, which is evident in network effects (preferential attachment) and the focal areas of environmental work. However, we find limited evidence that age or resources of the nonprofit are predictive of funding and the most influential factor determining a funder-grantee relationship is the natural hazard risk of the community served by the nonprofit. Our findings suggest interconnected funding dynamics of pluralism and elitism in the Texas environmental philanthropy landscape, prompting further discussion about the potential synergies of these patterns and the implications for environmental funding practices. [ABSTRACT FROM AUTHOR]

This paper addresses a significant gap in drug market literature by examining high-level drug trafficking networks in Japan. We focus on three aspects: the structure of drug importation networks, the impact of transport methods on these structures, and the role of Japan’s mafia, the yakuza. Using novel statistical techniques that extend exponential random graph models (ERGMs) to multi-network samples, we analyse 573 Japanese trial documents on wholesale drug importation. We test the theory that trafficking operations with higher information-processing demands exhibit more efficiency-oriented network structures, while governance-type groups avoid expanding into trade activities. Our findings support these theories, showing that networks with higher information-processing demands are more efficiency-oriented but maintain security. Conversely, smaller networks with simpler transport methods prioritise security and concealment. Additionally, the yakuza do not organisationally engage in drug trafficking; when involved, yakuza members act as independent entrepreneurs. [ABSTRACT FROM AUTHOR]

Motivated by debates about California's net migration loss, we employ valued exponential-family random graph models to analyze the inter-county migration flow network in the United States. We introduce a protocol that visualizes the complex effects of potential underlying mechanisms and perform in silico knockout experiments to quantify their contribution to the California Exodus. We find that racial dynamics contribute to the California Exodus, urbanization ameliorates it, and political climate and housing costs have little impact. Moreover, the severity of the California Exodus depends on how one measures it, and California is not the state with the most substantial population loss. This paper demonstrates how generative statistical models can provide mechanistic insights beyond simple hypothesis-testing. [ABSTRACT FROM AUTHOR]

The passage of the Inflation Reduction Act has been perceived as a substantial shift away from the history of more contentious climate politics in the US. We apply social network methods to interrogate an updated dataset that assesses the degree to which recent policy outcomes are a shift away from earlier policies and positions. We empirically test for homophily, a building block of polarisation, analysing four waves of survey data collected over 12 years from the community of political elites engaged in the issue of climate politics. Using Exponential Random Graph (ERG) modeling, we provide clear evidence that the stances of the top policy actors working on climate change have not shifted substantially. Instead, we document how the policy was successful due to its ability to combine the Administration's desire to support clean energy along with fossil fuel interests' aims of expanding extraction and profiting from a transition away from fossil fuels. [ABSTRACT FROM AUTHOR]

This paper discusses how to derive multidimensional conformable diffusion equation from continuous time random walks process by employing fractional Laplace transform and the conformable fractional derivative defined by Khalil et al in [10]. The results show that there exists intimate relationship between the stretched exponential function and conformable diffusion equation involving the conformable fractional derivative. The relationship is analogous to the relationship between the exponential function and usual diffusion equation involving usual derivative and the relationship between the Mittag-Leffler function and subdiffusion or slow diffusion equation involving Caputo fractional derivative. Multidimensional conformable FokkerPlanck equation is also derived here. The equation describes diffusion process influenced by external force fields. Conformable semigroup associated with the solution to the conformable diffusion equation has similar properties to the properties of the semigroup associated with the solution to usual diffusion except the semigroup property. For sufficiently large time, the graphs of the solution to the conformable diffusion equation and the subdiffusion equation involving Caputo fractional derivative are sufficiently close. Especially, for, the graphs are sufficiently close for . In presence of nonzero constant external force fields, the particle involved in the diffusion process moves faster toward the directions of the external force fields. [ABSTRACT FROM AUTHOR]

High-order structures have been recognised as suitable models for systems going beyond the binary relationships for which graph models are appropriate. Despite their importance and surge in research on these structures, their random cases have been only recently become subjects of interest. One of these high-order structures is the chemical hypergraph, which relates couples of subsets (hypervertices) of an arbitrary number of vertices. Here we develop the Erdős–Rényi model for chemical hypergraphs, which corresponds to the random realisation of edges of the complete chemical hypergraph. A particular feature of random chemical hypergraphs is that the ratio between their expected number of edges and their expected degree or size is 3/2 for large number of vertices. We highlight the suitability of chemical hypergraphs for modelling large collections of chemical reactions and the importance of random chemical hypergraphs to analyse the unfolding of chemistry. [ABSTRACT FROM AUTHOR]

In this paper, we study the order of the largest connected component of a random graph having two sources of randomness: first, the graph is chosen randomly from all graphs with a given degree sequence, and then bond percolation is applied. Far from being able to classify all such degree sequences, we exhibit several new threshold phenomena for the order of the largest component in terms of both sources of randomness. We also provide an example of a degree sequence for which the order of the largest component undergoes an unbounded number of jumps in terms of the percolation parameter, giving rise to a behavior that cannot be observed without percolation. [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]