Submitted by admin tede (tede@pucgoias.edu.br) on 2017-08-10T18:29:13Z No. of bitstreams: 1 REGINA DUARTE RIBEIRO MELO.pdf: 4787890 bytes, checksum: f1e4799a54a2be2090102e3ea15abdda (MD5) / Made available in DSpace on 2017-08-10T18:29:13Z (GMT). No. of bitstreams: 1 REGINA DUARTE RIBEIRO MELO.pdf: 4787890 bytes, checksum: f1e4799a54a2be2090102e3ea15abdda (MD5) Previous issue date: 2017-04-06 / This paper presents the application of Complex Networks Theory and Analysis of Social Networks (ARS) to evaluate the scientific production of the Academic Postgraduate Programs in Production Engineering. The data were collected in the Sucupira Platform (PS) for the period from 2013 to 2015, part of the current evaluation quadrennium (2013 to 2016). The database was arranged in Excel spreadsheets with the variables acquired from the PS. The data were transformed from the extension xlsx to csv, when compatibilizing them for use of software R, version 3.1.1 and environment RStudio 0.99.891. The developed scripts used the Igraph, Network, Bipartite and Ggraph packages that were suitable for bipartite network analysis. The study of the demographic patterns of collaboration between programs indicates that these are stronger among programs from the same region. The production patterns of the CAPES 3 programs indicated the production of the 1437 articles in the period, most of which are from strata B5 and lower production in upper strata (A1, A2 and B1), in which 5002 employees participated, Of external participants. When analyzing the standards of all the programs, it was noticed that the CAPES concepts of the programs obtained in the triennium 2010-2012 did not imply in the higher productions in the upper strata. The most wanted journals for publications in A1 (Journal of Cleaner Production, with 18.51%), for A2 (Energy Policy with 8.11%) and B1 (International Journal, Advanced Manufacturing Technology with 6.44%). The ARS corroborated in the exploration of the data in bipartite network evidencing its potential of analysis and visualization. / Este trabalho apresenta a aplicação da Teoria de Redes Complexas e Análise de Redes Sociais (ARS) para avaliação da produção científica dos Programas de Pós-graduação Acadêmicos em Engenharia de Produção. Os dados foram coletados na Plataforma Sucupira (PS) para o período de 2013 a 2015, parte do quadriênio de avaliação atual (2013 a 2016). A base de dados foi disposta em planilhas do Excel com as variáveis adquiridas da PS. Os dados foram transformados da extensão xlsx para csv, ao compatibilizá-los para utilização do software R, versão 3.1.1 e ambiente RStudio 0.99.891. Os scripts desenvolvidos utilizaram os pacotes Igraph, Network, Bipartite e Ggraph que foram adequados para as análises das redes bipartidas. O estudo dos padrões demográficos de colaboração entre os programas aponta que estes são mais fortes entre programas de mesma região. Os padrões de produção dos programas conceito CAPES 3 indicaram a produção dos 1437 artigos no período, em que a maioria são do estrato B5 e menor produção em estratos superiores (A1, A2 e B1), nos quais participaram 5002 colaboradores, que são em maioria de participantes externos. Quando analisados os padrões de todos os programas notou-se que os conceitos CAPES dos programas obtidos no triênio 2010-2012 não implicaram nas maiores produções nos estratos superiores. Os periódicos mais procurados para publicações em A1 (Journal of Cleaner Production, com 18,51%), para A2 (Energy Policy, com 8,11%) e B1 (International Journal, Advanced Manufacturing Technology, com 6,44%). A ARS corroborou na exploração dos dados em rede bipartida evidenciando seu potencial de análise e visualização.

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.

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.

Les méthodes d'apprentissage semi-supervisé constituent une catégorie de méthodes d'apprentissage automatique qui combinent points étiquetés et données non labellisées pour construire le classifieur. Dans la première partie de la thèse, nous proposons un formalisme d'optimisation général, commun à l'ensemble des méthodes d'apprentissage semi-supervisé et en particulier aux Laplacien Standard, Laplacien Normalisé et PageRank. En utilisant la théorie des marches aléatoires, nous caractérisons les différences majeures entre méthodes d'apprentissage semi-supervisé et nous définissons des critères opérationnels pour guider le choix des paramètres du noyau ainsi que des points étiquetés. Nous illustrons la portée des résultats théoriques obtenus sur des données synthétiques et réelles, comme par exemple la classification par le contenu et par utilisateurs des systèmes pair-à-pair. Cette application montre de façon édifiante que la famille de méthodes proposée passe parfaitement à l’échelle. Les algorithmes développés dans la deuxième partie de la thèse peuvent être appliquées pour la sélection des données étiquetées, mais également aux autres applications dans la recherche d'information. Plus précisément, nous proposons des algorithmes randomisés pour la détection rapide des nœuds de grands degrés et des nœuds avec de grandes valeurs de PageRank personnalisé. A la fin de la thèse, nous proposons une nouvelle mesure de centralité, qui généralise à la fois la centralité d'intermédiarité et PageRank. Cette nouvelle mesure est particulièrement bien adaptée pour la détection de la vulnérabilité de réseau. / Semi-supervised learning methods constitute a category of machine learning methods which use labelled points together with unlabeled data to tune the classifier. The main idea of the semi-supervised methods is based on an assumption that the classification function should change smoothly over a similarity graph. In the first part of the thesis, we propose a generalized optimization approach for the graph-based semi-supervised learning which implies as particular cases the Standard Laplacian, Normalized Laplacian and PageRank based methods. Using random walk theory, we provide insights about the differences among the graph-based semi-supervised learning methods and give recommendations for the choice of the kernel parameters and labelled points. We have illustrated all theoretical results with the help of synthetic and real data. As one example of real data we consider classification of content and users in P2P systems. This application demonstrates that the proposed family of methods scales very well with the volume of data. The second part of the thesis is devoted to quick detection of network central nodes. The algorithms developed in the second part of the thesis can be applied for the selections of quality labelled data but also have other applications in information retrieval. Specifically, we propose random walk based algorithms for quick detection of large degree nodes and nodes with large values of Personalized PageRank. Finally, in the end of the thesis we suggest new centrality measure, which generalizes both the current flow betweenness centrality and PageRank. This new measure is particularly well suited for detection of network vulnerability.

Le programme de réplication d’environ la moitié du génome des mammifères est caractérisé par des U/N-domaines de réplication de l’ordre du méga-base en taille. Ces domaines sont bordés par des origines de réplication maitresses (MaOris) correspondantes à des régions (~200 kb) de chromatine ouverte favorables à l’initiation précoce de la réplication et de la transcription. Grâce au développement récent de technologies à haut débit de capture de conformations des chromosomes (Hi-C), des matrices de fréquences de co-localisation 3D entre toutes les paires de loci sont désormais déterminées expérimentalement. Il est apparu que les U/N-domaines sont reliés à l’organisation du génome en unités structurelles. Dans cette thèse, nous avons effectué une analyse combinée de données de Hi-C de lignées cellulaires humaines et de profils de temps de réplication pour explorer davantage les relations structure/fonction dans le noyau. Cela nous a conduit à décrire de nouveaux domaines de réplication de grande tailles (>3 Mb) : les split-U-domaines aussi bordés par des MaOris; à démontrer que la vague de réplication initiée aux MaOris ne dépend que du temps pendant la phase S et de montrer que le repliement de la chromatine est compatible avec un modèle d’équilibre 3D pour les régions euchromatiniennes à réplication précoces et un modèle d’équilibre 2D pour les régions heterochromatiniennes à réplication tardives associées à la lamina nucléaire. En représentant les matrices de co-localisation issues du Hi-C en réseaux d’interactions structurelles et en déployant des outils de la théorie des graphes, nous avons aussi démontré que les MaOris sont des hubs interconnectés à longue portée dans le réseau structurel, fondamentaux pour l’organisation 3D du génome et nous avons développé une méthodologie multi-échelle basée sur les ondelettes sur graphes pour délimiter objectivement des unités structurelles à partir des données Hi-C. Ce travail nous permet de discuter de la relation entre les domaines de réplication et les unités structurelles entre les différentes lignées cellulaires humaines. / The replication program of about one half of mammalian genomes is characterized by megabase-sized replication U/N-domains. These domains are bordered by master replication origins (MaOris) corresponding to ~200 kb regions of open chromatin favorable for early initiation of replication and transcription. Thanks to recent high-throughput chromosome conformation capture technologies (Hi-C), 3D co-localization frequency matrices between all genome loci are now experimentally determined. It appeared that U/N-domains were related to the organization of the genome into structural units. In this thesis, we performed a combined analysis of human Hi-C data and replication timing profiles to further explore the structure/function relationships in the nucleus. This led us to describe novel large (>3 Mb) replication timing split-U domains also bordered by MaOris, to demonstrate that the replication wave initiated at MaOris only depends of the time during S phase and to show that chromatin folding is compatible with a 3D equilibrium in early-replicating euchromatin regions turning to a 2D equilibrium in the late-replicating heterochromatin regions associated to nuclear lamina. Representing Hi-C co-localization matrices as structural networks and deploying graph theoretical tools, we also demonstrated that MaOris are long-range interconnected hubs in the structural network, central to the 3D organization of the genome and we developed a novel multi-scale methodology based on graph wavelets to objectively delineate structural units from Hi-C data. This work allows us to discuss the relationship between replication domains and structural units across different human cell lines.

Cette thèse fournit au lecteur un recueil d'applications de la théorie des graphes ; à ce but, des outils sur mesure, adaptés aux applications considérées, ont été conçus et mis en œuvre de manière inspirée par les données.Dans la première partie, une nouvelle métrique de centralité, nommée “bridgeness”, est présentée, basée sur une décomposition de la centralité intermédiaire (“betweenness centrality”) standard. Une composante, la “connectivité locale”, correspondante approximativement au degré d'un noeud, est différenciée de l'autre, qui, en revanche, évalue les propriétés structurelles à longue distance. En effet, cette dernière fournit une mesure de l'efficacité de chaque noeud à “relayer” parties faiblement connectées d'un réseau ; une caractéristique importante de cette métrique est son agnosticisme en ce qui concerne la structure de la communauté sous jacente éventuelle.Une deuxième application vise à décrire les caractéristiques dynamiques des graphes temporels qui apparaissent au niveau mésoscopique. L'ensemble de données de choix comprend 40 ans de publications scientifiques sélectionnées. L'apparition et l'évolution dans le temps d'un domaine d'étude spécifique (les ondelettes) sont capturées, en discriminant les caractéristiques persistantes des artefacts transitoires résultants du processus de détection des communautés, intrinsèquement bruité, effectué indépendamment sur des instantanées statiques successives. La notion de “flux laminaire”, sur laquelle repose le “score de complexité” que nous cherchons à optimiser, est présentée.Dans le même ordre d'idées, un réseau d'investisseurs japonais a été construit, sur la base d'un ensemble de données qui comprend des informations (indirectes) sur les filiales étrangères en copropriété. Une question très débattue dans le domaine de l'économie industrielle, l'hypothèse de Miwa-Ramseyer, a été démontrée de manière concluante comme fausse, du moins sous sa forme forte. / This thesis provides the reader with a compendium of applications of network theory; tailor-madetools suited for the purpose have been devised and implemented in a data-driven fashion. In the first part, a novel centrality metric, aptly named “bridgeness”, is presented, based on adecomposition of the standard betweenness centrality. One component, local connectivity, roughlycorresponding to the degree of a node, is set apart from the other, which evaluates longer-rangestructural properties. Indeed, the latter provides a measure of the relevance of each node in“bridging” weakly connected parts of a network; a prominent feature of the metric is its agnosticism with regard to the eventual ground truth community structure.A second application is aimed at describing dynamic features of temporal graphs which are apparent at the mesoscopic level. The dataset of choice includes 40 years of selected scientific publications.The appearance and evolution in time of a specific field of study (“wavelets”) is captured,discriminating persistent features from transient artifacts, which result from the intrinsically noisy community detection process, independently performed on successive static snapshots. The concept of “laminar stream”, on which the “complexity score” we seek to optimize is based, is introduced.In a similar vein, a network of Japanese investors has been constructed, based on a dataset which includes (indirect) information on co-owned overseas subsidiaries. A hotly debated issue in the field of industrial economics, the Miwa-Ramseyer hypothesis, has been conclusively shown to be false, at least in its strong form.

Made available in DSpace on 2016-03-15T19:37:48Z (GMT). No. of bitstreams: 1 Willyan Daniel Abilhoa.pdf: 1956528 bytes, checksum: 5d317e6fd19aebfc36180735bcf6c674 (MD5) Previous issue date: 2014-02-05 / Fundação de Amparo a Pesquisa do Estado de São Paulo / Twitter is a microblog service that generates a huge amount of textual content daily. All this content needs to be explored by means of techniques, such as text mining, natural language processing and information retrieval. In this context, the automatic keyword extraction is a task of great usefulness that can be applied to indexing, summarization and knowledge extrac-tion from texts. A fundamental step in text mining consists of building a text representation model. The model known as vector space model, VSM, is the most well-known and used among these techniques. However, some difficulties and limitations of VSM, such as scalabil-ity and sparsity, motivate the proposal of alternative approaches. This dissertation proposes a keyword extraction method, called TKG (Twitter Keyword Graph), for tweet collections that represents texts as graphs and applies centrality measures for finding the relevant vertices (keywords). To assess the performance of the proposed approach, two different sets of exper-iments are performed and comparisons with TF-IDF and KEA are made, having human clas-sifications as benchmarks. The experiments performed showed that some variations of TKG are invariably superior to others and to the algorithms used for comparisons. / O Twitter é um serviço de microblog que gera um grande volume de dados textuais. Todo esse conteúdo precisa ser explorado por meio de técnicas de mineração de textos, processamento de linguagem natural e recuperação de informação com o objetivo de extrair um conhecimento que seja útil de alguma forma ou em algum processo. Nesse contexto, a extração automática de palavras-chave é uma tarefa que pode ser usada para a indexação, sumarização e compreensão de documentos. Um passo fundamental nas técnicas de mineração de textos consiste em construir um modelo de representação de documentos. O modelo chamado mode-lo de espaço vetorial, VSM, é o mais conhecido e utilizado dentre essas técnicas. No entanto, algumas dificuldades e limitações do VSM, tais como escalabilidade e esparsidade, motivam a proposta de abordagens alternativas. O presente trabalho propõe o método TKG (Twitter Keyword Graph) de extração de palavras-chave de coleções de tweets que representa textos como grafos e aplica medidas de centralidade para encontrar vértices relevantes, correspondentes às palavras-chave. Para medir o desempenho da abordagem proposta, dois diferentes experimentos são realizados e comparações com TF-IDF e KEA são feitas, tendo classifica-ções humanas como referência. Os experimentos realizados mostraram que algumas variações do TKG são superiores a outras e também aos algoritmos usados para comparação.