Graph embedding, aiming to learn low-dimensional representations for nodes in graphs, has attracted increasing attention due to its critical application including node classification, link prediction and clustering in social network analysis. Most existing algorithms for graph embedding only rely on the topology information and fail to use the copious information in nodes as well as edges. As a result, their performance for many tasks may not be satisfactory. In this thesis, we proposed a novel and general framework for graph embedding with rich text information (GERI) through constructing a heterogeneous network, in which we integrate node and edge content information with graph topology. Specially, we designed a novel biased random walk to explore the constructed heterogeneous network with the notion of flexible neighborhood. Our sampling strategy can compromise between BFS and DFS local search on heterogeneous graph. To further improve our algorithm, we proposed semi-supervised GERI (SGERI), which learns graph embedding in an discriminative manner through heterogeneous network with label information. The efficacy of our method is demonstrated by extensive comparison experiments with 9 baselines over multi-label and multi-class classification on various datasets including Citeseer, Cora, DBLP and Wiki. It shows that GERI improves the Micro-F1 and Macro-F1 of node classification up to 10%, and SGERI improves GERI by 5% in Wiki.

This thesis concerns applications of some probabilistic tools to phylogeny reconstruction and population genetics. Modelling the evolution of species by continuous-time random walks on the signed permutation groups, we study the asymptotic medians of a set of random permutations sampled from simple random walks at time 0.25cn, for c> 0. Running k independent random walks all starting at identity, we prove that the medians approximate the ancestor (identity permutation) up to time 0.25n, while there exists a constant c>1 after which the medians loose credibility as an estimator. We study the median of a set of random permutations on the symmetric group endowed with different metrics. In particular, for a special metric of dissimilarity, called breakpoint, where the space is not geodesic, we find a large group of medians of random permutations using the concept of partial geodesics (or geodesic patches). Also, we study the Fleming-Viot process in random environment (FVRE) via martingale and duality methods. We develop the duality method to the case of time-dependent and quenched martingale problems. Using a family of dual processes we prove the convergence of the Moran processes in random environments to FVRE in Skorokhod topology. We also study the long-time behaviour of FVRE and prove the existence of equilibrium for the joint annealed-environment process and prove an ergodic theorem for the latter.

What is the probability that in a fair coin toss game (a simple random walk) we go bankrupt in n steps when there is an initial lead of some known or unknown quantity $m? What is the distribution of the number of steps N that it takes for the lead to vanish? This thesis explores some of the features of this first passage to the origin (FPO) distribution. First, we explore the distribution of N when m is known. Next, we compute the maximum likelihood estimators of m for a fixed n and also the posterior distribution of m when we are given that m follows some known prior distribution.

In this paper we will investigate the connection between a random walk and a continuous time stochastic process. Donsker's Theorem states that a random walk under certain conditions will converge to a Wiener process. We will provide a detailed proof of this theorem which will be used to prove that a geometric random walk converges to a geometric Brownian motion.

We explore the role of cooperativity and large deviations on a set of fundamental non-equilibrium many-body systems. In the cooperative asymmetric exclusion process, particles hop to the right at a constant rate only when the right neighboring site is vacant and hop at a faster rate when the left neighbor is occupied. In this model, a host of new heterogeneous density profile evolutions arise, including inverted shock waves and continuous compression waves. Cooperativity also drives the growth of complex networks via preferential attachment, where well-connected nodes are more likely to attract future connections. We introduce the mechanism of hindered redirection and show that it leads to network evolution by sublinear preferential attachment. We further show that no local growth rule can recreate superlinear preferential attachment. We also introduce enhanced redirection and show that the rule leads to networks with three unusual properties: (i) many macrohubs -- nodes whose degree is a finite fraction of the number of nodes in the network, (ii) a non-extensive degree distribution, and (iii) large fluctuations between different realizations of the growth process. We next examine large deviations in the diffusive capture model, where N diffusing predators initially all located at L 'chase' a diffusing prey initially at x<L. The prey survives if it reaches a haven at the origin without meeting any predator. We reduce the stochastic movement of the many predators to a deterministic trajectory of a single effective predator. Using optimized Monte Carlo techniques, we simulate up to 10^500 predators to confirm our analytic prediction that the prey survival probability S ~ N^-z^2, where z=x/L. Last, we quantify `survival of the scarcer' in two-species competition. In this model, individuals of two distinct species reproduce and engage in both intra-species and inter-species competition. Here a well-mixed population typically reaches a quasi steady state. We show that in this quasi-steady state the situation may arise where species A is less abundant than B but rare fluctuations make it more likely that species B first becomes extinct.

Nous nous intéressons dans cette thèse à l'organisation des systèmes distribués dynamiquesde grande taille : ensembles de machines capables de communiquer entre elles et pouvant à toutinstant se connecter ou se déconnecter. Nous proposons de partitionner le système en groupesconnexes, appelés clusters. Afin d'organiser des réseaux de grande taille, nous construisons unestructure hiérarchique imbriquée dans laquelle les clusters d'un niveau sont regroupés au seinde clusters du niveau supérieur. Pour mener à bien ce processus, nous mettons en place desmécanismes permettant aux clusters d'être les noeuds d'un nouveau système distribué exécutantl'algorithme de notre choix. Cela nécessite en particulier des mécanismes assurant la cohérence decomportement pour le niveau supérieur au sein de chaque cluster. En permettant aux clusters deconstituer un nouveau système distribué exécutant notre algorithme de clustering, nous construisonsune hiérarchie de clusters par une approche ascendante. Nous démontrons cet algorithme endéfinissant formellement le système distribué des clusters, et en démontrant que chaque exécutionde notre algorithme induit sur ce système une exécution de l'algorithme de niveau supérieur. Celanous permet, en particulier, de démontrer par récurrence que nous calculons bien un clusteringhiérarchique imbriqué. Enfin, nous appliquons cette démarche à la résolution des collisions dansles réseaux de capteurs. Pour éviter ce phénomène, nous proposons de calculer un clusteringadapté du système, qui nous permet de calculer un planning organisant les communications ausein du réseau et garantissant que deux messages ne seront jamais émis simultanément dans laportée de communication de l'un des capteurs / To manage and handle large scale distributed dynamic distributed systems, constitutedby communicating devices that can connect or disconnect at any time, we propose to computeconnected subgraphs of the system, called clusters. We propose to compute a hierarchical structure,in which clusters of a level are grouped into clusters of the higher level. To achieve this goal,we introduce mechanisms that allow clusters to be the nodes of a distinct distributed system,that executes an algorithm. In particular, we need mechanisms to maintain the coherence of thebehavior among the nodes of a cluster regarding the higher level. By allowing clusters to be nodesof a distributed system that executes a clustering algorithm, we compute a nested hierarchicalclustering by a bottom-up approach. We formally define the distributed system of clusters, andprove that any execution of our algorithm induces an execution of the higher level algorithm onthe distributed system of clusters. Then, we prove by induction that our algorithm computes anested hierarchical clustering of the system. Last, we use this approach to solve a problem thatappears in sensor networks : collision. To avoid collisions, we propose to compute a clusteringof the system. This clustering is then used to compute a communication schedule in which twomessages cannot be sent at the same time in the range of a sensor

No description available.

No description available.

Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts. / Mathematics

This study explores optimal strategies for maximizing scores and winning in the popular dice game Qwixx, analyzing both single and multiplayer gameplay scenarios. Through extensive simulations, various strategies were tested and compared, including a scorebased approach that uses a formula tuned by MCMC random walks, and race-to-lock approaches which use absorbing Markov chain qualities of individual score sheet rows to find ways to lock rows as quickly as possible. Results indicate that employing a scorebased strategy, considering gap, count, position, skip, and likelihood scores, significantly improves performance in single player games, while move restrictions based on specific dice roll sums in the race-to-lock strategy were found to enhance winning and scoring points in multiplayer games. While the results do not achieve the optimal scores attained by prior informal work, the study provides valuable insights into decision-making processes and gameplay optimization for Qwixx enthusiasts, offering practical guidance for players seeking to enhance their performance and strategic prowess in the game. It also serves as a lesson for how to approach optimization problems in the future.