No description available.

No description available.

Dans cette thèse nous étudions un problème fondamental, le partitionnement de graphe, dans le contexte de la croissance rapide des données, le volume des données continues à augmenter, allant des réseaux sociaux à l'internet des objets. En particulier, afin de vaincre les propriétés intraitables existant dans de nombreuses graphies, par exemple, la distribution des degrés en loi de puissance, nous appliquons un nouveau mode pour coupe de sommet, à la place de la méthode traditionnelle (coupe de bord), ainsi que pour assurer une charge de travail équilibrée et raisonnablement dans le traitement de graphe distribué. En outre, pour réduire le coût de communication inter-partitions, nous proposons une méthode de partition de bord basée sur les blocs, qui peut explorer efficacement les structures graphiques sous-jacentes au niveau local. , afin d'optimiser l'exécution de l'algorithme de graphe. Par cette méthode, le temps d'exécution et des communications généraux peuvent être considérablement réduits par rapport aux approches existantes. Les challenges qui se posent dans les grands graphiques comprennent également leur grande variété. Comme nous le savons, la plupart des applications graphiques au monde réel produisent des ensembles de données hétérogènes, dans lesquels les sommets et / ou les arêtes peuvent avoir des différents types ou des différentes étiquettes. De nombreuses algorithmes de fouille de graphes sont également proposés avec beaucoup d'intérêt pour les attributs d'étiquette. Pour cette raison, notre travail est étendu aux graphes de multicouches en prenant en compte la proximité des arêtes et la distribution des étiquettes lors du processus de partitionnement. En fin de cette thèse, Nous démontré à la ses performances exceptionnelles sur les ensembles de données du monde réel. / In this thesis, we mainly focus on a fundamental problem, graph partitioning, in the context of unexpectedly fast growth of data sources, ranging from social networks to internet of things. Particularly, to conquer intractable properties existing in many graphs, e.g. power-law degree distribution, we apply the novel fashion vertex-cut, instead of the traditional edge-cut method, for achieving balanced workload in distributed graph processing. Besides, to reduce the inter-partition communication cost, we present a block-based edge partition method who can efficiently explore the locality underlying graphical structures, to enhance the execution of graph algorithm. With this method, the overhead of both communication and runtime can be decreased greatly, compared to existing approaches. The challenges arising in big graphs also include their high-variety. As we know, most of real life graph applications produce heterogenous datasets, in which the vertices and/or edges are allowed to have different types or labels. A big number of graph mining algorithms are also proposed with much concern for the label attributes. For this reason, our work is extended to multi-layer graphs with taking into account the edges closeness and labels distribution during partitioning process. Its outstanding performance over real-world datasets is demonstrated finally.

L’objet de cette thèse est d’étudier plusieurs modèles probabilistes reliant les marches aléatoires et les arbres aléatoires issus de processus de branchement critiques.Dans la première partie, nous nous intéressons au modèle de marche aléatoire à valeurs dans un réseau euclidien et indexée par un arbre de Galton–Watson critique conditionné par la taille. Sous certaines hypothèses sur la loi de reproduction critique et la loi de saut centrée, nous obtenons, dans toutes les dimensions, la vitesse de croissance asymptotique du nombre de points visités par cette marche, lorsque la taille de l’arbre tend vers l’infini. Ces résultats nous permettent aussi de décrire le comportement asymptotique du nombre de points visités par une marche aléatoire branchante, quand la taille de la population initiale tend vers l’infini. Nous traitons également en parallèle certains cas où la marche aléatoire possède une dérive constante non nulle.Dans la deuxième partie, nous nous concentrons sur les propriétés fractales de la mesure harmonique des grands arbres de Galton–Watson critiques. On comprend par mesure harmonique la distribution de sortie, hors d’une boule centrée à la racine de l’arbre, d’une marche aléatoire simple sur cet arbre. Lorsque la loi de reproduction critique appartient au domaine d’attraction d’une loi stable, nous prouvons que la masse de la mesure harmonique est asymptotiquement concentrée sur une partie de la frontière, cette partie ayant une taille négligeable par rapport à celle de la frontière. En supposant que la loi de reproduction critique a une variance finie, nous arrivons à évaluer la masse de la mesure harmonique portée par un sommet de la frontière choisi uniformément au hasard. / The aim of this Ph. D. thesis is to study several probabilistic models linking the random walks and the random trees arising from critical branching processes.In the first part, we consider the model of random walk taking values in a Euclidean lattice and indexed by a critical Galton–Watson tree conditioned by the total progeny. Under some assumptions on the critical offspring distribution and the centered jump distribution, we obtain, in all dimensions, the asymptotic growth rate of the range of this random walk, when the size of the tree tends to infinity. These results also allow us to describe the asymptotic behavior of the range of a branching random walk, when the size of the initial population goes to infinity. In parallel, we treat likewise some cases where the random walk has a non-zero constant drift.In the second part, we focus on the fractal properties of the harmonic measure on large critical Galton–Watson trees. By harmonic measure, we mean the exit distribution from a ball centered at the root of the tree by simple random walk on this tree. If the critical offspring distribution is in the domain of attraction of a stable distribution, we prove that the mass of the harmonic measure is asymptotically concentrated on a boundary subset of negligible size with respect to that of the boundary. Assuming that the critical offspring distribution has a finite variance, we are able to calculate the mass of the harmonic measure carried by a random vertex uniformly chosen from the boundary.

Cette thèse traite de la survie et des généalogies de populations en présence de sélection dans quelques modèles simples de physique statistique inspirés de la biologie.<br /><br />La première partie étudie l'évolution de marches aléatoires avec branchements unidimensionnelles en présence d'un seuil de survie qui croît linéairement au cours du temps. En reliant les propriétés de ces marches aléatoires à une équation de propagation de fronts, nous étudions la transition vers l'extinction de ces marches lorsque la vitesse du seuil croît et obtenons les comportements critiques de la probabilité de survie. Nous construisons également un processus biaisé décrivant une population de telles marches conditionnée sur sa taille à un instant final. Cette construction permet d'étudier le régime quasi-stationnaire près de la vitesse critique. Enfin, nous présentons un modèle exactement soluble sur lequel plusieurs conjectures peuvent être vérifiées.<br /><br />Dans une seconde partie, nous étudions des populations de taille constante du point de vue des généalogies et des temps de coalescence. Nous expliquons dans quelle mesure certains modèles d'évolution avec sélection se rapprochent des modèles de polymères dirigés et montrons plusieurs résultats numériques qui mettent en évidence l'existence de classes d'universalité dans les généalogies. En absence de sélection, nous étudions la dynamique des temps de coalescence et de l'âge de l'ancêtre commun d'une population, ainsi que les corrélations de ce dernier avec la diversité génétique dans un cas simple.

Les voies de signalisation cellulaires permettent aux cellules de percevoir et d'échanger de l'information sous la forme de signaux chimiques. Un tel signal génère une réponse de la cellule au travers des étapes cruciales de réception et transduction. Différents types de protéines sont organisés dans une cascade de réactions de proche en proche qui relaient le signal de l'extérieur vers l'intérieur de la cellule, notamment au travers de la membrane. Les protéines de signalisation sont restreintes à des compartiments avec des degrés de liberté différents, et diffusent soit dans la membrane cellulaire qui est bidimensionnelle, soit dans le cytoplasme qui est en trois dimensions. De plus, au sein même de ces espaces, leurs distributions respectives sont hétérogènes. Or l'étude de la dynamique des voies de signalisation repose classiquement sur des modèles mathématiques supposant une homogénéité de distribution spatiale. Nous avons développé des modèles de réactions biochimiques entre populitions de molécules oú l'état et la position de chaque molécule sont caractérisés. La diffusion et les interactions entre molécules simulées sont reproduites sur la base de processus stochastiques issus de la biophysique. Ceci permet de recréer des distributions spatiales et des modes de diffusion hétérogènes tels qu'observés en biologie et d'étudier leur effet sur la dynamique de la signalisation en simulation. L'exploitation des modèles a été menée sur les différentes étapes de signalisation. Premièrement, l'étude a porté sur l'interaction entre un ligand dans le milieu extracellulaire et des récepteurs membranaires fixes. Lorsque les récepteurs forment des grappes au lieu d'être répartis uniformément, cela provoque une perte de sensibilité globale de l'étage de réception. Deuxièmement, l'analyse a été poursuivie au niveau de l'étage de transduction entre les récepteurs et un effecteur au niveau de la membrane. Là aussi, une distribution en grappe plutôt qu'uniforme des récepteurs provoque une perte de sensibilité. Enfin, l'étude s'est portée sur un modèle intégrant un mécanisme de diffusion non-homogène en mettant en interaction des récepteurs mobiles et leur substrat membranaire. Lorsque des zones restreintes de diffusion ralentie sont définies sur la membrane, deux effets opposés apparaissent sur la dynamique de transduction : un phénomène d'amplification si le ralentissement affecte les deux protéines, et un phénomène de perte de sensibilité si seuls les récepteurs sont ralentis. Globalement, les résultats illustrent comment les hétérogénéités spatiales modifient les distributions de collision et d'évènements de réaction dans le temps et l'espace à l'échelle microscopique, et comment cela se traduit par un effet sur la dynamique globale de la voie de signalisation à l'échelle macroscopique.

On étudie certaines propriétés d'une classe de processus aléatoires réels à temps continu, les marches aléatoires multifractales. Une particularité remarquable de ces processus tient en leur propriété d'autosimilarité : la loi du processus à petite échelle est identique à celle à grande échelle moyennant un facteur aléatoire multiplicatif indépendant du processus. La première partie de la thèse se consacre à la question de la convergence du moment empirique de l'accroissement du processus dans une asymptotique assez générale, où le pas de l'accroissement peut tendre vers zéro en même temps que l'horizon d'observation tend vers l'infini. La deuxième partie propose une famille de tests non-paramétriques qui distinguent entre marches aléatoires multifractales et semi-martingales d'Itô. Après avoir montré la consistance de ces tests, on étudie leur comportement sur des données simulées. On construit dans la troisième partie un processus de marche aléatoire multifractale asymétrique tel que l'accroissement passé soit négativement corrélé avec le carré de l'accroissement futur. Ce type d'effet levier est notamment observé sur les prix d'actions et d'indices financiers. On compare les propriétés empiriques du processus obtenu avec des données réelles. La quatrième partie concerne l'estimation des paramètres du processus. On commence par montrer que sous certaines conditions, deux des trois paramètres ne peuvent être estimés. On étudie ensuite les performances théoriques et empiriques de différents estimateurs du troisième paramètre, le coefficient d'intermittence, dans un cas gaussien / We study some properties of a class of real-valued, continuous-time random processes, namely multifractal random walks. A striking feature of these processes lie in their scaling property : the distribution of the process at small scale is the same as the distribution at large scale, given some random multiplicative factor independent of the process. The first part of the dissertation deals with the convergence of the empirical moment of the increment of the process in a rather general asymptotic setting where the step of the increment may go to zero while the observation horizon may also go to infinity. In the second part, we propose a family of nonparametric tests that separate multifractal random walks from Itô semi-martingales. After showing the consistency of these tests, we study their behavior on simulations.In the third part, we build a skewed multifractal random walk process, such that the past increment is negatively correlated with the future squared increment. Such a "leverage effect" is notably seen on financial stock and index prices. We compare the empirical properties of this process with real data. The fourth part deals with the parametric estimation of the process. We first show that under certain conditions, one can not estimate two of the three parameters, even if the sample path is continuously observed on some interval. We next study the theoretical and empirical performances of some estimators of the third parameter, the intermittency coefficient, in a Gaussian case

Le réseau magnétique consiste en un ensemble de petites concentrations de flux magnétique sur la photosphère solaire. Vu sa petite échelle de taille et de flux, à la limite de détection, son comportement n'est connu que depuis récemment. Les interactions du réseau sont pourtant cruciales afin de comprendre la dynamo et l'irradiance solaires, car beaucoup de caractérisques du réseau dépendent de ces interactions. De plus, le réseau est la principale contribution magnétique surfacique à l'irradiance solaire. Les modèles existants du réseau ne tenaient jusqu'à maintenant pas compte des interactions du réseau. Nous avons tenté de combler cette lacune avec notre modèle. Nos simulations impliquent une marche aléatoire en 2D de tubes de flux magnétiques sur la photosphère solaire. Les tubes de flux sont injectés puis soumis à des règles de déplacement et d'interaction. L'injection se fait à deux échelles, respectivement la plus petite et la plus grande observables: les tubes de flux élémentaires et les taches solaires. Des processus de surface imitant ceux observés sont inclus, et consistent en l'émergence, la coalescence, l'annulation et la submergence de flux. La fragmentation des concentrations n'est présente que pour les taches, sous forme de désintégration libérant des tubes de flux. Le modèle est appliqué au cycle solaire 21 (1976-1986, le mieux documenté en termes de caractéristiques de taches solaires. Il en résulte des réponses à deux questions importantes en physique solaire. La première est: l'injection de flux magnétique à deux échelles très distinctes peut-elle conduire à une distribution de flux en loi de puissance comme on l'observe, si l'on inclut des processus de surface qui retraitent le flux? Cette question est étroitement liée à l'origine de la dynamo solaire, qui pourrait produire ladite distribution. Nous trouvons qu'on peut effectivement produire une telle distribution avec ce type d'injection et ce type de processus de surface. Cela implique que la distribution de flux observée ne peut servir à déterminer quel type de dynamo opère dans le Soleil. La deuxième question à laquelle nous avons apporté un élément de réponse est celle à savoir combien de temps il faut au réseau pour retrouver son état d'activité de base. Cet état a été observé lors du minimum de Maunder en 1645-1715 et touche de près la question de l'influence de l'activité solaire sur le climat terrestre. Le récent minimum d'activité est considéré par certains comme ayant atteint cet état. Nous trouvons plutôt que ça n'a pas été le cas. En effet, le temps de relaxation du réseau que nous avons calculé est supérieur au temps écoulé entre la fin du dernier cycle solaire d'activité et celui de l'amorce du présent cycle. / The magnetic network is an ensemble of small magnetic flux concentrations on the solar photosphere. Given its small scale in size and flux, at the detection limit, its behavior has only been known since recently. The network's interactions are crucial in understanding the solar dynamo and the solar irradiance, as many network characteristics depend on these interactions. The network is the main surface magnetic contribution to the solar irradiance. The extant models of the network so far did not consider interactions. We have attempted to remedy this failing with our model. Our simulations involve a random walk in 2D of magnetic flux tubes on the solar photosphere. The flux tubes are injected, then undergo displacement and interaction rules. Injection occurs on two scales, the smallest and the largest observable respectively: elementary flux tubes and sunspots. Surface processes are included which imitate the ones observed: emergence, coalescence, cancellation and submergence of flux. Fragmentation of concentrations only happens for sunspots, as disintegration releasing flux tubes from the spot. The model is applied to solar cycle 21 (1976-1986), the best documented in terms of sunspot characteristics. Two important questions in solar physics have been answered with this model. The first pertains to whether flux injection at two very distinct flux scales can lead to a flux distribution in the shape of a power law, as observed, in the presence of surface mechanisms which reprocess the flux. This question is tied to the origin of the solar dynamo, which could produce (or not) this distribution. We find that it does produce the aforementioned distribution. This implies that the observed flux distribution cannot be used to constrain the type of dynamo operating in the Sun, because the surface flows can equally well produce the observed flux distribution. The second question is how long the network takes to return to its baseline activity level during a prolonged activity minimum. This state was observed during the Maunder minimum in 1645-1715 and bears strongly on the relationship between solar activity and Earth climate. The recent activity minimum is considered by certain authors to have reached the baseline state of solar activity. However, we find that this was not the case. The network relaxation time we calculate is longer than the duration of the last minimum.

La dispersion dans des milieux poreux homogènes (empilements de grains) a été étudiée par des mesures par résonance magnétique nucléaire (RMN) et des simulations de marches aléatoires dans un réseau de pores. La RMN permet de mesurer l’ensemble des déplacements des molécules d’eau durant un temps tΔ, et d’obtenir propagateurs et moments caractéristiques. L’évolution temporelle du second moment σ (σ2 ∝ taΔ) permet de caractériser de manière précise le régime de dispersion des molécules (Gaussien ou anormal). Des mesures pour des écoulements de 15 < Pe < 45 dans un empilement de grains de 30μm ont permis d’observer une dispersion anormale faiblement super-dispersive (a = 1.17) en écoulement saturé et une augmentation progressive du caractère super-dispersif avec la diminution de la saturation en eau (jusqu’à a = 1.5 pour 42 %)lors d’une co-injection stationnaire eau-huile. En écoulement saturé, les propagateurs et courbes de percée sont quasi-gaussiennes, tandis qu’en écoulement insaturé, les propagateurs sont asymétriques et les courbes de percée présentent des trainées aux grands temps. Dans ces conditions, on montre que la dispersion anormale observée est mieux décrite par des lois stables de Lévy que par des lois gaussiennes. Des simulations de marche aléatoire ont été réalisées dans un réseau de pores extrait d’un milieu poreux réel par imagerie microscanner.Elles permettent d’obtenir les mêmes informations que la RMN, les marcheurs se déplaçant par advection et diffusion. Ces simulations montrent l’existence d’une stagnation non observée dans les expériences, montrant que la simplification du réseau poreux est trop importante et empêche de reproduire certains aspects du champ de vitesses détecté par la RMN. Toutefois, l’évolution temporelle du second moment a également un caractère super-dispersif à temps long à 100 % de saturation / We investigated dispersion in homogeneous porous media (grain packs) by nuclear magnetic resonance (NMR) measurements and random walk simulations in pore networks. We measured water molecules displacements during a time interval tΔ by NMR measurements, which allows us to obtain propagators and charateristic cumulants of displacements such as the mean square displacement σ. The evolution of the cumulant σ as a function of time tΔ (σ2 ∝ taΔ) is a very sensitive test of Gaussian behaviour compared to the analysis of the shape of propagators. In a homogeneous 30μm grain pack and low Peclet numbers (15 < Pe < 45), we observed weak super dispersion in saturated conditions (a = 1.17) and gradually stronger super-dispersionas the water saturation decreases (up to a = 1.5 for 42 %) during steady-state oil-water two phase flow. Insaturated conditions, propagators and breakthrough curves are Gaussian or nearly Gaussian, whereas in two phase conditions, propagators are non symmetric and breakthrough curves show thick tails at long time. Weshow that the anomalous dispersion observed is better explained by Lévy stable laws (asymetric for longitudina ldispersion, and symetric for transverse dispersion) than by Gaussian laws. Random walk simulations were performed in a pore network constructed using high resolution images of the grain pack. They allow us to obtain the same informations than the NMR, with walkers submitted to diffusive and advective effects. The simulations show the existence of an anomalous stagnation not observed in experiments, highlighting the oversimplification of the pore network that prevent reproducing some aspects of the velocity field detected by NMR. However, the simulations indicate similarly a super-dispersion at long time in saturated conditions

Nous étudions le déterminant du laplacien sur les fibrés vectoriels sur les graphes et l'utilisons, en lien avec des techniques d'analyse complexe discrète, pour comprendre des modèles de physique statistique. Nous calculons certaines constantes de réseaux, construisons des limites d'échelles d'excursions de la marche aléatoire à boucles effacées sur les surfaces, et étudions certains champs gaussiens et processus déterminantaux. / We study the determinant of the Laplacian on vector bundles on graphs and use it, combined with discrete complex analysis, to study models of statistical physics. We compute exact lattice constants, construct scaling limits for excursions of the loop-erased random walk on surfaces, and study some Gaussian fields and determinantal processes.