Self-avoiding walks on a d-dimensional hypercubic lattice are used to model a polymer interacting with a surface. One can choose to weight the walk by the number of vertices or the number of edges on the surface and define the free energy of the polymer using equilibrium statistical mechanics. We look at the behaviour of the free energy in the limit that temperature goes to zero and also derive inequalities relating the critical points of the two weighting schemes. A combined model with weights associated with both the number of vertices and the number of edges on the surface is investigated and the properties of its phase diagram are explored. Finally, we look at Motzkin paths and partially-directed walks in the combined edge and vertex model and compare their results to the self-avoiding walk’s.

With the increasing popularity of social networking applications, large volumes of graph data are becoming available. Large graphs are also derived by structure extraction from relational, text, or scientific data (e.g., relational tuple networks, citation graphs, ontology networks, protein-protein interaction graphs). Nodeto-node proximity is the key building block for many graph based applications that search or analyze the data. Among various proximity measures, random walk with restart (RWR) is widely adapted because of its ability to consider the global structure of the whole network. Although RWR-based similarity search has been well studied before, there is no prior work on reverse top-k proximity search in graphs based on RWR. We discuss the applicability of this query and show that the direct application of existing methods on RWR-based similarity search to solve reverse top-k queries has very high computational and storage demands. To address this issue, we propose an indexing technique, paired with an on-line reverse top-k search algorithm. In the indexing step, we compute from the graph G a graph index, which is based on a K X |V| matrix, containing in each column v the K largest approximate proximity values from v to any other node in G. K is application-dependent and represents the highest value of k in a practical reverse top-k query. At each column v of the index, the approximate values are lower bounds of the K largest proximity values from v to all other nodes. Given the graph index and a reverse top-k query q (k _ K), we prove that the exact proximities from any node v to query q can be efficiently computed by applying the power method. By comparing these with the corresponding lower bounds taken from the k-th row of the graph index, we are able to determine which nodes are certainly not in the reverse top-k result of q. For some of the remaining nodes, we may also be able to determine that they are certainly in the reverse top-k result of q, based on derived upper bounds for the k-th largest proximity value from them. Finally, for any candidate that remains, we progressively refine its approximate proximities, until based on its lower or upper bound it can be determined not to be or to be in the result. The proximities refined during a reverse top-k are used to update the graph index, making its values progressively more accurate for future queries. Our experimental evaluation shows that our technique is efficient and has manageable storage requirements even when applied on very large graphs. We also show the effectiveness of the reverse top-k search in the scenarios of spam detection and determining the popularity of authors. / published_or_final_version / Computer Science / Master / Master of Philosophy

No description available.

Proefschrift Universiteit van Amsterdam. / Met lit. opg. - Met samenvatting in het Nederlands.

Thesis (Ph. D.)--University of Washington, 1999. / Vita. Includes bibliographical references (p. 114).

Thesis (M.Sc.)--York University, 2005. Graduate Programme in Mathematics and Statistics. / Typescript. Includes bibliographical references (leaves 99-102). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url%5Fver=Z39.88-2004&res%5Fdat=xri:pqdiss &rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR11932

This thesis is about graph-indexed random walks, Lipschitz mappings and graph homo- morphisms. It discusses connections between these notions, surveys the existing results, and shows new results. Graph homomorphism is an adjacency-preserving mapping between two graphs. Our main objects of study are graph homomorphisms to an infinite path. We are interested in two parameters: maximum range and average range. The average range of a graph is the expected size of the image of a uniformly picked random homomorphism to an infinite path. We obtain formulas for several graph classes and investigate main conjectures on this parameter. For maximum range parameter we show a general formula and an algorithm to compute it for general graphs. Besides that, we study the problem of extending a prescribed partial graph homomorphism to a full graph homomorphism. We show that this problem is polynomial in some cases. 1

This study investigates the independence assumption of the theory of random walks in stock market prices through the simulation of the moving average strategy. In the process of doing so, three related questions are examined: (1) Does the past relative volatility of a stock furnish a useful indication of its future behavior? (2) Is the performance of the decision rule improved by applying it to those securities which are likely to be highly volatile? (3) Does positive dependence in successive monthly price changes exist? The purpose of Test No. 1 was to gauge the tendency for a stock's relative volatility to remain constant over two adjacent intervals of time. As measured by the coefficient of variation, the volatility of each of the 200 securities was computed over the 1936 to 1945 and 1946 to 1955 decades. In order to evaluate the strength of the relationship between these paired observations, a rank correlation analysis was performed. The results indicated a substantial difference in relative volatility for each security over the two ten-year periods. In Test No. 2 a different experimental design was employed to determine whether the relative volatility of a stock tended to remain within a definite range over time. According to their volatility in the 1936 to 1945 period, the 200 securities were divided into ten groups. Portfolio No. 1 contained the twenty most volatile securities while Portfolio No. 2 consisted of the next twenty most volatile, etc. An average coefficient of variation was calculated for each group over the periods, 1936 to 1945 and 1946 to 1955. The rank correlation analysis on these ten paired observations revealed that the most volatile securities, as a group, tended to remain the most volatile. Test No. 3 consisted of the application of the moving average strategy (for long positions only) to forty series of month-end prices covering the interval, 1956 to 1966. These securities had demonstrated a high relative volatility over the previous decade and, on the basis of the findings reported in Test No. 2, it was forecasted that they would be the most volatile of the sample of 200 in the period under investigation. Four different moving averages ranging from three to six months, and thirteen different thresholds ranging from 2 to 50 per cent were simulated. The results of the simulation showed the moving average strategy to be much inferior to the two buy-and-hold models. Every threshold regardless of the length of the moving average yielded a negative return. In addition, the losses per threshold were spread throughout the majority of stocks. Altogether, therefore, considerable evidence was found in favour of the random walk theory of stock price behavior. / Business, Sauder School of / Graduate

This is an imaginative and speculative project that takes its point of departure from an architectural competition announced in 2009 for a new cemetery on Järvafältet.  The project is curated according to three walks: The level walk -uses varying levels to accommodate different types of burial. The sound walk - uses sound as a means of memorializing the deceased. The node walk – rethinks the conventional religious segregation of cemetery space toward integration and an ecological way of reusing land for burial.

A dissertation submitted in fulfillment of the requirements for the degree of Masters in Science in the, The Structured Light Group Department of Physics, University of the Witwatersrand, Johannesburg, 2018 / At the quantum level, entities and systems often behave counter-intuitively which we have come to describe with wave-particle duality. Accordingly, a particle that moves definitively from one position to another in our classical experience does something completely different on the quantum scale. The particle is not localized at any one position, but spreads out over all the possibilities as it moves. Here the particle can interfere with itself with wave-like propagation and generate, what is known as a Quantum Walk. This is the quantum mechanical analogue of the already well-known and used Random Walk where the particle takes random steps across the available positions, building up a series of random paths. The mechanics behind the random walk has already proved largely useful in many fields, from finance to simulation and computation. Analogously, the quantum walk promises even greater potential for development. Here, with many of the algorithms already developed, it would allow computations to outperform current classical methods on an unprecedented level. Additionally, by implementing these mechanics on various levels, it is possible to simulate and understand various quantum mechanical systems and phenomenon. This phenomenon consequently represents a significant advancement in several fields of study. Although there has been considerable theoretical development of this phenomenon, its potential now lies in implementing these quantum walks physically. Here, a physical system is required such that the quantum walk may be sustainably achieved, easily detected and dynamically altered as needed. Many systems have been subsequently proposed and demonstrated, but the criteria for a useful quantum walk leaves many such avenues lacking with the largest number of steps yet to reach 100 to the best of our knowledge. As a result, we explored a classical take on the quantum walk, utilizing the wave properties of light to achieve analogous mechanics with the advantage of the increased degree of control and robustness. While such an approach is not new, we considered a particular method where the quantum walk could be implemented in the spatial modes of light. By exploiting the non-separability (classical entanglement) of polarization and orbital angular momentum, such a classical quantum walk could be realized with greater intuitive implications and the potential for further study into the quantum mechanical nature of this phenomenon, over and above that of the other schemes, by walking the quantum-classical divide. The work presented here subsequently centres on experimentally achieving a quantum walk with classically entangled light for further development and useful implementation. Moreover, this work focused on demonstrating the sustainability, control and robustness necessary for this scheme to be beneficial for future development. In Chapter 1, an intuitive introduction is presented, highlighting the mechanics of this phenomenon that make it different from the Random walk counterpart. We also explore why this phenomenon is of such great importance with an overview of applications that physical implementation can result in. A more in-depth look into the dynamics and mathematical aspects of this walk is found in Chapter 2. Here a detailed look into the mechanisms behind the walk is taken with mathematical analysis. Furthermore, the subsequent differences and implications associated viii with utilizing classical light is explored, answering the question of what is quantum about the quantum walk. As the focus of this chapter is largely cemented in establishing a solid theoretical background, we also look into the physics behind classical light and develop the theoretical basis in the direction of structured light, with an emphasis on establishing classically entangled beams. Chapters 3 and 4 present the experimental work done throughout the course of this dissertation. With Chapter 3 we establish and characterize the elements necessary for obtaining a quantum walk in the spatial modes of light by utilizing waveplates as coins, q-plates as step operators and entanglement generators as well as mode sorters in a detection system. We also look into the characteristics of the modes that will be produced with these elements, allowing the propagation properties of the beam to be experimentally accounted for. In Chapter 4, we examine the experimental considerations of how to achieve a realistic and sustainable quantum walk. Here, we consider and implement the scheme proposed by Goyal et. al. [] where a light pulse follows a looped path, allowing the physical resources to be constant throughout the walk. We also show the experimental limitations of the equipment being utilized and the various steps needed to compensate. Finally, we not only implement a quantum walk with classically entangled light for the first time, but also demonstrate the flexibility of the system. Here, we achieve a maximum of 8 steps and show 5 different types of walks with varying dynamics and symmetry. The last chapter (Chapter 5) gives a summary of the dissertation in context of the goals and achievements of this work. The outlook and implications of these results are discussed and future steps outlined for extending this scheme into a highly competitive alternative for viable implementation of quantum walks for computing and simulation. / XL2019