Recommender systems have become paramount to customize information access and reduce information overload. They serve multiple uses, ranging from suggesting products and artifacts (to consumers), to bringing people together by the connections induced by (similar) reactions to products and services. This thesis presents a graph-theoretic model that casts recommendation as a process of 'jumping connections' in a graph. In addition to emphasizing the social network aspect, this viewpoint provides a novel evaluation criterion for recommender systems. Algorithms for recommender systems are distinguished not in terms of predicted ratings of services/artifacts, but in terms of the combinations of people and artifacts that they bring together. We present an algorithmic framework drawn from random graph theory and outline an analysis for one particular form of jump called a 'hammock.' Experimental results on two datasets collected over the Internet demonstrate the validity of this approach. / Master of Science

Most real-world networks exhibit a high clustering coefficient— the probability that two neighbors of a node are also neighbors of each other. We propose four algorithms CONF-1, CONF-2, THROW-1, and THROW-2 which are based on the configuration model and that take triangle degree sequence (representing the number of triangles/corners at a node) and single-edge degree sequence (representing the number of single-edges/stubs at a node) as input and generate a random graph with a tunable clustering coefficient. We analyze them theoretically and empirically for the case of a regular graph. CONF-1 and CONF-2 generate a random graph with the degree sequence and the clustering coefficient anticipated from the input triangle and single-edge degree sequences. At each time step, CONF-1 chooses each node for creating triangles or single edges with the same probability, while CONF-2 chooses a node for creating triangles or single edge with a probability proportional to their number of unconnected corners or unconnected stubs, respectively. Experimental results match quite well with the anticipated clustering coefficient except for highly dense graphs, in which case the experimental clustering coefficient is higher than the anticipated value. THROW-2 chooses three distinct nodes for creating triangles and two distinct nodes for creating single edges, while they need not be distinct for THROW-1. For THROW-1 and THROW-2, the degree sequence and the clustering coefficient of the generated graph varies from the input. However, the expected degree distribution, and the clustering coefficient of the generated graph can also be predicted using analytical results. Experiments show that, for THROW-1 and THROW-2, the results match quite well with the analytical results. Typically, only information about degree sequence or degree distribution is available. We also propose an algorithm DEG that takes degree sequence and clustering coefficient as input and generates a graph with the same properties. Experiments show results for DEG that are quite similar to those for CONF-1 and CONF-2. / Master of Science

The phenomenon of scale dependent spectral dimension has attracted special interest in the quantum gravity community over the last eight years. It was first observed in computer simulations of the causal dynamical triangulation (CDT) approach to quantum gravity and refers to the reduction of the spectral dimension from 4 at classical scales to 2 at short distances. Thereafter several authors confirmed a similar result from different approaches to quantum gravity. Despite the contribution from different approaches, no analytical model was proposed to explain the numerical results as the continuum limit of CDT. In this thesis we introduce graph ensembles as toy models of CDT and show that both the continuum limit and a scale dependent spectral dimension can be defined rigorously. First we focus on a simple graph ensemble, the random comb. It does not have any dynamics from the gravity point of view, but serves as an instructive toy model to introduce the characteristic scale of the graph, study the continuum limit and define the scale dependent spectral dimension. Having defined the continuum limit, we study the reduction of the spectral dimension on more realistic toy models, the multigraph ensembles, which serve as a radial approximation of CDT. We focus on the (recurrent) multigraph approximation of the two-dimensional CDT whose ensemble measure is analytically controlled. The latter comes from the critical Galton-Watson process conditioned on non-extinction. Next we turn our attention to transient multigraph ensembles, corresponding to higher-dimensional CDT. Firstly we study their fractal properties and secondly calculate the scale dependent spectral dimension and compare it to computer simulations. We comment further on the relation between Horava-Lifshitz gravity, asymptotic safety, multifractional spacetimes and CDT-like models.

Recent years have seen progress in the analysis of the heat kernel for certain reversible random walks in random environments. In particular the work of Barlow(2004) showed that the heat kernel for the random walk on the infinite component of supercritical bond percolation behaves in a Gaussian fashion. This heat kernel control was then used to prove a quenched functional central limit theorem. Following this work several examples have been analysed with anomalous heat kernel behaviour and, in some cases, anomalous scaling limits. We begin by generalizing the first result - looking for sufficient conditions on the geometry of the environment that ensure standard heat kernel upper bounds hold. We prove that these conditions are satisfied with probability one in the case of the random walk on continuum percolation and use the heat kernel bounds to prove an invariance principle. The random walk on dynamic environment is then considered. It is proven that if the environment evolves ergodically and is, in a certain sense, geometrically d-dimensional then standard on diagonal heat kernel bounds hold. Anomalous lower bounds on the heat kernel are also proven - in particular the random conductance model is shown to be "more anomalous" in the dynamic case than the static. Finally, the reflected random walk amongst random conductances is considered. It is shown in one dimension that under the usual scaling, this walk converges to reflected Brownian motion.

This thesis studies two Markov processes describing the evolution of a system of many interacting random components. These processes undergo an absorbing-state phase transition, i.e., as one variates the parameter values, the process exhibits a transition from a convergence regime to one of the absorbing-states to an active regime. In Chapter 2 we study Activated Random Walk, which is an interacting particle system where the particles can be of two types and their number is conserved. Firstly, we provide a new lower bound for the critical density on Z as a function of the jump distribution and of the sleeping rate and we prove that the critical density is not a constant function of the jump distribution. Secondly, we prove that on Zd in the case of biased jump distribution the critical density is strictly less than one, provided that the sleeping rate is small enough. This answers a question that has been asked by Dickman, Rolla, Sidoravicius [9, 28] in the case of biased jump distribution. Our results have been presented in [33]. In Chapter 3 we study a class of probabilistic cellular automata which are related by a natural coupling to a special type of oriented percolation model. Firstly, we consider the process on a finite torus of size n, which is ergodic for any parameter value. By employing dynamic-renormalization techniques, we prove that the average absorption time grows exponentially (resp. logarithmically) with n when the model on Z is in the active (resp. absorbing) regime. This answers a question that has been asked by Toom [37]. Secondly, we study how the neighbourhood of the model affects the critical probability for the process on Z. We provide a lower bound for the critical probability as a function of the neighbourhood and we show that our estimates are sharp by comparing them with our numerical estimates. Our results have been presented in [34, 35].

Dans cette thèse, nous nous intéressons à la monotonie de la vitesse de la marche aléatoire excitée (MAE) avec biais $bein[0,1]$ dans la première direction $e_1$. Nous présentons une nouvelle preuve de la monotonie de la vitesse pour des grandes dimensions $dgeq d_0$ et pour le cas où le paramètre $be$ est petit quand $dgeq 8$. Ensuite, nous considérons les marches aléatoires avec plusieurs cookies aléatoires. La monotonie de la vitesse est ausi prouvée pour les cas particuliers par exemple des dimensions sont grandes, le paramètre de dérive $be$ est petit ou le nombre de cookies est grand. Ce sont les cas où la marche aléatoire est proche à la marche aléatoire simple. Pour l'existence de la vitesse, nous avons montré la loi des grands nombres pour un cas particulier du cookie aléatoire stationaire, mais nous n'arrivons pas encore pour le cas stationaire. Sur la monotonie, nous avons aussi vérifié que le nombre de points visités par la marche aléatoire simple avec biais $be$ est croissant.Finalement, une question très interessant: la monotonie de la vitesse, est-elle vraie pour la MAE pour les petites dimensions $2leq dleq 8.$ Pour cette motivation, nous avons prouvé que la vitesse est indéfiniment différentiable pour $be>0.$ Au point critique $0$, nous avons prouvé que la dérivée de la vitesse existe et égale $0$ pour $d=2$, existe et est positive pour $dgeq 4.$ Mais nous ne savons pas encore si la dérivée de l'ordre 2 en point $0$ existe ou au moin la dérivée est continue en $0$ pour prouver la monotonie de la vitesse au voisinage de $0$? / In this thesis, we are interested in the monotonicity of the speed of the excited random walk (ERW) with bias $bein[0,1]$ in the first direction $e_1.$ The speed is defined as the limit obtained by the law of large number for the horizontal component. The speed depend on the bias $be.$ We present a new proof of the monotonicity of the speed for the dimension $dgeq d_0$, where $d_0$ is large enough, or for the parameter $be$ is small when $dgeq 8$. After that, we consider the random walk with multi-random cookies. The monotonicity of the speed is also proved for some particular cas, for exemple when the dimension is high, or the parameter drift is small, or the number of cookies is large. These are the cas where the walk is near the simple random walk. For the existence of the speed, we also proved the law of large number for a particular cas of stationary cookie but we haven't yet gotten the cas stationary. On the monotonicity, we also proved the rang of the simple random walk with drift $be$ is increasing in the drift. Finally, a question very interesting: the monotonicity of the speed of ERW is true for the small dimension $2leq dleq 8$, isn't it? For this motivation, we proved the speed is infinitly differentiable for all $be>0.$ At the critical point $0,$ we also proved the derivative of the speed at $0$ exists and equals $0$ for $d=2$, exists and is positive for $dgeq 4.$ But we haven't yet known if the derivative of order $2$ at $0$ exists or at least the derivative is continuous at $0$ to prove the monotonicity of the speed in a neighbor of $0$.

Reliability and computational efficiency of classification error estimators are critical factors in classifier design. In a high-dimensional data setting where data is scarce, the conventional method of error estimation, cross-validation, can be very computationally expensive. In this thesis, we consider a particular discriminant analysis type classifier, the Randomly-Projected RLDA ensemble classifier, which operates under the assumption of such a ‘small sample’ regime. We conduct an asymptotic study of the generalization error of this classifier under this regime, which necessitates the use of tools from the field of random matrix theory. The main outcome of this study is a deterministic function of the true statistics of the data and the problem dimension that approximates the generalization error well for large enough dimensions. This is demonstrated by simulation on synthetic data. The main advantage of this approach is that it is computationally efficient. It also constitutes a major step towards the construction of a consistent estimator of the error that depends on the training data and not the true statistics, and so can be applied to real data. An analogous quantity for the Randomly-Projected LDA ensemble classifier, which appears in the literature and is a special case of the former, is also derived. We motivate its use for tuning the parameter of this classifier by simulation on synthetic data.

Cette thèse présente une étude des propriétés de la lumière émise par des diffuseurs atomiques distribués aléatoirement dans l'espace euclidien, et interagissant avec le champ électromagnétique. Dans ce cadre, une théorie ab initio des lasers aléatoires est formulée en terme des propriétés statistiques de la `matrice de Green'. Cette dernière appartient à la famille des matrices aléatoires euclidiennes (MAE) pour lesquelles nous développons une théorie analytique donnant notamment accès à la distribution de probabilité de leurs valeurs propres. Dans un premier temps, nous démontrons les équations quantiques microscopiques régissant la dynamique du champ électrique ainsi que celle des opérateurs atomiques, et explicitons comment la matrice de Green (dont les éléments sont égaux à la fonction de Green de l'équation de Helmholtz évaluée entre les différentes paires d'atomes constituant le milieu) émerge naturellement du formalisme quantique. Nous exprimons à la fois l'intensité et le spectre de la lumière en termes des propriétés de la matrice de Green, caractérisons les forces de Langevin quantiques, et montrons de quelle manière le seuil semi-classique d'un laser aléatoire est affecté par la prise en considération des fluctuations quantiques (chapitres 2 et 3). Une description mésoscopique et semi-classique de la lumière diffusée par un grand nombre d'atomes soumis à une pompe externe et distribués aléatoirement dans l'espace libre est présentée dans le quatrième chapitre. Après avoir établi une condition de seuil laser universelle, valide quelle que soit la configuration des atomes, nous démontrons une équation de transport obéie par l'intensité moyenne en présence de gain, discutons différentes approximations de cette dernière (équation de Bethe-Salpeter, équation de Boltzmann, équation de diffusion), établissons un `mapping' avec les MAE, et analysons la condition de seuil laser déduite de l'équation de transport. Poussés par la volonté de caractériser analytiquement les propriétés statistiques de la matrice de Green, nous développons dans les chapitres 5 et 6 une théorie générale des MAE, hermitiennes et non hermitiennes, valide dans la limite de grande taille matricielle. Nous obtenons des équations couplées pour la résolvante et le corrélateur des vecteur propres d'une MAE arbitraire, puis testons la validité de nos résultats sur trois matrices jouant un rôle important dans l'étude de la propagation des ondes en milieux désordonnés: la matrice de Green dans l'espace tridimensionnel, sa partie imaginaire, et sa partie réelle. D'un point de vue physique, nous sommes capables de décrire analytiquement avec une bonne précision la distribution de probabilité des taux d'émission lumineux dus à un grand nombre d'atomes, ainsi que celle du déplacement lumineux collectif dû à l'interaction lumière-matière. Par ailleurs, nous proposons d'utiliser la distribution des valeurs propres de la matrice de Green non hermitienne comme une carte unique sur laquelle peuvent s'identifier différents régimes de désordre (balistique, diffusif, localisé, milieu effectif, superradiance). Finalement, nous combinons les équations microscopiques de l'interaction lumière-matière avec nos résultats relatifs aux MAE non-hermitiennes afin de caractériser dans le détail le comportement des lasers aléatoires. Le seuil laser ainsi que l'intensité au delà du seuil sont calculés analytiquement dans l'approximation semi-classique, et le spectre de la lumière sous le seuil est évalué en prenant en compte les effets quantiques. Notre théorie s'applique aussi bien à basse densité qu'à haute densité de diffuseurs atomiques. / This thesis is devoted to the study of the properties of light emitted by a collection of atomic scatterers distributed at random positions in Euclidean space and interacting with the electromagnetic field. In this respect, an ab initio analytic theory of random lasing is formulated in terms of the statistical properties of the so-called `Green's matrix'. The latter belongs to the family of Euclidean random matrices (ERM's), for which we develop an analytic theory giving access to their eigenvalue distribution. First, we derive quantum microscopic equations for the electric field and atomic operators, and show how the non-Hermitian Green's matrix (a matrix with elements equal to the Green's function of the Hemholtz equation between pairs of atoms in the system) emerges in the quantum formalism. We provide expressions for the intensity and the spectrum of light in terms of the properties of the Green's matrix, characterize quantum Langevin forces, and reveal how the semiclassical random laser threshold is washed out by quantum fluctuations (chapters 2 and 3). A mesoscopic and semiclassical description of light scattered by an arbitrary large number of pumped atoms randomly distributed in free space is the subject of chapter 4. After deriving a universal lasing threshold condition valid for any configuration of atoms, we provide a microscopic derivation of transport equation in the presence of gain, discuss various approximations of the latter (Bethe-Salpeter, Boltzmann, diffusion equations), reveal a mapping to ERM's, and analyze the lasing threshold condition inferred from the transport equation. Facing the problem of characterizing analytically the statistical properties of the Green's matrix, we develop in chapters 5 and 6 a theory for Hermitian and non-Hermitian ERM's in the limit of large matrix size. We obtain self-consistent equations for the resolvent and the eigenvector correlator of arbitrary ERM and apply our results to three different ERM's relevant to wave propagation in random media: the three-dimensionnal Green's matrix, its imaginary part and its real part. From a physical point of view, we are able to describe analytically with a fair precision the full probability distribution of decay rates of light emitted by a large number of atoms, as well as of the collective frequency shift induced by the light-matter interaction. In addition, we promote the idea that the eigenvalue distribution of the Green's matrix can serve as a map on which signatures of various regimes of disorder can be distinguished (ballistic, diffusive, localized, effective medium, and superradiance regimes). Finally, we combine microscopic equations of motion of light-matter interaction with our results for non-Hermitian ERM's to tackle the problem of random lasing. Lasing threshold and the intensity of laser emission are calculated analytically in the semiclassical approximation, and the spectrum of light below threshold is computed by taking into account quantum effects. Our theory applies all the way from low to high density of atoms.

Random Forest é uma técnica computacionalmente eciente que pode operar rapida-mente sobre grandes bases de dados. Ela tem sido usada em muitos projetos de pesquisa recentes e aplicações do mundo real em diversos domínios, entre eles a bioinformática uma vez que a Random Forest consegue lidar com bases que apresentam muitos atributos e poucos exemplos. Porém, ela é de difícil compreensão para especialistas humanos de diversas áreas. A pesquisa de mestrado aqui relatada tem como objetivo criar um modelo simbólico, ou seja, uma única árvore a partir da Random Forest para a classicação de bases de dados de expressão gênica. Almeja-se assim, aumentar a compreensão por parte dos especialistas humanos sobre o processo que classica os exemplos no mundo real tentando manter um bom desempenho. Os resultados iniciais obtidos com o algoritmo aqui proposto são pro-missores, uma vez que ela apresenta, em alguns casos, desempenho melhor do que outro algoritmo amplamente utilizado (J48) e um pouco inferior à Random Forest. Além disso, a árvore criada apresenta, no geral, tamanho menor do que a árvore criada pelo algoritmo J48. / Random Forest is a computationally ecient technique which can operate quickly over large datasets. It has been used in many research projects and recent real-world applications in several elds, including bioinformatics since Random Forest can handle datasets having many attributes, and few examples. However, it is dicult for human experts to understand it. The research reported here aims to create a symbolic model, i.e. a single tree from a Random Forest for the classication of gene expression datasets. Thus, we hope to increase the understanding by human experts on the process that classies the examples in the real world trying to keep a good performance. Initial results obtained from the proposed algorithm are promising since it presents in some cases performance better than other widely used algorithm (J48) and a slightly lower than a Random Forest. Furthermore, the induced tree presents, in general, a smaller size than the tree built by the algorithm J48.

O presente trabalho estuda o modelo de Blume-Capel na rede aleatória e também analisa a inclusão de um termo de campo cristalino aleatório e de um termo de campo local aleatório. Ao resolver o modelo na rede aleatória, uma técnica de conectividade finita foi utilizada, na qual cada spin é conectado a um número finito de outros spins. Os spins foram conectados de acordo com uma distribuição de Poisson, os termos de campo aleatório seguiram uma distribuição bimodal e as interações entre os spins foram consideradas uniformes. Desse modo, só há desordem nas conexões entre os spins. O foco desse trabalho foi determinar como a natureza da transição de fase é alterada com a conectividade e se há um comportamento reentrante das linhas de transição de fase. A técnica de réplicas é usada para obter equações de ponto de sela para a distribuição de campos locais. Um Ansatz de simetria de réplicas foi utilizado para a função de ordem e esse foi escrito em termos de uma distribuição bidimensional de campos efetivos, onde uma das componentes é associada com um termo linear dos spins e a outra com o termo de campo cristalino. Com isso, equações para as funções de ordem e a energia livre podem ser obtidas. Uma técnica de dinâmica populacional é usada para resolver numericamente a equação auto-consistente para a distribuição de campos locais e outros parâmetros, como a magnetização, a atividade da rede e a energia livre. Os resultados indicam que a natureza da transição ferromagnética-paramagnética, a posição do ponto tricrítico e a existência de reentrância dependem fortemente do valor da conectividade e, nos casos com um termo de campo aleatório, dependem da intensidade dos campos aleatórios. No caso em que o campo cristalino é aleatório, o ponto tricrítico é suprimido para valores acima de um certo valor de aleatoriedade. / The present work studies the Blume-Capel model in a random network and also analyses the inclusion of a random crystal-field term and a random field term. To solve the model in a random network a finite connectivity technique is used, in which each spin is connected to a finite number of other spins. The spins were connected according a Poisson distribution, the random field terms followed a bimodal distribution and the bonds between the spins were considered uniform. Thus, there is only a connection disorder. The focus of this work was on determining how the nature of the phase transition changes with the connectivity and the random fields and if there is a reentrant behavior of the phase boundaries. The replica technique is used to obtain saddle-point equations for the effective local-field distribution. The replica symmetric Ansatz for the order function is written in terms of a two-dimensional effective-field distribution, where one of the components is associated with a linear form in the spins and the other with the crystal-field term. This allows one to derive equations for the order function and for the free-energy. A population dynamics procedure is used to solve numerically a self-consistency equation for the distribution of the local field and with it some physical parameters, like magnetization and free-energy. The results obtained indicate that the nature of the F-P transition, the location of the tricritical point and the presence of a reentrant phase depend strongly on the connectivity. In the cases with a random field term, those are also dependent on the intensity of the fields. For the case with a random crystal-field term, the tricritical point is supressed above a certain value of randomness.