Suchergebnisse

AbstractWe study the interplay between the diffusion of a harmful state in a network of contacts and the possibility of individual agents to undertake costly investment to protect themselves against infection. We characterize how equilibrium diffusion outcomes, such as the immunization rate, total prevalence and welfare, respond to changes in the architecture of the network, and show that these responses depend on the details of the diffusion process.

AbstractReal-world networks are often compared to random graphs to assess whether their topological structure could be a result of random processes. However, a simple random graph in large scale often lacks social structure beyond the dyadic level. As a result we need to generate clustered random graph to compare the local structure at higher network levels. In this paper a generalized version of Gleeson's algorithmG(VS, VT, ES, ET, S, T)is advanced to generate a clustered random graph in large-scale which persists the number of vertices |V|, the number of edges |E|, and the global clustering coefficientCΔas in the real network and it works successfully for nine large-scale networks. Our new algorithm also has advantages in randomness evaluation and computation efficiency when compared with the existing algorithms.

AbstractExponential random graph models, or ERGMs, are a flexible and general class of models for modeling dependent data. While the early literature has shown them to be powerful in capturing many network features of interest, recent work highlights difficulties related to the models' ill behavior, such as most of the probability mass being concentrated on a very small subset of the parameter space. This behavior limits both the applicability of an ERGM as a model for real data and inference and parameter estimation via the usual Markov chain Monte Carlo algorithms. To address this problem, we propose a new exponential family of models for random graphs that build on the standard ERGM framework. Specifically, we solve the problem of computational intractability and "degenerate" model behavior by an interpretable support restriction. We introduce a new parameter based on the graph-theoretic notion of degeneracy, a measure of sparsity whose value is commonly low in real-world networks. The new model family is supported on the sample space of graphs with bounded degeneracy and is called degeneracy-restricted ERGMs, or DERGMs for short. Since DERGMs generalize ERGMs—the latter is obtained from the former by setting the degeneracy parameter to be maximal—they inherit good theoretical properties, while at the same time place their mass more uniformly over realistic graphs. The support restriction allows the use of new (and fast) Monte Carlo methods for inference, thus making the models scalable and computationally tractable. We study various theoretical properties of DERGMs and illustrate how the support restriction improves the model behavior. We also present a fast Monte Carlo algorithm for parameter estimation that avoids many issues faced by Markov Chain Monte Carlo algorithms used for inference in ERGMs.

Methods for descriptive network analysis have reached statistical maturity and general acceptance across the social sciences in recent years. However, methods for statistical inference with network data remain fledgling by comparison. We introduce and evaluate a general model for inference with network data, the Exponential Random Graph Model (ERGM) and several of its recent extensions. The ERGM simultaneously allows both inference on covariates and for arbitrarily complex network structures to be modeled. Our contributions are three-fold: beyond introducing the ERGM and discussing its limitations, we discuss extensions to the model that allow for the analysis of non-binary and longitudinally observed networks and show through applications that network-based inference can improve our understanding of political phenomena.

In the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph Kn and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament Tk on k vertices. Maker wins if, at the end of the game, her digraph contains a copy of Tk; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for k = (2-o(1))log2 n, improving the constant factor in previous results of Beck and the second author. This is asymptotically tight since it is known that for k = (2-o(1))log2 n Breaker can prevent the underlying graph of Maker's digraph from containing a k-clique. Moreover, the precise value of our lower bound differs from the upper bound only by an additive constant of 12. We also discuss the question of whether the random graph intuition, which suggests that the threshold for k is asymptotically the same for the game played by two 'clever' players and the game played by two 'random' players, is supported by the tournament game. It will turn out that, while a straightforward application of this intuition fails, a more subtle version of it is still valid. Finally, we consider the orientation game version of the tournament game, where Maker wins the game if the final digraph-also containing the edges directed by Breaker-possesses a copy of Tk. We prove that in that game Breaker has a winning strategy for k = (4 + o(1))log2 n.

AbstractHyperbolic random graphs (HRGs) and geometric inhomogeneous random graphs (GIRGs) are two similar generative network models that were designed to resemble complex real-world networks. In particular, they have a power-law degree distribution with controllable exponent
$\beta$
and high clustering that can be controlled via the temperature
$T$
.We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to
$T = 0$
. We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, that is, they involve no approximation.Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify the desired expected average degree as input.Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straightforward inclusion does not hold in practice. However, the difference is negligible for most use cases.