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.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-04-24T14:37:15Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese_bnm_OK.pdf: 5126585 bytes, checksum: 5ccba23295950094b489a2df805e0815 (MD5) / Made available in DSpace on 2017-04-24T14:37:15Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese_bnm_OK.pdf: 5126585 bytes, checksum: 5ccba23295950094b489a2df805e0815 (MD5) Previous issue date: 2016-09-09 / O crescente uso de redes sociais online tem feito com que usuários compartilhem, também, informações detalhadas a respeito dos locais que os mesmos frequentam, criando uma ligação entre o mundo físico (o movimento destes usuários no globo) e o mundo virtual (o que eles expressam sobre esses movimentos nas redes). O “check-in” é a funcionalidade responsável pelo compartilhamento da localização. Em uma rede social com essa funcionalidade, qualquer usuário pode publicar o local em que o mesmo está em determinado instante de tempo. Esta tese apresenta novas abordagens de análise de redes sociais online considerando as dimensões social, espacial e temporal que são inerentes à publicação de check-ins de usuários. As informações sociais, espaciais e temporais são definidas sob a perspectiva de encontros de usuários, sendo este o objeto de estudo dessa tese. Encontros ocorrem quando duas pessoas (dimensão social), estão em algum local (dimensão espacial), em determinado instante de tempo (dimensão temporal) e decidem publicar esse encontro através de check-ins. Além de apresentar um algoritmo para detecção de encontros, é definido um modelo para representação desses encontros. Este modelo é chamado de SiST (do inglês, SocIal, Spatial and Temporal) e modela encontros por meio de redes complexas. Para validar o modelo proposto, foram utilizados dados reais de redes sociais online. Com esses dados, os encontros foram detectados e analisados sob diferentes perspectivas com o objetivo de investigar a existência de alguma lei que governe a publicação dos mesmos, bem como para identificar padrões relativos a sua ocorrência, como padrões temporais, por exemplo. Além disso, as redes construídas a partir do modelo SiST também foram analisadas em termos de suas propriedades estruturais e topológicas. Por meio de redes SiST também foram estudados padrões de movimentação de usuários, como situações em que usuários se movimentam em grupo no globo ou situações em que um usuário é seguido por outros. / The growing use of online social networks has caused users to share detailed information about the places they visit, resulting on a clear connection between the physical world (i.e. the movement of these users on the globe) and the virtual world (which they express about these movements in the social network). The functionality responsible for sharing location by users is named as “check in”. In a social network with this feature, any user can publish their visited places. This thesis presents new approaches for online social networks analysis considering the social, spatial and temporal dimensions that are implicit in the publication of users check-ins. Social, spatial and temporal information is defined from the perspective of “user encounters”, which is the study object of this thesis. Users encounters occur when two people (social dimension) are somewhere (spatial dimension) in a given time (temporal dimension) and decide to publish this meeting through check-ins. In addition to the algorithm presented for encounters detection, we also defined a model for representation of these encounters. This model is called as SiST (SocIal, Spatial and Temporal). The SiST model basically represent encounters by a graph structure. To validate the proposed approach, we used real data from online social networks. With these data the users encounters were detected and analyzed from different perspectives aiming at investigating the existence of any law governing the publication of encounters and also to identify patterns related to its occurrence, like temporal patterns, for example. Furthermore, the graphs built from SiST model were also analyzed in terms of its structural and topological properties. Through the SiST networks the users movements were studied as well, like in situations in which users move in group or situations where users are followed by other users.

Submitted by (edna.saturno@ufrpe.br) on 2017-03-30T14:56:43Z No. of bitstreams: 1 RohgiToshio Meneses Chikushi.pdf: 6493487 bytes, checksum: b95c0c692d050783c78c20f7a212f0e6 (MD5) / Made available in DSpace on 2017-03-30T14:56:43Z (GMT). No. of bitstreams: 1 RohgiToshio Meneses Chikushi.pdf: 6493487 bytes, checksum: b95c0c692d050783c78c20f7a212f0e6 (MD5) Previous issue date: 2014-08-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The electroencephalogram (EEG) is still an important tool in the diagnosis of neurodiseases. As recording technique offers an excellent temporal resolution, instantly capturing brain electrical activity. Recent studies suggest that non-linear dynamic time series as EEG can be transformed into complex networks by the methods of visibility graph and the recurrence network. The builded complex network allows many parameters or network metrics to characterize normal and epleptics. In this work, we transform EEG signals to complex networks and identify the metrics to find statistical diferences between normal and epleptical groups. We show that exist significant statistical differences in the network metrics from the normals and epileptics conditions. We conclude that the transformation of the EEG signal in complex networks provide a helpful tool to diagnostic the brain states. / O eletroencefalograma (EEG) ainda é uma ferramenta importante no diagnóstico de desordens neurológicas. Como técnica de registro, oferece uma excelente resolução temporal, capturando instantaneamente a atividade cerebral. Estudos recentes em dinâmica não linear sugerem que séries temporais como o EEG podem ser transformadas em redes complexas por meio de mapeamentos como o método de visibilidade e o de recorrência. Essas redes, em analogia às rede neuronais, representam as características de complexidade dinâmica do sistema nervoso. Neste trabalho, transformamos sinais de EEG em redes complexas derivadas da reconstrução dos espaços de fase, com base no conceito de recorrência. A aplicação de redes complexas na análise não linear da dinâmica da atividade cerebral, possibilitou diferenciar estados normais e epilépticos por meio da comparação das medidas topológicas dessas redes. Identificamos diferenças significativas ao compararmos os registros de EEG em condições normais e epilépticas usando as métricas das redes e concluímos que a transformação do EEG em redes complexas fornece um grande número de parâmetros úteis para caracterização e possível diagnóstico dos estados do comportamento cerebral normal e epiléptico.

Orientador: Marcus Aloizio Martinez de Aguiar / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Fisica Gleb Wataghin / Made available in DSpace on 2018-08-10T18:23:05Z (GMT). No. of bitstreams: 1 Chinellato_DavidDobrigkeit_M.pdf: 15300810 bytes, checksum: 36fdea424f1c7f83a5f50742e82465f8 (MD5) Previous issue date: 2007 / Resumo: Nesta tese, estudamos as propriedades estatísticas de processos dinâmicos de influência em redes complexas sujeitas a perturbações externas. Consideramos redes cujos nós admitem dois estados internos, digamos 0 e 1. Os estados internos se alteram de acordo com os estados dos nós vizinhos. Supomos que há N1 nós com estado interno fixo em 1, N0 elementos com estado interno fixo em 0 e outros N elementos com estado interno livre. Os nós com estado interno ½xo podem ser interpretados como perturbações externas à subrede de N elementos livres. Este sistema é uma generalização do modelo do eleitor [25] e pode descrever diversas situações interessantes, indo de sistemas sociais [26] para a física e a genética. Neste trabalho, calcularemos analiticamente a evolução de um sistema de rede totalmente conectada, obtendo expressões para as distribuições de equilíbrio de uma rede qualquer e também de todas as probabilidades de transição. Em seguida, generalizamos os resultados para o caso em que N0 e N1 são menores do que 1, representando um acoplamento fraco do sistema com um reservatório externo. Mostramos que os resultados exatos são excelentes aproximações para várias outras redes, incluindo redes aleatórias, reticuladas, livres de escala, estrela e mundo pequeno, e estudamos a dinâmica destas outras redes numericamente. Finalmente, demonstramos que, se os dois parâmetros da solução para redes totalmente conectadas, N0 e N1, forem alterados para valores efetivos para cada tipo de rede específico, o nosso resultado analítico explica satisfatoriamente todas as dinâmicas e estados assintóticos de outras topologias. O nosso modelo é portanto bastante geral, se aplicado cuidadosamente / Abstract: We study the statistical properties of in²uence networks subjected to external perturbations. We consider networks whose nodes have internal states that can assume the values 0 or 1. The internal states can change depending on the state of the neighboring nodes. We let N1 nodes be frozen in the state 1, N0 be frozen in the state 0 and the remaining N nodes be free to change their internal state. The frozen nodes are interpreted as external perturbations to the sub-network of N free nodes. The system is a generalization of the voter model [25] and can describe a variety of interesting situations, from social systems [26] to physics and genetics. In this thesis, we calculate analytically the equilibrium distribution and the transition probabilities between any two states for arbitrary values of N, N1 and N0 for the case of fully connected networks. Next we generalize the results for the case where N0 and N1 are smaller than 1, representing the weak coupling of the network to an external reservoir. We show that our exact results are excellent approximations for several other topologies, including random, regular lattices, scale-free, star and small world networks, and study the dynamics of these other networks numerically. We then proceed to show that, by appropriately tuning the two parameters from the solution from fully connected networks, N0and N1, to eÿective values when dealing with other, more sophisticated network types, we can easily explain their asymptotic network behaviour. Our model is therefore quite general in applicability, if used consciously / Mestrado / Física Estatistica e Termodinamica / Mestre em Física

O grande volume de dados armazenados em meio digital dificulta a anáalise e extração de informações por um ser humano sem que seja utilizada alguma ferramenta computacional inteligente. A área de Aprendizado de Máquina (AM) estuda e desenvolve algoritmos para o processamento e obtenção automática de conhecimento em dados digitais. Tradicionalmente, os algoritmos de AM modelam os dados analisados com base na abordagem proposicional; entretanto, recentemente com a disponibilidade de conjuntos de dados relacionais novas abordagens têm sido estudadas, como a modelagem utilizando redes complexas. Redes complexas é uma área de pesquisa recente e ativa que têm atraíido a atenção de pesquisadores e tem sido aplicada em diversos domínios. Mais especificamente, o estudo de detecção de comunidades em redes complexas é o tema principal deste trabalho. Detectar comunidades consiste em buscar grupos de vértices densamente conectados entre si em uma rede. Detectar a melhor divisão em comunidades de uma rede é um problema NP-completo, o que requer que o desenvolvimento de soluções viáveis baseiem-se em heurísticas como, por exemplo, medidas de qualidade. Newman prop^os a medida de modularidade Q que tem se mostrado eficiiente na análise de comunidades em redes. Este trabalho apresenta o Algoritmo Multinível de Otimização de Modularidade (AMOM) que é baseado a na otimização da medida de modularidade e integrado na estratégia multinível. A estratégia multinível é composta de três fases: (i) sucessivas compactações da rede inicial com base em contrações de arestas e fus~oes de vértices, (ii) particionamento da rede reduzida utilizando Algoritmo de Otimização de Modularidade (AOM) modificado, e (iii) sucessivas descompactações das redes intermediárias até que se retorne a rede inicial. O principal atrativo da estratégia é viabilizar a utilização de algoritmos custosos no particionamento do grafo compactado, uma vez que neste grafo a quantidade de vértices e arestas é uma fração reduzida em relação ao grafo inicial. O trabalho também propõe dois novos métodos para refinamento dos particionamentos durante a fase de uncoasening. A fiim de avaliar a escalabilidade e eficiiência da metodologia proposta foram realizados experimentos empíricos em redes consideradas benchmark. Os resultados demonstram um significativo ganho de desempenho, mantendo bons resultados qualitativos / Human based analysis of large amount of data is a hard task when no intelligent computer aid is provided. In this context, Machine Learning (ML) algorithms are aimed at automatically processing and obtaining knowledge from data. In general, ML algorithms use a propositional representation of data such as an attribute-value table. However, this model is not suitable for relational information modeling, which can be better accomplished using graphs or networks. In this context, complex networks have been call attention of scientific community recently and many applications in different domains have been developed. In special, one of complex networks research trends is the community detection field which is the main focus of this work. Community detection is the problem of finding dense and disjoint connected groups of vertices in a network. The problem is a well know NP-complete task which requires heuristics approaches, like quality measures, to be addressed. Newman introduced a specific quality measure called modularity that proved to be useful for analysis communities in networks. This work presents a new algorithm, called Multilevel Modularity Optimization Algorithm, based on modularity measure optimization integrated in a multilevel graph partitioning strategy. The multilevel graph partitioning scheme consists of three phases: (i) reduction of the size (coarsen) of original graph by collapsing vertices and edges, (ii) partitioning the coarsened graph, and (iii) uncoarsen it to construct a partition for the original graph. The rationale behind this strategy is to apply a computationally expensive method in a coarsened graph, i.e., with a significantly reduced number of vertices and edges. In addition, it is proposed two new methods that uses modularity and clustering coefficient for partition refinement. Empirical evaluation on benchmarks networks using this approach demonstrate a significant speed up gain compared to the original modularity-based algorithm, keeping a good quality clusters partitioning

Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-01-11T14:23:04Z No. of bitstreams: 1 weineresmeriobatistadeoliveira.pdf: 1837068 bytes, checksum: 00992cd2cbc30abda6ffe4b76d1c6941 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-01-23T13:41:57Z (GMT) No. of bitstreams: 1 weineresmeriobatistadeoliveira.pdf: 1837068 bytes, checksum: 00992cd2cbc30abda6ffe4b76d1c6941 (MD5) / Made available in DSpace on 2018-01-23T13:41:57Z (GMT). No. of bitstreams: 1 weineresmeriobatistadeoliveira.pdf: 1837068 bytes, checksum: 00992cd2cbc30abda6ffe4b76d1c6941 (MD5) Previous issue date: 2017-09-01 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A proveniência é reconhecida hoje como um desafio central para estabelecer confiabilidade e prover segurança em sistemas computacionais. Em workflows científicos, a proveniência é considerada essencial para apoiar a reprodutibilidade dos experimentos, a interpretação dos resultados e o diagnóstico de problemas. Estes benefícios podem também ser utilizados em outros contextos, como, por exemplo, em processos de software. No entanto, para sua melhor compreensão e utilização, são necessários mecanismos eficientes e amigáveis. Pesquisas em visualização de software, ontologias e redes complexas podem ajudar neste processo, gerando novo conhecimento sobre os dados e informações estratégicas para tomada de decisão. Esta dissertação apresenta um framework chamado Visionary, para auxiliar na compreensão e uso dos dados de proveniência através de técnicas de visualização de software, ontologias e análise de redes complexas. O framework captura os dados de proveniência e gera novas informações usando ontologias e análise do grafo de proveniência. A visualização apresenta e destaca as inferências e os resultados obtidos com a análise. O Visionary é um framework livre de contexto que pode ser adaptado para qualquer sistema que utiliza o modelo PROV de proveniência. Com o objetivo de avaliar a proposta, foi realizado um estudo experimental que encontrou indícios que o framework auxilia na compreensão e análise dos dados de proveniência, dando suporte à tomada de decisão. / Provenance is recognized today as a central challenge to establish reliability and pro-vide security in computational systems. In scientific workflows, provenance is considered essential to support the reproducibility of experiments, interpretation of results and diagnosis of problems. We consider that these benefits can be used in new contexts, like software process. However, for a better understanding and use, efficient and friendly mechanisms are needed. Software visualization, ontology, and complex networks can help in this process by generating new data insights and strategic information for decision making. This dissertation presents a framework named Visionary, to assist in the understanding and use of provenance data through software visualization techniques, ontologies and analysis of complex networks. The framework captures the provenance data and generates new information using ontologies and analysis of provenance graph. The visualization presents and highlights the inferences and the results obtained with the analysis. Visionary is a context-free framework that can be adapted to any system that uses the PROV provenance model. In order to evaluate the proposal, an experimental study was carried out, which found indications that the framework assists in the understanding and analysis of provenance data, supporting decision making.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Este dissertaÃÃo foi dividida em duas partes, na primeira parte nÃs propomos um modelo de crescimento competitivo de gregados em redes complexas para simular a propagaÃÃo de idÃias ou opiniÃes em comunidades. Investigamos como as distribuiÃÃes de tamanhos de agregados variam com a topologia de construÃÃo da rede e com o nÃmero de sementes aleatoriamente dispersas na estrutura. Para tal, analisamos redes do tipo de Erdos-RÃnyi, redes de contato preferencial e a chamada rede Apoloniana. Esta Ãltima apresenta distribuiÃÃes de tamanho de agregado em forma de uma lei de potÃncia com um expoente aproximadamente 1. Resultados similares sÃo observados com as distribuiÃÃes obtidas para as fraÃÃes de votos por candidato Ãs eleiÃÃes proporcionais para deputados no Brasil. Na segunda parte, analisamos o comportamento temporal da atividade neural em redes com caracterÃsticas de mundo pequeno e em redes construÃdas segundo o modelo do contato preferencial. Nesta primeira topologia, estudamos como a sÃrie temporal se comporta com a variaÃÃo do alcance das conexÃes. Em ambas as topologias, observamos a formaÃÃo de perÃodos e investigamos como estes variam com o tamanho da rede. / The process by which news trends and ideas propagate in social communities can have a profound impact in the life of individuals. To understand thi process, we introduce a competitive cluster growth model in complex networks. In our model, each cluster represents the set of individuals with a certain opinion or preference. We investigate how the cluster size distribution depends on the topology of the network and how it is affected by the number of initial seeds dispersed in the structure. We study our model using different network models, namely, the Erdos-Renyi geometry, the preferential attachment model, and the so-called Apollonian network. This last complex geometry displays a cluster size distribution that follows a power-law with an exponent 1.0. Similar results have been obtained for the distributions of number of votes per candidate in the proportional elections for federal representation in Brazil. In the second part of this work, we investigate the temporal behavior of neural networks with small world topology and in networks built according to the preferential attachment model. In the first case we study the effect of the range of connections on the behavior of the time series. In both topologies, we detect the existence of cycles and investigate how their periods depend on the size of the system.

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.

A capacidade de um sistema sensorial detectar estímulos eficientemente é tradicionalmente dimensionada pela faixa dinâmica, que é simplesmente uma medida da extensão do intervalo de intensidades de estímulo para as quais a rede é suficientemente sensível. Muitas vezes, sistemas biológicos exibem largas faixas dinâmicas, que abrangem diversas ordens de magnitude. A compreensão desse fenômeno não é trivial, haja vista que todos os neurônios apresentam janelas de sensibilidade muito estreitas. Tentativas de explicação baseadas em argumentos de recrutamento sequencial dos neurônios sensoriais, com efeitos essencialmente aditivos, simplesmente não são realísticas, haja vista que seria preciso que os limiares de ativação das unidades também apresentassem um escalonamento por várias ordens de magnitude, para cobrir a faixa dinâmica empiricamente observada em nível macroscópico. Notavelmente, o modelo Kinouchi-Copelli (KC), que carrega o nome de seus idealizadores, mostrou que aquele comportamento pode ser um efeito coletivo (não aditivo) do conjunto de neurônios sensoriais. O modelo KC é uma rede de unidades excitáveis com dinâmicas estocásticas e acoplados segundo uma topologia de grafo aleatório. Kinouchi e Copelli mostraram que a taxa espontânea de disparo dos neurônios (ou atividade média) sinaliza uma transição de fase fora do equilíbrio do tipo ordem-desordem, e que exatamente no ponto crítico desta transição (em termos de um parâmetro ligado às características estruturais da rede) a sensibilidade a estímulos externos é máxima, ou seja, a faixa dinâmica exibe uma otimização crítica. Neste trabalho, investigamos como o ponto crítico depende da topologia, utilizando os modelos mais comuns das chamadas redes complexas. Além disso, estudamos computacionalmente os padrões de atividade (avalanches neuronais) exibidos pelo modelo, com especial atenção às mudanças qualitativas de comportamento devido às mudanças de topologia. Comentaremos também a relação desses resultados com experimentos recentes de monitoramento de dinâmicas neurais. / The capacity of a sensory system in efficiently detecting stimuli is usually given by the dynamic range, a simple measure of the range of stimulus intensity over which the network is sensible enough. Many times biological systems exhibit large dynamic ranges, covering many orders of magnitude. There is no easy explanation for that, since individual neurons present very short dynamic ranges isolatedly. Arguments based on sequential recruitment are doomed to failure since the corresponding arrangement of the limiar thresholds of the units over many orders of magnitude is unrealistic. Notably the so-called Kinouchi-Copelli (KC) model strongly suggested that large dynamic range should be a collective effect of the sensory neurons. The KC model is a network of stochastic excitable elements coupled as a random graph. KC showed the spontaneous activity of the network signals an order-disorder nonequilibrium phase transition and that the dynamic range exhibits an optimum precisely at the critical point (in terms of a control parameter related to structural properties of the network). In this work, we investigate how the critical point depends on the topology, considering the alternatives among the standard complex networks. We also study the burts of activity (neuronal avalanches) exhibited by the model, focusing on the qualitative changes due to alternative topologies. Finally we comment on possible connections among our results and recent observations of neural dynamics.

Due to a large amount of textual information available on the Internet, the task of automatic document summarization has gained significant importance. Document summarization became important because its focus is the development of techniques aimed at finding relevant and concise content in large volumes of information without changing its original meaning. The purpose of this Masters work is to use network theory concepts for extractive document summarization for both Single Document Summarization (SDS) and Multi-Document Summarization (MDS). In this work, the documents are modeled as networks, where sentences are represented as nodes with the aim of extracting the most relevant sentences through the use of ranking algorithms. The edges between nodes are established in different ways. The first approach for edge calculation is based on the number of common nouns between two sentences (network nodes). Another approach to creating an edge is through the similarity between two sentences. In order to calculate the similarity of such sentences, we used the vector space model based on Tf-Idf weighting and word embeddings for the vector representation of the sentences. Also, we make a distinction between edges linking sentences from different documents (inter-layer) and those connecting sentences from the same document (intra-layer) by using multilayer network models for the Multi-Document Summarization task. In this approach, each network layer represents a document of the document set that will be summarized. In addition to the measurements typically used in complex networks such as node degree, clustering coefficient, shortest paths, etc., the network characterization also is guided by dynamical measurements of complex networks, including symmetry, accessibility and absorption time. The generated summaries were evaluated by using different corpus for both Portuguese and English language. The ROUGE-1 metric was used for the validation of generated summaries. The results suggest that simpler models like Noun and Tf-Idf based networks achieved a better performance in comparison to those models based on word embeddings. Also, excellent results were achieved by using the multilayered representation of documents for MDS. Finally, we concluded that several measurements could be used to improve the characterization of networks for the summarization task. / Devido à grande quantidade de informações textuais disponíveis na Internet, a tarefa de sumarização automática de documentos ganhou importância significativa. A sumarização de documentos tornou-se importante porque seu foco é o desenvolvimento de técnicas destinadas a encontrar conteúdo relevante e conciso em grandes volumes de informação sem alterar seu significado original. O objetivo deste trabalho de Mestrado é usar os conceitos da teoria de grafos para o resumo extrativo de documentos para Sumarização mono-documento (SDS) e Sumarização multi-documento (MDS). Neste trabalho, os documentos são modelados como redes, onde as sentenças são representadas como nós com o objetivo de extrair as sentenças mais relevantes através do uso de algoritmos de ranqueamento. As arestas entre nós são estabelecidas de maneiras diferentes. A primeira abordagem para o cálculo de arestas é baseada no número de substantivos comuns entre duas sentenças (nós da rede). Outra abordagem para criar uma aresta é através da similaridade entre duas sentenças. Para calcular a similaridade de tais sentenças, foi usado o modelo de espaço vetorial baseado na ponderação Tf-Idf e word embeddings para a representação vetorial das sentenças. Além disso, fazemos uma distinção entre as arestas que vinculam sentenças de diferentes documentos (inter-camada) e aquelas que conectam sentenças do mesmo documento (intra-camada) usando modelos de redes multicamada para a tarefa de Sumarização multi-documento. Nesta abordagem, cada camada da rede representa um documento do conjunto de documentos que será resumido. Além das medições tipicamente usadas em redes complexas como grau dos nós, coeficiente de agrupamento, caminhos mais curtos, etc., a caracterização da rede também é guiada por medições dinâmicas de redes complexas, incluindo simetria, acessibilidade e tempo de absorção. Os resumos gerados foram avaliados usando diferentes corpus para Português e Inglês. A métrica ROUGE-1 foi usada para a validação dos resumos gerados. Os resultados sugerem que os modelos mais simples, como redes baseadas em Noun e Tf-Idf, obtiveram um melhor desempenho em comparação com os modelos baseados em word embeddings. Além disso, excelentes resultados foram obtidos usando a representação de redes multicamada de documentos para MDS. Finalmente, concluímos que várias medidas podem ser usadas para melhorar a caracterização de redes para a tarefa de sumarização.