Online Social Networks (OSNs) such as Facebook, Twitter, and YouTube are among the most popular sites on the Internet. Billions of users are connected through these sites, building strong and effective communities to share views and ideas, and make recommendations nowadays. Therefore, by choosing an appropriate user-base from billions of people is required to analyze the structure and key characteristics of the large social graphs to improve current systems and to design new applications. For this reason, node sampling technique plays an important role to study large-scale social networks. As a basic requirement, the sampled nodes and their links should possess similar statistical features of the original network, otherwise the conclusion drawn from the sampled network may not be appropriate for the entire population. Hence, good sampling strategies are key to many online social network applications. For instance, before introducing a new product or adding new feature(s) of a product to the online social network community, that specific new product or the additional feature has to be exposed to only a small set of users, who are carefully chosen to represent the complete set of users. As such, different random walk-based sampling techniques have been introduced to produce samples of nodes that not only are internally well-connected but also capture the statistical features of the whole network. Traditionally, walk-based techniques do not have the restriction on the number of times that a node can be re-visited while sampling. This may lead to an inefficient sampling method, because the walk may be "stuck" at a small number of high-degree nodes without being able to reach out to the rest of the nodes. A random walk, even after a large number of hops, may not be able to obtain a sampled network that captures the statistical features of the entire network. In this thesis, we propose two walk-based sampling techniques to address the above problem, called K-Avoiding Random Walk (KARW) and Neighborhood-Avoiding Random Walk (NARW). With KARW, the number of times that a node can be re-visited is constrained within a given number K. With NARW, the random walk works in a "jump" fashion, since the walk starts outside of the N-hop neighborhood from the current node chosen randomly. By avoiding the current nodes neighboring area of level-N, NARW is expected to reach out the other nodes within the entire network quickly. We apply these techniques to construct multiple independent subgraphs from a social graph, consisting of 63K users with around a million connections between users collected from a Facebook dataset. By simulating our proposed strategies, we collect performance metrics and compare the results with the current state-of-the-art sampling techniques (Uniform Random Sampling, Random Walk, and Metropolis Hastings Random Walk). We also calculate some of the key statistical features (i.e., degree distribution, betweenness centrality, closeness centrality, modularity, and clustering coefficient) of the sampled graphs to get an idea about the network structures that essentially represent the original social graph. / Graduate / 0984 / shahed.anwar@gmail.com

In a parallel vertex-centered finite element multigrid solver, segmental refinement can be used to avoid all inter-process communication on the fine grids. While domain decomposition methods generally require coupled subdomain processing for the numerical solution to a nonlinear elliptic boundary value problem, segmental refinement exploits that subdomains are almost decoupled with respect to high-frequency error components. This allows to perform multigrid with fully decoupled subdomains on the fine grids, which was proposed as a sequential low-storage algorithm by Brandt in the 1970s, and as a parallel algorithm by Brandt and Diskin in 1994. Adams published the first numerical results from a multilevel segmental refinement solver in 2014, confirming the asymptotic exactness of the scheme for a cell-centered finite volume implementation. We continue Brandt’s and Adams’ research by experimentally investigating the scheme’s accuracy with a vertex-centered finite element segmental refinement solver. We confirm that full multigrid accuracy can be preserved for a few segmental refinement levels, although we observe a different dependency on the segmental refinement parameter space. We show that various strategies for the grid transfers between the finest conventional multigrid level and the segmental refinement subdomains affect the solver accuracy. Scaling results are reported for a Cray XC30 with up to 4096 cores.

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.

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.

It is widely believed that the scaling limit of the self-avoiding walk (SAW) is given by Schramm's SLE₈/₃. In fact, it is known that if SAW has a scaling limit which is conformally invariant, then the distribution of such a scaling limit must be given by SLE₈/₃. The purpose of this paper is to study the relationship between SAW and SLE₈/₃, mainly through the use of restriction measures; conformally invariant measures that satisfy a certain restriction property. Restriction measures are stochastic processes on randomly growing fractal subsets of the complex plane called restriction hulls, though it turns out that SLE₈/₃ measure is also a restriction measure. Since SAW should converge to SLE₈/₃ in the scaling limit, it is thought that many important properties of SAW might also hold for restriction measures, or at the very least, for SLE₈/₃. In [DGKLP2011], it was shown that if one conditions an infinite length self-avoiding walk in half-plane to have a bridge height at y-1, and then considers the walk up to height y, then one obtains the distribution of self-avoiding walk in the strip of height y. We show in this paper that a similar result holds for restriction measures ℙ(α), with α ∈ [5/8,1). That is, if one conditions a restriction hull to have a bridge point at some z ∈ ℍ, and considers the hull up until the time it reaches z, then the resulting hull is distributed according to a restriction measure in the strip of height Im(z). This relies on the fact that restriction hulls contain bridge points a.s. for α ∈ [5/8,1), which was shown in [AC2010]. We then proceed to show that a more general form of that result holds for restriction hulls of the same range of parameters α. That is, if one conditions on the event that a restriction hull in ℍ passes through a smooth curve γ at a single point, and then considers the hull up to the time that it reaches the point, then the resulting hull is distributed according to a restriction hull in the domain which lies underneath the curve γ. We then show that a similar result holds in simply connected domains other than ℍ. Next, we conjecture the existence of an object called the infinite length quarter-plane self-avoiding walk. This is a measure on infinite length self-avoiding walks, restricted to lie in the quarter plane. In fact, what we show is that the existence of such a measure depends only on the validity of a relation similar to Kesten's relation for irreducible bridges in the half-plane. The corresponding equation for irreducible bridges in the quarter plane, Conjecture 4.1.19, is believed to be true, and given this result, we show that a measure on infinite length quarter-plane self-avoiding walks analogous to the measure on infinite length half-plane self-avoiding walks (which was proven to exist in [LSW2002] exists. We first show that, given Conjecture 4.1.19, the measure can be constructed through a concatenation of a sequence of irreducible quarter-plane bridges, and then we show that the distributional limit of the uniform measure on finite length quarter-plane SAWs exists, and agrees with the measure which we have constructed. It then follows as a consequence of the existence of such a measure, that quarter-plane bridges exist with probability 1. As a follow up to the existence of the measure on infinite length quarter-plane SAWs, and the a.s. existence of quarter-plane bridge points, we then show that quarter plane bridge points exist for restriction hulls of parameter α ∈ [5/8,3/4), and we calculate the Hausdorff measure of the set of all such bridge points. Finally, we introduce a new type of (conjectured) scaling limit, which we are calling the fixed irreducible bridge ensemble, for self-avoiding walks, and we conjecture a relationship between the fixed irreducible bridge ensemble and chordal SLE₈/₃ in the unit strip {z ∈ ℍ : 0 < Im(z) < 1}.

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

Low rank approximation is the problem of finding two low rank factors W and H such that the rank(WH) << rank(A) and A ≈ WH. These low rank factors W and H can be constrained for meaningful physical interpretation and referred as Constrained Low Rank Approximation (CLRA). Like most of the constrained optimization problem, performing CLRA can be computationally expensive than its unconstrained counterpart. A widely used CLRA is the Non-negative Matrix Factorization (NMF) which enforces non-negativity constraints in each of its low rank factors W and H. In this thesis, I focus on scalable/distributed CLRA algorithms for constraints such as boundedness and non-negativity for large real world matrices that includes text, High Definition (HD) video, social networks and recommender systems. First, I begin with the Bounded Matrix Low Rank Approximation (BMA) which imposes a lower and an upper bound on every element of the lower rank matrix. BMA is more challenging than NMF as it imposes bounds on the product WH rather than on each of the low rank factors W and H. For very large input matrices, we extend our BMA algorithm to Block BMA that can scale to a large number of processors. In applications, such as HD video, where the input matrix to be factored is extremely large, distributed computation is inevitable and the network communication becomes a major performance bottleneck. Towards this end, we propose a novel distributed Communication Avoiding NMF (CANMF) algorithm that communicates only the right low rank factor to its neighboring machine. Finally, a general distributed HPC- NMF framework that uses HPC techniques in communication intensive NMF operations and suitable for broader class of NMF algorithms.

This is a literature review article. The purpose of this article is to explain and provide a deeperunderstanding of economic and industrial espionage. Furthermore, it describes legal andillegal methods of espionage and highlights the different aspects of preventing espionage suchas; technical, operational, physical and personnel security. A number of theoretical conceptshave been extracted and analyzed from different scientific articles which have beensummarized and anticipated in the form of theoretical framework. Incredible results are oftenproduced by exploiting industrial espionage. By concentrating on complete security, and notsimply specialized security, data security experts can altogether hamper enemy endeavors totake their association's data resources.

In this paper we present a simple combinatorial approach for the derivation of zero avoiding transition probabilities in a Markovian r- node series Jackson network. The method we propose offers two advantages: first, it is conceptually simple because it is based on transition counts between the nodes and does not require a tensor representation of the network. Second, the method provides us with a very efficient technique for numerical computation of zero avoiding transition probabilities. / Series: Forschungsberichte / Institut für Statistik

The hypercube Qn is the graph whose vertices are the ordered n-tuples of zeros and ones, where two vertices are adjacent iff they differ in exactly one coordinate. A partial edge coloring f of a graph G is a mapping from a subset of edges of G to a set of colors; it is called proper if no pair of adjacent edges share the same color. A (possibly partial and unproper) coloring f is avoidable if there exists a proper coloring g such that no edge has the same color under f and g. An unavoidable coloring h is called minimal if it would be avoidable by letting any colored edge turn noncolored. We construct a computer program to find all minimal unavoidable edge colorings of Q3 using up to 3 colors, and draw some conclusions for general Qn.