Graphs are commonly selected as a model of scientific information: graphs can successfully represent imprecise, uncertain, noisy data; and graph theory has a well-developed mathematical apparatus forming a solid and sound foundation for graph research. Design and experimental confirmation of new, scalable, and practical analytics for massive graphs have been actively researched for decades. Our work concentrates on developing new accurate and efficient algorithms that calculate the most influential nodes and communities in an arbitrary graph. Our algorithms for graph decomposition into families of most influential communities compute influential communities faster and using smaller memory footprint than existing algorithms for the problem. Our algorithms solving the problem of influence maximization in large graphs use much smaller memory than the existing state-of-the-art algorithms while providing solutions with equal accuracy. Our main contribution is designing data structures and algorithms that drastically cut the memory footprint and scale up the computation of influential communities and nodes to massive modern graphs. The algorithms and their implementations can efficiently handle networks of billions of edges using a single consumer-grade machine. These claims are supported by extensive experiments on large real-world graphs of different types. / Graduate

abstract: The purpose of information source detection problem (or called rumor source detection) is to identify the source of information diffusion in networks based on available observations like the states of the nodes and the timestamps at which nodes adopted the information (or called infected). The solution of the problem can be used to answer a wide range of important questions in epidemiology, computer network security, etc. This dissertation studies the fundamental theory and the design of efficient and robust algorithms for the information source detection problem. For tree networks, the maximum a posterior (MAP) estimator of the information source is derived under the independent cascades (IC) model with a complete snapshot and a Short-Fat Tree (SFT) algorithm is proposed for general networks based on the MAP estimator. Furthermore, the following possibility and impossibility results are established on the Erdos-Renyi (ER) random graph: $(i)$ when the infection duration $<\frac{2}{3}t_u,$ SFT identifies the source with probability one asymptotically, where $t_u=\left\lceil\frac{\log n}{\log \mu}\right\rceil+2$ and $\mu$ is the average node degree, $(ii)$ when the infection duration $>t_u,$ the probability of identifying the source approaches zero asymptotically under any algorithm; and $(iii)$ when infection duration $<t_u,$ the breadth-first search (BFS) tree starting from the source is a fat tree. Numerical experiments on tree networks, the ER random graphs and real world networks show that the SFT algorithm outperforms existing algorithms. In practice, other than the nodes' states, side information like partial timestamps may also be available. Such information provides important insights of the diffusion process. To utilize the partial timestamps, the information source detection problem is formulated as a ranking problem on graphs and two ranking algorithms, cost-based ranking (CR) and tree-based ranking (TR), are proposed. Extensive experimental evaluations of synthetic data of different diffusion models and real world data demonstrate the effectiveness and robustness of CR and TR compared with existing algorithms. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2015

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

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Polyhedra are geometric solids formed by a &#64257;nite number of polygons they can be convex or non-convex, regular or not regular. This work we make three demonstrations of Eulerâs theorem for polyhedra in one plane being used graphs. We will adopt preliminary de&#64257;nitions of polygons, polyhedra and graphs and make a brief study of the theorem before the demonstrations analysis when the theorem is valid and what conditions exist polyhedra, since the theorem is accepted. The work brings some applications in the form of questions in the theory presented. / Os poliedros sÃo sÃlidos geomÃtricos formados por uma quantidade &#64257;nita de polÃgonos. Eles podem ser convexos ou nÃo convexos, regulares ou nÃo regulares . Neste trabalho fazemos trÃs demonstraÃÃes do teorema de Euler para poliedros no plano, sendo uma utilizado grafos. Adotaremos de&#64257;niÃÃes preliminares de polÃgonos, poliedros e grafos e faremos um breve estudo do teorema antes das demonstraÃÃes analisado quando o teorema à valido em quais condiÃÃes existem os poliedros, uma vez que o teorema à aceito. O trabalho traz algumas aplicaÃÃes em forma de questÃes da teoria apresentada.

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.

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.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-24T12:22:13Z No. of bitstreams: 1 marcusviniciusaraujo.pdf: 4473223 bytes, checksum: 20a2e9096b36c11bf249fc1b9983987e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-24T12:55:51Z (GMT) No. of bitstreams: 1 marcusviniciusaraujo.pdf: 4473223 bytes, checksum: 20a2e9096b36c11bf249fc1b9983987e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-24T12:56:01Z (GMT) No. of bitstreams: 1 marcusviniciusaraujo.pdf: 4473223 bytes, checksum: 20a2e9096b36c11bf249fc1b9983987e (MD5) / Made available in DSpace on 2017-03-24T12:56:01Z (GMT). No. of bitstreams: 1 marcusviniciusaraujo.pdf: 4473223 bytes, checksum: 20a2e9096b36c11bf249fc1b9983987e (MD5) Previous issue date: 2016-08-18 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O presente trabalho tem por objetivo instigar nos leitores que tenham acesso a ele,um olhar mais crítico e questionador em relação aos gráficos estatísticos que surgem diariamente na mídia, e também servir como material de apoio em uma aula de Estatística, esclarecendo aos discentes a importância da compreensão de tal conteúdo para um pleno exercer da cidadania. Para atingir a tais fins, o mesmo foi dividido em duas partes. A primeira, um referencial teórico, traz uma revisão sobre os conceitos iniciais da Estatística, mais especificamente sobre as estruturas necessárias para compreensão e construção de gráficos. A segunda, um estudo de cinco casos (cinco gráficos estatísticos divulgados pela mídia) e as respectivas análises sobre cada um deles, pretende assim levar o leitor a uma postura mais amadurecida e cautelosa perante os mesmos. / This study aims to entice in readers who have access to it, a look more critical and questioning in relation to the statistical graphs that appear daily in the media, and also serveassupportmaterialinaStatisticsclass,explainingtostudentstheimportanceofsuch content understanding to a full exercise of citizenship. To achieve such purposes, it was divided into two parts. The first, a theoretical referential, provides a review of the initial concepts of Statistics, more specifically on the structures necessary for understanding and building graphics. The second one, a study of five cases (five statistical charts released by the media) and the analysis of each of them, plans to take the reader to become aware of such material to a more mature and cautious stance towards them.

Orientador: Celmar Guimarães da Silva / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-23T22:48:20Z (GMT). No. of bitstreams: 1 MarcheteFilho_JoaoRubens_M.pdf: 10431540 bytes, checksum: 5b2b14817538f82611b82878238e256c (MD5) Previous issue date: 2013 / Resumo: A utilização de grafos acíclicos direcionados permite a representação gráfica de estruturas hierárquicas, o que facilita encontrar padrões e tendências durante a análise dessas estruturas. A principal abordagem de desenho automático desses grafos divide seus vértices em camadas, de tal modo que as arestas sempre apontem para uma mesma direção. Um dos principais critérios estéticos dessas estruturas visuais é evitar, sempre que possível, o cruzamento entre arestas, facilitando assim o entendimento do desenho. Os algoritmos de redução de cruzamentos devem também prover essa solução em um tempo inferior a 0,1 segundo, tornando mais apropriada sua utilização em estruturas visuais interativas. Nesta dissertação, pesquisou-se como uma estrutura de dados conhecida por árvore PQR poderia ser utilizada a fim de aperfeiçoar dois métodos de redução de cruzamentos: BC e MEDIAN. Dentre os novos métodos desenvolvidos, destacaram se: PQR_BC2 para o aperfeiçoamento do BC; PQR_M2 para o aperfeiçoamento do MEDIAN. Os resultados obtidos através da aplicação dos métodos a pacotes de grafos amplamente utilizados na literatura mostram que os métodos baseados em árvores PQR superaram o método BC e o método MEDIAN, com relação à redução de cruzamentos, em 42% dos casos, empatando nesse critério em 45% dos grafos analisados. Além disso, os métodos baseados em árvores PQR também executaram em um tempo viável para aplicação em estruturas visuais interativas / Abstract: The use of directed acyclic graphs allows the graphical representation of hierarchical structures, which eases to find patterns and trends during the analysis of these structures. The main approach to automatic design of these graphs divides its vertices in layers so that the edges always point toward the same direction. One of the major aesthetic criteria of such visual structures is to avoid, whenever possible, the crossing between the edges, thereby facilitating the understanding of the drawing. The crossing reduction algorithms must also provide this solution in a time less than 0.1 second, allowing its use in interactive visual structures. In this dissertation, was investigated as a data structure known as PQR tree could be used to improve both methods for reducing crossings: BC and MEDIAN. Among the new methods developed, stood out: PQR_BC2 for improvement of BC; PQR_M2 for improving the MEDIAN. The results obtained by applying the methods to packets of graphs widely used in the literature show that the methods based on PQR trees outperformed the BC method and the MEDIAN method, with respect to the crossing reduction, in 42% of cases, tying this criterion in 45% of the graph analyzed. In addition, methods based on PQR trees also performed at a feasible time for application to interactive visual structures / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Notre enquête a été conduite auprès de membres d’un groupe d’anciens élèves hébergé sur le site de réseau social professionnel LinkedIn. Elle a permis de produire deux résultats. Le premier résultat est une typologie des figures du réseautage en ligne. Nous proposons trois figures. Le NetMining, qui relève d’un usage exploratoire du site et oùl’utilisateur cumule de nombreux contacts. Le NetWorking où l’utilisateur sélectionne des relations sur la base de critères précis. Le NetSticking où l’utilisateur reproduit en ligne un réseau personnel basé sur la confiance. Ces trois tendances permettent de souligner deux caractéristiques propres aux pratiques de réseautage en ligne. D’une part, elles reposent surune pluralité de dispositifs de communication où LinkedIn occupe une place tantôt centrale, tantôt marginale. D’autre part, ces pratiques ne reposent pas nécessairement sur la poursuite d’une action planifiée. Le second résultat produit par notre enquête est un dispositif d’étude des pratiques de réseautage. Il associe des techniques de visualisation de graphes et analyses d’entretiens semi-directifs / Our study had been carried on members of a social network hosted on the professional social network site, LinkedIn. It produced two main outcomes. The first is a typology of online Networking on three different classes. The first is the NetMining, which is a exploratory use of the website, where the user accumulated contacts. The second category is the NetWorking, where the users select contacts based on defined characteristics. The NetSticking is the third category, in which the user reproduced online a personal network based on trust. Those three categories highlight two main characteristics, specific to online networking. First, networking uses different means of communication, in whichLinkedIn is sometimes central, but sometimes marginal. Those practices are besides not necessarily based on planed actions. The Second result of our enquiry is a study device of the networking practices which associated graphs visualization technics and semi-directed interviews analyses