Random graph

Summary

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph. Models A random graph is obtained by starting with a set of n isolated vertices and adding successive edges between them at random. The aim of the study in

Official source

https://en.wikipedia.org/wiki/Random_graph

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (38)

Related publications

Related people (8)

Related people

Related units (6)

Related units

Related concepts (24)

Related concepts

Related courses (13)

Related courses

Related lectures (21)

Related lectures

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by describing the asymptotic behavior of the diameter and the flooding time on the graph for a set of light-tailed edge-weights, and we prove that it is the largest class of densities for which these precise asymptotic expressions for the diameter/flooding time hold. We then show how the weighted optimal path can be constructed using a particular positive recurrent Markov chain. We finally study, in the last chapter, the noise sensitivity of the model by replacing every edge-weight independently by a new realization of the same distribution, with probability epsilon. We show that the optimal paths between two vertices before and after this modification are asymptotically ''independent'' conditioning on the graph, as the number of vertices tends to infinity.

EPFL2020

Over recent years, many large network datasets become available, giving rise to novel and valuable applications of data mining and machine learning techniques. These datasets include social networks, the structure of the Internet, and protein-interaction networks, to name just a few. Graph mining exploits information hidden in these data to shed light on such problems as finding relevant pages on the web, or identifying communities of strongly connected individuals. Clearly, to address such problems, we first need the complete and reliable network graph. In many real-world scenarios, the full graph is not available for free. For example, data-collection processes may be noisy and unreliable or node identifiers may be hidden for privacy protection. Therefore, we cannot rely on the node labels to infer the full graph. In this thesis, we address fundamental and practical questions of inferring a true full network from multiple ambiguous observations. We formulate two variations of this problem: network alignment and network assembly. In each variant, we address two types of questions: first, we characterize how graph features impact the fundamental feasibility of reconstruction; second, we seek efficient algorithms that can scale to very large networks. In the first part of this thesis, we consider network alignment. We assume two large, noisy observations of the true network that are not labeled. Network alignment refers to the problem of aligning the vertices of the two networks using only structural cues and it can be viewed as a generalization of the classic graph-isomorphism problem. We make the following contributions. First, we introduce a random bigraph model with parameters p, t and s that generates two correlated graphs. We characterize conditions on p, t and s for the feasibility of alignment of two graphs. Second, we create an algorithm named percolation graph-matching (PGM) that builds an alignment from a small set of pre-matched nodes S. We prove conditions on the parameters p, t , s and r for which PGM succeeds, and we establish a phase transition in |S|. In the second part of this thesis, we consider network assembly. We assume many small, noisy observations of the true network, called patches. The node labels are either absent or not unique. The network assembly problem consists in reconstructing the true graph from these patches. We make the following contributions. First, we introduce a novel random-graph model with parameters p and q that generates a network with high clustering. We characterize conditions on p and q for feasibility of assembly. Second, we propose a heuristic assembly algorithm to reconstruct the true graph from arbitrary patches with label ambiguity.

EPFL2017

We consider the contact process on a random graph with a fixed degree distribution given by a power law. We follow the work of Chatterjee and Durrett [2], who showed that for arbitrarily small infection parameter lambda, the survival time of the process is larger than a stretched exponential function of the number of vertices. For lambda close to 0 (that is, "near criticality"), we obtain sharp bounds for the typical density of infected sites in the graph, as the number of vertices tends to infinity. We exhibit three different regimes for this density, depending on the tail of the degree law.

Univ Washington, Dept Mathematics2013

EPFL2017