The advancement of modern technologies has resulted in an explosive growth of complex systems, such as the Internet, biological, social, and various infrastructure networks, which have, in turn, contributed to the rise of massive networks. During the past decade, analyzing and mining of these networks has become an emerging research area with many real-world applications. The most relevant problems in this area include: collecting and managing networks, modeling and generating random networks, and developing network mining algorithms. In the era of big data, speed is not an option anymore for the effective analysis of these massive systems, it is an absolute necessity. This motivates the need for parallel algorithms on modern high-performance computing (HPC) systems including multi-core, distributed, and graphics processor units (GPU) based systems. In this dissertation, we present distributed memory parallel algorithms for generating massive random networks and a novel GPU-based algorithm for index searching. This dissertation is divided into two parts. In Part I, we present parallel algorithms for generating massive random networks using several widely-used models. We design and develop a novel parallel algorithm for generating random networks using the preferential-attachment model. This algorithm can generate networks with billions of edges in just a few minutes using a medium-sized computing cluster. We develop another parallel algorithm for generating random networks with a given sequence of expected degrees. We also design a new a time and space efficient algorithmic method to generate random networks with any degree distributions. This method has been applied to generate random networks using other popular network models, such as block two-level Erdos-Renyi and stochastic block models. Parallel algorithms for network generation pose many nontrivial challenges such as dependency on edges, avoiding duplicate edges, and load balancing. We applied novel techniques to deal with these challenges. All of our algorithms scale very well to a large number of processors and provide almost linear speed-up. Dealing with a large number of networks collected from a variety of fields requires efficient management systems such as graph databases. Finding a record in those databases is very critical and typically is the main bottleneck for performance. In Part II of the dissertation, we develop a GPU-based parallel algorithm for index searching. Our algorithm achieves the fastest throughput ever reported in the literature for various benchmarks. / Ph. D. / The advancement of modern technologies has resulted in an explosive growth of complex systems, such as the Internet, biological, social, and various infrastructure networks, which have, in turn, contributed to the rise of massive networks. During the past decade, analyzing and mining of these networks has become an emerging research area with many real-world applications. The most relevant problems in this area include: collecting and managing networks, modeling and generating random networks, and developing network mining algorithms. As the networks are massive in size, we need faster algorithms for the quick and effective analysis of these systems. This motivates the need for parallel algorithms on modern high-performance computing (HPC) based systems. In this dissertation, we present HPC-based parallel algorithms for generating massive random networks and managing large scale network data. This dissertation is divided into two parts. In Part I, we present parallel algorithms for generating massive random networks using several widely-used models, such as the preferential attachment model, the Chung-Lu model, the block two-level Erdős-Rényi model and the stochastic block model. Our algorithms can generate networks with billions of edges in just a few minutes using a medium-sized HPC-based cluster. We applied novel load balancing techniques to distribute workloads equally among the processors. As a result, all of our algorithms scale very well to a large number of processors and provide almost linear speed-up. In Part II of the dissertation, we develop a parallel algorithm for finding records by given keys. Dealing with a large number of network data collected from a variety of fields requires efficient database management systems such as graph databases. Finding a record in those databases is very critical and typically is the main bottleneck for performance. Our algorithm achieves the fastest data lookup throughput ever reported in the literature for various benchmarks.

Graph signal processing analyzes signals supported on the nodes of a network with respect to a shift operator matrix that conforms to the graph structure. For shift-invariant graph filters, which are polynomial functions of the shift matrix, the filter response is defined by the value of the filter polynomial at the shift matrix eigenvalues. Thus, information regarding the spectral decomposition of the shift matrix plays an important role in filter design. However, under stochastic conditions leading to uncertain network structure, the eigenvalues of the shift matrix become random, complicating the filter design task. In such case, empirical distribution functions built from the random matrix eigenvalues may exhibit deterministic limiting behavior that can be exploited for problems on large-scale random networks. Acceleration filters for distributed average consensus dynamics on random networks provide the application covered in this thesis work. The thesis discusses methods from random matrix theory appropriate for analyzing adjacency matrix spectral asymptotics for both directed and undirected random networks, introducing relevant theorems. Network distribution properties that allow computational simplification of these methods are developed, and the methods are applied to important classes of random network distributions. Subsequently, the thesis presents the main contributions, which consist of optimization problems for consensus acceleration filters based on the obtained asymptotic spectral density information. The presented methods cover several cases for the random network distribution, including both undirected and directed networks as well as both constant and switching random networks. These methods also cover two related optimization objectives, asymptotic convergence rate and graph total variation.

The deterministic theory of graphs and networks is used successfully in cases where no random component is needed. However in practice, a number of decision-making and conflict situations require the inclusion of a stochastic element directly into the model. The objective of this thesis is the introduction of stochastic optimization and its application on random networks. The reader will become familiar with three approaches to stochastic optimization. Namely two-stage optimization, multi-stage optimization and chance constraint optimization. Finally, the studied issue is demonstrated on a real telecommunication network example.

No description available.

Networks (or graphs) are an effective abstraction for representing many real-world complex systems. Analyzing various structural properties of and dynamics on such networks reveal valuable insights about the behavior of such systems. In today's data-rich world, we are deluged by the massive amount of heterogeneous data from various sources, such as the web, infrastructure, and online social media. Analyzing this huge amount of data may take a prohibitively long time and even may not fit into the main memory of a single processing unit, thus motivating the necessity of efficient parallel algorithms in various high-performance computing (HPC) platforms. In this dissertation, we present distributed and shared memory parallel algorithms for some important network analytic problems. First, we present distributed memory parallel algorithms for switching edges in a network. Edge switch is an operation on a network, where two edges are selected randomly, and one of their end vertices are swapped with each other. This operation is repeated either a given number of times or until a specified criterion is satisfied. It has diverse real-world applications such as in generating simple random networks with a given degree sequence and in modeling and studying various dynamic networks. One of the steps in our edge switch algorithm requires generating multinomial random variables in parallel. We also present the first non-trivial parallel algorithm for generating multinomial random variables. Next, we present efficient algorithms for assortative edge switch in a labeled network. Assuming each vertex has a label, an assortative edge switch operation imposes an extra constraint, i.e., two edges are randomly selected and one of their end vertices are swapped with each other if the labels of the end vertices of the edges remain the same as before. It can be used to study the effect of the network structural properties on dynamics over a network. Although the problem of assortative edge switch seems to be similar to that of (regular) edge switch, the constraint on the vertex labels in assortative edge switch leads to a new difficulty, which needs to be addressed by an entirely new algorithmic approach. We first present a novel sequential algorithm for assortative edge switch; then we present an efficient distributed memory parallel algorithm based on our sequential algorithm. Finally, we present efficient shared memory parallel algorithms for generating random networks with exact given degree sequence using a direct graph construction method, which involves computing a candidate list for creating an edge incident on a vertex using the Erdos-Gallai characterization and then randomly creating the edges from the candidates. / Ph. D. / Network analysis has become a popular topic in many disciplines including social sciences, epidemiology, biology, and business as it provides valuable insights about many real-world systems represented as networks. The recent advancement of science and technology has resulted in a massive growth of such networks, and mining and processing such massive networks poses significant challenges, which can be addressed by various high-performance computing (HPC) platforms. In this dissertation, we present parallel algorithms for a few network analytic problems using HPC platforms. Random networks are widely used for modeling many complex real-world systems such as the Internet, biological, social, and infrastructure networks. Most prior work on generating random graphs involves sequential algorithms, and they can be broadly categorized in two classes: (i) edge switching and (ii) stub-matching. We present parallel algorithms for generating random graphs using both the edge switching and stub-matching methods. Our parallel algorithms for switching edges can generate random networks with billions of edges in a few minutes with 1024 processors. We have studied several load balancing methods to equally distribute workload among the processors to achieve the best performance. The parallel algorithm for generating random graphs using the stub-matching method also shows good speedup for medium-sized networks. We believe the proposed parallel algorithms will prove useful in analyzing and mining of emerging networks.

Complex organization is found in many biological systems. For example, biopolymers could possess very hierarchic structure, which provides their functional peculiarity. Understating such, complex organization allows describing biological phenomena and predicting molecule functions. Besides, we can try to characterize the specific phenomenon by some probabilistic quantities (variances, means, etc), assuming the primary biopolymer structure to be randomly formed according to some statistical distribution. Such a formulation is oriented toward evolutionary problems.Artificially constructed biological network is another common object of statistical physics with rich functional properties. A behavior of cells is a consequence of complex interactions between its numerous components, such as DNA, RNA, proteins and small molecules. Cells use signaling pathways and regulatory mechanisms to coordinate multiple processes, allowing them to respond and to adapt to changing environment. Recent theoretical advances allow us to describe cellular network structure using graph concepts to reveal the principal organizational features shared with numerous non-biological networks.The aim of this thesis is to develop bunch of methods for studying statistical and dynamic objects of complex architecture and, in particular, scale-free structures, which have no characteristic spatial and/or time scale. For such systems, the use of standard mathematical methods, relying on the average behavior of the whole system, is often incorrect or useless, while a detailed many-body description is almost hopeless because of the combinatorial complexity of the problem. Here we focus on two problems.The first part addresses to statistical analysis of random biopolymers. Apart from the evolutionary context, our studies cover more general problems of planar topology appeared in description of various systems, ranging from gauge theory to biophysics. We investigate analytically and numerically a phase transition of a generic planar matching problem, from the regime, where almost all the vertices are paired, to the situation, where a finite fraction of them remains unmatched.The second part of this work focus on statistical properties of networks. We demonstrate the possibility to define co-expression gene clusters within a network context from their specific motif distribution signatures. We also show how a method based on the shortest path function (SPF) can be applied to gene interactions sub-networks of co-expression gene clusters, to efficiently predict novel regulatory transcription factors (TFs). The biological significance of this method by applying it on groups of genes with a shared regulatory locus, found by genetic genomics, is presented. Finally, we discuss formation of stable patters of motifs in networks under selective evolution in context of creation of islands of "superfamilies".

Stability analysis of networked dynamical systems has been of interest in many disciplines such as biology and physics and chemistry with applications such as LASER cooling and plasma stability. These large networks are often modeled to have a completely random (Erdös-Rényi) or semi-random (Small-World) topologies. The former model is often used due to mathematical tractability while the latter has been shown to be a better model for most real life networks. The recent emergence of cyber physical systems, and in particular the smart grid, has given rise to a number of engineering questions regarding the control and optimization of such networks. Some of the these questions are: How can the stability of a random network be characterized in probabilistic terms? Can the effects of network topology and system dynamics be separated? What does it take to control a large random network? Can decentralized (pinning) control be effective? If not, how large does the control network needs to be? How can decentralized or distributed controllers be designed? How the size of control network would scale with the size of networked system? Motivated by these questions, we began by studying the probability of stability of synchronization in random networks of oscillators. We developed a stability condition separating the effects of topology and node dynamics and evaluated bounds on the probability of stability for both Erdös-Rényi (ER) and Small-World (SW) network topology models. We then turned our attention to the more realistic scenario where the dynamics of the nodes and couplings are mismatched. Utilizing the concept of ε-synchronization, we have studied the probability of synchronization and showed that the synchronization error, ε, can be arbitrarily reduced using linear controllers. We have also considered the decentralized approach of pinning control to ensure stability in such complex networks. In the pinning method, decentralized controllers are used to control a fraction of the nodes in the network. This is different from traditional decentralized approaches where all the nodes have their own controllers. While the problem of selecting the minimum number of pinning nodes is known to be NP-hard and grows exponentially with the number of nodes in the network we have devised a suboptimal algorithm to select the pinning nodes which converges linearly with network size. We have also analyzed the effectiveness of the pinning approach for the synchronization of oscillators in the networks with fast switching, where the network links disconnect and reconnect quickly relative to the node dynamics. To address the scaling problem in the design of distributed control networks, we have employed a random control network to stabilize a random plant network. Our results show that for an ER plant network, the control network needs to grow linearly with the size of the plant network.

De nombreux systèmes biologiques présentent une organisation complexe. Par exemple, les biopolymères peuvent posséder une structure très hiérarchisée responsable de leur fonction particulière. Comprendre la complexité de cette organisation permet de décrire des phénomènes biologiques et de prédire les fonctions des molécules. En outre, en supposant que la structure primaire du polymère est formée aléatoirement, nous pouvons essayer de caractériser ce phénomène par des grandeurs probabilistes (variances, moyennes, etc). Cette formulation est propre aux problèmes d'évolution.Les réseaux biologiques sont d'autres objets communs de la physique statistique possédant de riches propriétés fonctionnelles. Pour décrire un mécanisme biologique, on utilise différents types de réseaux biomoléculaires. Le développement de nouvelles approches peut nous aider à structurer, représenter et interpréter des données expérimentales, comprendre les processus cellulaires et prédire la fonction d'une molécule.L'objectif de cette thèse est de développer des méthodes pour l'étude d'objets statiques ou dynamiques, ayant une architecture complexe. Ici, nous nous intéressons à deux problèmes.La première partie est consacrée à l'analyse statistique des biopolymères aléatoires. Nous étudions une transition de phase présente dans les séquences aléatoires de l'ARN. On met alors en évidence deux modes : le régime où presque toutes les bases qui composent l'ARN sont couplées et la situation où une fraction finie de ces bases restent non complémentaires.La deuxième partie de cette thèse se concentre sur les propriétés statistiques des réseaux. Nous développons des méthodes pour l'identification d'amas de gènes co-expressifs sur les réseaux et la prédiction de gènes régulateurs novateurs. Pour cela, nous utilisons la fonction du plus court chemin et l'analyse du profil des motifs formés par ces amas. Ces méthodes ont pu prédire les facteurs de transcription impliqués dans le processus de longévité. Enfin, nous discutons de la formation de motifs stables sur les réseaux due à une évolution sélective. / Complex organization is found in many biological systems. For example, biopolymers could possess very hierarchic structure, which provides their functional peculiarity. Understating such, complex organization allows describing biological phenomena and predicting molecule functions. Besides, we can try to characterize the specific phenomenon by some probabilistic quantities (variances, means, etc), assuming the primary biopolymer structure to be randomly formed according to some statistical distribution. Such a formulation is oriented toward evolutionary problems.Artificially constructed biological network is another common object of statistical physics with rich functional properties. A behavior of cells is a consequence of complex interactions between its numerous components, such as DNA, RNA, proteins and small molecules. Cells use signaling pathways and regulatory mechanisms to coordinate multiple processes, allowing them to respond and to adapt to changing environment. Recent theoretical advances allow us to describe cellular network structure using graph concepts to reveal the principal organizational features shared with numerous non-biological networks.The aim of this thesis is to develop bunch of methods for studying statistical and dynamic objects of complex architecture and, in particular, scale-free structures, which have no characteristic spatial and/or time scale. For such systems, the use of standard mathematical methods, relying on the average behavior of the whole system, is often incorrect or useless, while a detailed many-body description is almost hopeless because of the combinatorial complexity of the problem. Here we focus on two problems.The first part addresses to statistical analysis of random biopolymers. Apart from the evolutionary context, our studies cover more general problems of planar topology appeared in description of various systems, ranging from gauge theory to biophysics. We investigate analytically and numerically a phase transition of a generic planar matching problem, from the regime, where almost all the vertices are paired, to the situation, where a finite fraction of them remains unmatched.The second part of this work focus on statistical properties of networks. We demonstrate the possibility to define co-expression gene clusters within a network context from their specific motif distribution signatures. We also show how a method based on the shortest path function (SPF) can be applied to gene interactions sub-networks of co-expression gene clusters, to efficiently predict novel regulatory transcription factors (TFs). The biological significance of this method by applying it on groups of genes with a shared regulatory locus, found by genetic genomics, is presented. Finally, we discuss formation of stable patters of motifs in networks under selective evolution in context of creation of islands of "superfamilies".

Estuda-se o espalhamento de doenças contagiosas utilizando modelos suscetível-infectado-recuperado (SIR) representados por equações diferenciais ordinárias (EDOs) e por autômatos celulares probabilistas (ACPs) conectados por redes aleatórias. Cada indivíduo (célula) do reticulado do ACP sofre a influência de outros, sendo que a probabilidade de ocorrer interação com os mais próximos é maior. Efetuam-se simulações para investigar como a propagação da doença é afetada pela topologia de acoplamento da população. Comparam-se os resultados numéricos obtidos com o modelo baseado em ACPs aleatoriamente conectados com os resultados obtidos com o modelo descrito por EDOs. Conclui-se que considerar a estrutura topológica da população pode dificultar a caracterização da doença, a partir da observação da evolução temporal do número de infectados. Conclui-se também que isolar alguns infectados causa o mesmo efeito do que isolar muitos suscetíveis. Além disso, analisa-se uma estratégia de vacinação com base em teoria dos jogos. Nesse jogo, o governo tenta minimizar os gastos para controlar a epidemia. Como resultado, o governo realiza campanhas quase-periódicas de vacinação. / The spreading of contagious diseases is studied by using susceptible-infected-recovered (SIR) models represented by ordinary differential equations (ODE) and by probabilistic cellular automata (PCA) connected by random networks. Each individual (cell) of the PCA lattice experiences the influence of others, where the probability of occurring interaction with the nearest ones is higher. Simulations for investigating how the disease propagation is affected by the coupling topology of the population are performed. The numerical results obtained with the model based on randomly connected PCA are compared to the results obtained with the model described by ODE. It is concluded that considering the topological structure of the population can pose difficulties for characterizing the disease, from the observation of the time evolution of the number of infected individuals. It is also concluded that isolating a few infected subjects can cause the same effect than isolating many susceptible individuals. Furthermore, a vaccination strategy based on game theory is analyzed. In this game, the government tries to minimize the expenses for controlling the epidemic. As consequence, the government implements quasi-periodic vaccination campaigns.

Submitted by Anna Patricia Pachas Manrique (annapamanrique@gmail.com) on 2017-02-23T20:20:56Z No. of bitstreams: 1 20_02 (1).pdf: 1460371 bytes, checksum: e98c8f4713680550a770e8efcc7ffa14 (MD5) / Approved for entry into archive by Janete de Oliveira Feitosa (janete.feitosa@fgv.br) on 2017-08-03T17:52:37Z (GMT) No. of bitstreams: 1 20_02 (1).pdf: 1460371 bytes, checksum: e98c8f4713680550a770e8efcc7ffa14 (MD5) / Made available in DSpace on 2017-08-18T14:34:31Z (GMT). No. of bitstreams: 1 20_02 (1).pdf: 1460371 bytes, checksum: e98c8f4713680550a770e8efcc7ffa14 (MD5) Previous issue date: 2016-08-29 / The speed and comprehensiveness global level with the pathogen has spread in recent years has drawn attention to the importance of the contact’s social network structure. In fact, the topology of the networks in which members of society interact has influenced the dynamics of epidemics. Studies have shown that pathogens when disiparem in scale-free networks have different effects when compared broadcast in random networks, such as the classic models. In these there were epidemic threshold, may somehow the health ministry have a control on the dissipation of diseases by applying certain measures such as vaccines. Already in models in which are considered the networks, specifically the free network scale, the threshold disappears. Thus, the epidemic threshold depends on the topology is required to include within this structure models Because of the importance of these networks, random networks and scalefree have been implemented along the epidemics of propagation models to check the epidemic threshold and the characteristic time, noting that the epidemic threshold disappears / A velocidade e a abrangência a nível mundial com que os agentes patogênicos tem se disseminado nos últimos anos tem chamado a atenção para a importância da estrutura da rede social de contato . De fato, a topologia das redes na qual os membros da sociedade interagem têm influenciado na dinâmica das epidemias.Estudos têm demostrado que os agentes patogênicos ao se dissiparem em redes livres de escala tem efeitos diferentes se comparado quando difundidos em redes aleatórias, como nos modelos clássicos. Nestes existiam limiar de epidemia ,podendo de alguma forma as entidades de saúde ter um controle sobre a dissipação das enfermidades , aplicando certas medidas como as vacinas por exemplo. Já nos modelos nos quais são consideradas as redes , especificamente a rede livre de escala,este limiar desaparece. Desta forma, o limiar de epidemia ao depender da topologia se faz necessário incluir esta estrutura dentro dos modelos epidemiológicos. Devido a importância destas redes , redes aleatórias e principalmente redes livres de escala foram implementadas junto a modelos de propagação de epidemias para verificar o limiar de epidemia e o tempo característico , verificando que o limiar de epidemia desaparece.