A utilização de redes complexas para a descriçãoi de diversos sistemas naturais e artificias,compreendidos nas mais diversas áreas do conhecimento humano, tem se mostrado uma abordagem poderosa para a redução da complexidade inerente a tais sistemas. Em muitos casos, tal complexidade resulta do número de componentes envolvidos e de suas intrincadas relações. Uma forma de reduzir a complexidade associada a tais sistemas, consiste em identificar e agrupar componentes que possuam características similares. Sendo assim, desenvolvemos nesta tese métodos de identificação de comunidades em redes complexas. Tais métodos se baseiam na ideia de que comunidades surgem quando grupos de vértices possuem um número mais elevado de conexões entre os vértices do mesmo grupo do que com vértices externos à este grupo. Além disso, utilizamos a função modularidade como função objetivo e como forma de avaliação e comparação dos resultados obtidos nesta tese com resultados previamente reportados na literatura. Uma vez estabelecido um método de identificação de comunidades, utilizamos a abordagem de redes complexas para a determinação de domínios estruturais de proteínas. Para tal, criamos redes de contato entre os aminoácidos de uma proteí?na buscando representar apenas as ligações relevantes do ponto de vista topológico. Por meio destas representações, aplicamos os métodos de identificação de comunidades desenvolvidos nesta tese, no intuito de identificar domínios estruturais de cadeias proteicas. Por fim, desenvolvemos um método específico para a identificação de domínios em proteínas com dois domínios sequencias, concluindo desta forma, os objetivos propostos nesta tese. / The use of complex networks for the representation of various natural and artificial sys- tems in the most diverse fields of human knowledge, has proven to be a powerful approach for the reduction of the complexity in the study of such systems. In many cases, this complexity emerges from the number of components of the system and from the intricate relationship between them. A reduction in this complexity is made possible by the iden- tification and grouping of the components of the system with similar characteristics. In this way, we developed in this thesis, methods for community identification in complex networks. Such methods are based on the notion that communities arise when groups of vertices are more densely connected with vertices of their same group, than with ver- tices belonging to other groups in the network. Moreover, the modularity function has been used as an objective function, and as a score for the evaluation and comparison of the results obtained in this thesis with the results reported in the literature of complex networks. Upon the establishment of a method for community detection, we used the framework of complex networks to the determination of structural protein domains. The- refore, we have created contact networks of amino acids of protein chains, focusing on the representation of only the most relevant interactions between them, from a topological point of view. We have applied to these networks the methods for community identi- fication developed in this thesis, aiming to identify the structural domains of proteins. Finally, we have developed a specific method for the identification of protein domains in protein chains with two sequential domains, concluding in this way, the objectives proposed in this thesis.

O reconhecimento de autoria é uma área de pesquisa efervescente, com muitas aplicações, incluindo detecção de plágio, análise de textos históricos, reconhecimento de mensagens terroristas ou falsificação de documentos. Modelos teóricos de redes complexas já são usados para o reconhecimento de autoria, mas alguns aspectos importantes têm sido ignorados. Neste trabalho, exploramos a dinâmica de redes de co-ocorrência e a relação com as palavras que representam os nós e descobrimos que ambas são claras assinaturas de autoria. Com otimização dos descritores da topologia das redes e de algoritmos de aprendizado de máquina, foi possível obter taxas de acerto maiores que 85%, sendo atingida uma taxa de 98.75% em um caso específico, para coleções de 80 livros, cada uma compilada de 8 autores de língua inglesa com 10 livros por autor. Esta tese demonstra que existem ainda aspectos inexplorados das redes de co-ocorrência de textos, o que deve permitir avanços ainda maiores no futuro próximo. / Authorship attribution is an active research area with many applications, including detection of plagiarism, analysis of historical texts, terrorist message identification or document falsification. Theoretical models of complex networks are already used for authorship attribution, but some issues have been ignored. In this thesis, we explore the dynamics of co-occurrence networks and the role of words, and found that they are both clear signatures of authorship. Using optimized descriptors for the network topology and machine learning algorithms, it has been possible to achieve accuracy rates above 85%, with a rate of 98.75% being reached in a particular case, for collections of 80 books produced by 8 English-speaking writers with 10 books per author. It is also shown that there are still many unexplored aspects of co-occurrence networks of texts, which seems promising for near future developments.

A teoria das redes complexas tem se consolidado por seu forte caráter interdisciplinar, relativa simplicidade conceitual e ampla aplicabilidade na modelagem de sistemas reais. Embora tendo evoluído rapidamente, uma série de problemas ainda não foram estudados usando as redes complexas. Em especial, sistemas envolvendo acoplamento e interação entre diferentes redes complexas têm sido pouco investigados. Na presente monografia, apresentamos duas contribuições fundamentais no estudo desses sistemas. A primeira consiste num modelo que descreve a interação entre um padrão de massa evoluindo numa rede regular com uma rede complexa que se organiza para impedir a evolução desse padrão. Os vértices da rede complexa se ativam e se movem sobre a rede regular conforme são requisitados por seus vizinhos, que se ativam pela rede regular. Essa última ativação ocorre quando a concentração de massa ultrapassa um limiar na respectiva posição do vértice e consiste em liberar uma difusão oposta de massa neutralizadora contra a massa original. A dinâmica mostrou-se completamente relacionada à estrutura da rede de controle. A presença de concentradores no modelo de Barabási-Albert tem papel fundamental para acelerar o processo de geração de massa neutralizadora. Por outro lado, a distribuição uniforme de vizinhos da rede de Erdös-Rényi resultou numa melhora de desempenho na presença de várias regiões distintas contendo massa original. A segunda contribuição consiste num modelo de interação entre duas espécies (predador e presa) através de campos sensitivos, que dependem da distância Euclidiana entre dois indivíduos e do seu respectivo tipo. Padrões espaço-temporais emergem nesse sistema e estão diretamente relacionados à intensidade de atração entre os indivíduos da mesma espécie. Para entender a evolução do sistema e quantificar a transferência de informação entre os diferentes aglomerados, duas redes complexas são construídas onde os vértices representam os indivíduos. Na primeira rede, o peso das conexões é dado pela distância Euclidiana entre os indivíduos e na segunda, pelo tempo que eles permaneceram suficientemente próximos. A partir de um mecanismo de fusão entre as duas redes, obtemos uma terceira rede complexa onde os vértices correspondem a grupos espaciais definidos a partir de um processo de limiarização dos pesos da primeira rede. Algumas configurações de parâmetros privilegiam a sobrevivência de presas enquanto outras beneficiam a caça dos predadores. / Complex network theory has become very popular because of its interdisciplinarity, conceptual simplicity and wide applicability to model real systems. Although fast growing, there is a number of problems which have not been addressed by using complex networks. For example, few efforts have been directed to systems involving coupling and interaction between different complex networks. In the following monography, we present two fundamental contributions in the study of such systems. The first consists in a model which describes the interaction dynamics between a mass pattern evolving in a regular network with a complex network, which are expected to control the pattern evolution. As soon as a complex network node is activated by the regular network, it requests help from its topological neighbours and activates them. The activation is triggered when the mass concentration overcomes a threshold in the node position and consists in liberating an opposite diffusion intended to eliminate the original pattern. The dynamics is completely related to the structure of the control network. The existence of hubs in the Barabási-Albert model plays a fundamental role to accelerate the opposite mass generation. Conversely, the uniform distribution of neighbours in the Erdös-Rényi network provided an increase in the efficiency when several focuses of the original pattern were distributed in the regular network. The second contribution consists in a model based on interactions between two species (predator and prey) provided by sensitive fields which depends of the Euclidean distance between two agents and on their respective types. Spatio-temporal patterns emerge in the system which are directly related to the attraction intensity between same species agents. To understand the dynamics evolution and quantify the information transfer through different clusters, we built two complex networks where the nodes represent the agents. In the first network, the edge weight is given by the Euclidean distance between two agents and, in the second network, by the amount of time two agents become close one another. By following a merging process, another network is obtained whose nodes correspond to spatial groups defined by a weight thresholding process in the first network. Some configurations favor the preys survival, while predators efficiency are improved by other ones.

O relacionamento entre estrutura e dinâmica em redes complexas foi considerado utilizando-se uma ampla gama de diferentes técnicas. Diversas redes reais foram estudadas em termos das correlações entre grau e atividade. A medida de atividade é definida como a proporção de visitas por vértice no regime estacionário do passeio aleatório simples. O estudo desse tipo de correlação é importante pois pode fornecer subsídios para que uma propriedade dinâmica de um vértice possa ser obtida somente analisando-se seu(s) grau(s). O conceito de acessibilidade foi abordado nesse contexto, permitindo que fossem evidenciadas diferentes correlações, em redes como a WWW, de acordo com a intensidade de acessibilidade dos vértices. Propôs-se também um novo modelo de rede baseado no crescimento do número de vértices em que novas conexões são criadas com probabilidade proporcional à atividade de cada vértice. Esse modelo pode ser entendido como uma generalização do modelo de Barabási e Albert para redes com arestas direcionadas. Utilizando-se um conjunto de diversas medidas estruturais, mostrou-se que o novo modelo apresenta, entre outros modelos tradicionais de redes, a maior compatibilidade com três redes corticais. Foi também desenvolvido um método para caracterização da distribuição de subgrafos e seus inter-relacionamentos. O principal aspecto dessa metodologia é a expansão gradual dos subgrafos, desenvolvida para que os vértices que encontram-se fora de subgrafos possam ter suas relevâncias quantificadas em termos da importância no estabelecimento das conexões entre subgrafos. Experimentos para ilustração do método foram realizados utilizando-se quatro modelos de redes e cinco redes reais, e os resultados obtidos foram relacionados aos processos dinâmicos de transporte e de espalhamento. Outro tópico aqui considerado é o dos efeitos da amostragem de redes corticais, quantificados por meio de análise multivariada e classificação, fazendo uso de um conjunto de medidas estruturais de redes. Esses efeitos também foram mensurados em termos do comportamento dinâmico das redes (sincronização e acessibilidade). Simulações dos métodos de encefalografia MEG e EEG mostraram que as redes amostradas podem apresentar características bem diferentes das da rede original, principalmente no caso de amostras pequenas. Adicionalmente, a rede integrada da bactéria Escherichia coli foi analisada, a qual incorpora (i) regulação de transcrição gênica, (ii) vias metabólicas e de sinalização e (iii) interações entre proteínas. Outliers foram identificados no relacionamento entre grau e atividade, os quais representam reguladores globais de transcrição. Além disso, verificou-se que esses outliers são genes altamente expressos em diferentes condições, apresentando, portanto, uma natureza global no controle de diversos outros genes da célula. / The relationship between structure and dynamics was addressed by employing a wide range of different approaches. First, the correlations between degree and activity were studied in various real-world networks. The activity is defined as the proportion of visits to each node in the steady-state regime of the simple random walk. This type of correlation can provide means to assess node activity only in terms of the degree. The concept of accessibility was included in this analysis, showing an intimate relationship (in networks such as the WWW) between the type of correlation and the level of accessibility observed on nodes. A new complex network model founded on growth was also proposed, with new connections being established proportionally to the current activity of each node. This model can be understood as a generalization of the Barabási-Albert model for directed networks. By using several topological measurements we showed that this new model provides, among several other traditional theoretical types of networks, the greatest compatibility with three real-world cortical networks. Additionally, we developed a novel approach considering non-overlapping subgraphs and their interrelationships and distribution through a given network. The main aspect of the methodology is a novel merging procedure developed to assess the relevance of nodes (in relation to the overall subgraph interconnectivity) lying outside subgraphs. Experiments were carried out on four types of network models and five instances of real-world networks, in order to illustrate the application of the method. Furthermore, these results were related to the properties of the transport and spreading processes. Other topic here addressed is the sampling problem in cortical networks. Effects of sampling were quantified using multivariate analysis and classifiers based on structural network measurements. Samples were also evaluated in terms of their dynamical behavior using a synchronization model and the measure of accessibility. By simulating MEG/EEG recordings it was found that sampled networks may substantially deviate from the respective original networks, mainly for small sample sizes. We also report an analysis of the integrated network of Escherichia coli, which incorporates (i) transcriptional regulatory interactions, (ii) metabolic/signaling feedback and (iii) protein-protein interactions. Network outliers, which represent global transcriptional regulators, were identified in the relationship between out-degree and activity. These outliers are highly and widely expressed across conditions, therefore supporting their global nature in controlling many genes in the cell.

A teoria das redes complexas é uma área altamente interdisciplinar que oferece recursos para o estudo dos mais variados tipos de sistemas complexos, desde o cérebro até a sociedade. Muitos problemas da natureza podem ser modelados como redes, tais como: as interações protéicas, organizações sociais, o mercado financeiro, a Internet e a World Wide Web. A organização de todos esses sistemas complexos pode ser representada por grafos, isto é, vértices conectados por arestas. Tais topologias têm uma influencia fundamental sobre muitos processos dinâmicos. Por exemplo, roteadores altamente conectados são fundamentais para manter o tráfego na Internet, enquanto pessoas que possuem um grande número de contatos sociais podem contaminar um grande número de outros indivíduos. Ao mesmo tempo, estudos têm mostrado que a estrutura do cérebro esta relacionada com doenças neurológicas, como a epilepsia, que está ligada a fenômenos de sincronização. Nesse trabalho, apresentamos como técnicas de mineração de dados podem ser usadas para estudar a relação entre topologias de redes complexas e processos dinâmicos. Tal estudo será realizado com a simulação de fenômenos de sincronização, falhas, ataques e propagação de epidemias. A estrutura das redes será caracterizada através de métodos de mineração de dados, que permitirão classificar redes de acordo com um conjunto de modelos e determinar padrões de conexões presentes na organização de diferentes tipos de sistemas complexos. As análises serão realizadas com aplicações em neurociências, biologia de sistemas, redes sociais e Internet / The theory of complex networks is a highly interdisciplinary reseach area offering resources for the study of various types of complex systems, from the brain to the society. Many problems of nature can be modeled as networks, such as protein interactions, social organizations, the financial market, the Internet and World Wide Web. The organization of all these complex systems can be represented by graphs, i.e. a set of vertices connected by edges. Such topologies have a fundamental influence on many dynamic processes. For example, highly connected routers are essential to keep traffic on the Internet, while people who have a large number of social contacts may infect many other individuals. Indeed, studies have shown that the structure of brain is related to neurological conditions such as epilepsy, which is relatad to synchronization phenomena. In this text, we present how data mining techniques data can be used to study the relation between complex network topologies and dynamic processes. This study will be conducted with the simulation of synchronization, failures, attacks and the epidemics spreading. The structure of the networks will be characterized by data mining methods, which allow classifying according to a set of theoretical models and to determine patterns of connections present in the organization of different types of complex systems. The analyzes will be performed with applications in neuroscience, systems biology, social networks and the Internet

Segmentação de imagens é ainda uma etapa desafiadora do processo de reconhecimento de padrões. Entre as abordagens de segmentação, muitas são baseadas em particionamento em grafos, as quais apresentam alguns inconvenientes, sendo um deles o tempo de processamento muito elevado. Com as recentes pesquisas na teoria de redes complexas, as técnicas de reconhecimento de padrões baseadas em grafos melhoraram consideravelmente. A identificação de grupos de vértices pode ser considerada um processo de detecção de comunidades de acordo com a teoria de redes complexas. Como o agrupamento de dados está relacionado com a segmentação de imagens, esta também pode ser abordada através de redes complexas. No entanto, a segmentação de imagens baseado em redes complexas apresenta uma limitação fundamental, que é o número excessivo de nós na rede. Neste trabalho é proposta uma abordagem de redes complexas para segmentação de imagens de grandes dimensões que é ao mesmo tempo precisa e rápida. Para alcançar este objetivo, é incorporado o conceito de Super Pixels, visando reduzir o número de nós da rede. Os experimentos mostraram que a abordagem proposta produz segmentações de boa qualidade em baixo tempo de processamento. Além disso uma das principais contribuições deste trabalho é a determinação dos melhores parâmetros, uma vez que torna o método bastante independente dos parâmetros, o que não fora alcançado antes em nenhuma pesquisa da área / Image segmentation is still a challenging stage of the pattern recognition process. Amongst the various segmentation approaches, some are based on graph partitioning, many of which show some drawbacks, such as the high processing times. Recent trends on complex network theory have contributed considerably to the development of graph-based pattern recognition techniques. The identification of group of vertices can be considered a community detection process according to complex network theory. Since data clustering is closely related to image segmentation, image segmentation tasks can also be tackled by complex networks. However, complex network-based image segmentation poses a very important limitation: the excessive number of nodes of the underlying network. In this work we propose a approach based on complex networks suitable for the segmentation of image with large dimensions that is accurate and yet fast. To accomplish that, we have incorporated the concept of Super Pixels aiming at reducing the number of the nodes in the network. The results have shown that the proposed approach delivered accurate image segmentation within low computational times. Another contribution worth mentioning is the determination of the best values for the parameters needed by the underlying graphbased segmentation and community detection algorithms, which enabled the proposed approach to become less dependent on the parameters. To the best of our knowledge, this is a new contribution to the field

Cities are complex systems of transportation and social activity; their structure can be used to model urban street networks i.e. complex network that represents the geometry of a city allowing analytical activities for data-driven decision-making. The geometry of a city holds intrinsic information that can support activities related to the analysis of the urban scenario; of higher importance is the use of such information to enhance the quality of life of its inhabitants and/or to understand the dynamics of an urban center. Several of these analytical processes lacks in-depth methodologies to analyze crime patterns and ill-designed urban structures, which can provide for public safety and urban design. Consequently, it is our goal to provide means for the structural and topological analysis of highly criminal regions of cities represented as complex networks, and for the identification of urban planning inconsistencies that point to regions that lack access from/to points of interest in a city. In this regard, we devised a set of algebraic and algorithmic procedures that are capable of revealing patterns and provide for data comprehension. More specifically, we introduced pre-processing techniques to transform georeferenced electronic maps into graph representations of cities; we used metric-based and epidemic processes to understand the dynamics of cities in what refers to criminality; finally, we introduced a novel set of formalisms and operations based on set theory to identify design flaws concerning access in urban centers. Our results refer to approaches to preprocess and prepare maps in the form of urban street networks; to the analyses of crimes based on their spatial disposition; to the development of a model to describe criminal activities; and, to the advance of a concept based on critical problems in the urban design. / As cidades são sistemas complexos de interação social e de transporte. Suas estruturas podem ser usadas para modelar redes de mobilidade urbana i.e. redes complexas que representam a geometria de uma cidade permitindo a consecução de atividades analíticas para descoberta de padrões e para a tomada de decisão baseada em dados. A geometria da cidade carrega informações intrínsecas que auxiliam atividades relacionadas à análise de dados provenientes do cenário urbano. As informações inerentes a tais análises podem ser usadas para melhorar a qualidade de vida dos habitantes de uma região, ou para entender a dinâmica de centros urbanos. Diversos processos analíticos aplicados a tais cenários carecem de metodologias para analisar o padrão criminal e para identificar estruturas urbanas mal planejadas. Deste modo, este trabalho tem por objetivo prover meios para análise topológica de regiões criminais e para a identificação de inconsistências urbanas, as quais apontam para regiões que carecem de mobilidade e acesso para outras regiões de uma cidade. Neste sentido, foi desenvolvido um conjunto de procedimentos algébricos e algorítmicos capazes de revelar padrões e meios para compreensão e análise dos dados. Mais especificamente, foram desenvolvidos métodos de pré-processamento para transformar mapas eletrônicos georreferenciados em grafos que representam cidades, foi utilizado um conjunto métrico analítico e outro com base em processos epidêmicos para entender a dinâmica intrínseca à criminalidade de uma cidade, e por fim, foi desenvolvido um conjunto de formalismos e operações baseados em teoria dos conjuntos para identificar falhas no desenho das estruturas urbanas que impactam no acesso viário em centros urbanos. Os resultados deste trabalho versam sobre o desenvolvimento de novos métodos para preparar mapas na forma de redes de mobilidade urbana; na análise de crimes baseada em sua disposição espacial; no desenvolvimento de um modelo capaz de descrever a atividade criminal de uma cidade; e, em um conceito baseado na análise de regiões críticas identificadas a partir do desenho urbano.

Esse trabalho consiste em um estudo sobre a aplicabilidade da medida de centralidade de intermediação (betweenness centrality) combinada com demandas de tráfego em redes viárias com o objetivo de identificar os principais pontos dessas redes. Como principais pontos refere-se aqui aos que aparecem com maior frequência entre os caminhos utilizados pelos motoristas que se deslocam pela rede viária. Trata-se de um estudo exploratório, que se inicia com a aplicação da centralidade de intermediação sobre redes simples, estendendo-se até simulações sobre redes baseadas em mapas reais. Nesse trabalho é analisado o comportamento da medida de centralidade sobre a topologia da rede - i.e. tanto sem considerar uma demanda, como considerando demandas de diversas magnitudes. Para ilustrar a proposta, os resultados são confrontados com valores de centralidade de intermediação calculados sobre as taxas de ocupação das vias extraídas de simulação microscópica. Ao final, foram apresentadas evidências de que o método proposto consegue explicar os fluxos de tráfego com melhor desempenho do que a centralidade de intermediação original. No entanto, o método mostrou-se muito sensível à função de custo utilizada na atribuição da demanda de tráfego ao grafo da rede. Os melhores resultados demonstrados pela abordagem proposta foram obtidos em experimentos sobre redes não regulares e com demandas de tráfego não uniformes. No caso de redes regulares com demanda uniforme, o melhor desempenho foi obtido pelo cálculo da centralidade sem considerar a demanda, mas atribuindo-se o custo unitário às arestas do grafo representativo da rede. / This work consists of a study of applicability of betweenness centrality combined with traffic demands in road networks with the objective of identifying their central points. By central points we refer to those which appear with high frequency among the paths used by drivers that move along the road network. It is an exploratory study, which begins with the application of the betweenness centrality on simple networks, extending to simulations on networks based on real maps. In this study we have analyzed the behavior of the metric over the network topology - i.e. without considering demand, as well as experiments considering demands with several magnitudes. To illustrate the proposed method, the results are compared with betweenness centrality values calculated over roadways occupation rates extracted from microscopic simulation. At the end, evidence that the proposed method can explain traffic flows with better performance than the original betweenness centrality were presented. However, the proposed method was shown to be very sensitive to the cost function used in the allocation of the graph network traffic demand. The best results demonstrated by the proposed approach were obtained in experiments on nonregular networks and non-uniform traffic demands. In the case of regular networks with uniform demand, the best performance was obtained by calculating the betweenness centrality without considering the demand, but assigning the unitary cost to the edges of the network graph.

Orientador: Varese Salvador Timóteo / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-17T09:47:55Z (GMT). No. of bitstreams: 1 Pereira_VanessaHelena_M.pdf: 2435236 bytes, checksum: c61f3c9e770fd549a5b0fac102f12ffc (MD5) Previous issue date: 2010 / Resumo: A necessidade da operação intermitente de redes complexas leva ao estudo das falhas nas redes de topologia livre de escala (Scale-Free) de Barabási-Albert. Neste trabalho introduzem-se as teorias fundamentais ao estudo das redes complexas, além da revisão de vários trabalhos científicos relacionados às falhas e aos mecanismos de contenção destas. Utilizando o software Attacker-Defender, são construídas várias redes complexas Scale-Free de diferentes tamanhos, representadas por grafos. Estas redes são utilizadas para simular dois tipos de falhas mais frequentes: falhas aleatórias e falhas direcionadas aos hubs (nós com maior número de arestas incidentes) em duas etapas. Na primeira etapa, em dez tamanhos de redes são testadas quatro situações distintas. Na segunda etapa, em sete tamanhos de redes, são testadas dez diferentes vulnerabilidades. A partir da análise dos resultados da primeira etapa, observa-se qual dos quatro cenários analisados é o mais vantajoso para contenção de falhas nas redes. A análise da segunda etapa permite definir a descrição matemática do comportamento dos nós sobreviventes e atingidos no pós-falha, em cada uma das redes, para cada tipo de falha, através de métodos e funções específicas encontradas. / Abstract: The need for the intermittent operation of complex networks leads to the study of failures in these networks topology called Scale-Free, Barabási-Albert. In this work we introduce the fundamental theories to the study of complex networks, in addition to reviewing various scientific studies related to the failures and the mechanisms against cascade failures. Using the Attacker-Defender software, Scale-Free complex networks of different sizes are built, represented as graphs. These networks are used to simulate the two most common types of failures: random failures and attacks to hubs (nodes with the largest number of incident edges) in two steps. In the first step in ten sizes of networks are tested in distinct four cases. In the second step, in seven sizes of networks are tested ten different vulnerabilities. From the analysis of the results of the first step, it is observed which cases are best for the networks. The analysis of the second step provides the mathematical description of the behavior of the survivors and the affected nodes, after the failure in each network for each type of failure, through methods and specific functions was found. / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Um nÃmero significativo de redes reais apresentam caracterÃsticas espaciais bem definidas. NÃs estudamos como topologias de redes espacialmente correlacionadas podem influenciar processos de navegaÃÃo atravÃs das mesmas. Para isso estudamos o comportamento do mÃnimo caminho mÃdio para redes definidas dentro de modelo de Kleinberg para analisar a navegaÃÃo ditada por regras de conhecimento global. O modelo que Kleinberg caracteriza-se por permitir conexÃes de longo alcance entre dois vÃrtices u e v distribuÃdas por uma distribuiÃÃo de probabilidade em lei de potÃncia. Para um melhor entendimento das caracterÃsticas topolÃgicas apresentadas por essa famÃlia de redes, nÃs aplicamos o modelo epidÃmico suscetÃvel-infectado-suscetÃvel (SIS), e com isso verificamos que o modelo de Kleinberg apresenta fenÃmeno de mundo pequeno apenas para uma determinada faixa de valores assumidos pelo expoente de agregaÃÃo α. Em seguida, introduzimos um modelo de redes espacialmente embutidas, conceitualmente inspirado no modelo de Kleinberg. Este traduz-se na introduÃÃo de um vÃnculo para a distribuiÃÃo das conexÃes de longo alcance. Associamos este vÃnculo a um possÃvel custo envolvido no processo de adiÃÃo de novas conexÃes de longo alcance à rede. Estudamos como esse vÃnculo no custo afeta a navegaÃÃo na rede, tendo como base de comparaÃÃo os trabalhos de Kleinberg para a navegaÃÃo com conhecimento local da topologia, e nossos resultados considerando a navegaÃÃo com conhecimento global. / A significant number of real networks have well-defined spatial characteristics. We studied how network with spatially correlated topolgies can influence the processes of navigation through them. For this, we study the behavior of the average shortest-path length to networks defined within Kleinbergâs model [1, 2] to analyze the navigation dictated by rules of global knowledge. The Kleinbergâs model is characterized by allowing long-range connections between two vertices u and v distributed by a power-law probability distribution. For a better understanding of the topological characteristics presented by this family of networks, we applied the epidemic model susceptible-infected-susceptible (SIS) and we found that, we see that the Kleinbergâs model presents the small-world phenomenon only for a certain range of values of the clustering exponent α. We introduced a model of spatially embedded networks, conceptually based on the Kleinbergâs model. This model consist in introduction of a constrain to the distribution of long-range connections. We associate his constrain to a possible cost involved in the process of adding new long-range connections to the network. We studied how this cost constrain affects the navigation through the system, taking as a basis for comparison the work of Kleinberg for navigation with local knowledge, and our results conserning for navigation with global knowledge.