No description available.

<p dir="ltr">This dissertation introduces a novel graph embedding paradigm, leveraging a force-directed scheme for graph embedding. In the field of graph embedding, an "embedding" refers to the process of transforming elements of a graph such as nodes, or edges, or potentially other structural information of the graph into a low-dimensional space, typically a vector space, while preserving the graph's structural properties as much as possible. The dimensions of the space are supposed to be much smaller than the elements of the graph that are to be embedded. This transformation results in a set of vectors, with each vector representing a node (or edge) in the graph. The goal is to capture the essence of the graph's topology, node connectivity, and other relevant features in a way that facilitates easier processing by machine learning algorithms, which often perform better with input data in a continuous vector space.</p><p dir="ltr">The main premise of kinematics-based force-directed graph embedding is that the nodes are considered as massive mobile objects that can be moved around in the embedding space under force. In this PhD thesis, we devised a general theoretical framework for the proposed graph embedding paradigm and provided the mathematical proof of convergence given the required constraints. From this point on, the objective was to explore force functions and parameters and methods of applying them in terms of their efficacy regarding graph embedding applications. We found some force functions that outperformed the state-of-the-art methods.</p><p dir="ltr">The author of this manuscript believes that the proposed paradigm will open a new chapter, specifically in the field of graph embedding and generally in the field of embedding.</p>

Esta dissertação apresenta MagnetViz, uma técnica para visualização de grafos. Enquanto a maior parte das técnicas visualizam um layout de grafo estático pre-computado, MagnetViz permite que usuários dinamicamente alterem o layout de um grafo de forma a melhor satisfazer suas necessidades. Isso é feito ao construir em cima da metáfora de física de algoritmos dirigidos à força para proporcionar aos usuários imãs virtuais, que podem atrair nodos que satisfazem um conjunto de critérios associados a eles. Critérios podem ser baseados na topologia ou semântica do grafo. Através de boundary shapes, que são simples formas geométricas que podem ser colocadas ao redor de imãs, usuários podem também definir regiões na cena onde os nodos atraídos devem permanecer. Grafos são descritos usando GraphML, uma linguagem baseada em XML, que permite a especificação dos nodos e arestas e de atributos para essas entidades. Após a submissão de um grafo como entrada, MagnetViz o exibe utilizando uma versão modificada do algoritmo clássico de Fruchterman and Rheingold, e permite que usuário, a seguir, insira imãs na cena. Usuários podem construir as condições associadas aos imãs utilizando os atributos dos nodos e arestas, além de atributos topológicos próprios de grafos. Para a avaliação de MagnetViz, foi primeiro analisado o desempenho da técnica ao ajudar usuários a executarem tarefas definidas por uma taxonomia de tarefas de visualização de grafos encontrada na literatura. Então, MagnetViz foi testada em um contexto prático através de um estudo de caso. Uma rede de co-autorias foi escolhida como conjunto de dados e o protótipo de MagnetViz foi inicialmente usado para responder questões relevantes a esses dados e então testado por um grupo de potenciais usuários, que tinham de usa-lo para responder essas mesmas perguntas. Após testar a aplicação, os sujeiotos receberam questionários sobre usas opiniões quanto a usabilidade, aplicabilidade, relevância e resultados visuais da técnica. Enquanto alguns aspectos da técnica ainda podem ser melhorados, os resultados da avaliação provaram que MagnetViz é uma abordagem válida para interação com visualizações de grafos. / This dissertation presents MagnetViz, a technique for the visualization of graphs. While most techniques visualize a static pre-computed graph layout, MagnetViz allows users to dynamically alter the layout of a graph to better satisfy their needs. This is done by building on the physics metaphor of force-directed algorithms to provide users with virtual magnets, which can attract nodes that fulfill a set of criteria associated with them. Criteria can be based on either the topology or semantics of the graph. Through boundary shapes, which are simple geometric shapes that can be placed around magnets, users can also define regions within the scene where the attracted nodes should remain. Graphs are described in GraphML, a XML-like description language which allows the specification of nodes and edges between nodes as well as attributes associated to nodes and edges. After loading a graph, Magnetviz displays it using a slightly modified version of the classical Fruchterman and Reingold' algorithm, and allows the user to insert magnets. Users can build the criteria associated with the magnets using the attributes of nodes and/or edges, besides the common graphs' topological attributes. For MagnetViz's evaluation, it was first analyzed how the technique fared in aiding users to perform tasks defined by a graph visualization task taxonomy described in the literature. Then, MagnetViz was tested within a practical context by means of a case study. A co-authorship network was chosen as the target dataset. The MagnetViz prototype was initially used to answer questions relevant to this dataset and then tested by a group of potential users, who had to use it to answer these same questions. After trying the application, subjects answered questionnaires about their opinion on the technique's usability, applicability, relevance and visual results. While some aspects of the technique should still be refined, results of the evaluation proved MagnetViz to be a valid approach when it comes to interaction with graph visualizations.

Esta dissertação apresenta MagnetViz, uma técnica para visualização de grafos. Enquanto a maior parte das técnicas visualizam um layout de grafo estático pre-computado, MagnetViz permite que usuários dinamicamente alterem o layout de um grafo de forma a melhor satisfazer suas necessidades. Isso é feito ao construir em cima da metáfora de física de algoritmos dirigidos à força para proporcionar aos usuários imãs virtuais, que podem atrair nodos que satisfazem um conjunto de critérios associados a eles. Critérios podem ser baseados na topologia ou semântica do grafo. Através de boundary shapes, que são simples formas geométricas que podem ser colocadas ao redor de imãs, usuários podem também definir regiões na cena onde os nodos atraídos devem permanecer. Grafos são descritos usando GraphML, uma linguagem baseada em XML, que permite a especificação dos nodos e arestas e de atributos para essas entidades. Após a submissão de um grafo como entrada, MagnetViz o exibe utilizando uma versão modificada do algoritmo clássico de Fruchterman and Rheingold, e permite que usuário, a seguir, insira imãs na cena. Usuários podem construir as condições associadas aos imãs utilizando os atributos dos nodos e arestas, além de atributos topológicos próprios de grafos. Para a avaliação de MagnetViz, foi primeiro analisado o desempenho da técnica ao ajudar usuários a executarem tarefas definidas por uma taxonomia de tarefas de visualização de grafos encontrada na literatura. Então, MagnetViz foi testada em um contexto prático através de um estudo de caso. Uma rede de co-autorias foi escolhida como conjunto de dados e o protótipo de MagnetViz foi inicialmente usado para responder questões relevantes a esses dados e então testado por um grupo de potenciais usuários, que tinham de usa-lo para responder essas mesmas perguntas. Após testar a aplicação, os sujeiotos receberam questionários sobre usas opiniões quanto a usabilidade, aplicabilidade, relevância e resultados visuais da técnica. Enquanto alguns aspectos da técnica ainda podem ser melhorados, os resultados da avaliação provaram que MagnetViz é uma abordagem válida para interação com visualizações de grafos. / This dissertation presents MagnetViz, a technique for the visualization of graphs. While most techniques visualize a static pre-computed graph layout, MagnetViz allows users to dynamically alter the layout of a graph to better satisfy their needs. This is done by building on the physics metaphor of force-directed algorithms to provide users with virtual magnets, which can attract nodes that fulfill a set of criteria associated with them. Criteria can be based on either the topology or semantics of the graph. Through boundary shapes, which are simple geometric shapes that can be placed around magnets, users can also define regions within the scene where the attracted nodes should remain. Graphs are described in GraphML, a XML-like description language which allows the specification of nodes and edges between nodes as well as attributes associated to nodes and edges. After loading a graph, Magnetviz displays it using a slightly modified version of the classical Fruchterman and Reingold' algorithm, and allows the user to insert magnets. Users can build the criteria associated with the magnets using the attributes of nodes and/or edges, besides the common graphs' topological attributes. For MagnetViz's evaluation, it was first analyzed how the technique fared in aiding users to perform tasks defined by a graph visualization task taxonomy described in the literature. Then, MagnetViz was tested within a practical context by means of a case study. A co-authorship network was chosen as the target dataset. The MagnetViz prototype was initially used to answer questions relevant to this dataset and then tested by a group of potential users, who had to use it to answer these same questions. After trying the application, subjects answered questionnaires about their opinion on the technique's usability, applicability, relevance and visual results. While some aspects of the technique should still be refined, results of the evaluation proved MagnetViz to be a valid approach when it comes to interaction with graph visualizations.

Esta dissertação apresenta MagnetViz, uma técnica para visualização de grafos. Enquanto a maior parte das técnicas visualizam um layout de grafo estático pre-computado, MagnetViz permite que usuários dinamicamente alterem o layout de um grafo de forma a melhor satisfazer suas necessidades. Isso é feito ao construir em cima da metáfora de física de algoritmos dirigidos à força para proporcionar aos usuários imãs virtuais, que podem atrair nodos que satisfazem um conjunto de critérios associados a eles. Critérios podem ser baseados na topologia ou semântica do grafo. Através de boundary shapes, que são simples formas geométricas que podem ser colocadas ao redor de imãs, usuários podem também definir regiões na cena onde os nodos atraídos devem permanecer. Grafos são descritos usando GraphML, uma linguagem baseada em XML, que permite a especificação dos nodos e arestas e de atributos para essas entidades. Após a submissão de um grafo como entrada, MagnetViz o exibe utilizando uma versão modificada do algoritmo clássico de Fruchterman and Rheingold, e permite que usuário, a seguir, insira imãs na cena. Usuários podem construir as condições associadas aos imãs utilizando os atributos dos nodos e arestas, além de atributos topológicos próprios de grafos. Para a avaliação de MagnetViz, foi primeiro analisado o desempenho da técnica ao ajudar usuários a executarem tarefas definidas por uma taxonomia de tarefas de visualização de grafos encontrada na literatura. Então, MagnetViz foi testada em um contexto prático através de um estudo de caso. Uma rede de co-autorias foi escolhida como conjunto de dados e o protótipo de MagnetViz foi inicialmente usado para responder questões relevantes a esses dados e então testado por um grupo de potenciais usuários, que tinham de usa-lo para responder essas mesmas perguntas. Após testar a aplicação, os sujeiotos receberam questionários sobre usas opiniões quanto a usabilidade, aplicabilidade, relevância e resultados visuais da técnica. Enquanto alguns aspectos da técnica ainda podem ser melhorados, os resultados da avaliação provaram que MagnetViz é uma abordagem válida para interação com visualizações de grafos. / This dissertation presents MagnetViz, a technique for the visualization of graphs. While most techniques visualize a static pre-computed graph layout, MagnetViz allows users to dynamically alter the layout of a graph to better satisfy their needs. This is done by building on the physics metaphor of force-directed algorithms to provide users with virtual magnets, which can attract nodes that fulfill a set of criteria associated with them. Criteria can be based on either the topology or semantics of the graph. Through boundary shapes, which are simple geometric shapes that can be placed around magnets, users can also define regions within the scene where the attracted nodes should remain. Graphs are described in GraphML, a XML-like description language which allows the specification of nodes and edges between nodes as well as attributes associated to nodes and edges. After loading a graph, Magnetviz displays it using a slightly modified version of the classical Fruchterman and Reingold' algorithm, and allows the user to insert magnets. Users can build the criteria associated with the magnets using the attributes of nodes and/or edges, besides the common graphs' topological attributes. For MagnetViz's evaluation, it was first analyzed how the technique fared in aiding users to perform tasks defined by a graph visualization task taxonomy described in the literature. Then, MagnetViz was tested within a practical context by means of a case study. A co-authorship network was chosen as the target dataset. The MagnetViz prototype was initially used to answer questions relevant to this dataset and then tested by a group of potential users, who had to use it to answer these same questions. After trying the application, subjects answered questionnaires about their opinion on the technique's usability, applicability, relevance and visual results. While some aspects of the technique should still be refined, results of the evaluation proved MagnetViz to be a valid approach when it comes to interaction with graph visualizations.

The need to visualise sets of data and networks within a company is awell-known task. In this thesis, research has been done of techniques used to visualize complex networks in order to find out if there is a generalized optimal technique that can visualize complex networks. For this purpose an application was implemented containing three different views, which were selected from the research done on the subject. As it turns out, it points toward that there is no generalized optimal technique that can be used to default visualize complex networksin a satisfactory way. A definit conclusion could not be given due to the fact that all visualization techniques which could not be evaluated within this thesis timeframe. / Behov av att visualisera data inom bolag är ett känt faktum. Denna avhandling har använt olika tekniker för att undersöka om det existerar en generell optimal teknik som kan tillämpas vid visualisering av komplexa nätverk. Vid genomförandet implementerades en applikation med tre olika vyer som valdes ut baserat på forskning inom det valda området. Resultatet visade att det inte existerar en generell optimalteknik som kan tillämpas vid visualisering av komplexa nätverk, det medför att en definitiv slutsats inte kan dras. Det på grund av att alla de visualiseringstekniker som existerar inte kunde undersökas inom examensarbetets tidsram.

Cette thèse se concentre sur la problématique suivante : comment assister un utilisateur novice pour l'aider à obtenir un dessin de son graphe qui soit adapté à ses besoins ? En effet, les méthodes de dessins actuelles, très nombreuses, nécessitent une grande expertise pour obtenir un dessin de bonne qualité. Or, par manque d'expertise, les utilisateurs novices ne peuvent pour l'instant pas produire des dessins d'une telle qualité à partir de leurs données. La solution proposée consiste à mettre en place un système interactif proposant à l'utilisateur différents dessins pour un même graphe afin qu'il obtienne un résultat qui réponde correctement à ses besoins. Ce système se base sur un algorithme de force modifié utilisé par un système d'algorithme génétique hautement modulable. L'objectif de la modification apportée à l'algorithme de dessin étant de pouvoir générer plusieurs dessins intéressants pour un même graphe. / The main objective of this thesis is to deal with assisting a novice user in drawinga graph which conforms to his/her needs. Currently, a lot of different methods for graph drawing exist, but they need an high level of expertise to be efficiently used. However, novice users don't have this kind of expertise, and thus they usually use the most common drawing methods. We design a solution to deal with this problem using an interactive system which generate several different drawings for a graph and then let the user choose which best conform to his/her constraints. This system is based on a modified force-directed algorithm controlled by a highly parameterisable genetic algorithm. The aim of the modification applied to the force-directed algorithm is to generate several different and interesting drawings of the same graph, by setting the parameters for each vertex (instead of global graph values).

Displaying the architecture of a software system is not a simple task. Showing all of the available information will unnecessarily complicate the view, while showing too little might render the view unhelpful. Furthermore, showing the dynamics of the operation of such a system is even more challenging. This thesis project describes the development of a graphical tool that can both display the configuration of an advanced authentication, authorization, and accounting (AAA) system and the messages passed between nodes in the system.  The solution described uses force-based graph layouts coupled with adaptive filters as well as vector-based rendering to deliver a view of the status of the system. Force-based layout spreads out the nodes in an adaptive fashion. The adaptive filters starts by showing what is most often the most relevant information, but can be configured by the user. Finally, the vector based rendering offers unlimited zoom into the individual nodes in the graph in order to display additional detailed information. Unified Modeling Language (UML) sequence charts are used to display the message flow inside the system (both between nodes and inside individual nodes). To validate the results of this thesis project each iteration of the design was evaluated through meetings with the staff at Aptilo Networks. These meetings provided feedback on the direction the project was taking as well as provided input (such as ideas for features to implement). The result of this thesis project shows a way to display the status of an AAA system with multiple properties displayed at the same time. It combines this with a view of the flow of messages and application of policies in the network via a dynamically generated UML sequence diagram. As a result human operators are able to see both the system’s architecture and the dynamics of its operation using the same user interface. This integrated view should enable more effective management of the AAA system and facilitate responding to problems and attacks. / Att visualisera arkitekturen av ett mjukvarusystem är inte lätt. Visas all tillgänglig information så blir vyn för komplicerad medan ifall för lite visas så blir vyn onödig. Att samtidigt visa dynamiken som uppstår när systemet arbetar är ytterligare en utmaning. Detta examensprojektet beskriver hur utvecklingen av ett grafiskt verktyg, som både kan visa konfigurationen av ett avancerat autentisering-, tillåtelse- och bokförings-system (AAA) och meddelanden som skickas mellan noder i systemet.&lt;p&gt; Lösningen använder en kraftriktad graflayout tillsammans med adaptiva filter och vektorbaserad rendering för att visa en vy av systemets status. De adaptiva filtren börjar med att visa den information som oftast är mest relevant men kan ställas in av användaren. Nyttjandet av vektorbaserad grafik tillhandahåller obegränsade möjligheter för användaren att zooma in på delar av grafen för att visa mer detaljerad information. UML sekvensdiagram används för att visa medelandeflödet inuti systemet (både mellan noder och inuti noder). För att utvärdera resultatet av examensprojektet blev varje iteration av designen utvärderad vid möten med personalen på Aptilo Networks. Dessa möten gav återkoppling på vilken rikting projektet tog samt input med t. ex. id´eer på nya egenskaper att lägga till. Resultatet av detta examensarbete visar ett sätt att visa statusen för ett AAA system med många av systemets egenskaper visade samtidigt. Det kombinerar detta med en vy av flödet av meddelanden och applikationpolicies i nätverket via ett dynamiskt genererat UML sekvensdiagram. Resultatet av detta är att mänskliga operatörer kan se både systemets arkitektur och dynamiken i hur det fungerar i samma gränssnitt. Detta gränssnitt bör möjliggöra mer effektiv hantering av AAA systemet och underlätta lösningar på både problem i systemet och attacker mot systemet.

We propose a real-time system to visualize multi-viewpoint visibility information for terrains, supporting flight path optimization for view coverage or vehicle exposure to ground. A volume rendered display and a haptic interface assist the user in selecting, assessing, and refining the computed flight path. We construct a three-dimensional scalar field representing the visibility of a point above the terrain, describe an efficient algorithm to compute visibility, and develop visual and haptic schemes to interact with the visibility field. Given the origin and destination, the desired flight path is computed using an efficient simulation of an articulated rope under the influence of the visibility gradient. The simulation framework also accepts user input, via the haptic interface, thereby allowing manual refinement of the flight path.

I den här studien utformas och implementeras en prototyp av ett automatiskt grafritningsverktyg. Under processen analyseras och evalueras flera välkända och viktiga algoritmer. Algoritmen som används i prototypen modifieras och förbättras för att uppfylla företaget FindOuts speciella krav. Dessutom strävar vi efter att hitta förbättringar med avseende på visualisering och prestanda för algoritmer genom att studera aktuella arbeten. Genom litteraturoch empiriska studier, drar vi slutsatsen att Sugiyama-ramverket passar bäst för hierarkiska och liknande grafer. Den genererade grafritningen är stabil, läsbar och följer de flesta estetiska kriterier. Dessutom används kraftbaserad layout för att placera de icke sammanhängande delgraferna på lämpliga positioner. Attraktionsoch repulsionskraft mellan delgrafer gör att hela grafen blir kompakt utan överlappning, vilket är ett av företagets krav. Några problem såsom att lägga till nya noder och kanter är inte helt lösta på grund av konflikten mellan estetiska kriterier och användarkrav. Vi anser att en algoritm baserad på användarkrav är lämplig att integreras i en nästa generation av vår prototyp. En del av heuristiken kan också förbättras. Vi presenterar möjliga lösningar och föreslår att en noggrann jämförelse mellan olika algoritmer bör tas upp i framtida arbete. / A prototype of an automatic graph drawing tool was designed and implemented in this thesis project. In this process various well-known and important algorithms were analyzed and evaluated. Algorithms applied in the prototype were modified and improved to fulfill FindOut’s special requirements. Besides this, a pursuit of an improvement on visualizations and performance of algorithms was conducted by studying the latest research works. Through these theoretical and empirical studies, we concluded that the Sugiyama framework is the most suitable algorithm to generate the workflow type of graph. The generated graphs are stable, readable and follows most aesthetic standards. Furthermore, force-directed algorithms were utilized to put graphs at appropriate positions. The attraction and repulsion force between sub-graphs can make the whole graph compact without overlapping, which fulfills the company’s requirement. However some of the problems, such as importing new nodes and edges, have not been perfectly resolved due to the conflict between the aesthetic and user requirements. Thus we think that a user-constraints based algorithm is suitable to be integrated into our next generation prototype. Some of the heuristics also have room for improvement. We discussed the possible solutions and suggested that a comparative study of different algorithms should be included in the future work.