No contexto de Redes Complexas, particularmente das redes sociais, grupos de objetos densamente conectados entre si, esparsamente conectados a outros grupos, são denominados de comunidades. Detecção dessas comunidades tornou-se um campo de crescente interesse científico e possui inúmeras aplicações práticas. Nesse contexto, surgiram várias pesquisas sobre estratégias multinível para particionar redes com elevada quantidade de vértices e arestas. O objetivo dessas estratégias é diminuir o custo do algoritmo de particionamento aplicando-o sobre uma versão reduzida da rede original. Uma possibilidade dessa estratégia, ainda pouco explorada, é utilizar heurísticas de refinamento local para melhorar a solução final. A maioria das abordagens de refinamento exploram propriedades gerais de redes complexas, tais como corte mínimo ou modularidade, porém, não exploram propriedades inerentes de domínios específicos. Por exemplo, redes sociais são caracterizadas por elevado coeficiente de agrupamento e assortatividade significativa, consequentemente, maximizar tais características pode conduzir a uma boa solução e uma estrutura de comunidades bem definida. Motivado por essa lacuna, neste trabalho é proposto um novo algoritmo de refinamento, denominado RSim, que explora características de alto grau de transitividade e assortatividade presente em algumas redes reais, em particular em redes sociais. Para isso, adotou-se medidas de similaridade híbridas entre pares de vértices, que utilizam os conceitos de vizinhança e informações de comunidades para interpretar a semelhança entre pares de vértices. Uma análise comparativa e sistemática demonstrou que o RSim supera os algoritmos de refinamento habituais em redes com alto coeficiente de agrupamento e assortatividade. Além disso, avaliou-se o RSim em uma aplicação real. Nesse cenário, o RSim supera todos os métodos avaliado quanto a eficiência e eficácia, considerando todos os conjuntos de dados selecionados. / In the context of complex networks, particularly social networks, groups of densely interconnected objects, sparsely linked to other groups are called communities. Detection of these communities has become a field of increasing scientific interest and has numerous practical applications. In this context, several studies have emerged on multilevel strategies for partitioning networks with high amount of vertices and edges. The goal of these strategies is to reduce the cost of partitioning algorithm by applying it on a reduced version of the original network. The possibility for this strategy, yet little explored, is to apply local refinement heuristics to improve the final solution. Most refinement approaches explore general properties of complex networks, such as minimum cut or modularity, however, do not exploit inherent properties of specific domains. For example, social networks are characterized by high clustering coefficient and significant assortativity, hence maximize such characteristics may lead to a good solution and a well-defined community structure. Motivated by this gap, in this thesis, we propose a new refinement algorithm, called RSim, which exploits characteristics of high degree of transitivity and assortativity present in some real networks, particularly social networks. For this, we adopted hybrid similarity measures between pairs of vertices, using the concepts of neighborhood and community information to interpret the similarity between pairs of vertices. A systematic and comparative analysis showed that the RSim statistically outperforms usual refinement algorithms in networks with high clustering coefficient and assortativity. In addition, we assessed the RSim in a real application. In this scenario, the RSim surpasses all evaluated methods in efficiency and effectiveness, considering all the selected data sets.

Os componentes celulares não atuam sozinhos, mas sim em uma rede de interações. Neste sentido, é fundamental descobrir como os genes se relacionam e compreender a dinâmica do sistema biológico. Este conhecimento pode contribuir para o tratamento de doenças, para o melhoramento genético de plantas e aumento de produção agrícola, por exemplo. Muitas redes gênicas são desconhecidas ou apenas conhecidas parcialmente. Neste contexto, a inferência de Redes Gênicas surgiu como possível solução e tem por objetivo recuperar a rede a partir de dados de expressão gênica utilizando modelos probabilísticos. No entanto, um problema intrínseco da inferência de redes é formalmente descrito como maldição da dimensionalidade (a quantidade de variáveis é muito maior que a quantidade de amostras). No contexto biológico, este problema é ainda agravado pois é necessário lidar com milhares de genes e apenas um ou duas dezenas de amostras de dados de expressão. Assim, os modelos de inferência buscam contornar este problema propondo soluções que minimizem o erro de estimação. Nos modelos de predição ainda há muitos empates, isto é, apenas os dados de expressão não são suficientes para decidir pela interação correta entre os genes. Neste contexto, a proposta de integração de outros dados biológicos além do dado de expressão gênica surge como possível solução. No entanto, estes dados são heterogêneos: referem-se a interações físicas, relacionamentos funcionais, localização, dentre outros. Além disto são representados de diferentes formas: como dado quantitativo, qualitativo, como atributos nominais ou atributos ordinais. Algumas vezes organizados em estrutura hierárquica, em outras como um grafo e ainda como anotação descritiva. Além disto, não está claro como cada tipo de dado pode contribuir com a inferência e redução do erro dos modelos. Portanto, é fundamental buscar compreender a relação entre os dados biológicos disponíveis, bem como investigar como integrá-los na inferência. Assim, neste trabalho desenvolveu-se três metodologias de integração de dados e a contribuição de cada tipo foi analisada. Os resultados mostraram que o uso conjunto de dados de expressão e outros dados biológicos melhora a predição das redes. Também apontaram para diferença no potencial de redução do erro de acordo com o tipo de dado. Além disto, os resultados mostraram que o conhecimento da topologia da rede também reduz o erro além de inferir redes topologicamente coerentes com a topologia esperada / It is widely known that the cellular components do not act in isolation but through a network of interactions. In this sense, it is essential to discover how genes interact with each other and to understand the dynamics of the biological system. This knowledge can contribute for the treatment of diseases, contribute for plant breeding and increased agricultural production. In this context, the inference of Gene Networks (GNs) has emerged as a possible solution, studying how to recover the network from gene expression data through probabilistic models. However, a known problem of network inference is formally described as curse of dimensionality (the number of variables is much larger than the number of samples). In biological problems, it is even worse since there is only few samples and thousands of genes. However, there are still many ties found in the prediction models, that is, only the expression data are frequently not enough to decide the correct interaction between genes. In this context, data integration is proposed as a possible solution. However, the data are heterogeneous, refer to physical interactions and functional location. They are represented in different ways as quantitative or qualitative information, being nominal or ordinal attributes. Sometimes organized in hierarchical structure or as a graph. In addition, it is unclear how each type of data can contribute to the inference and reduction of the error. Therefore, it is very important to understand the relationship between the biological information available. Also, it is important to investigate how to integrate them in the inference algorithm. Thus, this work has developed three data integration methodologies and also, the contribution of biological information was analyzed. The results showed that the combined use of expression data and biological information improves the inference. Moreover, the results shows distinct behaviour of distinct data in error reduction. Also, experiments that include topological features into the models, shows that the knowledge of the network topology can increase the corrctness of the inferred newtorks

Nos últimos 60 anos, os modelos de difusão de produtos e de inovações tiveram penetração tão ampla nos mais diversos campos de investigação científica que se tornaram ubíquos, sendo empregados em contextos diversos como no marketing, na Medicina, na Antropologia, na Geografia, por exemplo. Essa abrangência é devido ao papel vital que produtos, inovações e novas tecnologias têm na vida dos indivíduos e no impacto que exercem nas dinâmicas e no desenvolvimento de comunidades, países e de suas economias. Porém, após os grandes saltos dados nas décadas de 1960 e 1970, os estudos em difusão de bens de consumo duráveis deram lugar a pesquisas em sistemas de inovação nas duas décadas seguintes, só voltando a gerar maior interesse acadêmico a partir da década de 2000, com o surgimento dos sistemas de Gestão de Relacionamento com Clientes Customer Relationship Management (CRM) , que tornou disponível um enorme volume de dados; e, também, com o desenvolvimento de novas técnicas de análise, como a modelagem de sistemas complexos. Tendo em vista a carência de estudos integrando modelos de difusão competitiva com modelos de redes usando topologias de redes parcialmente conectadas (small world e livres de escala), este estudo tem como objetivo geral caracterizar a dinâmica da difusão competitiva proposta em redes small world do tipo Watts-Strogatz. Foram realizadas simulações tanto da formulação clássica do modelo de difusão de produtos e de inovações, proposto por Bass (1969), como de proposições mais modernas para difusão competitiva, como os propostos por Libai, Muller e Peres (2009a; 2009b; 2009c) e por Peres, Muller e Mahajan (2010), além de desenvolver um novo modelo incorporando ao de Libai, Muller e Peres (2009c) a topologia de redes de pequeno mundo e outras características de difusão competitiva não presentes na formulação original , permitindo fazer inferências sobre o comportamento da difusão em diversos cenários que não são explicitamente previstos nas formulações clássicas. Por sua lógica intuitiva e simples, o modelo proposto neste trabalho é de valor significativo para o ensino e para a pesquisa da difusão competitiva / In the last 60 years, product and innovation models were so widespread in so many fields of study that they became ubiquitous, being employed in such diverse backgrounds like marketing, medicine, anthropology and geography. Such widespread influence arises from the fact that products, innovations and Technologies have a big role in any individuals daily lives and a huge impact on the development and dynamics of communities, countries and its economies. After huge leaps on this field of research during the 1960s and 1970s, its study faded away from mainstream research in the following two decades. Only regaining widespread academic interest in the beginning of 21st century, with the advent of Customer Relationship Management systems, which made available huge amounts of data, other factors that contributed to this resurgence in diffusion literature were the advancements on new tools for research, notably the developments in complex systems theory and network theory. In the view of the still small, but rapidly increasing, number of studies integrating competitive diffusion and network models of partially connected networks (such as small world networks and scale-free networks), this study aims to characterize the dynamics of competitive diffusion in small world networks with the Watts-Strogatz topology. For its intended purpose, simulations were created, both for the classical formulation of the Bass Diffusion Model, as well as more modern approaches for competitive diffusion, such as the models proposed by Libai, Muller and Peres and Peres, Muller and Mahajan. A new model was developed in order expand the model proposed by Libai et al (2009c) in order incorporate the small world network topology and other characteristics associated to competition that were not explicitly represented. Allowing the inference of behaviors in various scenarios that are not explicitly covered in the classical formulations. For intuitive logic and simplicity, it is believed that this model is of significant value for teaching and for the study of competitive diffusion

Centralidades são medidas desenvolvidas para determinar a importância dos nós e ligações, utilizando as características estruturais das redes para esta finalidade. As medidas de centralidade são, portanto, essenciais no estudo de redes complexas pois os sistemas representados por elas geralmente são formados por muitos elementos, e com isso, torna-se inviável estudar individualmente cada um deles; dessa forma é necessário identificar os nós e ligações que são mais relevantes em cada situação. Todavia, com o surgimento de ideias diferentes de como esses elementos podem ser importantes, diversas medidas foram propostas com o intuito de evidenciar elementos que passam despercebidos pelas demais. Neste trabalho utilizamos a correlação de Pearson para avaliar o quão semelhantes são as classificações fornecidas pelas centralidades para redes representando sistemas reais e modelos teóricos. Para avaliar a efetividade das medidas e como elas afetam cada sistema, atacamos as redes usando as centralidades como indicadores para a ordem de remoção dos nós e ligações. Procurando caracterizar as redes usando suas diferenças estruturais, realizamos uma análise de componentes principais empregando as correlações entre os pares de centralidade como características de cada sistema. Nossos resultados mostraram que na maioria dos casos medidas distintas estão correlacionadas, o que indica que em geral os mesmos elementos são evidenciados pelas diferentes centralidades; também observamos que as correlações são mais fortes nos modelos do que nos sistemas reais. Os ataques mostraram que medidas fortemente correlacionadas podem influenciar as redes de maneiras distintas, evidenciando a importância do conjunto de elementos selecionados por cada medida. Nosso último resultado demonstra que as correlações entre os pares de centralidades podem ser utilizados tanto para a diferenciação e caracterização de redes quanto na avaliação de modelos que representem melhor a estrutura de um sistema específico. / Centrality measures were developed to evaluate the importance of nodes and links based on the structure of networks. Centralities are essential in the study of networks because these systems are usually large, which make manual analysis of all nodes and links impossible; therefore recognizing such elements is a vital task. As nodes and links can be considered essential by different reasons, a large number of measures were proposed to identify important elements that were not highlighted by the other ones. In our study, we use Pearson\'s correlation coefficient to measure the similarity between rankings of nodes and links provided by different centralities for real and model based networks. We also perform attacks to networks, using these rankings to determine the order of removal of nodes and links, intending to evaluate and compare the efficiency and how the systems react to attacks guided by different centralities. Finally, we use the correlation coefficients between the pairs of centralities as properties of networks, and perform a principal component analysis with them, to evaluate if differences among network structures can be detected from correlations. Our results showed that centrality measures are frequently correlated, which means that the same elements can be highlighted by different centralities. We also noticed that the correlation coefficients are larger in models than in real world networks. The results of the attacks experiment showed that even when two measures are highly correlated, they can affect networks in distinct ways, meaning that the group of the nodes and links provided by each measure are relevant for the study of networks systems. Our last result evidenced that correlations among centrality measures can be used for characterization of networks and to evaluate how well models represent them.

A Sumarização Automática de Textos tem considerável importância nas tarefas de localização e utilização de conteúdo relevante em meio à quantidade enorme de informação disponível atualmente em meio digital. Nessa área, procura-se desenvolver técnicas que possibilitem obter o conteúdo mais relevante de documentos, de maneira condensada, sem alterar seu significado original, e com mínima intervenção humana. O objetivo deste trabalho de mestrado foi investigar de que maneira conceitos desenvolvidos na área de Redes Complexas podem ser aplicados à Sumarização Automática de Textos, mais especificamente à sumarização extrativa. Embora grande parte das pesquisas em sumarização tenha se voltado para a utilização de técnicas extrativas, ainda é possível melhorar o nível de informatividade dos extratos gerados automaticamente. Neste trabalho, textos foram representados como redes, das quais foram extraídas medidas tradicionalmente utilizadas na caracterização de redes complexas (por exemplo, coeficiente de aglomeração, grau hierárquico e índice de localidade), com o intuito de fornecer subsídios à seleção das sentenças mais significativas de um texto. Essas redes são formadas pelas sentenças (representadas pelos vértices) de um determinado texto, juntamente com as repetições (representadas pelas arestas) de substantivos entre sentenças após lematização. Cada método de sumarização proposto foi aplicado no córpus TeMário, de textos jornalísticos em português, e em córpus das conferências DUC, de textos jornalísticos em inglês. A avaliação desse estudo foi feita por meio da realização de quatro experimentos, fazendo-se uso de métodos de avaliação automática (Rouge-1 e Precisão/Cobertura de sentenças) e comparando-se os resultados com os de outros sistemas de sumarização extrativa. Os melhores sumarizadores propostos referem-se aos seguintes conceitos: d-anel, grau, k-núcleo e caminho mínimo. Foram obtidos resultados comparáveis aos dos melhores métodos de sumarização já propostos para o português, enquanto que, para o inglês, os resultados são menos expressivos. / Automatic Text Summarization has considerably importance in tasks such as finding and using relevant content in the enormous amount of information available nowadays in digital media. The focus in this field is on the development of techniques that allow someone to obtain the most relevant content of documents, in a condensed way, preserving the original meaning and with little (or even none) human help. The purpose of this MSc project was to investigate a way of applying concepts borrowed from the studies of Complex Networks to the Automatic Text Summarization field, specifically to the task of extractive summarization. Although the majority of works in summarization have focused on extractive techniques, it is still possible to obtain better levels of informativity in extracts automatically generated. In this work, texts were represented as networks, from which the most significant sentences were selected through the use of ranking algorithms. Such networks are obtained from a text in the following manner: the sentences are represented as nodes, and an edge between two nodes is created if there is at least one repetition of a noun in both sentences, after the lemmatization step. Measurements typically employed in the characterization of complex networks, such as clustering coefficient, hierarchical degree and locality index, were used on the basis of the process of node (sentence) selection in order to build an extract. Each summarization technique proposed was applied to the TeMário corpus, which comprises newspaper articles in Portuguese, and to the DUC corpora, which comprises newspaper articles in English. Four evaluation experiments were carried out, by means of automatic evaluation measurements (Rouge-1 and sentence Precision/Recall) and comparison with the results obtained by other extractive summarization systems. The best summarizers are the ones based on the following concepts: d-ring, degree, k-core and shortest path. Performances comparable to the best summarization systems for Portuguese were achieved, whilst the results are less significant for English.

There any many different aspects in natural languages and their related dynamics that have been studied. In the case of languages, some quantitative analyses have been done by using stochastic models. Furthermore, natural languages can be understood as complex systems. Thus, there is a possibility to use set of tools development to analyse complex networks, which are computationally represented by graphs, also to analyse natural languages. Furthermore, these tools can be used to represent and analyse some related dynamics taking place on the networks. Observe that knowledge is intrinsically related to language, because language is the vehicle used by humans beings to transmit dicoveries, and the language itself is also a type of knowledge. This thesis is divided into two types of analyses: (i) texts and (II) dynamical aspects. In the first part, we proposed networks representations of text in different scales analyses, starting from the analysis of writing style considering word adjacency networks (co-occurence) to understand local patterns of words, to a mesoscopic representation, which is created from chunks of text and grasps information of the unfolding of the story. In the second part, we considered the structure and dynamics related to knowledge and language, in this case, starting from the larger scale, in which we studied the connectivity between applied and theoretical physics. In the following, we simulated the knowledge acquisition by researchers in a multi-agent dynamics and an intelligent machine that solves problems, which is represented by a network. At the smallest considered scale, we simulate the transmission of networks. This transmission considers the data as a series of organized symbols that is obtained from a dynamics. In order to improve the speed of transmission, the series can be compacted. For that, we considered the information theory and Huffman code. The proposed network-based approaches were found to be suitable to deal with the employed analysis for all of the tested scales. / Existem diversos aspectos das linguagens naturais e de dinâmicas relacionadas que estão sendo estudadas. No caso das línguas, algumas análises quantitativas foram feitas usando modelos estocásticos. Ademais, linguagens naturais podem ser entendidas como sistemas complexos. Para analisar linguagens naturais, existe a possibilidade de utilizar o conjunto de ferramentas que já foram desenvolvidas para analisar redes complexas, que são representadas computacionalmente. Além disso, tais ferramentas podem ser utilizadas para representar e analisar algumas dinâmicas relacionadas a redes complexas. Observe que o conhecimento está intrinsecamente relacionado à linguagem, pois a linguagem é o veículo usado para transmitir novas descobertas, sendo que a própria linguagem também é um tipo de conhecimento. Esta tese é dividida em dois tipos de análise : (i) textos e (ii) aspectos dinâmicos. Na primeira parte foram propostas representações de redes de texto em diferentes escalas de análise. A partir da análise do estilo de escrita, considerando redes de adjacência de palavras (co-ocorrência) para entender padrões locais de palavras, até uma representação mesoscópica, que é criada a partir de pedaços de texto e que representa informações do texto de acordo com o desenrolar da história. Na segunda parte, foram consideradas a estrutura e dinâmica relacionadas ao conhecimento e à linguagem. Neste caso, partiu-se da escala maior, com a qual estudamos a conectividade entre física aplicada e física teórica. A seguir, simulou-se a aquisição de conhecimento por pesquisadores em uma dinâmica multi-agente e uma máquina inteligente que resolve problemas, que é representada por uma rede. Como a menor escala considerada, foi simulada a transmissão de redes. Essa transmissão considera os dados como uma série de símbolos organizados que são obtidos a partir de uma dinâmica. Para melhorar a velocidade de transmissão, a série pode ser compactada. Para tanto, foi utilizada a teoria da informação e o código de Huffman. As propostas de abordagens baseadas em rede foram consideradas adequadas para lidar com a análise empregada, em todas as escalas testadas.

ARAÚJO, Eduardo Barbosa. Scientific Collaboration Networks from Lattes Database: Topology, Dynamics and Gender Statistics. 2016. 88 f. Tese (Doutorado em Física) - Programa de Pós-Graduação em Física, Departamento de Física, Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Edvander Pires (edvanderpires@gmail.com) on 2016-07-19T15:58:54Z No. of bitstreams: 1 2016_tese_ebaraujo.pdf: 3600069 bytes, checksum: a78e83ffda97c499e589b405da4da3c8 (MD5) / Approved for entry into archive by Edvander Pires (edvanderpires@gmail.com) on 2016-07-19T15:59:07Z (GMT) No. of bitstreams: 1 2016_tese_ebaraujo.pdf: 3600069 bytes, checksum: a78e83ffda97c499e589b405da4da3c8 (MD5) / Made available in DSpace on 2016-07-19T15:59:07Z (GMT). No. of bitstreams: 1 2016_tese_ebaraujo.pdf: 3600069 bytes, checksum: a78e83ffda97c499e589b405da4da3c8 (MD5) Previous issue date: 2016 / Understanding the dynamics of research production and collaboration may reveal better strategies for scientific careers, academic institutions and funding agencies. Here we propose the use of a large and multidisciplinary database of scientific curricula in Brazil, namely, the Lattes Platform, to study patterns of scientific production and collaboration. Detailed information about publications and researchers is available in this database. Individual curricula are submitted by the researchers themselves so that co-authorship is unambiguous. Researchers can be evaluated by scientific productivity, geographical location and field of expertise. Our results show that the collaboration network is growing exponentially for the last three decades, with a distribution of number of collaborators per researcher that approaches a power-law as the network gets older. Moreover, both the distributions of number of collaborators and production per researcher obey power-law behaviors, regardless of the geographical location or field, suggesting that the same universal mechanism might be responsible for network growth and productivity. We also show that the collaboration network under investigation displays a typical assortative mixing behavior, where teeming researchers (i.e., with high degree) tend to collaborate with others alike. Moreover, we discover that on average men prefer collaborating with other men than with women, while women are more egalitarian. This is consistently observed over all fields and essentially independent on the number of collaborators of the researcher. The solely exception is for engineering, where clearly this gender bias is less pronounced, when the number of collaborators increases. We also find that the distribution of number of collaborators follows a power-law, with a cut-off that is gender dependent. This reflects the fact that on average men produce more papers andhave more collaborators than women. We also find that both genders display the same tendency towards interdisciplinary collaborations, except for Exact and Earth Sciences, where women having many collaborators are more open to interdisciplinary research. / Compreender a dinâmica de produção e colaboração em pesquisa pode revelar melhores estratégias para carreiras científicas, instituições acadêmicas e agências de fomento. Neste trabalho nós propomos o uso de uma grande e multidisciplinar base de currículos científicos brasileira, a Plataforma Lattes, para o estudo de padrões em pesquisa científica e colaborações. Esta base de dados inclui informações detalhadas acerca de publicações e pesquisadores. Currículos individuais são enviados pelos próprios pesquisadores de forma que a identificação de coautoria não é ambígua. Pesquisadores podem ser classificados por produção científica, localização geográfica e áreas de pesquisa. Nossos resultados mostram que a rede de colaborações científicas tem crescido exponencialmente nas últimas três décadas, com a distribuição do número de colaboradores por pesquisador se aproximando de uma lei de potência à medida que a rede evolui. Além disso, ambas a distribuição do número de colaboradores e a produção por pesquisador seguem o comportamento de leis de potência, independentemente da região ou áreas, sugerindo que um mesmo mecanismo universal pode ser responsável pelo crescimento da rede e pela produtividade dos pesquisadores. Também mostramos que as redes de colaboração investigadas apresentam um típico comportamento assortativo, no qual pesquisadores de alto nível (com muitos colaboradores) tendem a colaborador com outros semelhantes. Em seguida, mostramos que homens preferem colaborar com outros homens enquanto mulheres são mais igualitárias ao estabelecer suas colaborações. Isso é consistentemente observado em todas as áreas e é essencialmente independente do número de colaborações do pesquisador. A única exceção sendo a área de Engenharia, na qual este viés é claramente menos pronunciado para pesquisadores com muitas colaborações. Também mostramos que o número de colaborações segue o comportamento de leis de potência, com um cutoff dependente do gênero. Isso se reflete no fato de que em média mulheres produzem menos artigos e têm menos colaborações que homens. Também mostramos que ambos os gêneros exibem a mesma tendência quanto a colaborações interdisciplinares, exceto em Ciências Exatas e da Terra, nas quais mulheres tendo mais colaboradores são mais propensas a pesquisas interdisciplinares.

Orientador: David Corrêa Martins Júnior / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Neurociência e Cognição, 2016. / A biologia sistêmica é um campo de pesquisa interdisciplinar que estuda as complexas interações que ocorrem entre os componentes biológicos de um organismo vivo com o objetivo de entender o seu comportamento, o qual emerge a partir dessas interações. Essas interações compõem uma rede altamente complexa, cujos interagentes podem ser de diversas naturezas. Nesse contexto, as doenças complexas são caracterizadas justamente por serem poligênicas e multifatoriais, ou seja, a gênese e o desenvolvimento dessas doenças são uma consequência da interação conjunta de diversos fatores, incluindo não apenas genes, proteínas e outras moléculas, como também fatores epigenéticos e ambientais. No entanto, diferentes métodos de priorização gênica apresentam resultados (listas de genes) com baixa convergência. Assim, a comparação desses métodos é uma questão crucial. Os objetivos principais da presente dissertação foram a realização de uma extensa revisão da literatura em relação às técnicas de priorização de genes associados a doenças complexas e a comparação de algumas dessas técnicas. Foram selecionadas duas ferramentas: o WGCNA (Weighted Gene Correlation Network Analysis) e o NERI (Network-Medicine Relative Importance), ambos métodos que baseiam-se em teoria de redes complexas e co-expressão para priorização gênica, sendo que o NERI tem o diferencial de modelar as hipóteses da Network Medicine para priorização com base na integração de dados de expressão, de redes de interação proteína-proteína (PPI) e de estudos de associação. Para comparação dos resultados, foram utilizados três bancos de dados de expressão gênica relacionados a esquizofrenia. Como previsto, devido ao diferencial de integração de dados proposto pelo NERI, tal técnica resultou em listas de genes com replicação superior à obtida pelo WGCNA para os três bancos de dados em questão. Além disso a interseção entre as listas de genes priorizados de cada metodologia foi baixa, com poucos genes sendo compartilhados pelos resultados dos dois métodos. Ambas metodologias selecionaram genes com relevância biológica relacionada a esquizofrenia, incluindo grupos de genes relacionados a atividade do sistema imune (infecções, estresse), atividade do Sistema Nervoso Central (atividade sináptica, crescimento axonal) e também de embriogênese. Baseando-se nesses resultados, conclui-se que a análise de redes e a integração de dados biológicos são fundamentais para uma ferramenta apresentar resultados promissores, sobretudo no âmbito da descoberta de novos genes e suas redes de interação biológica que seriam possivelmente desconhecidas se fosse realizada apenas a análise individual de cada tipo de dado biológico disponível. / Systems Biology is an interdisciplinary research field which studies the complex interactions that occur between biological compounds of a living organism in order to understand their behavior, which emerges from these interactions. Such interactions compose a highly complex network, whose elements can be of several types. In this context, complex diseases are characterized precisely by being of polygenic and multifactorial nature, i.e., the genesis and development of these diseases are a result of the joint interaction of several factors, including not only genes, proteins and other molecules, but also epigenetic and environmental factors. However, many methods for gene prioritization present results (list of genes) with small convergence. Thus, the comparison involving those methods is a crucial issue. The main objectives of this master thesis was to perform an extensive literature review related to gene prioritization techniques associated to complex diseases and the comparison of part of these techniques. Two techniques were selected: WGCNA (Weighted Gene Correlation Network Analysis) and NERI (Network-Medicine Relative Importance), both methods based on complex networks theory and co-expression for gene prioritization, but NERI having the differential of modeling the Network Medicine hypotheses for prioritization based on integration of expression, protein-protein interaction (PPI) network and association studies. For comparison of the results, three gene expression databases related to schizophrenia were adopted. As predicted, due to the data integration proposed by NERI, such technique resulted in genes lists with superior replication for the three databases mentioned. Additionally, the intersection between the results of the genes lists prioritized by the two methodologies was small, with few genes being found in both lists. Both methods selected biologically relevant to schizophrenia, including groups of genes related to imune system activity (infections, stress), Central Nervous System activity (synaptic activity, axonal growth) and embryogenesis. From these results, it follows that network analysis and biological data integration are fundamental for a gene prioritization method to present promising results, mainly for discovery of new genes and their biological interaction networks that would possibly be unknown if only an individual analysis of each biological data available were performed.

Made available in DSpace on 2014-12-17T15:14:51Z (GMT). No. of bitstreams: 1 AderaldoILA.pdf: 552788 bytes, checksum: cd003388ac958c41a47622d93e45969e (MD5) Previous issue date: 2010-03-12 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / We present a nestedness index that measures the nestedness pattern of bipartite networks, a problem that arises in theoretical ecology. Our measure is derived using the sum of distances of the occupied elements in the adjacency matrix of the network. This index quantifies directly the deviation of a given matrix from the nested pattern. In the most simple case the distance of the matrix element ai,j is di,j = i+j, the Manhattan distance. A generic distance is obtained as di,j = (i? + j?)1/?. The nestedness ?ndex is defined by = 1 − where is the temperature of the matrix. We construct the temperature index using two benchmarks: the distance of the complete nested matrix that corresponds to zero temperature and the distance of the average random matrix that is defined as temperature one. We discuss an important feature of the problem: matrix occupancy. We address this question using a metric index ? that adjusts for matrix occupancy / Apresentamos um ?ndice de aninhamento que mede o padr?o de aninhamento de redes bipartidas, um problema que surge em ecologia te?rica. Nossa medida ? constru?da atrav?s da soma das dist?ncias dos elementos ocupados na matriz de adjac?ncia da rede. Este ?ndice quantifica diretamente o desvio de uma dada matriz em rela??o a um padr?o aninhado. No caso mais simples a dist?ncia do elemento ai,j da matriz ? di,j = i + j, a dist?ncia de Manhattan. Uma dist?ncia gen?rica ? obtida atrav?s de di,j = (i? + j?)1/?. O ?ndice de aninhamento ? definido por = 1 − , onde ? a temperatura da matriz. Constru?mos o ?ndice de temperatura utilizando dois padr?es de refer?ncia: a dist?ncia da matriz completamente aninhada, que corresponde `a temperatura zero, e a dist?ncia da matriz aleat?ria m?dia, definida de modo que sua temperatura seja um. Discutimos uma importante caracter?stica do problema, a ocupa??o da matriz. Abordamos esta quest?o introduzindo o ?ndice m?trico ? que permite o ajuste de matrizes com diferentes ocupa??es

Made available in DSpace on 2014-12-17T15:15:01Z (GMT). No. of bitstreams: 1 ThiagoCCN_DISSERT.pdf: 2332508 bytes, checksum: bbc84148d8aa1acc5070a5a68ca8b3b6 (MD5) Previous issue date: 2012-06-29 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Following the study of Andrade et al. (2009) on regular square lattices, here we investigate the problem of optimal path cracks (OPC) in Complex Networks. In this problem we associate to each site a determined energy. The optimum path is defined as the one among all possible paths that crosses the system which has the minimum cost, namely the sum of the energies along the path. Once the optimum path is determined, at each step, one blocks its site with highest energy, and then a new optimal path is calculated. This procedure is repeated until there is a set of blocked sites forming a macroscopic fracture which connects the opposite sides of the system. The method is applied to a lattice of size L and the density of removed sites is computed. As observed in the work by Andrade et al. (2009), the fractured system studied here also presents different behaviors depending on the level of disorder, namely weak, moderated and strong disorder intensities. In the regime of weak and moderated disorder, while the density of removed sites in the system does not depend of the size L in the case of regular lattices, in the regime of high disorder the density becomes substantially dependent on L. We did the same type of study for Complex Networks. In this case, each new site is connected with m previous ones. As in the previous work, we observe that the density of removed sites presents a similar behavior. Moreover, a new result is obtained, i.e., we analyze the dependency of the disorder with the attachment parameter m / Seguindo a linha do trabalho de Andrade e colaboradores (2009) em redes regulares, n?s investigamos o problema da fratura atrav?s do caminho ?timo (optimal path cracks -OPC) em Redes Complexas. Neste problema n?s associamos para cada s?tio uma determinada energia. O caminho ?timo ? definido como aquele, dentre todos os poss?veis, que atravessa o sistema e tem o menor custo, ou seja, a menor soma das energias ao longo do caminho. Uma vez que o caminho ?timo ? determinado, em cada passo, n?s bloqueamos o s?tio com maior energia e a partir de ent?o um novo caminho ?timo ? calculado. Este procedimento ? repetido at? que existe um conjunto de s?tios bloqueados que forma uma fratura macrosc?pica a qual conecta lados opostos do sistema. O m?todo ? aplicado numa rede de lado L e a densidade de s?tios removidos ? computada. Como observado no trabalho de Andrade e colaboradores, o sistema fraturado que n?s estudamos tamb?m apresenta diferentes comportamentos dependendo do n?vel da desordem, que pode ser fraca, moderada ou forte. No regime de desordem fraca e moderada, a densidade de s?tios removidos no sistema n?o depende do tamanho L no caso de redes regulares, enquanto no regime de desordem forte a densidade se torna substancialmente dependente de L. N?s fizemos o mesmo tipo de estudo para Redes Complexas. Numa rede complexa caso, cada novo s?tio ? conectado a m s?tios que j? est?o presentes na rede. Como no trabalho anterior, n?s observamos que a densidade de s?tios removidos apresenta um comportamento similar. Al?m disso, um novo resultado ? obtido, isto ?, n?s analisamos a depend?ncia da desordem com o par?metro de liga??o m