Search

Intangible cultural heritage (ICH) has the potential to enhance tourism supply and activate tourism resources. This study constructs an alienation and host authenticity model to analyze the attitudes of ICH performers towards support for tourism. Specifically, it investigates the views of giant puppet show performers at the Mount E'mei Scenic Area in China, which is a nationally recognized and first-selected representative traditional drama project of ICH. By employing an asymmetric configuration modeling approach within qualitative comparative analysis, the study identifies six dimensions of ICH performers' alienation (powerlessness, meaninglessness, normlessness, isolation, self-estrangement, and cultural alienation) and three aspects of their host authenticity (personal value, interpersonal value, and ICH value). Based on these findings, the study confirms the impact of ICH performers' alienation, host authenticity, and demographic characteristics on their support for tourism. This understanding is crucial for the development, growth, and continuity of a tourist destination. Specifically, this study contributes to a new comprehension of the combined model of alienation and host authenticity, as well as the support for tourism by a host community as represented by ICH performers, thereby making a significant contribution to the understanding of the impact of ICH. [ABSTRACT FROM AUTHOR]

AbstractThe configuration model is a standard tool for uniformly generating random graphs with a specified degree sequence, and is often used as a null model to evaluate how much of an observed network’s structure can be explained by its degree structure alone. A Markov chain Monte Carlo (MCMC) algorithm, based on a degree-preserving double-edge swap, provides an asymptotic solution to sample from the configuration model. However, accurately and efficiently detecting when this Markov chain is sufficiently close to its stationary distribution remains an unsolved problem. Here, we provide a solution to sample from the configuration model using this standard MCMC algorithm. We develop an algorithm, based on the assortativity of the sampled graphs, for estimating the gap between effectively independent MCMC states, and a computationally efficient gap-estimation heuristic derived from analyzing a corpus of 509 empirical networks. We provide a convergence detection method based on the Dickey-Fuller Generalized Least Squares test, which we show is more accurate and efficient than three alternative Markov chain convergence tests. Supplementary materials for the proposed methods can be found here. [ABSTRACT FROM AUTHOR]

In this work we show that given any integer-valued random variable D with finite mean such that E [ D ] > 2 and P (D ≥ 1) = 1 , it is possible to build a configuration model whose giant component has degree distribution that converges in probability to D and give a way to compute the starting degree distribution to achieve this property. [ABSTRACT FROM AUTHOR]

Centrality measures aim to indicate who is important in a network. Various notions of 'being important' give rise to different centrality measures. In this paper, we study how important the central vertices are for the connectivity structure of the network, by investigating how the removal of the most central vertices affects the number of connected components and the size of the giant component. We use local convergence techniques to identify the limiting number of connected components for locally converging graphs and centrality measures that depend on the vertex's neighbourhood. For the size of the giant, we prove a general upper bound. For the matching lower bound, we specialise to the case of degree centrality on one of the most popular models in network science, the configuration model , for which we show that removal of the highest-degree vertices destroys the giant most. [ABSTRACT FROM AUTHOR]

The paper is devoted to experimental studies of new methods of cognitive modeling by testing them on a variety of artificially created cognitive models. The features of the process of obtaining such models are studied, and the concepts of a formal cognitive map and a formal cognitive model are introduced. An approach to generating a formal cognitive map with given characteristics, based on the use of random graph models, is proposed and partially formalized. A modification of the configuration model has been carried out, and examples of generating formal fuzzy cognitive maps based on it are given. The architecture of a software solution aimed at supporting experimental research in cognitive modeling is described. Directions for further research, both theoretical and applied in nature, are formulated. [ABSTRACT FROM AUTHOR]

Copyright of Tunnel Construction / Suidao Jianshe (Zhong-Yingwen Ban) is the property of Tunnel Construction Editorial Office 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.)

We consider a Markovian model of an SIR epidemic spreading on a contact graph that is drawn uniformly at random from the set of all graphs with n vertices and given vertex degrees. Janson, Luczak and Windridge (Random Struct Alg 45(4):724–761, 2014) prove that the evolution of such an epidemic is well approximated by the solution to a simple set of differential equations, thus providing probabilistic underpinnings to the works of Miller (J Math Biol 62(3):349–358, 2011) and Volz (J Math Biol 56(3):293–310, 2008). The present paper provides an additional probabilistic interpretation of the limiting deterministic functions in Janson, Luczak and Windridge (Random Struct Alg 45(4):724–761, 2014), thus clarifying further the connection between their results and the results of Miller and Volz. [ABSTRACT FROM AUTHOR]

Digital transformation is an important strategic decision for the sustainable development of enterprises, which helps enterprises achieve sustainable performance, sustainable management, and even sustainable business models. While there have been a number of useful studies discussing the impetus of digital transformation, most of them have neglected the role from employees, especially their attitudes and perceptions towards transformation. Focusing on employees' openness to digital transformation, we selected six antecedents to construct a configuration model, using fsQCA and NCA methods to explore the complex causal relationship between each antecedent and openness to digital transformation. This aims to derive the activation paths for employees' openness to digital transformation, so as to help the enterprises' digital transformation and further achieve sustainable development. Through the data analysis of 462 employees of Chinese enterprises, the following conclusions are drawn: firstly, single antecedents are not necessary conditions for high/non-high digital transformation openness activation; secondly, there are three configurations associated with the high openness activation of digital transformation: a comprehensive collaboration type under internal environment dominance (S1a + S1b), the consideration of both an internal and external environment type under mindfulness characteristics' dominance (S2), and a mindful substitution type under internal environment dominance (S3); and finally, there are four configurations associated with non-high digital transformation openness activation and an asymmetric relationship exists with the high digital transformation openness activation path. [ABSTRACT FROM AUTHOR]

As the proportion of new energy continues to increase, the safety and stability of the new power system are challenged, urgently requiring the allocation of new flexible resources. This paper proposes a two-stage robust capacity optimization model considering flexibility demand constraints. Firstly, the uncertain characteristics of new energy are described, and a model of flexible resource adjustment capacity is established. Then, uncertain parameters are introduced to construct a robust capacity optimization model considering supply-demand balance, solved by column constraint generation algorithm and KKT theorem. Finally, a power system in a certain region of China is selected as the simulation object for empirical analysis to verify the effectiveness of the constructed model. The results show that the two-stage robust configuration optimization model constructed in this paper can address the uncertainty of power system and the flexibility demand brought by new energy, and the planning results can achieve a balance between the safety and economy of the new power system. [ABSTRACT FROM AUTHOR]

With the premise that social interactions are described by power-law distributions, we study the stochastic dynamics of SIR (Susceptible-Infected-Removed) compartmental models on static scale-free random networks generated via the configuration model. We compare simulations of our model to analytical results, providing a closed formula and a lower bound for the probability of having a minor epidemic of the disease. We explore the variability in disease spread by stochastic simulations. In particular, we demonstrate how important epidemic indices change as a function of the contagiousness of the disease and the connectivity of the network. Our results quantify the role of the starting node's degree in determining these indices, commonly used to describe epidemic spread. Our results and implementation set a baseline for studying epidemic spread on networks, showing how analytical methods can help in the interpretation of stochastic simulations. [ABSTRACT FROM AUTHOR]

We study competing first passage percolation on graphs generated by the configuration model with infinite-mean degrees. Initially, two uniformly chosen vertices are infected with a type 1 and type 2 infection, respectively, and the infection then spreads via nearest neighbors in the graph. The time it takes for the type 1 (resp. 2) infection to traverse an edge e is given by a random variable $X_1(e)$ (resp. $X_2(e)$) and, if the vertex at the other end of the edge is still uninfected, it then becomes type 1 (resp. 2) infected and immune to the other type. Assuming that the degrees follow a power-law distribution with exponent $\tau \in (1,2)$ , we show that with high probability as the number of vertices tends to infinity, one of the infection types occupies all vertices except for the starting point of the other type. Moreover, both infections have a positive probability of winning regardless of the passage-time distribution. The result is also shown to hold for the erased configuration model, where self-loops are erased and multiple edges are merged, and when the degrees are conditioned to be smaller than $n^\alpha$ for some $\alpha\gt 0$. [ABSTRACT FROM AUTHOR]

Analysing social networks is challenging. Key features of relational data require the use of non-standard statistical methods such as developing system-specific null, or reference, models that randomize one or more components of the observed data. Here we review a variety of randomization procedures that generate reference models for social network analysis. Reference models provide an expectation for hypothesis testing when analysing network data. We outline the key stages in producing an effective reference model and detail four approaches for generating reference distributions: permutation, resampling, sampling from a distribution, and generative models. We highlight when each type of approach would be appropriate and note potential pitfalls for researchers to avoid. Throughout, we illustrate our points with examples from a simulated social system. Our aim is to provide social network researchers with a deeper understanding of analytical approaches to enhance their confidence when tailoring reference models to specific research questions.

Consider a system of homogeneous interacting diffusive particles labeled by the nodes of a unimodular Galton–Watson tree, where the state of each node evolves infinitesimally like a d-dimensional diffusion whose drift coefficient depends on (the histories of) its own state and the states of neighboring nodes, and whose diffusion coefficient depends only on (the history of) its own state. Under suitable regularity assumptions on the coefficients, an autonomous characterization is obtained for the marginal distribution of the dynamics of the neighborhood of a typical node in terms of a certain local equation, which is a new kind of stochastic differential equation that is nonlinear in the sense of McKean. This equation describes a finite-dimensional non-Markovian stochastic process whose infinitesimal evolution at any time depends not only on the structure and current state of the neighborhood, but also on the conditional law of the current state given the past of the states of neighborhing nodes until that time. Such marginal distributions are of interest because they arise as weak limits of both marginal distributions and empirical measures of interacting diffusions on many sequences of sparse random graphs, including the configuration model and Erdös–Rényi graphs whose average degrees converge to a finite non-zero limit. The results obtained complement classical results in the mean-field regime, which characterize the limiting dynamics of homogeneous interacting diffusions on complete graphs, as the number of nodes goes to infinity, in terms of a corresponding nonlinear Markov process. However, in the sparse graph setting, the topology of the graph strongly influences the dynamics, and the analysis requires a completely different approach. The proofs of existence and uniqueness of the local equation rely on delicate new conditional independence and symmetry properties of particle trajectories on unimodular Galton–Watson trees, as well as judicious use of changes of measure. [ABSTRACT FROM AUTHOR]

This brief note highlights a largely overlooked similarity between the SIR ordinary differential equations used for epidemics on the configuration model of a Poisson network and the classical mass-action SIR equations introduced nearly a century ago by Kermack and McKendrick. We demonstrate that the decline pattern in susceptibles is identical for both models. This equivalence carries practical implications: the susceptibles decay curve, often referred to as the epidemic or incidence curve, is frequently used in empirical studies to forecast epidemic dynamics. Although the curves for susceptibles align perfectly, those for infections do differ. Yet, the infection curves tend to converge and become almost indistinguishable in high-degree networks. In summary, our analysis suggests that under many practical scenarios, it's acceptable to use the classical SIR model as a close approximation to the Poisson SIR network model. [ABSTRACT FROM AUTHOR]

Many applications require randomly sampling bipartite graphs with fixed degrees or randomly sampling incidence matrices with fixed row and column sums. Although several sampling algorithms exist, the 'curveball' algorithm is the most efficient with an asymptotic time complexity of |$O(n~log~n)$| and has been proven to sample uniformly at random. In this article, we introduce the 'fastball' algorithm, which adopts a similar approach but has an asymptotic time complexity of |$O(n)$|⁠. We show that a C |$\texttt{++}$| implementation of fastball randomly samples large bipartite graphs with fixed degrees faster than curveball, and illustrate the value of this faster algorithm in the context of the fixed degree sequence model for backbone extraction. [ABSTRACT FROM AUTHOR]

We provide a general purpose result for the coupling of exploration processes of random graphs, both undirected and directed, with their local weak limits when this limit is a marked Galton–Watson process. This class includes in particular the configuration model and the family of inhomogeneous random graphs with rank-1 kernel. Vertices in the graph are allowed to have attributes on a general separable metric space and can potentially influence the construction of the graph itself. The coupling holds for any fixed depth of a breadth-first exploration process. [ABSTRACT FROM AUTHOR]

In this paper, which is a culmination of our previous research efforts, we provide a general framework for studying mixing profiles of non-backtracking random walks on dynamic random graphs generated according to the configuration model. The quantity of interest is the scaling of the mixing time of the random walk as the number of vertices of the random graph tends to infinity. Subject to mild general conditions, we link two mixing times: one for a static version of the random graph, the other for a class of dynamic versions of the random graph in which the edges are randomly rewired but the degrees are preserved. With the help of coupling arguments we show that the link is provided by the probability that the random walk has not yet stepped along a previously rewired edge. To demonstrate the utility of our framework, we rederive our earlier results on mixing profiles for global edge rewiring under weaker assumptions, and extend these results to an entire class of rewiring dynamics parametrised by the range of the rewiring relative to the position of the random walk. Along the way we establish that all the graph dynamics in this class exhibit the trichotomy we found earlier, namely, no cut-off, one-sided cut-off or two-sided cut-off. For interpolations between global edge rewiring, the only Markovian graph dynamics considered here, and local edge rewiring (i.e., only those edges that are incident to the random walk can be rewired), we show that the trichotomy splits further into a hexachotomy, namely, three different mixing profiles with no cut-off, two with one-sided cutoff, and one with two-sided cut-off. Proofs are built on a new and flexible coupling scheme, in combination with sharp estimates on the degrees encountered by the random walk in the static and the dynamic version of the random graph. Some of these estimates require sharp control on possible short-cuts in the graph between the edges that are traversed by the random walk. • We give a framework to study mixing of non-backtracking random walks on dynamic graphs. • We describe mixing profiles for a class of graph dynamics parametrised by their range. • For a class of graph dynamics we observe a hexachotomy in their mixing profiles. [ABSTRACT FROM AUTHOR]

Certain defence mechanisms of phages against the immune system of their bacterial host rely on cooperation of phages. Motivated by this example we analyse invasion probabilities of cooperative parasites in moderately structured host populations. We assume that hosts occupy the vertices of a configuration model and offspring parasites move to neighbouring sites to infect new hosts. Parasites (usually) reproduce only when infecting a host simultaneously and then generate many offspring. In this regime we identify and analyse the spatial scale of the population structure at which invasion of parasites turns from being an unlikely to a highly probable event. [ABSTRACT FROM AUTHOR]

There are several Rubik Cube types; their internal structure is complex, making them harder to understand, analyze, and design. Since the Rubik's Cube is a complex mechanism consisting of a large number of parts, its reconfigurable theory and bifurcation characteristics need to be studied. Thus, this paper first presents the piece matrix for each Rubik's Cube piece based on its motion characteristics, taking the classic third-order Rubik's Cube and Square-1 Rubik's Cube as examples. This allows the authors to explain the meaning of elements within the piece matrix. The Rubik's Cube reconfigurable configuration model is established next, and its reconfigurable motion model and the associated configuration are given. The Rubik's Cube reconfigurable motion model in any configuration is obtained by using the transformation matrix. The Rubik's Cube bifurcation characteristics are analyzed on the basis of reconfigurable configuration model. The work at hand improves the existing reconfigurable theory of Rubik's Cube mechanism and offers beneficial classification cubes to the subsequent research and synthesis. [ABSTRACT FROM AUTHOR]

We study a stochastic compartmental susceptible–infected (SI) epidemic process on a configuration model random graph with a given degree distribution over a finite time interval. We split the population of graph vertices into two compartments, namely, S and I, denoting susceptible and infected vertices, respectively. In addition to the sizes of these two compartments, we keep track of the counts of SI-edges (those connecting a susceptible and an infected vertex) and SS-edges (those connecting two susceptible vertices). We describe the dynamical process in terms of these counts and present a functional central limit theorem (FCLT) for them as the number of vertices in the random graph grows to infinity. The FCLT asserts that the counts, when appropriately scaled, converge weakly to a continuous Gaussian vector semimartingale process in the space of vector-valued càdlàg functions endowed with the Skorokhod topology. We discuss applications of the FCLT in percolation theory and in modelling the spread of computer viruses. We also provide simulation results illustrating the FCLT for some common degree distributions. [ABSTRACT FROM AUTHOR]

We study the susceptible–infected–recovered (SIR) epidemic on a random graph chosen uniformly over all graphs with certain critical, heavy-tailed degree distributions. We prove process level scaling limits for the number of individuals infected on day h on the largest connected components of the graph. The scaling limits contain non-negative jumps corresponding to some vertices of large degree. These weak convergence techniques allow us to describe the height profile of the α -stable continuum random graph (Goldschmidt et al., 2022; Conchon-Kerjan and Goldschmidt, 2023), extending results known in the Brownian case (Miermont and Sen, 2022). We also prove model-independent results that can be used on other critical random graph models. [ABSTRACT FROM AUTHOR]

Community detection is a key data analysis problem across different fields. During the past decades, numerous algorithms have been proposed to address this issue. However, most work on community detection does not address the issue of statistical significance. Although some research efforts have been made towards mining statistically significant communities, deriving an analytical solution of $p$ p -value for one community under the configuration model is still a challenging mission that remains unsolved. The configuration model is a widely used random graph model in community detection, in which the degree of each node is preserved in the generated random networks. To partially fulfill this void, we present a tight upper bound on the $p$ p -value of a single community under the configuration model, which can be used for quantifying the statistical significance of each community analytically. Meanwhile, we present a local search method to detect statistically significant communities in an iterative manner. Experimental results demonstrate that our method is comparable with the competing methods on detecting statistically significant communities. [ABSTRACT FROM AUTHOR]

Multi-layer networks of multiplex type represent relational data on a set of entities (nodes) with multiple types of relations (edges) among them where each type of relation is represented as a network layer. A large group of popular community detection methods in networks are based on optimizing a quality function known as the modularity score, which is a measure of the extent of presence of module or community structure in networks compared to a suitable null model. Here we introduce several multi-layer network modularity and model likelihood quality function measures using different null models of the multi-layer network, motivated by empirical observations in networks from a diverse field of applications. In particular, we define multi-layer variants of the Chung-Lu expected degree model as null models that differ in their modeling of the multi-layer degrees. We propose simple estimators for the models and prove their consistency properties. A hypothesis testing procedure is also proposed for selecting an appropriate null model for data. These null models are used to define modularity measures as well as model likelihood based quality functions. The proposed measures are then optimized to detect the optimal community assignment of nodes (Code available at: https://u.osu.edu/subhadeep/codes/). We compare the effectiveness of the measures in community detection in simulated networks and then apply them to four real multi-layer networks. [ABSTRACT FROM AUTHOR]

Infectious or contagious diseases can be transmitted from one person to another through social contact networks. In today's interconnected global society, such contagion processes can cause global public health hazards, as exemplified by the ongoing Covid-19 pandemic. It is therefore of great practical relevance to investigate the network transmission of contagious diseases from the perspective of statistical inference. An important and widely studied boundary condition for contagion processes over networks is the so-called epidemic threshold. The epidemic threshold plays a key role in determining whether a pathogen introduced into a social contact network will cause an epidemic or die out. In this paper, we investigate epidemic thresholds from the perspective of statistical network inference. We identify two major challenges that are caused by high computational and sampling complexity of the epidemic threshold. We develop two statistically accurate and computationally efficient approximation techniques to address these issues under the Chung-Lu modeling framework. The second approximation, which is based on random walk sampling, further enjoys the advantage of requiring data on a vanishingly small fraction of nodes. We establish theoretical guarantees for both methods and demonstrate their empirical superiority. [ABSTRACT FROM AUTHOR]

We study the simple random walk on the configuration model with given degree sequence (d1n, ..., dnn) and investigate the connected components of its vacant set at level u > 0. We show that the size of the maximal connected component exhibits a phase transition at level u* which can be related with the critical parameter of random interlacements on a certain Galton-Watson tree. We further show that there is a critical window of size n-1/3 around u* in which the largest connected components of the vacant set have a metric space scaling limit resembling the one of the critical Erdős-Rényi random graph. [ABSTRACT FROM AUTHOR]

The global structure of the minimal spanning tree (MST) is expected to be universal for a large class of underlying random discrete structures. However, very little is known about the intrinsic geometry of MSTs of most standard models, and so far the scaling limit of the MST viewed as a metric measure space has only been identified in the case of the complete graph (Addario-Berry et al. in Ann Probab 45(5):3075–3144, 2017). In this work, we show that the MST constructed by assigning i.i.d. continuous edge weights to either the random (simple) 3-regular graph or the 3-regular configuration model on n vertices, endowed with the tree distance scaled by n - 1 / 3 and the uniform probability measure on the vertices, converges in distribution with respect to Gromov–Hausdorff–Prokhorov topology to a random compact metric measure space. Further, this limiting space has the same law as the scaling limit of the MST of the complete graph identified in Addario-Berry et al. (2017) up to a scaling factor of 6 1 / 3 . Our proof relies on a novel argument that proceeds via a comparison between a 3-regular configuration model and the largest component in the critical Erdős–Rényi random graph. The techniques of this paper can be used to establish the scaling limit of the MST in the setting of general random graphs with given degree sequences provided two additional technical conditions are verified. [ABSTRACT FROM AUTHOR]

We study the problem of generalized degree-based percolation without memory, where the probability of node removal depends on a non-negative function of node degree within the remaining network. We derive a set of nonlinear ordinary differential equations describing the evolution of the degree distribution during the percolation process. Employing generating function methods, we calculate various quantities of interest such as the probability of a randomly selected node belonging to the giant component, the mean cluster size, and the critical point at which a network transitions from connected to fragmented. Validation of our approach is achieved through extensive Monte Carlo simulations and numerical solutions. Our results indicate that removing highly connected nodes with small preference probabilities significantly lowers the critical point compared to random removal. Moreover, our analytical framework is applicable to random networks generated by the configuration model with any bounded degree distribution. It provides a comprehensive and systematic approach to analyze network robustness against various degree-based attack strategies, offering valuable insights into network design and protection. • An exact analysis of degree-based percolation on random networks is performed. • A set of differential equations is derived to describe the percolation process. • Generating function technique is used to calculate various quantities of interest. • The approach works for random networks with any bounded degree distribution. • The approach is validated by numerical solutions and Monte Carlo simulations. [ABSTRACT FROM AUTHOR]

Abstract In this paper we present a generalization of the classical configuration model. Like the classical configuration model, the generalized configuration model allows users to specify an arbitrary degree distribution. In our generalized configuration model, we partition the stubs in the configuration model into b blocks of equal sizes and choose a permutation function h for these blocks. In each block, we randomly designate a number proportional to q of stubs as type 1 stubs, where q is a parameter in the range [0,1]. Other stubs are designated as type 2 stubs. To construct a network, randomly select an unconnected stub. Suppose that this stub is in block i. If it is a type 1 stub, connect this stub to a randomly selected unconnected type 1 stub in block h(i). If it is a type 2 stub, connect it to a randomly selected unconnected type 2 stub. We repeat this process until all stubs are connected. Under an assumption, we derive a closed form for the joint degree distribution of two random neighboring vertices in the constructed graph. Based on this joint degree distribution, we show that the Pearson degree correlation function is linear in q for any fixed b. By properly choosing h, we show that our construction algorithm can create assortative networks as well as disassortative networks. We present a percolation analysis of this model. We verify our results by extensive computer simulations.

Abstract We provide a novel family of generative block-models for random graphs that naturally incorporates degree distributions: the block-constrained configuration model. Block-constrained configuration models build on the generalized hypergeometric ensemble of random graphs and extend the well-known configuration model by enforcing block-constraints on the edge-generating process. The resulting models are practical to fit even to large networks. These models provide a new, flexible tool for the study of community structure and for network science in general, where modeling networks with heterogeneous degree distributions is of central importance.

Abstract We develop and test a rewiring method (originally proposed by Newman) which allows to build random networks having pre-assigned degree distribution and two-point correlations. For the case of scale-free degree distributions, we discretize the tail of the distribution according to the general prescription by Dorogovtsev and Mendes. The application of this method to Barabasi-Albert (BA) networks is possible thanks to recent analytical results on their correlations, and allows to compare the ensemble of random networks generated in the configuration model with that of “real” networks obtained from preferential attachment. For β≥2 (β is the number of parent nodes in the preferential attachment scheme) the networks obtained with the configuration model are completely connected (giant component equal to 100%). In both generation schemes a clear disassortativity of the small degree nodes is demonstrated from the computation of the function k nn . We also develop an efficient rewiring method which produces tunable variations of the assortativity coefficient r, and we use it to obtain maximally disassortative networks having the same degree distribution of BA networks with given β. Possible applications of this method concern assortative social networks.

We prove a law of large numbers for the order and size of the largest strongly connected component in the directed configuration model. Our result extends previous work by Cooper and Frieze (2004). [ABSTRACT FROM AUTHOR]

We consider a Markovian SIR-type (Susceptible → Infected → Recovered) stochastic epidemic process with multiple modes of transmission on a contact network. The network is given by a random graph following a multilayer configuration model where edges in different layers correspond to potentially infectious contacts of different types. We assume that the graph structure evolves in response to the epidemic via activation or deactivation of edges of infectious nodes. We derive a large graph limit theorem that gives a system of ordinary differential equations (ODEs) describing the evolution of quantities of interest, such as the proportions of infected and susceptible vertices, as the number of nodes tends to infinity. Analysis of the limiting system elucidates how the coupling of edge activation and deactivation to infection status affects disease dynamics, as illustrated by a two-layer network example with edge types corresponding to community and healthcare contacts. Our theorem extends some earlier results describing the deterministic limit of stochastic SIR processes on static, single-layer configuration model graphs. We also describe precisely the conditions for equivalence between our limiting ODEs and the systems obtained via pair approximation, which are widely used in the epidemiological and ecological literature to approximate disease dynamics on networks. The flexible modeling framework and asymptotic results have potential application to many disease settings including Ebola dynamics in West Africa, which was the original motivation for this study.

An important problem in modeling networks is how to generate a randomly sampled graph with given degrees. A popular model is the configuration model, a network with assigned degrees and random connections. The erased configuration model is obtained when self-loops and multiple edges in the configuration model are removed. We prove an upper bound for the number of such erased edges for regularly-varying degree distributions with infinite variance, and use this result to prove central limit theorems for Pearson's correlation coefficient and the clustering coefficient in the erased configuration model. Our results explain the structural correlations in the erased configuration model and show that removing edges leads to different scaling of the clustering coefficient. We prove that for the rank-1 inhomogeneous random graph, another null model that creates scale-free simple networks, the results for Pearson's correlation coefficient as well as for the clustering coefficient are similar to the results for the erased configuration model. [ABSTRACT FROM AUTHOR]

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, and the flooding time, which represents the time (weighted length) needed to reach all the vertices in the graph starting from a uniformly chosen vertex. Our result consists in describing the asymptotic behavior of the diameter and the flooding time, as the number of vertices n tends to infinity, in the case where the weight distribution G has an exponential tail behavior, and proving that this category of distributions is the largest possible for which the asymptotic behavior holds. [ABSTRACT FROM AUTHOR]

Random graphs with a given degree sequence are often constructed using the configuration model, which yields a random multigraph. We may adjust this multigraph by a sequence of switchings, eventually yielding a simple graph. We show that, assuming essentially a bounded second moment of the degree distribution, this construction with the simplest types of switchings yields a simple random graph with an almost uniform distribution, in the sense that the total variation distance is o(1). This construction can be used to transfer results on distributional convergence from the configuration model multigraph to the uniform random simple graph with the given vertex degrees. As examples, we give a few applications to asymptotic normality. We show also a weaker result yielding contiguity when the maximum degree is too large for the main theorem to hold. [ABSTRACT FROM AUTHOR]

We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph. [ABSTRACT FROM AUTHOR]

We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by Černý and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs. [ABSTRACT FROM AUTHOR]

Real-world social networks often exhibit high levels of clustering, positive degree assortativity, short average path lengths (small-world property) and right-skewed but rarely power law degree distributions. On the other hand homophily, defined as the propensity of similar agents to connect to each other, is one of the most fundamental social processes observed in many human and animal societies. In this paper we examine the extent to which homophily is sufficient to produce the typical structural properties of social networks. To do so, we conduct a simulation study based on the Social Distance Attachment (SDA) model, a particular kind of Random Geometric Graph (RGG), in which nodes are embedded in a social space and connection probabilities depend functionally on distances between nodes. We derive the form of the model from first principles based on existing analytical results and argue that the mathematical construction of RGGs corresponds directly to the homophily principle, so they provide a good model for it. We find that homophily, especially when combined with a random edge rewiring, is sufficient to reproduce many of the characteristic features of social networks. Additionally, we devise a hybrid model combining SDA with the configuration model that allows generating homophilic networks with arbitrary degree sequences and we use it to study interactions of homophily with processes imposing constraints on degree distributions. We show that the effects of homophily on clustering are robust with respect to distribution constraints, while degree assortativity can be highly dependent on the particular kind of enforced degree sequence. [ABSTRACT FROM AUTHOR]

The key to our investigation is an improved (and in a sense sharp) understanding of the survival time of the contact process on star graphs. Using these results, we show that for the contact process on Galton-Watson trees, when the offspring distribution (i) is subexponential the critical value for local survival λ2 = 0 and (ii) when it is geometric(p) we have λ2 ≤ Cp, where the Cp are much smaller than previous estimates. We also study the critical value λc(n) for "prolonged persistence" on graphs with n vertices generated by the configuration model. In the case of power law and stretched exponential distributions where it is known λc(n) → 0 we give estimates on the rate of convergence. Physicists tell us that λc(n) ~ 1/Λ n) where Λ (n) is the maximum eigenvalue of the adjacency matrix. Our results show that this is accurate for graphs with power-law degree distributions, but not for stretched exponentials. [ABSTRACT FROM AUTHOR]

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ1 (λ2) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ1 = λ2, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ1 ≠ λ2, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence. [ABSTRACT FROM AUTHOR]

We consider a dynamic random graph on n vertices that is obtained by starting from a random graph generated according to the configuration model with a prescribed degree sequence and at each unit of time randomly rewiring a fraction α n of the edges. We are interested in the mixing time of a random walk without backtracking on this dynamic random graph in the limit as n → ∞ , when α n is chosen such that lim n → ∞ α n (log n) 2 = β ∈ [ 0 , ∞ ]. In Avena et al. (2018) we found that, under mild regularity conditions on the degree sequence, the mixing time is of order 1 ∕ α n when β = ∞. In the present paper we investigate what happens when β ∈ [ 0 , ∞). It turns out that the mixing time is of order log n , with the scaled mixing time exhibiting a one-sided cutoff when β ∈ (0 , ∞) and a two-sided cutoff when β = 0. The occurrence of a one-sided cutoff is a rare phenomenon. In our setting it comes from a competition between the time scales of mixing on the static graph, as identified by Ben-Hamou and Salez (2017), and the regeneration time of first stepping across a rewired edge. [ABSTRACT FROM AUTHOR]

In this paper we consider Susceptible → Infectious → Recovered (SIR) epidemics on random graphs with clustering. To incorporate group structure of the underlying social network, we use a generalized version of the configuration model in which each node is a member of a specified number of triangles. SIR epidemics on this type of graph have earlier been investigated under the assumption of homogeneous infectivity and also under the assumption of Poisson transmission and recovery rates. We extend known results from literature by relaxing the assumption of homogeneous infectivity both in individual infectivity and between different kinds of neighbours. An important special case of the epidemic model analysed in this paper is epidemics in continuous time with arbitrary infectious period distribution. We use branching process approximations of the spread of the disease to provide expressions for the basic reproduction number R 0 , the probability of a major outbreak and the expected final size. In addition, the impact of random vaccination with a perfect vaccine on the final outcome of the epidemic is investigated. We find that, for this particular model, R 0 equals the perfect vaccine-associated reproduction number. Generalizations to groups larger than three are discussed briefly. [ABSTRACT FROM AUTHOR]

A large and sparse random graph with independent exponentially distributed link weights can be used to model the propagation of messages or diseases in a network with an unknown connectivity structure. In this article we study an extended setting where, in addition, the nodes of the graph are equipped with nonnegative random weights which are used to model the effect of boundary delays across paths in the network. Our main results provide approximative formulas for typical first passage times, typical flooding times, and maximum flooding times in the extended setting, over a time scale logarithmic with respect to the network size. [ABSTRACT FROM AUTHOR]

This study proposes an operationalisation of the term focus in healthcare operations. We develop a configuration model consisting of six interrelated dimensions that can be used to characterise hospital focus. The proposed dimensions of focus are Knowledge areas, Procedures, Medical conditions, Patient groups, Planning horizons and Levels of difficulty. The strength of these dimensions is shown through empirical examination, using a three-step methodology to analyse case study data from a unique transformation project where general hospitals were turned into new types of focused specialty hospitals. As our study takes a portfolio approach to the allocation of demand segments to different healthcare delivery units, it contributes to operations management knowledge with a model for segmenting healthcare demand from an operations perspective. This configuration model provides researchers and practitioners with a tool for understanding current configurations as well as for identifying potential new configurations of focus in healthcare. [ABSTRACT FROM AUTHOR]

A Markovian Susceptible → Infectious → Recovered (SIR) model is considered for the spread of an epidemic on a configuration model network, in which susceptible individuals may take preventive measures by dropping edges to infectious neighbours. An effective degree formulation of the model is used in conjunction with the theory of density dependent population processes to obtain a law of large numbers and a functional central limit theorem for the epidemic as the population size N → ∞ , assuming that the degrees of individuals are bounded. A central limit theorem is conjectured for the final size of the epidemic. The results are obtained for both the Molloy–Reed (in which the degrees of individuals are deterministic) and Newman–Strogatz–Watts (in which the degrees of individuals are independent and identically distributed) versions of the configuration model. The two versions yield the same limiting deterministic model but the asymptotic variances in the central limit theorems are greater in the Newman–Strogatz–Watts version. The basic reproduction number R 0 and the process of susceptible individuals in the limiting deterministic model, for the model with dropping of edges, are the same as for a corresponding SIR model without dropping of edges but an increased recovery rate, though, when R 0 > 1 , the probability of a major outbreak is greater in the model with dropping of edges. The results are specialised to the model without dropping of edges to yield conjectured central limit theorems for the final size of Markovian SIR epidemics on configuration-model networks, and for the size of the giant components of those networks. The theory is illustrated by numerical studies, which demonstrate that the asymptotic approximations are good, even for moderate N. [ABSTRACT FROM AUTHOR]

It is well known that many random graphs with infinite variance degrees are ultra‐small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k−(τ − 1) with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to 2loglogn|log(τ−2)| and 4loglogn|log(τ−2)|, respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order loglogn precisely when the minimal forward degree dfwd of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus 2/logdfwd. Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature. [ABSTRACT FROM AUTHOR]

Abstract An exact formula for computing the average hopcount of the shortest path in finite-size tree-like components of undirected unweighted random networks is proposed. In a tree-like component with size s , there exists virtually only one shortest path between two arbitrary nodes. The summation of hopcounts of all shortest paths can be calculated approximately by the summation of the betweenness of all nodes, and the difference between them is only a constant s (s − 1). Therefore, the average hopcount can be calculated by further dividing the summation by the number of all shortest paths. In this paper, we first derive the conditional probability p (k | s) of the degree distribution of finite components with size s and the summation of all nodal betweenness respectively. By means of these results, we obtain the exact formula for calculating the average hopcount. Also, We confirm the proposed formula by simulations for networks with Poisson and power law degree distributions respectively. [ABSTRACT FROM AUTHOR]