Graphe aléatoire | EPFL Graph Search

vignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Les deux modèles de base d'Erdős et Rényi Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme. Dans les deux modèles, il s'agit d'un graphe aléatoire non orienté, qui n'a ni boucles, ni arêtes multiples. On utilise les notations suivantes :

l'ensemble des sommets est {1, 2, 3, ..., n} noté par la suite \ [![n]!];
les arêtes potentiellement présentes sont les n(n–1)/2 parties à deux éléments de \ [![n]!]; l'ensemble de ces arêtes est parfois noté {[![n]!]\choose2}. Il sera noté toutefois J

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

Alignment and Assembly

Lyudmila Yartseva

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

Alignment and Assembly

Lyudmila Yartseva

EPFL2017