The past few years have seen the rapid rise of all things “social” on the web from the growth of online social networks like Facebook, to real-time communication services like Twitter, to user-contributed content sites like Flickr and YouTube, to content aggregators like Digg. Beyond these popular Web 2.0 successes, the emer- gence of Social Information Systems is promising to fundamentally transform what information we encounter and digest, how businesses market and engage with their customers, how universities educate and train a new generation of researchers, how the government investigates terror networks, and even how political regimes interact with their citizenry. Users have moved from being passive consumers of information (via querying or browsing) to becoming active participants in the creation of data and knowledge artifacts, actively sorting, ranking, and annotating other users and artifacts. This fundamental shift to social systems places new demands on providing de- pendable capabilities for knowing whom to trust and what information to trust, given the open and unregulated nature of these systems. The emergence of large-scale user participation in Social Information Systems suggests the need for the development of user-centric approaches to information quality. As a step in this direction this research proposes an interaction-based approach for modeling the notion of user im- portance. The interaction-based model is centered around the uniquely social aspects of these systems, by treating who communicates with whom (an interaction) as a core building block in evaluating user importance. We first study the interaction characteristics of Twitter, one of the most buzzworthy recent Social Web successes, examining the usage statistics, growth patterns, and user interaction behavior of over 2 million participants on Twitter. We believe this is the first large-scale study of dynamic interactions on a real-world Social Information System. Based on the anal- ysis of the interaction structure of Twitter, the second contribution of this thesis research is an exploration of approaches for measuring user importance. As part of this exploration, we study several different approaches that build on the inherent interaction-based framework of Social Information Systems. We explore this model through an experimental study over an interaction graph consisting of 800,000 nodes and about 1.9 million interaction edges. The user importance modeling approaches that we present can be applied to any Social Information System in which interactions between users can be monitored.

The ever increasing use of computer systems in society brings emergent challenges to companies and system designers. The reliability of software and hardware can be financially critical, and lives can depend on it. The growth in size and complexity of software, and increasing concurrency, compounds the problem. The potential for errors is greater than ever before, and the stakes are higher than ever before. Formal methods, particularly model checking, is an approach that attempts to prove mathematically that a model of the behaviour of a product is correct with respect to certain properties. Certain errors can therefore be proven never to occur in the model. This approach has tremendous potential in system development to provide guarantees of correctness. Unfortunately, in practice, model checking cannot handle the enormous sizes of the models of real-world systems. The reason is that the approach requires an exhaustive search of the model to be conducted. While there are exceptions, in general model checkers are said not to scale well. In this thesis, we deal with this scaling issue by using a guiding technique that avoids searching areas of the model, which are unlikely to contain errors. This technique is based on a process of model abstraction in which a new, much smaller model is generated that retains certain important model information but discards the rest. This new model is called a heuristic. While model checking using a heuristic as a guide can be extremely effective, in the worst case (when the guide is of no help), it performs the same as exhaustive search, and hence it also does not scale well in all cases. A second technique is employed to deal with the scaling issue. This technique is based on the concept of random walks. A random walk is simply a `walk' through the model of the system, carried out by selecting states in the model randomly. Such a walk may encounter an error, or it may not. It is a non-exhaustive technique in the sense that only a manageable number of walks are carried out before the search is terminated. This technique cannot replace the conventional model checking as it can never guarantee the correctness of a model. It can however, be a very useful debugging tool because it scales well. From this point of view, it relieves the system designer from the difficult task of dealing with the problem of size in model checking. Using random walks, the effort goes instead into looking for errors. The effectiveness of model checking can be greatly enhanced if the above two techniques are combined: a random walk is used to search for errors, but the walk is guided by a heuristic. This in a nutshell is the focus of this work. We should emphasise that the random walk approach uses the same formal model as model checking. Furthermore, the same heuristic technique is used to guide the random walk as a guided model checker. Together, guidance and random walks are shown in this work to result in vastly improved performance over conventional model checking. Verification has been sacrificed of course, but the new technique is able to find errors far more quickly, and deal with much larger models.

The ever increasing use of computer systems in society brings emergent challenges to companies and system designers. The reliability of software and hardware can be financially critical, and lives can depend on it. The growth in size and complexity of software, and increasing concurrency, compounds the problem. The potential for errors is greater than ever before, and the stakes are higher than ever before. Formal methods, particularly model checking, is an approach that attempts to prove mathematically that a model of the behaviour of a product is correct with respect to certain properties. Certain errors can therefore be proven never to occur in the model. This approach has tremendous potential in system development to provide guarantees of correctness. Unfortunately, in practice, model checking cannot handle the enormous sizes of the models of real-world systems. The reason is that the approach requires an exhaustive search of the model to be conducted. While there are exceptions, in general model checkers are said not to scale well. In this thesis, we deal with this scaling issue by using a guiding technique that avoids searching areas of the model, which are unlikely to contain errors. This technique is based on a process of model abstraction in which a new, much smaller model is generated that retains certain important model information but discards the rest. This new model is called a heuristic. While model checking using a heuristic as a guide can be extremely effective, in the worst case (when the guide is of no help), it performs the same as exhaustive search, and hence it also does not scale well in all cases. A second technique is employed to deal with the scaling issue. This technique is based on the concept of random walks. A random walk is simply a `walk' through the model of the system, carried out by selecting states in the model randomly. Such a walk may encounter an error, or it may not. It is a non-exhaustive technique in the sense that only a manageable number of walks are carried out before the search is terminated. This technique cannot replace the conventional model checking as it can never guarantee the correctness of a model. It can however, be a very useful debugging tool because it scales well. From this point of view, it relieves the system designer from the difficult task of dealing with the problem of size in model checking. Using random walks, the effort goes instead into looking for errors. The effectiveness of model checking can be greatly enhanced if the above two techniques are combined: a random walk is used to search for errors, but the walk is guided by a heuristic. This in a nutshell is the focus of this work. We should emphasise that the random walk approach uses the same formal model as model checking. Furthermore, the same heuristic technique is used to guide the random walk as a guided model checker. Together, guidance and random walks are shown in this work to result in vastly improved performance over conventional model checking. Verification has been sacrificed of course, but the new technique is able to find errors far more quickly, and deal with much larger models.

The ever increasing use of computer systems in society brings emergent challenges to companies and system designers. The reliability of software and hardware can be financially critical, and lives can depend on it. The growth in size and complexity of software, and increasing concurrency, compounds the problem. The potential for errors is greater than ever before, and the stakes are higher than ever before. Formal methods, particularly model checking, is an approach that attempts to prove mathematically that a model of the behaviour of a product is correct with respect to certain properties. Certain errors can therefore be proven never to occur in the model. This approach has tremendous potential in system development to provide guarantees of correctness. Unfortunately, in practice, model checking cannot handle the enormous sizes of the models of real-world systems. The reason is that the approach requires an exhaustive search of the model to be conducted. While there are exceptions, in general model checkers are said not to scale well. In this thesis, we deal with this scaling issue by using a guiding technique that avoids searching areas of the model, which are unlikely to contain errors. This technique is based on a process of model abstraction in which a new, much smaller model is generated that retains certain important model information but discards the rest. This new model is called a heuristic. While model checking using a heuristic as a guide can be extremely effective, in the worst case (when the guide is of no help), it performs the same as exhaustive search, and hence it also does not scale well in all cases. A second technique is employed to deal with the scaling issue. This technique is based on the concept of random walks. A random walk is simply a `walk' through the model of the system, carried out by selecting states in the model randomly. Such a walk may encounter an error, or it may not. It is a non-exhaustive technique in the sense that only a manageable number of walks are carried out before the search is terminated. This technique cannot replace the conventional model checking as it can never guarantee the correctness of a model. It can however, be a very useful debugging tool because it scales well. From this point of view, it relieves the system designer from the difficult task of dealing with the problem of size in model checking. Using random walks, the effort goes instead into looking for errors. The effectiveness of model checking can be greatly enhanced if the above two techniques are combined: a random walk is used to search for errors, but the walk is guided by a heuristic. This in a nutshell is the focus of this work. We should emphasise that the random walk approach uses the same formal model as model checking. Furthermore, the same heuristic technique is used to guide the random walk as a guided model checker. Together, guidance and random walks are shown in this work to result in vastly improved performance over conventional model checking. Verification has been sacrificed of course, but the new technique is able to find errors far more quickly, and deal with much larger models.

Diffusion and random walks have been studied for more than 100 years. However, there are still details in the methodology that are overlooked, and more information can be extracted from the typical data that is studied. In this thesis, I simulate random walks on two dimensional lattices with immobile obstacles configured in a variety of ways: periodic, random, and "Fuzzy" (a cross intermediate state of disorder between periodic and random). The primary goal is to develop a deeper understanding of "Fuzzy" systems by designing different ways of generating tunable disorder. An example of this is the universal Fz parameter that we developed to unify the natural disorder parameters of the various disorder generation methods we developed. Often times the importance of analysing the transient/anomalous regime with more precision and consistency is overlooked. In our work, we expand on random walk dynamics by applying non-standard probabilities, and justify our choice analytically and through a comparison of results. Furthermore we discuss how the transient regime should be analyzed so that there is consistency in the field. Other than discussing semantics of algorithms and analysis, we study the connection between the transient regime and the steady-state. We introduce two measures of the width of the transient/anomalous regime, and compare them to the crossover time. Using the width of the transient/anomalous regime we are able to provide an estimate of the steady-state diffusion coefficient without access to the steady-state simulation data.

Part I: The Theory of Brownian Vacancy Driven Walk We analyze the lattice walk performed by a tagged member of an infinite 'sea' of particles filling a d-dimensional lattice, in the presence of a single vacancy. The vacancy is allowed to be occupied with probability 1/2d by any of its 2d nearest neighbors, so that it executes a Brownian walk. Particle-particle exchange is forbidden; the only interaction between them being hard core exclusion. Thus, the tagged particle, differing from the others only by its tag, moves only when it exchanges places with the hole. In this sense, it is a random walk "driven" by the Brownian vacancy. The probability distributions for its displacement and for the number of steps taken, after n-steps of the vacancy, are derived. Neither is a Gaussian! We also show that the only nontrivial dimension where the walk is recurrent is d=2. As an application, we compute the expected energy shift caused by a Brownian vacancy in a model for an extreme anisotropic binary alloy. In the last chapter we present a Monte-Carlo study and a mean-field analysis for interface erosion caused by mobile vacancies. Part II: One-Dimensional Periodic Hopping Models with Broken Translational Invariance.Case of a Mobile Directional Impurity We study a random walk on a one-dimensional periodic lattice with arbitrary hopping rates. Further, the lattice contains a single mobile, directional impurity (defect bond), across which the rate is fixed at another arbitrary value. Due to the defect, translational invariance is broken, even if all other rates are identical. The structure of Master equations lead naturally to the introduction of a new entity, associated with the walker-impurity pair which we call the quasi-walker. Analytic solution for the distributions in the steady state limit is obtained. The velocities and diffusion constants for both the random walker and impurity are given, being simply related to that of the quasi-particle through physically meaningful equations. As an application, we extend the Duke-Rubinstein reputation model of gel electrophoresis to include polymers with impurities and give the exact distribution of the steady state. / Ph. D.

Organisms have movements that are usually modeled by particles’ random walks. Under some mathematical technical assumptions the movements are described by diffusion equations. However, empirical data often show that the movements are not simple random walks. Instead, they are correlated random walks and are described by telegraph equations. This thesis considers telegraph equations with and without bias corresponding to correlated random walks with and without bias. Analytical solutions to the equations with absorbing boundary conditions and their mean passage times are obtained. Numerical simulations of the corresponding correlated random walks are also performed. The simulation results show that the solutions are approximated very well by the corresponding correlated random walks and the mean first passage times are highly consistent with those from simulations on the corresponding random walks. This suggests that telegraph equations can be a good model for organisms with the movement pattern of correlated random walks. Furthermore, utilizing the consistency of mean first passage times, we can estimate the parameters of telegraph equations through the mean first passage time, which can be estimated through experimental observation. This provides biologists an easy way to obtain parameter values. Finally, this thesis analyzes the velocity distribution and correlations of movement steps of amoebas, leaving fitting the movement data to telegraph equations as future work.

The random walk is a powerful model. Chemistry, Physics, and Finance are just a few of the disciplines that model with the random walk. It is clear from its varied uses that despite its simplicity, the simple random walk it very flexible. There is one major drawback, however, to the simple random walk and the geometric random walk. The limiting distribution is either normal, lognormal, or a levy process with infinite variance. This thesis introduces an new random walk aimed at overcoming this drawback. Because the simple random walk and the geometric random walk are special cases of the proposed walk, it is called a generalized random walk. Several properties of the generalized random walk are considered. First, the limiting distribution of the generalized random walk is shown to include a large class of distributions. Second and in conjunction with the first, the generalized random walk is compared to the geometric random walk. It is shown that when parametrized properly, the generalized random walk does converge to the lognormal distribution. Third, and perhaps most interesting, is one of the limiting properties of the generalized random walk. In the limit, generalized random walks are closely connected with a u function. The u function is the key link between generalized random walks and its difference equation. Last, we apply the generalized random walk to option pricing.