Graphs have attracted researchers in various fields in that many different kinds of real-world entities and relationships between them can be represented and analyzed effectively and efficiently using graphs. In particular, researchers in data mining and machine learning areas have developed algorithms and models to understand the complex graph data better and perform various data mining tasks. While a large body of work exists on graph mining, most existing work does not fully exploit attributes attached to graph nodes or edges.<div><br></div><div>In this dissertation, we exploit node attributes to generate better solutions to several graph data mining problems addressed in the literature. First, we introduce the notion of statistically significant attribute associations in attribute graphs and propose an effective and efficient algorithm to discover those associations. The effectiveness analysis on the results shows that our proposed algorithm can reveal insightful attribute associations that cannot be identified using the earlier methods focused solely on frequency. Second, we build a probabilistic generative model for observed attributed graphs. Under the assumption that there exist hidden communities behind nodes in a graph, we adopt the idea of latent topic distributions to model a generative process of node attribute values and link structure more precisely. This model can be used to detect hidden communities and profile missing attribute values. Lastly, we investigate how to employ node attributes to learn latent representations of nodes in lower dimensional embedding spaces and use the learned representations to improve the performance of data mining tasks over attributed graphs.<br></div>

O aumento na disponibilidade de dados referentes a interação entre pessoas online tornou possível o estudo o processo de propagação de informações em redes sociais com volumes de dado antes jamais pensados. Neste trabalho, utilizamos dados do site de micro-blogging Twitter juntamente com conceitos de redes complexas para entender, caracterizar e classificar processos de difusão de informação observados nessa plataforma e em redes sociais em geral. Apresentamos importantes medidas para caracterização de cascatas de informação, bem como algoritmos eficientes para o seu cálculo. Com o auxilio dessas, mostramos que é possível quantificar a influência da rede social no processo de propagação de informação. Em seguida, constatamos que a informação tende a propagar por caminhos mínimos nessa rede. Por fim, mostramos que é possível utilizar apenas a topologia da rede social, sem nenhuma informação semântica, para agrupar tópicos, e que a topologia da rede social é fortemente influenciada pelos assuntos falados nela. Apesar de nosso trabalho possuir como base um único dataset, os métodos e medidas desenvolvidos são gerais e podem ser aplicados a qualquer processo de difusão de informação e a qualquer rede complexa. / The raise in the availability of data regarding interactions between people online has opened new doors to study the process of information diffusion in social networks. In this present work, we make use of the data from the micro-blogging website Twitteralong with complex networks concepts to understand, characterize and classify information diffusion processes observed in this platform and in social networks in general. We present important measures to characterize information cascades and efficient algorithms to calculate them. With the help of these measures, we show that it is possible to quantify the influence of the social network in the process of information diffusion. After that, we show that information does tend to travel along shortest paths on Twitter. Finally, we show that the topology of the social network, without any extra semantic information, can be used to aggregate topics, and that such topology is highly influenced by the topics being discussed on it. Altough we work with only a single dataset, our methods and measures developed are general and can be applied to any process of information diffusion and any complex network.

O uso de representações visuais constitui parte fundamental da prática de ensino de Ciências. Vários pesquisadores constatam que tais representações desempenham papel pedagógico essencial no processo ensino-aprendizagem das disciplinas científicas. Desta forma, surpreende notar que pouco se tenha investigado sobre o uso e o papel dessas representações no ensino-aprendizagem de Química. Diante deste quadro, a presente dissertação analisa uma forma de representação visual, o gráfico cartesiano, existente em livros didáticos de Química destinados ao nível Médio de ensino. Buscamos conhecer a prevalência, a função, a estrutura e a relação dos gráficos com os textos nos quis se encontram inseridos. As categorias de classificação destes gráficos, algumas originais, foram definidas em concordância com o marco teórico da Semiótica Social, área da Semiótica que considera, além do estudo intrínseco dos sinais, a sua inter-relação com as interações sociais, políticas e culturais. Foram também utilizados conhecimentos advindos da área de Educação em Ciências e da Ciência como prática social. Analisamos, também, qualitativamente, gráficos de alguns dos temas mais ricos neste tipo de representação não-verbal. Nossa análise concluiu que muitos dos gráficos apresentam deficiências estruturais, e que a sua relação com o texto não é suficientemente estabelecida, de modo que estes gráficos tendem a não ser adequadamente interpretados pelos alunos. / The use of visual representations constitutes a main aspect of the practice in science learning. Various researchers agree that such form of representation has an essential pedagogical role in science teaching-learning process. Thus it is remarkable that so little investigation on the use and role of these representations in Chemistry teaching has been conducted. In face of this situation, this study concerns a kind of visual representation, the Cartesian graph, available in Brazilian high school Chemistry textbooks. This work investigated the prevalence, the function, the structure, and the relation of the graphs with the context in which they are inserted. Some of the categories of the graph classification are original and were defined in agreement with the Social Semiotics theoretical approach, a semiotic field that works not only with signs intrinsically, but also with their interrelation with social, political and cultural interactions. The knowledge of science education and science as social practice were also considered. Some graphs of the subjects that made use of this type of non-verbal representation more frequently were analyzed qualitatively. The findings show that the majority of the graphs present structural deficiencies and that their relation with the main text is not sufficiently established; thus these graphs tend not to be adequately interpreted by the students.

In the first part of this thesis I consider site and bond percolation on a Random Connection Model and prove that for a wide range of connection functions the critical site probability is strictly greater than the critical bond probability and use this fact to improve previously known non-strict inequalities to strict inequalities. In the second part I consider percolation on the even phase of a Random Sequential Adsorption model and prove that the critical intensity is finite and strictly bigger than 1. Both of these main results make use of an enhancement technique.

Typescript (photocopy). / Digitized by Kansas Correctional Industries

Essa dissertação analisará uma abordagem investigativa de ensino de funções trigonométricas que prioriza a compreensão da relação entre movimentos circulares em diferentes velocidades com a formação gráfica gerada por esses movimentos. Com o auxílio do software Geogebra, diferentes movimentos foram criados, o que proporcionou a investigação gráfica por parte dos alunos. A atividade foi realizada no laboratório de informática onde, constantemente, houve investigação por parte dos alunos e intervenções significativas por parte do professor. Escolheu-se para essa pesquisa uma análise qualitativa embasada no processo descritivo das ações ocorridas em sala de aula. Para conhecer as características dessa abordagem, foi utilizado um estudo de casos. Após a atividade, os alunos conseguiram interpretar os principais movimentos gerados na circunferência e traduzi-los na sua forma gráfica. A análise mostra que os alunos não somente conseguiram desenvolver significados aos movimentos circulares, como também interpretaram corretamente situações cotidianas estabelecidas pelo professor ao fim do trabalho / This dissertation will analyze an investigative approach to the teaching of trigonometric functions that prioritizes the understanding of the relation between circular movements at different speeds with the graphical formation generated by these movements. With the help of the software Geogebra, different movements were created, which provided the graphic investigation by the students. The activity was carried out in the computer lab where, constantly, there was investigation by the students and significant interventions by the teacher. For this research, a qualitative analysis based on the descriptive process of the actions taken in the classroom was chosen. To know the characteristics of this approach, a case study was used. After the activity, the students were able to interpret the main movements generated on the circumference and translate them into their graphic form. The analysis shows that the students not only managed to develop meanings to the circular movements, but also correctly interpreted daily situations established by the teacher at the end of the work

O objetivo desta dissertação é estudar grafos com pesos nos vértices como um invariante global das aplicações de Gauss estáveis de superfícies compactas e orientadas. Apresentaremos também alguns invariantes locais que são importantes no estudo de aplicações estáveis. Abordaremos o problema de realização de grafos por aplicações de Gauss estáveis, considerando também um destes invariantes, o número de cúspides destas aplicações. Finalmente, usaremos matrizes para representar estes invariantes e definiremos classes de equivalências para estes representantes. Esta foi uma ideia que surgiu no final deste trabalho de mestrado. / The propose of this work is to study graphs with weights at the vertices as a global invariant of stable Gauss applications on compact and oriented surfaces. We also present some local invariants that are important to the study of stable applications. We approach the problem of realization of graphs by stable Gauss applications, also emphasizing one of these invariants, the number of cusps of these applications. Finally, we use matrices to represent these invariants and define equivalence classes for these representatives. This idea appeared at the end of this master\'s thesis.

Neste trabalho, aplicamos o algoritmo Breadth-First Search para encontrar o tamanho de uma componente conectada no grafo aleatório de Erdos-Rényi. Uma cadeia de Markov é obtida deste procedimento. Apresentamos alguns resultados bem conhecidos sobre o comportamento dessa cadeia de Markov. Combinamos alguns destes resultados para obter uma proposição sobre a probabilidade da componente atingir um determinado tamanho e um resultado de convergência do estado da cadeia neste instante. Posteriormente, aplicamos o teorema de convergência de Darling (2002) a sequência de cadeias de Markov reescaladas e indexadas por N, o número de vértices do grafo, para mostrar que as trajetórias dessas cadeias convergem uniformemente em probabilidade para a solução de uma equação diferencial ordinária. Deste resultado segue a bem conhecida lei fraca dos grandes números para a componente gigante do grafo aleatório de Erdos-Rényi, no caso supercrítico. Além disso, obtemos o limite do fluído para um modelo epidêmico que é uma extensão daquele proposto em Kurtz et al. (2008). / In this work, we apply the Breadth-First Search algorithm to find the size of a connected component of the Erdos-Rényi random graph. A Markov chain is obtained of this procedure. We present some well-known results about the behavior of this Markov chain, and combine some of these results to obtain a proposition about the probability that the component reaches a certain size and a convergence result about the state of the chain at that time. Next, we apply the convergence theorem of Darling (2002) to the sequence of rescaled Markov chains indexed by N, the number of vertices of the graph, to show that the trajectories of these chains converge uniformly in probability to the solution of an ordinary dierential equation. From the latter result follows the well-known weak law of large numbers of the giant component of the Erdos-Renyi random graph, in the supercritical case. Moreover, we obtain the uid limit for an epidemic model which is an extension of that proposed in Kurtz et al. (2008).

We consider the computational complexity of evaluating the Tutte polynomial of three particular classes of greedoid, namely rooted graphs, rooted digraphs and binary greedoids. Furthermore we construct polynomial-time algorithms to evaluate the Tutte polynomial of these classes of greedoid when they're of bounded tree-width. We also construct a Möbius function formulation for the characteristic polynomial of a rooted graph and determine the computational complexity of computing the coefficients of the Tutte polynomial of a rooted graph.

Projeções Multidimensionais são úteis para gerar visualizações adequadas para apoiar a análise exploratória de uma grande variedade de dados complexos e de alta dimensionalidade. Tarefas de análise visual de dados têm se beneficiado de projeções para explorar dados textuais, de imagens, de sensores, entre outros. Porém, diferentes técnicas de projeção e diferentes parametrizações de uma mesma técnica produzem resultados distintos para um mesmo conjunto de dados, pois as técnicas adotam estratégias distintas para representar os dados originais em um espaço cuja dimensionalidade permite sua visualização. Atualmente, ainda há poucos recursos para avaliar a qualidade dessas projeções e, em geral, as soluções existentes avaliam propriedades específicas, demandando grande esforço do analista para uma avaliação mais abrangente. Neste trabalho, introduzimos um arcabouço para computar medidas de avaliação de projeções com enfoque em análise de vizinhanças e de agrupamentos. Para elaborar este arcabouço, foi realizado um estudo de percepção para entender melhor como os usuários observam as projeções e foi conduzida uma investigação de representações dos dados capazes de favorecer a identificação de vizinhanças e de agrupamentos. Os padrões identificados no estudo de percepção auxiliaram a validar a representação dos dados, em que foi proposto um modelo de grafo, chamado de Extended Minimum Spanning Tree (EMST), capaz de capturar características condizentes com as observações dos participantes no estudo. O grafo EMST também foi validado por meio de dois estudos comparativos de identificação de vizinhanças e de agrupamentos. Com base neste arcabouço foram propostas cinco medidas de qualidade de projeções multidimensionais, duas delas para avaliar características relacionadas à separação visual das classes, e outras três para avaliar a preservação de propriedades do espaço original, especificamente a separação das classes, as vizinhanças e os agrupamentos. As medidas são ilustradas por meio de sua aplicação a conjuntos de dados artificiais, favorecendo a sua interpretação, bem como a conjuntos de dados reais, evidenciando a sua potencial utilidade em cenários reais. Também é apresentada uma comparação das novas medidas de preservação de vizinhanças com medidas similares descritas na literatura, permitindo identificar diferenças e semelhanças entre elas. / Multidimensional projections are valuable tools to generate visualizations that support exploratory analysis of a wide variety of complex high-dimensional data. Many examples are found in the literature of visual data analysis tasks that employ projections to explore, for instance, text, image, network and sensor data. Nonetheless, dierent projection techniques applied to a particular data set, or even alternative parameterizations of a single technique, can produce very distinct outcomes, as techniques adopt different strategies to reduce data dimensionality. Few resources are available to support assessing projection quality and, in general, existing solutions focus on specific properties. Thus, a broader assessment typically requires considerable human effort. In this work we introduce a framework to compute projection evaluation measures that focus on neighborhoods and clusters. To elaborate this framework we conducted (i) an experimental study to better understand how users perceive projections and (ii) an investigation of possible data representations capable of favoring the identification of neighborhoods and clusters. The observations resulting from the experimental study have been considered to propose and validate a novel graph data model, called Extended Minimum Spanning Tree (EMST), which captures data properties shown to be consistent with the observations by the participants in the study. The EMST graph has been validated by means of two comparative studies conducted to identify neighborhoods and clusters in multidimensional data. Under this framework, five novel measures of projection quality are introduced, two of them to assess properties related to the visual separation of classes, and three to assess the preservation of data properties in the original space, in particular the preservation of class separation, the preservation of neighborhoods and the preservation of groups. The quality measures have been applied to projections of synthetic data sets, favoring their understanding and interpretation, and also to projections of real data sets, illustrating their potential applicability in real scenarios. The newly introduced neighborhood preservation measures are also compared with existing methods in order to illustrate their differences and similarities.