Networks are present in computer science, sociology, biology, and neuroscience as well as in applied fields such as transportation, communication, medical industries. The growing volumes of data collection are pushing scalability and performance requirements on graph algorithms, and at the same time, a need for a deeper understanding of these structures through visualization arises. Network diagrams or graph drawings can facilitate the understanding of data, making intuitive the identification of the largest clusters, the number of connected components, the overall structure, and detecting anomalies, which is not achievable through textual or matrix representations. The aim of this study was to evaluate approaches that would enable visualization of a large scale peer-to-peer video live streaming networks. The visualization of such large scale graphs has technical limitations which can be overcome by filtering important structural data from the networks. In this study, four sampling algorithms for graph reduction were applied to large overlay peer-to-peer network graphs and compared. The four algorithms cover different approaches: selecting links with the highest weight, selecting nodes with the highest cumulative weight, using betweenness centrality metrics, and constructing a focus-based tree. Through the evaluation process, it was discovered that the algorithm based on betweenness centrality approximation offers the best results. Finally, for each of the algorithms in comparison, their resulting sampled graphs were visualized using a forcedirected layout with a 2-step loading approach to depict their effect on the representation of the graphs. / Nätverk återfinns inom datavetenskap, sociologi, biologi och neurovetenskap samt inom tillämpade områden så som transport, kommunikation och inom medicinindustrin. Den växande mängden datainsamling pressar skalbarheten och prestandakraven på grafalgoritmer, samtidigt som det uppstår ett behov av en djupare förståelse av dessa strukturer genom visualisering. Nätverksdiagram eller grafritningar kan underlätta förståelsen av data, identifiera de största grupperna, ett antal anslutna komponenter, visa en övergripande struktur och upptäcka avvikelser, något som inte kan uppnås med texteller matrisrepresentationer. Syftet med denna studie var att utvärdera tillvägagångssätt som kunde möjliggöra visualisering av ett omfattande P2P (peer-to-peer) livestreamingnätverk. Visualiseringen av större grafer har tekniska begränsningar, något som kan lösas genom att samla viktiga strukturella data från nätverken. I den här studien applicerades fyra provtagningsalgoritmer för grafreduktion på stora överlagringar av P2P-nätverksgrafer för att sedan jämföras. De fyra algoritmerna är baserade på val av länkar med högsta vikt, av nodar med högsta kumulativa vikt, betweenness-centralitetsvärden för att konstruera ett fokusbaserat träd som har de längsta vägarna uteslutna. Under utvärderingsprocessen upptäcktes det att algoritmen baserad på betweenness-centralitetstillnärmning visade de bästa resultaten. Dessutom, för varje algoritm i jämförelsen, visualiserades deras slutliga samplade grafer genom att använda en kraftstyrd layout med ett 2-stegs laddningsinfart.

It is a challenging task for interaction designers to find a way to design a digital artefact supporting serendipitous discovery. Its interdisciplinary nature requires sufficient knowledge of information visualization, social navigation and serendipity. Based on literature review and prior relevant works, several traces having potential to aid such exploration were defined. Through creating and testing AniMap, an interactive graph visualization for discovering new anime clips, in this thesis I argue that such an artefact has the potential to support serendipitous discovery, owing to its features of being information visualization, interactive and in a graph layout, coupled with users’ personal interests. Even so, finding details of how to influence serendipitous discovery remain an ongoing challenge considering the dynamic nature of serendipity.

No description available.

As one of the most essential data mining tasks, clustering analysis has been widely discussed and employed since its invention. Czekanowski’s diagram, which has been around for over a century as a visualization tool for exploring cluster distributions, is being improved continually. RMaCzek is a package of R, which is used to implement Czekanowski’s diagram. By using this package, users can plot a symmetric or asymmetric Czekanowski’s diagram. However, the user still has to manually judge the clustering result through the diagram, which will inevitably lead to the deviation of the subjective judgement and increase the user’s workload. In order to keep the advantages of Czekanowski’s diagram and exploit its potential, Czekanowski’s clustering algorithm is proposed in this thesis. A new clustering algorithm based on Czekanowski’s diagram that allows it to label the clustering results directly and mark the findings on the Czekanowski’s diagram. Czekanowski’s clustering supports two clustering methods, namely exact Czekanowski’s clustering and fuzzy Czekanowski’s clustering, so that users can choose different methods according to the characteristics of the analysis object. Besides, this thesis will also cover the upgraded RMaCzek R package’s application method, including how to use it for Czekanowski’s clustering, how to express the clustering outcomes by Czekanowski’s diagram and the improvement of plotting function. On the other hand, the performance of the new clustering algorithm will be evaluated in this thesis by comparing it with the other five commonly used clustering algorithms. Also, through some experiments, we were able to determine the impact of various algorithm parameters on clustering performance.

De nos jours, nous générons une quantité immensément grande de données juste en accomplissant nos simples tâches quotidiennes. L'analyse de ces données soulève des challenges ardus. Dans cette thèse, nous nous intéressons à deux aspects des données relationnelles. En premier lieu, nous considérons les données relationnelles dans lesquelles les relations sont pondérées. Un exemple concret serait le nombre commun de suiveurs entre deux utilisateurs de Twitter. Dans un deuxième temps, nous abordons le cas dynamique de ces données qui est inhérent à leur nature. Par exemple, le nombre de suiveurs communs pourrait changer au fil du temps. Dans cette thèse nous utilisons les graphes pour modéliser ces données qui sont à la fois complexes et évolutives. Les travaux de cette thèse s'articulent aussi autour de la détection de communautés pour les graphes pondérés et dynamiques. Pour un utilisateur expert, l'identification de ces communautés pourrait l'aider à comprendre la sémantique sous-jacente à la structure du graphe. Notre hypothèse repose sur l'utilisation des triangles comme ossature pour la détection de communautés. Cela nous a amenés à proposer plusieurs algorithmes : Séparation et évaluation, recherche gloutonne, heuristiques et algorithme génétique sont proposés. En se basant sur cet ensemble de triangles, nous proposons un algorithme de détection de communautés, appelé Tribase. L'idée conductrice de cet algorithme est de comparer les poids des communautés, permettant aux communautés dominantes d'acquérir plus de membres. Les résultats de l'étude comparative sur le benchmark LFR montrent que l'algorithme que nous proposons parvient à détecter les communautés dans les graphes dans lesquels une structure de communautés existe. De plus, l'applicabilité de notre algorithme a été testée sur des données réelles du projet ANR Info-RSN. Dans l'optique d'accompagner l'utilisateur expert dans son processus d'acquisition de l'information, une application visuelle et interactive a été implémentée. NLCOMS (Nœud-Lien et COMmunautéS) propose une panoplie de vues synchronisées pour la représentation de l'information. Par ailleurs, nous proposons dans cette thèse un algorithme de détection de communautés pour les graphes pondérés et dynamiques, appelé Dyci. Dyci permet de gérer les différents scénarios de mise à jour possibles de la structure du graphe. L'idée principale de Dyci est de guetter au cours du temps l'affaiblissement d'une communauté (en termes de poids) dans le but de reconsidérer localement sa place dans la structure, évitant ainsi une réindentification globale des communautés. Une étude comparative a été menée montrant que l'algorithme que nous proposons offre un bon compromis entre la solution obtenue et le temps de calcul. Finalement, l'intégration dans NLCOMS des visualisations adéquates pour la variante dynamique a été effectuée / Relational data in our society are on a constant increasing, rising arduous challenges. In this thesis, we consider two aspects of relational data. First, we are interested in relational data with weighted relationship. As a concrete example, relationships among Twitter's users could be weighted with regard to their shared number of followers. The second aspect is related to the dynamism which is inherent to data nature. As an instance, in the previous example the number of common followers between two Twitter's users can change over time. In order to handle these complex and dynamic relational data, we use the modelling strength of graphs. Another facet considered in this thesis deals with community identification on weighted and dynamic graphs. For an analyst, the community detection might be helpful to grasp the semantic behind the graph structure. Our assumption relies on the idea to use a set of disjoint pairwise triangles as a basis to detect the community structure. To select these triangles, several algorithms are proposed (i.e., branch-and-bound, greedy search, heuristics and genetic algorithm). Thereafter, we propose a community detection algorithm, called Tribase. In the latter, the weights of communities are compared allowing dominant communities to gain in size. Tribase is compared with the well-known LFR benchmark. The results show that Tribase identifies efficiently the communities while a community structure exists. Additionally, to asset Tribase on real-world data, we consider social networks data, especially Twitter's data, of the ANR-Info-RSN project. In order to support the analyst in its knowledge acquisition, we elaborate a visual interactive approach. To this end, an interactive application, called NLCOMS is introduced. NLCOMS uses multiple synchronous views for visualizing community structure and the related information. Furthermore, we propose an algorithm for the identification of communities over time, called Dyci. The latter takes advantage from the previously detected communities. Several changes' scenarios are considered like, node/edge addition, node/edge removing and edge weight update. The main idea of the proposed algorithm is to track whether a part of the weighted graph becomes weak over time, in order to merge it with the "dominant" neighbour community. In order to assess the quality of the returned community structure, we conduct a comparison with a genetic algorithm on real-world data of the ARN-Info-RSN project. The conducted comparison shows that Dyci algorithm provides a good trade-off between efficiency and consumed time. Finally, the dynamic changes which occur to the underlying graph structure can be visualized with NLCOMS which combines physical an axial time to fulfil this need

Visualizações de grafos para comunicação aparecem numa variedade de contextos que vão do acadêmico-científico até o jornalístico e até mesmo artístico. Diferente de visualizações de grafos para exploração e análise de dados, essas imagens são usadas para “contar uma história” que já se conhece ao invés da “procura de uma nova história” nos dados. Apesar de ser possível usar software para desenho de grafos e edição de diagramas para produzí-las, visualizações feitas dessa forma nem sempre preenchem os requisitos visuais impostos pelos seus contextos de uso. Programas de edição de imagens podem ser usados para fazer as melhorias necessárias, mas nem todas as modificações são possíveis e o processo de editar essas imagens pode exigir muito tempo e esforço. Neste trabalho, apresentamos uma investigação de visualizações nodo-aresta estáticas para comunicação e de como facilitar sua criação. A partir de uma desconstrução dessas imagens, identificando seus elementos essenciais, e analisando como são criadas, derivamos um conjunto de requisitos que ferramentas para a criação dessas visualizações devem preencher. Para verificar o efeito da metodologia na melhora do fluxo de trabalho de designers, com mais poder e flexibilidade, foi concebido e implementado um protótipo chamado GraphCoiffure. Com um foco especial em auxiliar usuários na criação de visualizações para publicação, Graph- Coiffure foi projetado como uma aplicação standalone que seria usada como um passo intermediário entre programas de desenho e edição de grafos e editores gráficos. Ele combina ferramentas para manipulação interativa de layouts com estilização similar a CSS para permitir que usuários criem e editem visualizações nodo-aresta estáticas. Ilustramos o funcionamento de GraphCoiffure com quatro casos de uso: a adaptação do layout de uma visualização para fazê-la funcionar em uma dada página, a reprodução do estilo de uma visualização e sua aplicação em outro grafo, e a criação integral de duas novas visualizações. Para obter feedback sobre GraphCoiffure, conduzimos uma avaliação informal através de entrevistas com três potenciais usuários, que disseram achar que GraphCoiffure beneficiaria seu trabalho. / Graph visualizations for communication appear in a variety of contexts that range from scientific/ academic to journalistic and even artistic. Unlike graph visualizations for exploration and analysis, these images are used to tell a story that is already known rather than to look for a story within the data. Although graph drawing and diagram editing software can be used to produce them, visualizations made this way do not always meet the visual requirements imposed by their context of use. Graphics authoring software can be used to make the necessary improvements, but not all modifications are possible and the process of editing these images may be very time-consuming and labor-intensive. In this work, we present an investigation of static node-link visualizations for communication and how to better support their creation. We began with a deconstruction of these images, breaking them down into their basic elements and analyzing how they are created. From this, we derived a set of requirements that tools aimed at supporting their creation should meet. To verify if taking all of this into account would improve the workflow and bring more flexibility and power to the users, we created our own prototype, which we named GraphCoiffure. With a special emphasis on helping users on creating visualizations for publication, GraphCoiffure was designed as a standalone application that would serve as an intermediary step between graph drawing and editing software and graphics editors. It combines interactive graph layout manipulation tools with CSS-like styling possibilities to let users create and edit static node-link visualizations for communication. We illustrate the use of GraphCoiffure with four use-case scenarios: the adaptation of a visualization’s layout to make it work on a given page, the reproduction of a visualization’s style and its application on another graph, and the creation of two visualizations from scratch. To obtain feedback on GraphCoiffure, we conducted an informal evaluation by interviewing three potential expert users, who found that it could be useful for their work.

Visualizações de grafos para comunicação aparecem numa variedade de contextos que vão do acadêmico-científico até o jornalístico e até mesmo artístico. Diferente de visualizações de grafos para exploração e análise de dados, essas imagens são usadas para “contar uma história” que já se conhece ao invés da “procura de uma nova história” nos dados. Apesar de ser possível usar software para desenho de grafos e edição de diagramas para produzí-las, visualizações feitas dessa forma nem sempre preenchem os requisitos visuais impostos pelos seus contextos de uso. Programas de edição de imagens podem ser usados para fazer as melhorias necessárias, mas nem todas as modificações são possíveis e o processo de editar essas imagens pode exigir muito tempo e esforço. Neste trabalho, apresentamos uma investigação de visualizações nodo-aresta estáticas para comunicação e de como facilitar sua criação. A partir de uma desconstrução dessas imagens, identificando seus elementos essenciais, e analisando como são criadas, derivamos um conjunto de requisitos que ferramentas para a criação dessas visualizações devem preencher. Para verificar o efeito da metodologia na melhora do fluxo de trabalho de designers, com mais poder e flexibilidade, foi concebido e implementado um protótipo chamado GraphCoiffure. Com um foco especial em auxiliar usuários na criação de visualizações para publicação, Graph- Coiffure foi projetado como uma aplicação standalone que seria usada como um passo intermediário entre programas de desenho e edição de grafos e editores gráficos. Ele combina ferramentas para manipulação interativa de layouts com estilização similar a CSS para permitir que usuários criem e editem visualizações nodo-aresta estáticas. Ilustramos o funcionamento de GraphCoiffure com quatro casos de uso: a adaptação do layout de uma visualização para fazê-la funcionar em uma dada página, a reprodução do estilo de uma visualização e sua aplicação em outro grafo, e a criação integral de duas novas visualizações. Para obter feedback sobre GraphCoiffure, conduzimos uma avaliação informal através de entrevistas com três potenciais usuários, que disseram achar que GraphCoiffure beneficiaria seu trabalho. / Graph visualizations for communication appear in a variety of contexts that range from scientific/ academic to journalistic and even artistic. Unlike graph visualizations for exploration and analysis, these images are used to tell a story that is already known rather than to look for a story within the data. Although graph drawing and diagram editing software can be used to produce them, visualizations made this way do not always meet the visual requirements imposed by their context of use. Graphics authoring software can be used to make the necessary improvements, but not all modifications are possible and the process of editing these images may be very time-consuming and labor-intensive. In this work, we present an investigation of static node-link visualizations for communication and how to better support their creation. We began with a deconstruction of these images, breaking them down into their basic elements and analyzing how they are created. From this, we derived a set of requirements that tools aimed at supporting their creation should meet. To verify if taking all of this into account would improve the workflow and bring more flexibility and power to the users, we created our own prototype, which we named GraphCoiffure. With a special emphasis on helping users on creating visualizations for publication, GraphCoiffure was designed as a standalone application that would serve as an intermediary step between graph drawing and editing software and graphics editors. It combines interactive graph layout manipulation tools with CSS-like styling possibilities to let users create and edit static node-link visualizations for communication. We illustrate the use of GraphCoiffure with four use-case scenarios: the adaptation of a visualization’s layout to make it work on a given page, the reproduction of a visualization’s style and its application on another graph, and the creation of two visualizations from scratch. To obtain feedback on GraphCoiffure, we conducted an informal evaluation by interviewing three potential expert users, who found that it could be useful for their work.

Visualizações de grafos para comunicação aparecem numa variedade de contextos que vão do acadêmico-científico até o jornalístico e até mesmo artístico. Diferente de visualizações de grafos para exploração e análise de dados, essas imagens são usadas para “contar uma história” que já se conhece ao invés da “procura de uma nova história” nos dados. Apesar de ser possível usar software para desenho de grafos e edição de diagramas para produzí-las, visualizações feitas dessa forma nem sempre preenchem os requisitos visuais impostos pelos seus contextos de uso. Programas de edição de imagens podem ser usados para fazer as melhorias necessárias, mas nem todas as modificações são possíveis e o processo de editar essas imagens pode exigir muito tempo e esforço. Neste trabalho, apresentamos uma investigação de visualizações nodo-aresta estáticas para comunicação e de como facilitar sua criação. A partir de uma desconstrução dessas imagens, identificando seus elementos essenciais, e analisando como são criadas, derivamos um conjunto de requisitos que ferramentas para a criação dessas visualizações devem preencher. Para verificar o efeito da metodologia na melhora do fluxo de trabalho de designers, com mais poder e flexibilidade, foi concebido e implementado um protótipo chamado GraphCoiffure. Com um foco especial em auxiliar usuários na criação de visualizações para publicação, Graph- Coiffure foi projetado como uma aplicação standalone que seria usada como um passo intermediário entre programas de desenho e edição de grafos e editores gráficos. Ele combina ferramentas para manipulação interativa de layouts com estilização similar a CSS para permitir que usuários criem e editem visualizações nodo-aresta estáticas. Ilustramos o funcionamento de GraphCoiffure com quatro casos de uso: a adaptação do layout de uma visualização para fazê-la funcionar em uma dada página, a reprodução do estilo de uma visualização e sua aplicação em outro grafo, e a criação integral de duas novas visualizações. Para obter feedback sobre GraphCoiffure, conduzimos uma avaliação informal através de entrevistas com três potenciais usuários, que disseram achar que GraphCoiffure beneficiaria seu trabalho. / Graph visualizations for communication appear in a variety of contexts that range from scientific/ academic to journalistic and even artistic. Unlike graph visualizations for exploration and analysis, these images are used to tell a story that is already known rather than to look for a story within the data. Although graph drawing and diagram editing software can be used to produce them, visualizations made this way do not always meet the visual requirements imposed by their context of use. Graphics authoring software can be used to make the necessary improvements, but not all modifications are possible and the process of editing these images may be very time-consuming and labor-intensive. In this work, we present an investigation of static node-link visualizations for communication and how to better support their creation. We began with a deconstruction of these images, breaking them down into their basic elements and analyzing how they are created. From this, we derived a set of requirements that tools aimed at supporting their creation should meet. To verify if taking all of this into account would improve the workflow and bring more flexibility and power to the users, we created our own prototype, which we named GraphCoiffure. With a special emphasis on helping users on creating visualizations for publication, GraphCoiffure was designed as a standalone application that would serve as an intermediary step between graph drawing and editing software and graphics editors. It combines interactive graph layout manipulation tools with CSS-like styling possibilities to let users create and edit static node-link visualizations for communication. We illustrate the use of GraphCoiffure with four use-case scenarios: the adaptation of a visualization’s layout to make it work on a given page, the reproduction of a visualization’s style and its application on another graph, and the creation of two visualizations from scratch. To obtain feedback on GraphCoiffure, we conducted an informal evaluation by interviewing three potential expert users, who found that it could be useful for their work.

The objective of the thesis is to explore graph layout and edge clustering to improve graph visibility and the overall edge crossings. A summary of tools focusing on improving of graph visualisation is given. The thesis describes in more details a method of geometry--based edge clustering. Further, the method is implemented in a C++ library. The library itself can handle both simple and more complex graphs with a lot of vertices and edges.

In der heutigen Zeit bilden Netzwerke, auf technologischer sowie sozialer Ebene, die zentralen Systeme in der Informationsverarbeitung. Graphen stellen mit ihren mathematischen Eigenschaften eine geeignete Art der Beschreibung von Netzwerken dar. Seit 1741, beginnend mit Eulers Königsberger Brückenproblem (Euler 1741), werden Graphen für die Visualisierung thematisiert. Mit Beginn der Netzwerktechnik Mitte des 20. Jahrhunderts und der Entstehung digitaler sowie sozialer Netzwerke wächst das Interesse an der Visualisierung von Graphen. Dies setzt sich zu Beginn des 21. Jahrhunderts mit dem Aufbau von Firmennetzwerken und deren steigender Komplexität fort. Verschiedene Bereiche wie Psychologie, Mathematik, Kunst, Mensch-Maschine-Systemtechnik und Mediengestaltung beeinflussen die Ausprägung der Visualisierung von Graphen. Insbesondere psychologische Aspekte der visuellen Wahrnehmung und der kognitiven Leistung bilden die Grundlage zur Gestaltung von Graphen. Netzwerke beinhalten einen hohen Informationsgrad für den Rezipienten. Am Beispiel komplexer Firmennetzwerke stellt sich die Herausforderung nach einer effizienten und individuellen Exploration. Aktuelle Lösungen in Form von Tabellen und Datenbankabfragesprachen erzeugen eine hohe kognitive Last des Nutzers. Die Darstellung von Netzwerken in Graphen unterstützt den Nutzer in der Erfassung des Kontexts. Aktuelle Visualisierungskonzepte für Graphen bieten nur geringe Möglichkeiten der individuellen Exploration. Dies resultiert in einem „Lost-in-Context“-Effekt und einer erhöhten kognitiven Last. Das Visualisierungs- und Interaktionskonzept dieser Arbeit ermöglicht die Reduktion des „Lost-in-Context“-Effekts sowie der kognitiven Last. Dieser Forschungsansatz der Arbeit lässt sich dazu in drei Betrachtungsbereiche unterteilen: das Gedächtnismodell zur visuellen Kognition, das globale Strukturmittel und die lokalen Strukturmittel der graphenbasierten Exploration. Im Bereich der visuellen Kognition wird als Grundlage das Gedächtnismodell von Kosslyn diskutiert und adaptiert. Diese Adaption für die graphenbasierte Exploration zeigt die Verwendung von mentalen Karten des Nutzers. Dies basiert auf der Identifikation von semantischen und numerischen Werten der wahrgenommenen Objekte. Das globale Strukturmittel „Multi-Level-of-Detail“-Konzept basiert auf der Abbildung semantischer und numerischer Eigenschaften von wahrgenommenen Objekten auf eine mentale Karte. Das Gedächtnismodell von Kosslyn wird für die graphenbasierte Exploration angepasst und stellt die Grundlage für diese Abbildung dar. Das globale Strukturmittel ermöglicht dem Nutzer, parallel mehrere Detailstufen in der Graphvisualisierung zu erzeugen und individuell zu manipulieren. Dies reduziert die kognitive Last während der graphenbasierten Exploration. Die Einführung des globalen Strukturmittels fordert die Betrachtung lokaler Strukturmittel zur visuellen Wahrnehmung und Gestaltung des Graphen. Im Bereich der lokalen Strukturmittel werden die verschiedenen graphischen und interaktiven Mittel zur graphenbasierten Exploration diskutiert. Vor dem Hintergrund des aufgestellten Gedächtnismodells sowie den Grundlagen der Gestaltgesetze wird ein Baukasten visueller Elemente zur Gestaltung von Graphen betrachtet. Dieser wird durch die Diskussion der Eigenschaften der Graphobjekte, zum Beispiel: Position, Größe, Form, Clustern und Bündeln, beeinflusst. In einer prototypischen Umsetzung des Konzepts wird, im Vergleich zu Tabellen und Datenbankabfragesprachen, am Beispiel eines komplexen Firmennetzwerks die Reduktion der kognitiven Last gezeigt. Die Evaluation der kognitiven Last erfolgt mittels des NASA-TLX. In einem „Within-Subject“ Experiment werden Experten zu dem Konzept befragt. Dieses zeigt, dass im Vergleich zu aktuellen Graphdarstellungen eine Reduktion des „Lost-in-Context“-Effekts eintritt. Zusätzlich konnte gezeigt werden, dass nicht alle gestalterischen Mittel der lokalen Strukturmittel, im Vergleich zu aktuellen Lösungen und Konzepten, eine Verbesserung brachten. Die zentralen Aspekte des eingeführten Konzepts zeigen die Verwendung von mentalen Karten während der graphenbasierten Exploration komplexer Netzwerke.