No description available.

No description available.

No description available.

No description available.

No description available.

This dissertation has two parts. In the first part, we focus on random inner product kernel matrices. Under various assumptions, many authors have proved that the limiting empirical spectral distribution (ESD) of such matrices A converges to the Marchenko- Pastur distribution. Here, we establish the corresponding rate of convergence. The strategy is as follows. First, we show that for z = u + iv ∈ C, v > 0, the distance between the Stieltjes transform m_A (z) of ESD of matrix A and Machenko-Pastur distribution m(z) is of order O (log n \ nv). Next, we prove the Kolmogorov distance between ESD of matrix A and Marchenko-Pastur distribution is of order O(3\log n\n). It is the less sharp rate for much more general class of matrices. This uses a Berry-Esseen type bound that has been employed for similar purposes for other families of random matrices. In the second part, random geometric graphs on the unit sphere are considered. Observing that adjacency matrices of these graphs can be thought of as random inner product matrices, we are able to use an idea of Cheng-Singer to establish the limiting for the ESD of these adjacency matrices. / Mathematics

Over the last decade, cellular networks have grown rapidly from circuit-switch-based voice-only networks to IP-based data-dominant networks, embracing not only traditional mobile phones, but also smartphones and mobile computers. The ever-increasing demands for reliable and high-speed data services have challenged the capacity and coverage of cellular networks. Research and development on femtocells seeks to provide a solution to fill coverage holes and to increase the network capacity to accommodate more mobile terminals and applications that requires higher bandwidth. Among the challenges associated with introducing femtocells in existing cellular networks, interference management and resource allocation are critical. In this dissertation, we address fundamental aspects of resource allocation for cellular networks with coexisting femtocells and macrocells on the downlink side, addressing questions such as: How many additional resource blocks are required to add femtocells into the current cellular system? What is the best way to reuse resources between femtocells and macrocells? How can we efficiently assign limited resources to network users? In this dissertation, we develop an analytical model of resource allocation based on random graphs. In this model, arbitrarily chosen communication links interfere with each other with a certain probability. Using this model, we establish asymptotic bounds on the minimum number of resource blocks required to make interference-free resource assignments for all the users in the network. We assess these bounds using a simple greedy resource allocation algorithm to demonstrate that the bounds are reasonable in finite networks of plausible size. By applying the bounds, we establish the expected impact of femtocell networks on macrocell resource allocation under a variety of interference scenarios. We proceed to compare two reuse schemes, termed shared reuse and split reuse, using three social welfare functions, denoted utilitarian fitness, egalitarian fitness, and proportionally fair fitness. The optimal resource split points, which separate resource access by femtocells and macrocells, are derived with respect to the above fitness functions. A set of simple greedy resource allocation algorithms are developed to verify our analysis and compare fitness values of the two reuse schemes under various network scenarios. We use the obtained results to assess the efficiency loss associated with split reuse, as an aid to determining whether resource allocators should use the simpler split reuse scheme or attempt to tackle the complexity and overhead associated with shared reuse. Due to the complexity of the proportionally fair fitness function, optimal resource allocation for cellular networks with femtocells and macrocells is difficult to obtain. We develop a genetic algorithm-based centralized resource allocation algorithm to yield suboptimal solutions for such a problem. The results from the genetic algorithm are used to further assess the performance loss of split reuse and provide a baseline suboptimal resource allocation. Two distributed algorithms are then proposed to give a practical solution to the resource allocation problem. One algorithm is designed for a case with no communications between base stations and another is designed to exploit the sharing of information between base stations. The numerical results from these distributed algorithms are then compared against to the ones obtained by the genetic algorithm and the performance is found to be satisfactory, typically falling within 8\% of the optimum social welfare found via the genetic algorithm. The capability of the distributed algorithms in adapting to network changes is also assessed and the results are promising. All of the work described thus far is carried out under a protocol model in which interference between two links is a binary condition. Though this model makes the problem more analytically tractable, it lacks the ability to reflect additive interference as in the SINR model. Thus, in the final part of our work, we apply conflict-free resource allocations from our distributed algorithms to simulated networks and examine the allocations under the SINR model to evaluate feasibility. This evaluation study confirms that the protocol-model-based algorithms, with a small adjustment, offer reasonable performance even under the more realistic SINR model. This work was supported by the National Institute of Justice, Office of Justice Programs, U.S. Department of Justice under Award No. 2005-IJ-CX-K017 and the National Science Foundation under Grant No. 0448131. Any opinions, findings, and conclusions or recommendations expressed in this dissertation are those of the author and do not necessarily reflect the views of the National Institute of Justice or the National Science Foundation. The NSF/TEKES Wireless Research Exchange Program also contributed to this work by funding a summer study. / Ph. D.

Thesis (MSc)--Stellenbosch University, 2011 / ENGLISH ABSTRACT: With billions of current internet users interacting through social networks, the need has arisen to analyze the structure of these networks. Many authors have proposed random graph models for social networks in an attempt to understand and reproduce the dynamics that govern social network development. This thesis proposes a random graph model that generates social networks using a community-based approach, in which users’ affiliations to communities are explicitly modeled and then translated into a social network. Our approach explicitly models the tendency of communities to overlap, and also proposes a method for determining the probability of two users being connected based on their levels of commitment to the communities they both belong to. Previous community-based models do not incorporate community overlap, and assume mutual members of any community are automatically connected. We provide a method for fitting our model to real-world social networks and demonstrate the effectiveness of our approach in reproducing real-world social network characteristics by investigating its fit on two data sets of current online social networks. The results verify that our proposed model is promising: it is the first community-based model that can accurately reproduce a variety of important social network characteristics, namely average separation, clustering, degree distribution, transitivity and network densification, simultaneously. / AFRIKAANSE OPSOMMING: Met biljoene huidige internet-gebruikers wat deesdae met behulp van aanlyn sosiale netwerke kommunikeer, het die analise van hierdie netwerke in die navorsingsgemeenskap toegeneem. Navorsers het al verskeie toevalsgrafiekmodelle vir sosiale netwerke voorgestel in ’n poging om die dinamika van die ontwikkeling van dié netwerke beter te verstaan en te dupliseer. In hierdie tesis word ’n nuwe toevalsgrafiekmodel vir sosiale netwerke voorgestel wat ’n gemeenskapsgebaseerde benadering volg, deurdat gebruikers se verbintenisse aan gemeenskappe eksplisiet gemodelleer word, en dié gemeenskapsmodel dan in ’n sosiale netwerk omskep word. Ons metode modelleer uitdruklik die geneigdheid van gemeenskappe om te oorvleuel, en verskaf ’n metode waardeur die waarskynlikheid van vriendskap tussen twee gebruikers bepaal kan word, op grond van hulle toewyding aan hulle wedersydse gemeenskappe. Vorige modelle inkorporeer nie gemeenskapsoorvleueling nie, en aanvaar ook dat alle lede van dieselfde gemeenskap vriende sal wees. Ons verskaf ’n metode om ons model se parameters te pas op sosiale netwerk datastelle en vertoon die vermoë van ons model om eienskappe van sosiale netwerke te dupliseer. Die resultate van ons model lyk belowend: dit is die eerste gemeenskapsgebaseerde model wat gelyktydig ’n belangrike verskeidenheid van sosiale netwerk eienskappe, naamlik gemiddelde skeidingsafstand, samedromming, graadverdeling, transitiwiteit en netwerksverdigting, akkuraat kan weerspieël.

We study graph parameters arising from different types of colourings of random graphs, defined broadly as an assignment of colours to either the vertices or the edges of a graph. The chromatic number X(G) of a graph is the minimum number of colours required for a vertex colouring where no two adjacent vertices are coloured the same. Determining the chromatic number is one of the classic challenges in random graph theory. In Chapter 3, we give new upper and lower bounds for the chromatic number of the dense random graph G(n,p)) where p ∈ (0,1) is constant. These bounds are the first to match up to an additive term of order o(1) in the denominator, and in particular, they determine the average colour class size in an optimal colouring up to an additive term of order o(1). In Chapter 4, we study a related graph parameter called the equitable chromatic number. This is defined as the minimum number of colours needed for a vertex colouring where no two adjacent vertices are coloured the same and, additionally, all colour classes are as equal in size as possible. We prove one point concentration of the equitable chromatic number of the dense random graph G(n,m) with m = pn(n-1)/2, p < 1-1/e² constant, on a subsequence of the integers. We also show that whp, the dense random graph G(n,p) allows an almost equitable colouring with a near optimal number of colours. We call an edge colouring of a graph G a rainbow colouring if every pair of vertices is joined by a rainbow path, which is a path where no colour is repeated. The least number of colours where this is possible is called the rainbow connection number rc(G). Since its introduction in 2008 as a new way to quantify how well connected a given graph is, the rainbow connection number has attracted the attention of a great number of researchers. For any graph G, rc(G)≥diam(G), where diam(G) denotes the diameter. In Chapter 5, we will see that in the random graph G(n,p), rainbow connection number 2 is essentially equivalent to diameter 2. More specifically, we consider G ~ G(n,p) close to the diameter 2 threshold and show that whp rc(G) = diam(G) ∈ {2,3}. Furthermore, we show that in the random graph process, whp the hitting times of diameter 2 and of rainbow connection number 2 coincide. In Chapter 6, we investigate sharp thresholds for the property rc(G)≤=r where r is a fixed integer. The results of Chapter 6 imply that for r=2, the properties rc(G)≤=2 and diam(G)≤=2 share the same sharp threshold. For r≥3, the situation seems quite different. We propose an alternative threshold and prove that this is an upper bound for the sharp threshold for rc(G)≤=r where r≥3.

Knowledge diffusion networks consist of individuals who exchange knowledge and knowledge flows connecting the individuals. By studying knowledge diffusion in a network perspective, it helps us understand how the connections between individuals affect the knowledge diffusion processes. Existing research on knowledge diffusion networks mostly adopts a uni-dimensional perspective, where all the individuals in the networks are assumed to be of the same type. It also assumes that there is only one type of knowledge flow in the network. This dissertation proposes a multi-dimensional perspective of knowledge diffusion networks and examines the patterns of knowledge diffusion with Exponential Random Graph Model (ERGM) based approaches. The objective of this dissertation is to propose a framework that effectively addresses the multi-dimensionality of knowledge diffusion networks, to enable researchers and practitioners to conceptualize the multi-dimensional knowledge diffusion networks in various domains, and to provide implications on how to stimulate and control the knowledge diffusion process. The dissertation consists of three essays, all of which examine the multi-dimensional knowledge diffusion networks in a specific context, but each focuses on a different aspect of knowledge diffusion. Chapter 2 focuses on how structural properties of networks affect various types of knowledge diffusion processes in the domain of commercial technology. The study uses ERGM to simultaneously model multiple types of knowledge flows and examine their interactions. The objective is to understand the impacts of network structures on knowledge diffusion processes. Chapter 3 focuses on examining the impact of individual attributes and the attributes of knowledge on knowledge diffusion in the context of scientific innovation. Based on social capital theory, the study also utilizes ERGM to examine how knowledge transfer and knowledge co-creation can be affected by the attributes of individual researchers and the attributes of scientific knowledge. Chapter 4 considers the dynamic aspect of knowledge diffusion and proposes a novel network model extending ERGM to identify dynamic patterns of knowledge diffusion in social media. In the proposed model, dynamic patterns in social media networks are modeled based on the nodal attributes of individuals and the temporal information of network ties.