Narrow Results

We introduce a new model of random graphs, that of random regular graphs with edge faults (which we denote by ), obtained by selecting the edges of a random member of the set of all regular graphs of degree r independently and with probability p. We can thus represent a communication network in which the links fail independently and with probability f =1-p.

In order to deal with this new model, we extend the notion of configurations and the translation lemma between configurations and random regular graphs provided by B. Bollobás, by introducing the concept of random configurations, to account for edge faults, and by providing an extended translation lemma between random configurations and graphs.

We investigate important connectivity properties of by estimating the ranges of r, f for which, with high probability, graphs a) are highly connected b) become disconnected and c) admit a giant connected component of small diameter.

This paper describes a random model for chemical graphs that captures the notion of valence along with algorithms to generate chemical graphs using this model. An approach for computing the probability that a particular chemical graph is generated under this model is provided. The model is also used to provide theoretical bounds on the accuracy of a class of canonical labeling algorithms for a class of hydrocarbons.

Here, we study an agent-based model of the evolution of tag-mediated cooperation on Erdős–Rényi random graphs. In our model, agents with heritable phenotypic traits play pairwise Prisoner's Dilemma-like games and follow one of the four possible strategies: Ethnocentric, altruistic, egoistic and cosmopolitan. Ethnocentric and cosmopolitan strategies are conditional, i.e. their selection depends upon the shared phenotypic similarity among interacting agents. The remaining two strategies are always unconditional, meaning that egoists always defect while altruists always cooperate. Our simulations revealed that ethnocentrism can win in both early and later evolutionary stages on directed random graphs when reproduction of artificial agents was asexual; however, under the sexual mode of reproduction on a directed random graph, we found that altruists dominate initially for a rather short period of time, whereas ethnocentrics and egoists suppress other strategists and compete for dominance in the intermediate and later evolutionary stages. Among our results, we also find surprisingly regular oscillations which are not damped in the course of time even after half a million Monte Carlo steps. Unlike most previous studies, our findings highlight conditions under which ethnocentrism is less stable or suppressed by other competing strategies.

The structural phase transition in complex network models is known to yield knowledge relevant for several problems of practical application. Examples include resilience of artificial networks, dynamics of epidemic spreading, among others. The model of random graphs is probably the simplest model of complex networks, and the solution of this model falls into the universality class mean field percolation. In this work, we concentrate on a similar problem, namely, the structural phase transition in the ensemble of random acyclic graphs. It should be noted that several approaches to the problem of random graphs, such as generating functions or the Molloy–Reed criterion, rely on the fact that before the critical point, cycles should not be present in random graphs. In this way, up to the critical point our solution should produce results that are equivalent to these other methods. Our approach takes advantage of the fact that acyclic graphs allow for an exact combinatorial enumeration of the whole ensemble, what leads to an exact expression for the entropy of this system. With this definition of entropy we can determine the onset of the critical transition as well as the critical exponents associated with the transition. Our results are illustrated with Monte-Carlo results and are discussed within the context of general random graphs, as well as in comparison with another model of acyclic graphs.

Function-Described Graphs (FDGs) have been introduced by the authors as a representation of an ensemble of Attributed Graphs (AGs) for structural pattern recognition alternative to first-order random graphs. Both optimal and approximate algorithms for error-tolerant graph matching, which use a distance measure between AGs and FDGs, have been reported elsewhere. In this paper, both the supervised and the unsupervised synthesis of FDGs from a set of graphs is addressed. First, two procedures are described to synthesize an FDG from a set of commonly labeled AGs or FDGs, respectively. Then, the unsupervised synthesis of FDGs is studied in he context of clustering a set of AGs and obtaining an FDG model for each cluster. Two algorithms based on incremental and hierarchical clustering, respectively, are proposed, which are parameterized by a graph matching method. Some experimental results both on synthetic data and a real 3D-object recognition application show that the proposed algorithms are effective for clustering a set of AGs and synthesizing the FDGs that describe the classes. Moreover, the synthesized FDGs are shown to be useful for pattern recognition thanks to the distance measure and matching algorithm previously reported.

The aim of this article is to present a random graph representation, that is based on second-order relations between graph elements, for modeling sets of attributed graphs (AGs). We refer to these models as Second-Order Random Graphs (SORGs). The basic feature of SORGs is that they include both marginal probability functions of graph elements and second-order joint probability functions. This allows a more precise description of both the structural and semantic information contents in a set of AGs and, consequently, an expected improvement in graph matching and object recognition. The article presents a probabilistic formulation of SORGs that includes as particular cases the two previously proposed approaches based on random graphs, namely the First-Order Random Graphs (FORGs) and the Function-Described Graphs (FDGs). We then propose a distance measure derived from the probability of instantiating a SORG into an AG and an incremental procedure to synthesize SORGs from sequences of AGs. Finally, SORGs are shown to improve the performance of FORGs, FDGs and direct AG-to-AG matching in three experimental recognition tasks: one in which AGs are randomly generated and the other two in which AGs represent multiple views of 3D objects (either synthetic or real) that have been extracted from color images. In the last case, object learning is achieved through the synthesis of SORG models.

A robotic agent operating in an unknown and complex environment may employ a search strategy of some kind to perform a navigational task such as reaching a given goal. In the process of performing the task, the agent can attempt to discover characteristics of its environment that enable it to choose a more efficient search strategy for that environment. If the agent is able to do this, we can say that it has "learned to navigate" — i.e., to improve its navigational performance. This paper describes how an agent can learn to improve its goal-finding performance in a class of discrete spaces, represented by graphs embedded in the plane. We compare several basic search strategies on two different classes of "random" graphs and show how information collected during the traversal of a graph can be used to classify the graph, thus allowing the agent to choose the search strategy best suited for that graph.

In this paper, we address the tradeoff between exploration and exploitation for agents which need to learn more about the structure of their environment in order to perform more effectively. For example, a software agent operating on the World Wide Web may need to learn which sites on the net are most useful, and the most efficient routes to those sites. We compare exploration strategies for a repeated task, where the agent is given some particular task to perform some number of times. Tasks are modeled as navigation on a partially known (deterministic) graph. This paper describes a new utility-based exploration algorithm for repeated tasks which interleaves exploration with task performance. The method takes into account both the costs and the potential benefits (for future task repetitions) of different exploratory actions. Exploration is performed in a greedy fashion, with the locally optimal exploratory action performed during repetition of each task. We experimentally evaluated our utility-based interleaved exploration algorithm against a heuristic search algorithm for exploration before task performance (a priori exploration) as well as a randomized interleaved exploration algorithm. We found that for a single repeated task, utility-based interleaved exploration consistently outperforms the alternatives, unless the number of task repetitions is very high. In addition, we extended the algorithms for the case of multiple repeated tasks, where the agent has a different, randomly-chosen task (from a known subset of possible tasks) to perform each time. Here too, we found that utility-based interleaved exploration is clear in most cases.

Social relations between people seldom follow regular lattice structures. In the Barabási–Albert model nodes link to the existing network structure with a probability proportional to the number of nodes previously attached. Here, we present an anthropologically motivated interpolation between Erdös–Rényi and Barabási–Albert rules, where people also prefer to help those who helped them in the past and explore some of its properties. The second part of the paper tackles the question how opinions spread through social networks. We restrict our analysis to one end of the spectrum: scale-free networks. We show for two different models how fast and how sustainable single individuals can influence an appreciable fraction of the population through social contacts.

The topological structures and robustness of the protein-protein interaction networks (PINs) is studied via random graph theory. Several global topological parameters are used to characterize PINs for seven species. Good evidence by correlation analysis support the fact that the seven PINs are well approximated by scale-free networks. It is also found that two of the species' PINs are well described by the hierarchical models. In particular, it is determined that the E. coli and the yeast PINs are well represented by the stochastic and deterministic hierarchical network models respectively. These results suggest that the hierarchical network model is a better description for certain species' PINs. Furthermore, it is demonstrated that PINs are robust with respective to failure, attack, random rewiring and edge deletion perturbations.

We present four models for a random graph and show that, in each case, the probability that a graph is intrinsically knotted goes to one as the number of vertices increases. We also argue that, for $n\ge 18$, most graphs of order $n$ are intrinsically knotted and, for $n\ge 2m+9$, most of order $n$ are not $m$-apex. We observe that $p(n)=1/n$ is the threshold for intrinsic knotting and linking in Gilbert’s model.

We propose a simulation-free framework for stress testing the resilience of a financial network to external shocks affecting balance sheets. Whereas previous studies of contagion effects in financial networks have relied on large scale simulations, our approach uses a simple analytical criterion for resilience to contagion, based on an asymptotic analysis of default cascades in heterogeneous networks. In particular, our methodology does not require to observe the whole network but focuses on the characteristics of the network which contribute to its resilience. Applying this framework to a sample network, we observe that the size of the default cascade generated by a macroeconomic shock across balance sheets may exhibit a sharp transition when the magnitude of the shock reaches a certain threshold: Beyond this threshold, contagion spreads to a large fraction of the financial system. An upper bound is given for the threshold in terms of the characteristics of the network.

In 2001, Le Bars proved that there exists an existential monadic second-order (EMSO) sentence such that the probability that it is true on $G(n,p=1/2)$ does not converge and conjectured that, for EMSO sentences with two first-order variables, the zero–one law holds. In this paper, we prove that the conjecture fails for $p\in \{\frac{3-\sqrt{5}}{2},\frac{\sqrt{5}-1}{2}\}$, and give new examples of sentences with fewer variables without convergence (even for $p=1/2$).

Static Edge Voting Model is a random graph model that implements a streamlined approach to graph construction. Within this framework, a finite set of nodes constitutes the network, where each node establishes connections by “voting” for potential edges, influenced by their unique states. The probability of forming a connection between two distinct nodes depends on the aggregate votes. This study demonstrates how this model can be employed to generate networks that exhibit the key attributes of socially constructed networks. These networks have a giant component, are small-worlds, have a fat-tailed degree distribution, exhibit high clustering coefficients and assortative. The model’s parameters are intuitively interpretable, allowing for the manipulation of different network properties to quantify their impact on various processes.

We study the transition to spatio-temporal intermittency in random network of coupled Chaté–Manneville maps. The relevant parameters are the network connectivity, coupling strength, and the local parameter of the map. We show that spatiotemporal intermittency occurs for some intervals or windows of the values of these parameters. Within the intermittency windows, the system exhibits periodic and other nontrivial collective behaviors. The detailed behavior depends crucially upon the topology of the random graph spanning the network. We present a detailed analysis of the results based on the thermodynamic formalism and random graph theory.

Bond percolation on Cayley graphs provides examples of random graphs. Other examples arise from the dynamical study of proper repetitive subgraphs of Cayley graphs. In this paper we demonstrate that these two families have mutually singular laws as a corollary of a general lemma about countable Borel equivalence relations on first countable Hausdorff spaces.

Smart contract risk can be defined as a financial risk of loss due to cyber attacks on or contagious failures of smart contracts. Its quantification is of paramount importance to technology platform providers as well as companies and individuals when considering the deployment of this new technology. That is why, as our primary contribution, we propose a structural framework of aggregate loss distribution for smart contract risk under the assumption of a tree-stars graph topology representing the network of interactions among smart contracts and their users. To our knowledge, there exist no theoretical frameworks or models of an aggregate loss distribution for smart contracts in this setting. To achieve our goal, we contextualize the problem in the probabilistic graph-theoretical framework using bond percolation models. We assume that the smart contract network topology is represented by a random tree graph of finite size, and that each smart contract is the center of a random star graph whose leaves represent the users of the smart contract. We allow for heterogeneous loss topology superimposed on this smart contract and user topology and provide analytical results and instructive numerical examples.

We describe a higher-dimensional generalization of edge expansion from graphs to simplicial complexes, which we discuss as a type of co-isoperimetric inequality. The main point is to observe that sufficiently dense random simplicial complexes have this expander-like property with high probability, a higher-dimensional analogue of the fact that random graphs are expanders.

The main goal of this paper is to understand how the length spectrum of a random surface depends on its genus. Here a random surface means a surface obtained by randomly gluing together an even number of triangles carrying a fixed metric.

Given suitable restrictions on the genus of the surface, we consider the number of appearances of fixed finite sets of combinatorial types of curves. Of any such set we determine the asymptotics of the probability distribution. It turns out that these distributions are independent of the genus in an appropriate sense.

As an application of our results we study the probability distribution of the systole of random surfaces in a hyperbolic and a more general Riemannian setting. In the hyperbolic setting we are able to determine the limit of the probability distribution for the number of triangles tending to infinity and in the Riemannian setting we derive bounds.

McKay proved the limiting spectral measures of the ensembles of d-regular graphs with N vertices converge to Kesten's measure as N → ∞. Given a large d-regular graph we assign random weights, drawn from some distribution , to its edges. We study the relationship between and the associated limiting spectral distribution obtained by averaging over the weighted graphs. We establish the existence of a unique "eigendistribution" (a weight distribution such that the associated limiting spectral distribution is a rescaling of ). Initial investigations suggested that the eigendistribution was the semi-circle distribution, which by Wigner's Law is the limiting spectral measure for real symmetric matrices. We prove this is not the case, though the deviation between the eigendistribution and the semi-circular density is small (the first seven moments agree, and the difference in each higher moment is O(1/d²)). Our analysis uses combinatorial results about closed acyclic walks in large trees, which may be of independent interest.