Preferential attachment networks with power law degree sequence undergo a phase transition when the power law exponent τ changes. For τ > 3 typical distances in the network are logarithmic in the size of the network and for 2 < τ < 3 they are doubly logarithmic. In this thesis, we identify the correct scaling constant for τ ∈ (2, 3) and discover a surprising dichotomy between preferential attachment networks and networks without preferential attachment. This contradicts previous conjectures of universality. Moreover, using a model recently introduced by Dereich and Mörters, we study the critical behaviour at τ = 3, and establish novel results for the scale of the typical distances under lower order perturbations of the attachment function.

Many processes and systems in nature and society can be characterized as large numbers of discrete elements that are (usually non-uniformly) interrelated. These networks were long thought to be random, but in the late 1990s, Barabási and Albert found that an underlying structure did in fact exist in many natural and technological networks that are now referred to as scale free. Since then, researchers have gained a much deeper understanding of this particular form of complexity, largely by combining graph theory, statistical physics, and advances in computing technology. This dissertation focuses on out-of-equilibrium dynamic processes as they unfold on these complex networks. Diffusion in networks of non-interacting nodes is shown to be temporally complex, while equilibrium is represented by a stable state with Poissonian fluctuations. Scale free networks achieve equilibrium very quickly compared to regular networks, and the most efficient are those with the lowest inverse power law exponent. Temporally complex diffusion also occurs in networks with interacting nodes under a cooperative decision-making model. At a critical value of the cooperation parameter, the most efficient scale free network achieves consensus almost as quickly as the equivalent all-to-all network. This finding suggests that the ubiquity of scale free networks in nature is due to Zipf's principle of least effort. It also suggests that an efficient scale free network structure may be optimal for real networks that require high connectivity but are hampered by high link costs.

Recently, there has been much interest in the resilience of complex networks to random failures and intentional attacks. The study of the network robustness is particularly important by several occasions. In one hand a higher degree of robustness to errors and attacks may be desired for maintaining the information flow in communication networks under attacks. On the other hand planning a very limited attack aimed at fragmenting a network by removal of minimum number of the most important nodes might have significant usage in drug design. Many real world networks were found to display scale free topology including WWW, the internet, social networks or regulatory gene and protein networks. In the recent studies it was shown that while these networks have a surprising error tolerance, their scale-free topology makes them fragile under intentional attack, leaving the scientists a challenge on how to improve the networks robustness against attacks. In this thesis, we studied the protein domain co-occurrence network of yeast which displays scale free topology generated with data from Biomart which links to Pfam database. Several networks obtained from protein domain co-occurrence network having exactly the same connectivity distribution were compared under attacks to investigate the assumption that the different networks with the same connectivity distribution do not need to have the same attack tolerances. In addition to this, we considered that the networks with the same connectivity distribution have higher attack tolerance as we organize the same resources in a better way. Then, we checked for the variations of attack tolerance of the networks with the same connectiviy distributions. Furthermore, we investigated whether there is an evolutionary mechanism for having networks with higher or lower attack tolerances for the same connectivity distribution. As a result of these investigations, the different networks with the same connectivity distribution do not have the same attack tolerances under attack. In addition to this, it was observed that the networks with the same connectivity distribution have higher attack tolerances as organizing the same resources in a better way which implies that there is an evolutionary mechanism for having networks with higher attack tolerance for the same connectivity distribution.

Networks are all around us, all the time. From the biochemistry of our cells to the web of friendships across the planet. From the circuitry of modern electronics to chains of historical events. A network is the result of the forces that shaped it. Thus the principles of network formation can be, to some extent, deciphered from the network itself. All such information comprises the structure of the network. The study of network structure is the core of modern network science. This thesis centres around three aspects of network structure: What kinds of network structures are there and how can they be measured? How can we build models for network formation that give the structure of networks in the real world? How does the network structure affect dynamical systems confined to the networks? These questions are discussed using a variety of statistical, analytical and modelling techniques developed by physicists, mathematicians, biologists, chemists, psychologists, sociologists and anthropologists. My own research touches all three questions. In this thesis I present works trying to answer: What is the best way to protect a network against sinister attacks? How do groups form in friendship networks? Where do traffic jams appear in a communication network? How is cellular metabolism organised? How do Swedes flirt on the Internet? . . . and many other questions.

nÃo hà / Na primeira parte deste trabalho, empregamos uma rede neural artificial (RNA) treinada com algoritmo back-propagation para inferir a volatilidade dos gases liquefeitos de petrÃleo (GLP) produzidos em uma torre de fracionamento de lÃquido de gÃs natural (LGN). Os resultados obtidos indicam que a RNA fornece melhores respostas do que um simulador desenvolvido com base fenomenolÃgica que se encontra em fase de implementaÃÃo na planta em estudo. Na segunda parte da dissertaÃÃo, o nosso objetivo primordial à demonstrar que os fluxogramas de processos de refinarias de petrÃleo podem estar intrinsecamente associados à topologias de redes complexas, que sÃo scale-free, exibem efeitos de mundo pequeno e possuem organizaÃÃo hierÃrquica. A emergÃncia dessas propriedades em redes artificiais à explicada como uma consequÃncia dos princÃpios usados no design de projeto dos processos, os quais incluem regras heurÃsticas e tÃcnicas algorÃtmicas. Esperamos que esses resultados sejam tambÃm vÃlidos para plantas quÃmicas de diferentes tipos e capacidades. / In the first part of this work we apply an artificial neural network (ANN) trained with a back-propagation algorithm to predict the volatility of liquefied petroleum gases (LPG) produced from a fractionation tower of natural gas liquid (NGL). Our analysis indicate that the ANN scheme provides better results than a simulator developed based phenomenological which is currently being implemented in the plant under study. In the second part, our primary objective is to demonstrate that flowsheets of oil refineries can be intrinsically associated to complex network topologies, which are scale-free, display small-word effect and have hierarchical organization. The emergence of these properties artificial networks is explained as a consequence of the design principles used in the processâ design, which include heuristics rules and algorithmic techniques. We expect these results to be also valid for chemical plants of different types and capacities.

<p>Networks are all around us, all the time. From the biochemistry of our cells to the web of friendships across the planet. From the circuitry of modern electronics to chains of historical events. A network is the result of the forces that shaped it. Thus the principles of network formation can be, to some extent, deciphered from the network itself. All such information comprises the structure of the network. The study of network structure is the core of modern network science. This thesis centres around three aspects of network structure: What kinds of network structures are there and how can they be measured? How can we build models for network formation that give the structure of networks in the real world? How does the network structure affect dynamical systems confined to the networks? These questions are discussed using a variety of statistical, analytical and modelling techniques developed by physicists, mathematicians, biologists, chemists, psychologists, sociologists and anthropologists. My own research touches all three questions. In this thesis I present works trying to answer: What is the best way to protect a network against sinister attacks? How do groups form in friendship networks? Where do traffic jams appear in a communication network? How is cellular metabolism organised? How do Swedes flirt on the Internet? . . . and many other questions.</p>

Ένα φαινόμενο που έκανε την εμφάνισή του τα τελευταία χρόνια είναι η μελέτη μεγάλων δικτύων που εμφανίζουν μια ιεραρχική δομή ανεξαρτήτως κλίμακας (large scale-free networks). Μια παραδοσιακή μέθοδος μοντελοποίησης δικτύων είναι η χρήση γραφημάτων και η χρησιμοποίηση αποτελεσμάτων που προκύπτουν από την Θεωρία Γράφων. Όμως στα κλασικά μοντέλα που έχουν μελετηθεί, δυο κόμβοι του ίδιου γραφήματος έχουν την ίδια πιθανότητα να συνδέονται με οποιουσδήποτε δυο άλλους κόμβους. Αυτός ο τρόπος μοντελοποίησης αποτυγχάνει να περιγράψει πολλά δίκτυα της καθημερινής ζωής, όπως δίκτυα γνωριμιών όπου οι κόμβοι συμβολίζουν ανθρώπους και συνδέονται μεταξύ τους αν γνωρίζονται άμεσα. Σε ένα τέτοιο δίκτυο είναι αναμενόμενο δυο φίλοι κάποιου ατόμου να έχουν μεγαλύτερη πιθανότητα να γνωρίζονται μεταξύ τους από ότι δυο τυχαία επιλεγμένοι ξένοι. Αυτό ακριβώς το φαινόμενο ονομάζεται συσσωμάτωση (clustering) και είναι χαρακτηριστικό για τα εν λόγω δίκτυα. Είναι γεγονός ότι πολλά δίκτυα που συναντώνται στη φύση αλλά και πάρα πολλά ανθρωπογενή δίκτυα εντάσσονται σε αυτήν την κατηγορία. Παραδείγματα τέτοιων είναι τα δίκτυα πρωτεϊνών, δίκτυα τροφικών αλυσίδων, επιδημικής διάδοσης ασθενειών, δίκτυα ηλεκτρικού ρεύματος, υπολογιστών, ιστοσελίδων του Παγκόσμιου Ιστού, δίκτυα γνωριμιών, επιστημονικών αναφορών (citations) κ.α. . Παρότι φαίνεται να άπτονται πολλών επιστημών όπως η Φυσική, η Βιολογία, η Κοινωνιολογία και η Πληροφορική, δεν έχουν τύχει ευρείας μελέτης, καθώς μέχρι στιγμής έλειπαν πραγματικά μεγάλα δίκτυα για πειραματική μελέτη (κενό που καλύφθηκε με την ανάπτυξη του Παγκόσμιου Ιστού). Μέχρι σήμερα δεν έχουν φωτιστεί όλα εκείνα τα σημεία και τα μεγέθη που είναι χαρακτηριστικά για αυτά τα δίκτυα και που πρέπει να εστιάσει η επιστημονική έρευνα, παρόλα αυτά έχει γίνει κάποια πρόοδος. Μια τέτοια έννοια που μπορεί να εκφραστεί με πολλά μεγέθη είναι η έννοια της κεντρικότητας (centrality) ενός κόμβου στο δίκτυο. Η χρησιμότητα ενός τέτοιου μεγέθους, αν μπορεί να οριστεί, είναι προφανής, για παράδειγμα στον τομέα της εσκεμμένης «επίθεσης» σε ένα τέτοιο δίκτυο (π.χ. δίκτυο υπολογιστών). Η ακριβής όμως συσχέτιση της κεντρικότητας με τα άλλα χαρακτηριστικά μεγέθη του δικτύου, όπως η συσσωμάτωση, δεν είναι γνωστή. Στόχος της εργασίας είναι να εμβαθύνει στην έννοια της κεντρικότητας, και χρησιμοποιεί σαν πεδίο πειραματισμών τον χώρο της εσκεμμένης επίθεσης σε ανεξάρτητα κλίμακας δίκτυα. Στο πλαίσιο αυτό γίνεται μια συνοπτική παρουσίαση των μοντέλων δικτύων που έχουν προταθεί μέχρι σήμερα και αναλύεται η έννοια της κεντρικότητας μέσω των παραδοσιακών ορισμών της από την επιστήμη της Κοινωνιολογίας. Στη συνέχεια προτείνεται μια σειρά ορισμών της κεντρικότητας που την συνδέουν με μεγέθη του δικτύου όπως ο συντελεστής συσσωμάτωσης. Η καταλληλότητα των ορισμών αυτών διαπιστώνεται στην πράξη, εξομοιώνοντας πειραματικά επιθέσεις σε ανεξάρτητα κλίμακας μεγάλα δίκτυα και χρησιμοποιώντας στρατηγικές επίθεσης που βασίζονται σε αυτές. / A trend in recent years is the study of large networks which possess a hierarchical structure independent of the current scale (large scale-free networks). A traditional method of network modelling is the use of graphs and the usage of results based on Graph Theory. Until recently, the classical models studied, describe the probability of two random vertices connecting with each other as equal for all pairs of vertices. This modelling fails to describe many everyday networks such as acquaintance networks, where the vertices are individuals and connect with an edge if they know each other

Made available in DSpace on 2015-03-26T13:35:10Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2430887 bytes, checksum: 46c97cae3636842e90c00b8d31b6f16a (MD5) Previous issue date: 2009-02-09 / Fundação de Amparo a Pesquisa do Estado de Minas Gerais / The dramatic resurgence and emergence of epidemic dengue and dengue hemorragic fever in the last two decades neatly define a global pandemic. The dispersion of dengue viruses combines local infections of humans bited by infective mosquitoes inside a city with long-range transmissions to non-infective vectors that feed the blood of infected people arriving from other urban areas. In the present work a cellular automata model for dengue epidemic is proposed and investigated through large-scale computer simulations. The model takes into account the main features concerning the population dynamics of mosquitoes and humans and the disease transmission cycle. Furthermore, the model is defined on a scale-free network in which each node is a square lattice in order to properly describe the environment as urban centers interconnected through a national transportation system. A nonzero epidemic threshold is found and it is approached with a power law behavior by the density of infected individuals, as observed in the small-world network of Watts and Strogatz. Also, it is studied the importance of three parameters for the dengue spreading: the diffusivity of the mosquitoes, the probability of a mosquito bites humans, and the travel's probability of people between two interconnected cities. Finally, maps of infected individuals are obtained in order to caracterise the epidemic spreading. / O dramático ressurgimento e a emergência da epidemia de dengue e dengue hemorrágica nas últimas duas décadas claramente definem uma pandemia global. A dispersão do vírus da dengue combina infecções locais dos seres humanos picados por mosquitos infectados dentro de uma cidade com transmissões de longo alcance por vetores não-infecciosos que se alimentam do sangue de pessoas infectadas provenientes de outras zonas urbanas. No presente trabalho um modelo de autômatos celulares para epidemias de dengue é proposto e investigado através de siulação por computador, em larga escala. O modelo leva em conta as principais características relativas à dinâmica das populações de mosquitos e seres humanos e o ciclo de transmissão da doença. Além disso, o modelo é definido em uma rede livre de escala, em que cada nó é uma rede quadrada, a fim de descrever adequadamente o meio ambiente como os centros urbanos interligados através do sistema de transporte nacional. Um limiar epidêmico diferente de zero é encontrado e é aproximado com um comportamento tipo lei de potência pela densidade de indivíduos infectados, como observado na rede mundo-pequeno de Watts-Strogatz. Também, é estudada a importância de três parâmetros na dispersão da dengue: a difusividade do mosquito, a probabilidade do mosquito picar um ser humano, e a probabilidade de viagem de pessoas entre duas cidades conectadas. Por fim, mapas de indivíduos infectados são obtidos a fim de caracterizar a difusão da epidemia.

Le calcul des valeurs propres intervient dans des modèles de maladies d’épidémiques et pourrait être utilisé comme un allié des campagnes de vac- cination dans les actions menées par les organisations de soins de santé. La modélisation épidémique peut être considérée, par analogie, comme celle des viruses d’ordinateur qui dépendent de l’état de graphe sous-jacent à un moment donné. Nous utilisons PageRank comme méthode pour étudier la propagation de l’épidémie et d’envisager son calcul dans le cadre de phé- nomène petit-monde. Une mise en œuvre parallèle de méthode multiple de "implicitly restar- ted Arnoldi method" (MIRAM) est proposé pour calculer le vecteur propre dominant de matrices stochastiques issus de très grands réseaux réels. La grande valeur de "damping factor" pour ce problème fait de nombreux algo- rithmes existants moins efficace, tandis que MIRAM pourrait être promet- teuse. Nous proposons également dans cette thèse un générateur de graphe parallèle qui peut être utilisé pour générer des réseaux synthétisés distri- bués qui présentent des structures "scale-free" et petit-monde. Ce générateur pourrait servir de donnée pour d’autres algorithmes de graphes également. MIRAM est mis en œuvre dans le cadre de trilinos, en ciblant les grandes données et matrices creuses représentant des réseaux sans échelle, aussi connu comme les réseaux de loi de puissance. Hypergraphe approche de partitionnement est utilisé pour minimiser le temps de communication. L’al- gorithme est testé sur un grille national de Grid5000. Les expériences sur les très grands réseaux tels que Twitter et Yahoo avec plus de 1 milliard de nœuds sont exécutées. Avec notre mise en œuvre parallèle, une accélération de 27× est satisfaite par rapport au solveur séquentiel / The eigenvalue equation intervenes in models of infectious disease prop- agation and could be used as an ally of vaccination campaigns in the ac- tions carried out by health care organizations. The epidemiological model- ing techniques can be considered by analogy, as computer viral propagation which depends on the underlying graph status at a given time. We point out PageRank as method to study the epidemic spread and consider its calcula- tion in the context of small-world phenomenon. A parallel implementation of multiple implicitly restarted Arnoldi method (MIRAM) is proposed for calculating dominant eigenpair of stochastic matrices derived from very large real networks. Their high damp- ing factor makes many existing algorithms less efficient, while MIRAM could be promising. We also propose in this thesis a parallel graph gen- erator that can be used to generate distributed synthesized networks that display scale-free and small-world structures. This generator could serve as a testbed for graph related algorithms. MIRAM is implemented within the framework of Trilinos, targeting big data and sparse matrices representing scale-free networks, also known as power law networks. Hypergraph partitioning approach is employed to minimize the communication overhead. The algorithm is tested on a nation wide cluster of clusters Grid5000. Experiments on very large networks such as twitter and yahoo with over 1 billion nodes are conducted. With our parallel implementation, a speedup of 27× is met compared to the sequential solver

In this work we analyse two problems coming from theoretical biology. In the first part we propose a spatially structured population model which is defined on a continuous lattice. In the model individuals disperse at a constant rate v and competition is local and delimitated by the competition radius R. Due to dispersal, the neighborhooh size fluctuates over time. We analyse how these variables affect the adaptive process. While the fixation probabilities of beneficial mutations are roughly the same as in a panmitic population for small and intermediate fitness effects s, a dependence on v and R appears for large s. These quantities also strongly influence fixation times. The model exhibits a dual behavior displaying a power-law growth for the fixation rate and speed of adaptation with the beneficial mutation rate as observed in spatially structured population models, but simultaneously showing a non-saturating behavior for the speed of adaptation with the population size. In the second part we numerically study the dynamics of model imune networks with random and scale-free topologies. We observe that a memory state is reached when the antigen is attached to the most connected sites of the network, where as a percolation state may occur when the antigen attaches to the less connected sites. For increasing values of the connectivity, its population converges exponentially to the asymptotic value of the memory state. On the other hand, the next-nearest populations evolve slowly as power-laws towards the virgin-like state. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho, analisamos dois problemas provenientes da biologia teórica. Na primeira parte, propomos um modelo de população espacialmente estruturada, que é definido numa rede contínua. No modelo, indivíduos se dispersam numa taxa constante v e a competição é local e delimitada pelo raio de competição R. Devido à dispersão, o tamanho da vizinhança flutua ao longo do tempo. Analisamos como essas variáveis afetam o processo adaptativo. Embora as probabilidades de fixação de mutações benéficas sejam aproximadamente as mesmas que numa população panmítica para valores de adaptação de pequeno e médio s, uma dependência de v e R aparece para grandes s. Estas quantidades também influenciam fortemente os tempos de fixação. O modelo exibe um comportamento duplo que indica um crescimento em lei de potência para a taxa de fixação e a velocidade de adaptação com a taxa de mutação benéfica como observado em modelos de população espacialmente estruturadas, mas simultaneamente mostra um comportamento não saturante para a velocidade de adaptação com o tamanho da população. Na segunda parte, estudamos numericamente a dinâmica de modelos de redes imunes com topologias aleatória e livre de escala. Observamos que um estado memória é alcançado quando o antígeno é ligado aos sítios mais conectados da rede enquanto que um estado de percolação pode ocorrer quando o antígeno se liga aos sítios menos conectados. Para maiores valores de conectividade, sua população converge exponencialmente para o valor assintótico do estado de memória. Por outro lado, as populações mais próximas evoluem lentamente, como leis de potência para o estado virgem.