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

A pesquisa apresenta um estudo sobre a superioridade dos analistas de mercado com relação aos modelos random walk na previsão de resultados futuros das empresas brasileiras de capital aberto a curto e longo prazo. A literatura tradicional indica superioridade irrestrita dos analistas de mercado sobre os modelos de séries temporais por conta das vantagens de tempo e informação desses agentes. No entanto, estudos recentes da literatura internacional apontam para a necessidade de reavaliação dessa superioridade indicando que, para determinadas características da empresa e principalmente para estimativas de longo prazo, não se verifica superioridade dos analistas com relação aos modelos de séries temporais. Partindo desses achados, essa pesquisa defende a TESE de que para o caso brasileiro a superioridade dos analistas não é irrestrita. Este trabalho avalia as previsões de lucro dos analistas e dos modelos random walk, simples e com crescimento, a curto e longo prazo, para as empresas brasileiras de capital aberto no período de 2010 a 2015. Os dados foram obtidos via plataforma da Thomson Reuters®, nas bases de dados do I/B/E/S® e Thomson Financial. Seguindo a literatura, foram utilizados testes de diferença de média. Como diferencial da pesquisa, foi realizada uma análise de dados em painel no sentido de permitir uma avaliação mais precisa sobre os determinantes da superioridade dos analistas para o caso brasileiro. Ainda, foi proposto um modelo de regressão linear simples para avaliar o conteúdo informacional das previsões dos analistas de mercado e dos modelos random walk. Os resultados indicam: i) maior acurácia de previsão paras os modelos random walk simples quando comparados com os modelos de random walk com crescimento; ii) para a amostra total, nota-se maior acurácia da previsão dos modelos random walk a curto e longo prazo, com superioridade dos analistas apenas para previsões com três meses de defasagem; iii) além da defasagem de previsão, a variabilidade dos lucros, a quantidade de analistas, a dispersão das estimativas dos analistas, o tamanho da empresa, o resultado positivo ou negativo, a listagem em índice de mercado e a idade da empresa no mercado de capitais são fatores que alteram a superioridade dos analistas para o caso brasileiro; iv) maior conteúdo informacional das previsões random walk para previsão de lucros futuros das empresas. Esses resultados são importantes nas decisões de investimento. Ainda, os achados são relevantes para pesquisas da área de finanças e contabilidade que utilizam essa variável para responder a diferentes questões de pesquisa, uma vez que, ao contrário do apontado pela literatura internacional, as evidências sugerem superioridade de previsão dos modelos random walk quando comparados às previsões dos analistas de mercado / The research presents a study regarding the superiority of market analysts in relation to the random walk models in the forecast of future results of Brazilian companies in the short and long term. The traditional literature indicates unrestricted superiority of market analysts on time series models because of the time and information advantages of these agents. However, recent studies in the international literature point to the need for a reassessment of this superiority, indicating that, for certain company characteristics and especially for long-term estimates, there is no superiority of analysts with respect to time series models. Based on these findings, this research advocates that in the case of Brazil, the superiority of analysts is not unrestricted. This paper evaluates the analysts\' forecasts and the random walk models, both simple and with growth, in the short and long term, for Brazilian publicly traded companies during the period from 2010 to 2015. Data was obtained via the Thomson Reuters® platform, in the I/B/E/S® and Thomson Financial®databases. Following the literature, mean-comparison tests (t-test) were used. As a research differential, a panel data analysis was carried out in order to allow a more precise evaluation of the determinants of analysts\' superiority for the case of Brazil. Furthermore, a simple linear regression model was proposed to evaluate the informational content of market analysts\' forecasts and random walk models. The results indicate: i) greater accuracy of prediction for the simple random walk models, when compared to the random walk models with growth ii) that for the total sample, we can see a greater accuracy of the forecast of random walk models in the short and long term, with analyst superiority only for forecasts with a 3-month lag; (iii) in addition to forecast lag, profit variability, analyst size, dispersion of analysts\' estimates, company size, positive or negative result, market index listing and age of the company in the capital market are factors that alter the superiority of the analysts in the case of Brazil; iv) greater informational content of the random walk forecasts for the prediction of future companies\' profits. These results are important for investment decisions. Moreover, the findings are relevant for research in the field of finance and accounting that use this variable to answer different research questions, since, contrary to the international literature, the evidence suggests forecasting superiority of the random walk models when compared to the market analysts\' forecasts.