A network of n transmitters and n receivers is considered. We assume that transmitter i aims to send data to its designated destination, receiver i. Communications occur in a single-hop fashion and destination nodes are simple linear receivers without multi-user detection. Therefore, in each time slot every source node can only talk to one other destination node. Thus, there is a total of n communication links. An important question now arises. How many links can be active in such a network so that each of them supports a minimum rate Rmin? This dissertation is devoted to this problem and tries to solve it in two di erent settings, dense and extended networks. In both settings our approach is asymptotic, meaning, we only examine the behaviour of the network when the number of nodes tends to in nity. We are also interested in the events that occur asymptotically almost surely (a.a.s.), i.e., events that have probabilities approaching one as the size of the networks gets large. In the rst part of the thesis, we consider a dense network where fading is the dominant factor a ecting the quality of transmissions. Rayliegh channels are used to model the impact of fading. It is shown that a.a.s. log(n)^2 links can simultaneously maintain Rmin and thus be active. In the second part, an extended network is considered where nodes are distant from each other and thus, a more complete model must take internode distances into account. We will show that in this case, almost all of the links can be active while maintaining the minimum rate.

A network of n transmitters and n receivers is considered. We assume that transmitter i aims to send data to its designated destination, receiver i. Communications occur in a single-hop fashion and destination nodes are simple linear receivers without multi-user detection. Therefore, in each time slot every source node can only talk to one other destination node. Thus, there is a total of n communication links. An important question now arises. How many links can be active in such a network so that each of them supports a minimum rate Rmin? This dissertation is devoted to this problem and tries to solve it in two di erent settings, dense and extended networks. In both settings our approach is asymptotic, meaning, we only examine the behaviour of the network when the number of nodes tends to in nity. We are also interested in the events that occur asymptotically almost surely (a.a.s.), i.e., events that have probabilities approaching one as the size of the networks gets large. In the rst part of the thesis, we consider a dense network where fading is the dominant factor a ecting the quality of transmissions. Rayliegh channels are used to model the impact of fading. It is shown that a.a.s. log(n)^2 links can simultaneously maintain Rmin and thus be active. In the second part, an extended network is considered where nodes are distant from each other and thus, a more complete model must take internode distances into account. We will show that in this case, almost all of the links can be active while maintaining the minimum rate.

Esse trabalho tem dois objetivos principais: o primeiro deles consiste em apresentar o estado da arte sobre processos de otimização combinatorial dando uma ênfase especial ao método Simulated Annealing (SA). São apresentados seu histórico, funcionalidades, algoritmo genérico e propostas de paralelização presentes na literatura. Além disso, é apresentado o algoritmo de geração de redes aleatórias contínuas, algoritmo, esse, projetado por pesquisadores do Instituto de Física da UFRGS que utiliza o método SA para gerar redes que atendam certas restrições. O segundo objetivo consiste empropor a paralelização desse algoritmo visando diminuir significativamente o tempo de geração de cada rede, que com o algoritmo seqüencial chega a demorar mais de um mês. Nessa etapa foi utilizada uma adaptação de um dos métodos propostos pela literatura juntamente com a técnica de divisão de domínio. Os resultados obtidos mostraram-se satisfatórios tanto em relação à qualidade numérica quanto à diminuição do tempo de processamento. Além disso, discute-se no trabalho a genericidade da proposta de paralelização a outros problemas baseados em SA. / This work has two main goals: the first one is to present the state of the art on combinatorial optimization processes, with a special emphasis to the Simulated Annealing (SA) method. The work presents its history, features, generic algorithm and proposed parallelization present in the literature. Moreover, the algorithm to generate random networks continued is presented. This algorithm was designed by researchers of the UFRGS Physics Institute and it uses the SA method. The second goal of this work is to propose a parallelization for this algorithm in order to decrease significantly the generation time of each network, that with the sequential algorithm reaches more than months. To do that was used an adaptation of one of the methods proposed by literature together with the domain partitioning technical. The results were satisfactory in terms of the numerical quality and in the decrease of the processing time. In addition, this work discusses the genericity of the proposed parallelization to other problems based on SA.

Esse trabalho tem dois objetivos principais: o primeiro deles consiste em apresentar o estado da arte sobre processos de otimização combinatorial dando uma ênfase especial ao método Simulated Annealing (SA). São apresentados seu histórico, funcionalidades, algoritmo genérico e propostas de paralelização presentes na literatura. Além disso, é apresentado o algoritmo de geração de redes aleatórias contínuas, algoritmo, esse, projetado por pesquisadores do Instituto de Física da UFRGS que utiliza o método SA para gerar redes que atendam certas restrições. O segundo objetivo consiste empropor a paralelização desse algoritmo visando diminuir significativamente o tempo de geração de cada rede, que com o algoritmo seqüencial chega a demorar mais de um mês. Nessa etapa foi utilizada uma adaptação de um dos métodos propostos pela literatura juntamente com a técnica de divisão de domínio. Os resultados obtidos mostraram-se satisfatórios tanto em relação à qualidade numérica quanto à diminuição do tempo de processamento. Além disso, discute-se no trabalho a genericidade da proposta de paralelização a outros problemas baseados em SA. / This work has two main goals: the first one is to present the state of the art on combinatorial optimization processes, with a special emphasis to the Simulated Annealing (SA) method. The work presents its history, features, generic algorithm and proposed parallelization present in the literature. Moreover, the algorithm to generate random networks continued is presented. This algorithm was designed by researchers of the UFRGS Physics Institute and it uses the SA method. The second goal of this work is to propose a parallelization for this algorithm in order to decrease significantly the generation time of each network, that with the sequential algorithm reaches more than months. To do that was used an adaptation of one of the methods proposed by literature together with the domain partitioning technical. The results were satisfactory in terms of the numerical quality and in the decrease of the processing time. In addition, this work discusses the genericity of the proposed parallelization to other problems based on SA.

Esse trabalho tem dois objetivos principais: o primeiro deles consiste em apresentar o estado da arte sobre processos de otimização combinatorial dando uma ênfase especial ao método Simulated Annealing (SA). São apresentados seu histórico, funcionalidades, algoritmo genérico e propostas de paralelização presentes na literatura. Além disso, é apresentado o algoritmo de geração de redes aleatórias contínuas, algoritmo, esse, projetado por pesquisadores do Instituto de Física da UFRGS que utiliza o método SA para gerar redes que atendam certas restrições. O segundo objetivo consiste empropor a paralelização desse algoritmo visando diminuir significativamente o tempo de geração de cada rede, que com o algoritmo seqüencial chega a demorar mais de um mês. Nessa etapa foi utilizada uma adaptação de um dos métodos propostos pela literatura juntamente com a técnica de divisão de domínio. Os resultados obtidos mostraram-se satisfatórios tanto em relação à qualidade numérica quanto à diminuição do tempo de processamento. Além disso, discute-se no trabalho a genericidade da proposta de paralelização a outros problemas baseados em SA. / This work has two main goals: the first one is to present the state of the art on combinatorial optimization processes, with a special emphasis to the Simulated Annealing (SA) method. The work presents its history, features, generic algorithm and proposed parallelization present in the literature. Moreover, the algorithm to generate random networks continued is presented. This algorithm was designed by researchers of the UFRGS Physics Institute and it uses the SA method. The second goal of this work is to propose a parallelization for this algorithm in order to decrease significantly the generation time of each network, that with the sequential algorithm reaches more than months. To do that was used an adaptation of one of the methods proposed by literature together with the domain partitioning technical. The results were satisfactory in terms of the numerical quality and in the decrease of the processing time. In addition, this work discusses the genericity of the proposed parallelization to other problems based on SA.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Socially-based networks are of particular interest amongst the variety of communication networks arising in reality. They are distinguished by having small average path length and high clustering coefficient, and so are examples of small-world networks. This thesis studies both real examples and theoretical models of small-world networks, with particular attention to average path length. Existing models of small-world networks, due to Watts and Strogatz (1998) and Newman and Watts (1999a), impose boundary conditions on a one dimensional lattice, and rewire links locally and probabilistically in the former or probabilistically adding extra links in the latter. These models are investigated and compared with real-world networks. We consider a model in which randomness is provided by the Erdos-Rényi random network models superposed on a deterministic one dimensional structured network. We reason about this model using tools and results from random graph theory. Given a disordered network C(n, p) formed by adding links randomly with probability p to a one dimensional network C(n). We improve the analytical result regarding the average path length by showing that the onset of smallworld behaviour occurs if pn is bounded away from zero. Furthermore, we show that when pn tends to zero, C(n, p) is no longer small-world. We display that the average path length in this case approaches infinity with the network order. We deduce that at least εn (where ε is a constant bigger than zero) random links should be added to a one dimensional lattice to ensure average path length of order log n. / AFRIKAANSE OPSOMMING: Sosiaal-baseerde netwerke is van besondere belang onder die verskeidenheid kommunikasie netwerke. Hulle word onderskei deur ’n klein gemiddelde skeidingsafstand en hoë samedrommingskoëffisiënt, en is voorbeelde van kleinwêreld netwerke. Hierdie verhandeling bestudeer beide werklike voorbeelde en teoretiese modelle van klein-wêreld netwerke, met besondere aandag op die gemiddelde padlengte. Bestaande modelle van klein-wêreld netwerke, te danke aan Watts en Strogatz (1998) en Newman en Watts (1999a), voeg randvoorwaardes by tot eendimensionele roosters, en herbedraad nedwerkskakels gebaseer op lokale kennis in die eerste geval en voeg willekeurig ekstra netwerkskakels in die tweede. Hierdie modelle word ondersoek en vergelyk met werklike-wêreld netwerke. Ons oorweeg ’n prosedure waarin willekeurigheid verskaf word deur die Erdös- Renyi toevalsnetwerk modelle wat op ’n een-dimensionele deterministiese gestruktureerde netwerk geimposeer word. Ons redeneer oor hierdie modelle deur gebruik te maak van gereedskap en resultate toevalsgrafieke teorie. Gegewe ’n wanordelike netwerk wat gevorm word deur skakels willekeurig met waarskynlikheid p tot ‘n een-dimensionele netwerk C(n) toe te voeg, verbeter ons die analitiese resultaat ten opsigte van die gemiddelde padlengte deur te wys dat die aanvang van klein-wêreld gedrag voorkom wanneer pn weg van nul begrens is. Verder toon ons dat, wanneer pn neig na nul, C(n, p) nie meer klein-wêreld is nie. Ons toon dat die gemiddelde padlengte in hierdie geval na oneindigheid streef saam met die netwerk groote. Ons lei af dat ten minste εn (waar εn n konstante groter as nul is) ewekansige skakels bygevoeg moet word by ’n een-dimensionele rooster om ‘n gemiddelde padlengte van orde log n te verseker.

Open-source software becomes increasingly popular nowadays. Many startup companies and small business owners choose to adopt open source software packages to meet their daily office computing needs or to build their IT infrastructure. Unlike proprietary software systems, open source software systems usually have a loosely-organized developer collaboration structure. Developers work on their "assignments" on a voluntary basis. Many developers do not physically meet their "co-workers." This unique developer collaboration pattern leads to unique software development process, and hence unique structure of software products. It is those unique characteristics of open source software that motivate this dissertation study. Our research follows the framework of the four key elements of software engineering: Project, People, Process and Product (Jacobson, Booch et al. 1999). This dissertation studies three of the four P's: People, Process and Product. Due to the large sizes and high complexities of many open source software packages, the traditional analysis methods and measures in software engineering can not be readily leveraged to analyze those software packages. In this dissertation, we adopt complex network theory to perform our analysis on open source software packages, software development process, and the collaboration among software developers. We intend to discover some common characteristics that are shared by different open source software packages, and provide a possible explanation of the development process of those software products. Specifically we represent real world entities, such as open source software source code or developer collaborations, with networks composed of inter-connected vertices. We then leverage the topological metrics that have been established in complex network theory to analyze those networks. We also propose our own random network growth model to illustrate open source software development processes. Our research results can be potentially used by software practitioners who are interested to develop high quality software products and reduce the risks in the development process. Chapter 1 is an introduction of the dissertation's structure and research scope. We aim at studying open source software with complex networks. The details of the 4-P framework will be introduced in that chapter. Chapter 2 analyzes five C-language based open source software packages by leveraging function dependency networks. That chapter calculates the topological measures of the dependency networks extracted from software source code. Chapter 3 analyzes the collaborative relationship among open source software developers. We extract developer's co-working data out of two software bug fixing data sets. Again by leveraging complex network theory, we find out a number of topological characteristics of the software developer networks, such as the scale-free property. We also realize the topological differences between from the bug side and from the developer side for the extracted bipartite networks. Chapter 4 is to compare two widely adopted clustering coefficient definitions, the one proposed by Watts and Strogatz, the other by Newman. The analytical similarities and differences between the two clustering coefficient definitions provide useful guidance to the proposal of the random network growth model that is presented in the next chapter. Chapter 5 aims to characterize the open source software development process. We propose a two-phase network growth model to illustrate the software development process. Our model describes how different software source code units interconnect as the size of the software grows. A case study was performed by using the same five open source software packages that have been adopted in Chapter 2. The empirical results demonstrate that our model provides a possible explanation on the process of how open source software products are developed. Chapter 6 concludes the dissertation and highlights the possible future research directions.

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.

In this dissertation, we developed a method that uses the redundant information implicitly generated inside a random network coding network to apply error correction to the transmitted message. The obtained results show that the developed implicit error correcting method can reduce the effect of errors in a random network coding network without the addition of redundant information at the source node. This method presents numerous advantages compared to the documented concatenated error correction methods. We found that various error correction schemes can be implemented without adding redundancy at the source nodes. The decoding ability of this method is dependent on the network characteristics. We found that large networks with a high level of interconnectivity yield more redundant information allowing more advanced error correction schemes to be implemented. Network coding networks are prone to error propagation. We present the results of the effect of link error probability on our scheme and show that our scheme outperforms concatenated error correction schemes for low link error probability. / Thesis (M.Ing. (Computer Engineering))--North-West University, Potchefstroom Campus, 2010.

In this dissertation, we developed a method that uses the redundant information implicitly generated inside a random network coding network to apply error correction to the transmitted message. The obtained results show that the developed implicit error correcting method can reduce the effect of errors in a random network coding network without the addition of redundant information at the source node. This method presents numerous advantages compared to the documented concatenated error correction methods. We found that various error correction schemes can be implemented without adding redundancy at the source nodes. The decoding ability of this method is dependent on the network characteristics. We found that large networks with a high level of interconnectivity yield more redundant information allowing more advanced error correction schemes to be implemented. Network coding networks are prone to error propagation. We present the results of the effect of link error probability on our scheme and show that our scheme outperforms concatenated error correction schemes for low link error probability. / Thesis (M.Ing. (Computer Engineering))--North-West University, Potchefstroom Campus, 2010.