• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 11
  • 5
  • 1
  • 1
  • Tagged with
  • 19
  • 19
  • 8
  • 6
  • 5
  • 5
  • 5
  • 5
  • 4
  • 4
  • 4
  • 3
  • 3
  • 3
  • 3
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

A Heuristic for the Constrained One-Sided Two-Layered Crossing Reduction Problem for Dynamic Graph Layout

Mai, Dung Hoang 01 January 2011 (has links)
Data in real-world graph drawing applications often change frequently but incrementally. Any drastic change in the graph layout could disrupt a user's "mental map." Furthermore, real-world applications like enterprise process or e-commerce graphing, where data change rapidly in both content and quantity, demand a comprehensive responsiveness when rendering the graph layout in a multi-user environment in real time. Most standard static graph drawing algorithms apply global changes and redraw the entire graph layout whenever the data change. The new layout may be very different from the previous layout and the time taken to redraw the entire graph degrades quickly as the amount of graph data grows. Dynamic behavior and the quantity of data generated by real-world applications pose challenges for existing graph drawing algorithms in terms of incremental stability and scalability. A constrained hierarchical graph drawing framework and modified Sugiyama heuristic were developed in this research. The goal of this research was to improve the scalability of the constrained graph drawing framework while preserving layout stability. The framework's use of the relational data model shifts the graph application from the traditional desktop to a collaborative and distributed environment by reusing vertex and edge information stored in a relational database. This research was based on the work of North and Woodhull (2001) and the constrained crossing reduction problem proposed by Forster (2004). The result of the constrained hierarchical graph drawing framework and the new Sugiyama heuristic, especially the modified barycenter algorithms, were tested and evaluated against the Graphviz framework and North and Woodhull's (2001) online graph drawing framework. The performance test results showed that the constrained graph drawing framework run time is comparable with the performance of the Graphviz framework in terms of generating static graph layouts, which is independent of database accesses. Decoupling graph visualization from the graph editing modules improved scalability, enabling the rendering of large graphs in real time. The visualization test also showed that the constrained framework satisfied the aesthetic criteria for constrained graph layouts. Future enhancements for this proposed framework include implementation of (1) the horizontal coordinate assignment algorithm, (2) drawing polylines for multilayer edges in the rendering module, and (3) displaying subgraphs for very large graph layouts.
2

GRAPH PATTERN MATCHING, APPROXIMATE MATCHING AND DYNAMIC GRAPH INDEXING

Jin, Wei 30 August 2011 (has links)
No description available.
3

Architecture autonome et distribuée d’adressage et de routage pour la flexibilité des communications dans l’internet / Autonomous and distributed architecture for addressing and routing to improve the flexibility of communications in internet

Cassagnes, Cyril 12 November 2012 (has links)
Les schémas de routage locaux basés sur des coordonnées prises dans le plan hyperbolique ont attiré un intérêt croissant depuis quelques années. Cependant, les solutions proposées sont toutes appliquées à des réseaux au topologie aléatoire et au nombre de nœuds limités. Dans le même temps, plusieurs travaux se sont concentrés sur la création de modèle topologique basé sur les lois de la géométrie hyperbolique. Dans ce cas, Il est montré que les graphes ont des topologies semblables à Internet et qu'un routage local hyperbolique atteint une efficacité proche de la perfection. Cependant, ces graphes ne garantissent pas le taux de réussite du routage même si aucune panne ne se produit. Dans cette thèse, l'objectif est de construire un système passant à l'échelle pour la création de réseau recouvrant capable de fournir à ses membres un service d'adressage et de routage résilient dans un environnement dynamique. Ensuite, nous étudions de quelle manière les réseaux P2PTV pourraient supporter un nombre d'utilisateur croissant. Dans cette thèse, nous essayons de répondre à cette question en étudiant les facteurs d'efficacité et de passage à l'échelle dans un système de diffusion vidéo P2P typique. Au travers des données fournies par Zattoo, producteur de réseau P2PTV, nous réalisons des simulations dont les résultats montrent qu'il y a encore des obstacles à surmonter avant que les réseaux P2P de diffusion vidéo puissent dépendre uniquement de leurs utilisateurs. / Local routing schemes based on virtual coordinates taken from the hyperbolic plane have attracted considerable interest in recent years.However, solutions have been applied to ad-hoc and sensor networks having a random topology and a limited number of nodes. In other hand, some research has focused on the creation of network topology models based on hyperbolic geometric laws. In this case, it has been shown that these graphs have an Internet-like topology and that local hyperbolic routing achieves a near perfect efficiency. However, with these graphs, routing success is not guaranteed even if no failures happen. In this thesis, we aim at building a scalable system for creating overlay networks on top of the Internet that would provide reliable addressing and routing service to its members in a dynamic environment.Next, we investigate how well P2PTV networks would support a growing number of users. In this thesis, we try to address this question by studying scalability and efficiency factors in a typical P2P based live streaming network. Through the use of the data provided by Zattoo a production P2PTV network, we carry out simulations whose results show that there are still hurdles to overcome before P2P based live streaming could depend uniquely of their users.
4

Une approche systémique à base d'agents et de graphes dynamiques pour modéliser l'interface logistique port-métropole / A systemic approach with an agent-based model and dynamic graphs to model the urban-port interface

Démare, Thibaut 27 September 2016 (has links)
Un système logistique est une composante essentielle d'un système spatial dans lequel les acteurs s'organisent autour d'infrastructures pour faire circuler des flux (de marchandises, d'information et financier) sur un territoire. L'organisation logistique globale résulte d'un processus auto-organisé et distribué de la part des acteurs. Ce travail vise à comprendre, à de multiples échelles, comment des acteurs autonomes et très hétérogènes (dans leurs modes de fonctionnements et dans leurs objectifs), s'organisent collectivement autour des infrastructures à leurs dispositions pour gérer des flux soumis à un ensemble de contraintes (temporelles, spatiales,...). On propose ici un modèle orienté agent permettant de simuler les processus de création et d'organisation des flux liés à la logistique sur un territoire. Le modèle prévoit de décrire l'interface entre les flux internationaux et les flux urbains afin de comprendre comment les dynamiques portuaires et urbaines cohabitent au sein du système. Le modèle intègre une dynamique structurelle et organisationnelle grâce aux graphes dynamiques afin de représenter l'évolution du système. Le modèle permet ainsi aux agents de s'adapter, comme dans la réalité, à des perturbations du système. / A logistic system is an essential component of a spatial system. Actors are organised around infrastructures in order to move different kinds of flow (of goods, of information, or financial) over a territory. The logistic organisation comes from an auto-organised and distributed process from the actors. This works aims to understand, at different scales, how autonomous and heterogeneous actors (according to their goals and methods to take decisions) are collectively organised around infrastructures to manage different kinds of flow, and despite numerous constraints (temporal, spatial,...). We propose an agent-based model which allows to simulate the processes to create and organise logistic flow over a territory. The model describes an interface between international and urban flow in order to understand how the port and urban dynamics work together. The model integrates a structural and organisational dynamics thanks to dynamic graphs in order to represent the evolution of this kind of system. Thus, the agents can adapt themselves to system's perturbations as in the reality.
5

Novel Frameworks for Mining Heterogeneous and Dynamic Networks

Fang, Chunsheng January 2011 (has links)
No description available.
6

Dynamic Graph Representation Learning on Enterprise Live Video Streaming Events

Stefanidis, Achilleas January 2020 (has links)
Enterprises use live video streaming as a mean of communication. Streaming high-quality video to thousands of devices in a corporate network is not an easy task; the bandwidth requirements often exceed the network capacity. For that matter, Peer-To-Peer (P2P) networks have been proven beneficial, as peers can exchange content efficiently by utilizing the topology of the corporate network. However, such networks are dynamic and their topology might not always be known. In this project we propose ABD, a new dynamic graph representation learning approach, which aims to estimate the bandwidth capacity between peers in a corporate network. The architecture of ABDis adapted to the properties of corporate networks. The model is composed of an attention mechanism and a decoder. The attention mechanism produces node embeddings, while the decoder converts those embeddings into bandwidth predictions. The model aims to capture both the dynamicity and the structure of the dynamic network, using an advanced training process. The performance of ABD is tested with two dynamic graphs which were produced by real corporate networks. Our results show that ABD achieves better results when compared to existing state-of-the-art dynamic graph representation learning models. / Företag använder live video streaming för både intern och extern kommunikation. Strömmning av hög kvalitet video till tusentals tittare i ett företagsnätverk är inte enkelt eftersom bandbreddskraven ofta överstiger kapaciteten på nätverket. För att minska lasten på nätverket har Peer-to-Peer (P2P) nätverk visat sig vara en lösning. Här anpassar sig P2P nätverket efter företagsnätverkets struktur och kan därigenom utbyta video data på ett effektivt sätt. Anpassning till ett företagsnätverk är ett utmanande problem eftersom dom är dynamiska med förändring över tid och kännedom över topologin är inte alltid tillgänglig. I det här projektet föreslår vi en ny lösning, ABD, en dynamisk approach baserat på inlärning av grafrepresentationer. Vi försöker estimera den bandbreddskapacitet som finns mellan två peers eller tittare. Architekturen av ABD anpassar sig till egenskaperna av företagsnätverket. Själva modellen bakom ABD använder en koncentrationsmekanism och en avkodare. Attention mekanismen producerar node embeddings, medan avkodaren konverterar embeddings till estimeringar av bandbredden. Modellen fångar upp dynamiken och strukturen av nätverket med hjälp av en avancerad träningsprocess. Effektiviteten av ABD är testad på två dynamiska nätverksgrafer baserat på data från riktiga företagsnätverk. Enligt våra experiment har ABD bättre resultat när man jämför med andra state-of the-art modeller för inlärning av dynamisk grafrepresentation.
7

Generalizing association rules in n-ary relations : application to dynamic graph analysis

Nguyen, Thi Kim Ngan 23 October 2012 (has links) (PDF)
Pattern discovery in large binary relations has been extensively studied. An emblematic success in this area concerns frequent itemset mining and its post-processing that derives association rules. In this case, we mine binary relations that encode whether some properties are satisfied or not by some objects. It is however clear that many datasets correspond to n-ary relations where n > 2. For example, adding spatial and/or temporal dimensions (location and/or time when the properties are satisfied by the objects) leads to the 4-ary relation Objects x Properties x Places x Times. Therefore, we study the generalization of association rule mining within arbitrary n-ary relations: the datasets are now Boolean tensors and not only Boolean matrices. Unlike standard rules that involve subsets of only one domain of the relation, in our setting, the head and the body of a rule can include arbitrary subsets of some selected domains. A significant contribution of this thesis concerns the design of interestingness measures for such generalized rules: besides a frequency measures, two different views on rule confidence are considered. The concept of non-redundant rules and the efficient extraction of the non-redundant rules satisfying the minimal frequency and minimal confidence constraints are also studied. To increase the subjective interestingness of rules, we then introduce disjunctions in their heads. It requires to redefine the interestingness measures again and to revisit the redundancy issues. Finally, we apply our new rule discovery techniques to dynamic relational graph analysis. Such graphs can be encoded into n-ary relations (n ≥ 3). Our use case concerns bicycle renting in the Vélo'v system (self-service bicycle renting in Lyon). It illustrates the added-value of some rules that can be computed thanks to our software prototypes.
8

Compile- and run-time approaches for the selection of efficient data structures for dynamic graph analysis

Schiller, Benjamin, Deusser, Clemens, Castrillon, Jeronimo, Strufe, Thorsten 11 January 2017 (has links) (PDF)
Graphs are used to model a wide range of systems from different disciplines including social network analysis, biology, and big data processing. When analyzing these constantly changing dynamic graphs at a high frequency, performance is the main concern. Depending on the graph size and structure, update frequency, and read accesses of the analysis, the use of different data structures can yield great performance variations. Even for expert programmers, it is not always obvious, which data structure is the best choice for a given scenario. In previous work, we presented an approach for handling the selection of the most efficient data structures automatically using a compile-time approach well-suited for constant workloads. We extend this work with a measurement study of seven data structures and use the results to fit actual cost estimation functions. In addition, we evaluate our approach for the computations of seven different graph metrics. In analyses of real-world dynamic graphs with a constant workload, our approach achieves a speedup of up to 5.4× compared to basic data structure configurations. Such a compile-time based approach cannot yield optimal results when the behavior of the system changes later and the workload becomes non-constant. To close this gap we present a run-time approach which provides live profiling and facilitates automatic exchanges of data structures during execution. We analyze the performance of this approach using an artificial, non-constant workload where our approach achieves speedups of up to 7.3× compared to basic configurations.
9

Nutzung mobiler Endgeräte zur Analyse von dynamischen Graphen im Raum vor einer Displaywall

Ragozina, Elizaveta 18 January 2017 (has links) (PDF)
Eine Graph-Visualisierung von Daten findet Einsatz in verschiedenen Domänen und erleichtert die Gewinnung von Erkenntnissen über Relationen. Viele Datensätze haben eine dynamische Natur und verändern sich über die Zeit. Dynamische Graphen kodieren die temporalen Änderungen der Objekte und ihrer Relationen. Der Vorteil der hochauflösenden Displaywand besteht darin, dass durch einen vergrößerten Darstellungsraum ein guter Überblick über die strukturellen Zusammenhänge entsteht. Der Einsatz der heutzutage sehr verbreiteten mobilen Endgeräte bietet eine lokale nutzerspezifische Darstellung für die Exploration und Manipulation der Graphen einschließlich ihrer dynamischen Komponente. Während sich viele Arbeiten auf die Analyse statischer Strukturen fokussieren, wird das Problem der Exploration und Visualisierung dynamischer Graphen vergleichsweise wenig adressiert. In der vorliegenden Arbeit werden die grundlegenden Aufgaben für die dynamischen Graphen sowie der Stand der Forschung über den interaktiven Raum der kombinierten Anwendung Displaywand und Mobilgerät untersucht. Auf dieser Basis werden die Interaktionskonzepte für die Exploration dynamischer Graphen und die Visualisierung der Änderungen erarbeitet. Der interaktive Raum bietet dabei die räumlichen Freiheitsgrade für die Gestaltung der Interaktionen. Die entstandene Konzeption dient abschließend als Grundlage für die prototypische Umsetzung in einem existierenden Projekt zur Exploration von Graphen mithilfe mobiler Endgeräte. / Graph visualization for data is used in various domains. It facilitates the extraction of knowledges about the relationships. Many datasets have a dynamic nature and change over time. Dynamic graphs ecode the temporal changes of objects and their relations. The advantage of the high-resolution displaywall is providing a good overview of the structural relations caused by an enlarged representation space. The use of nowadays widespread mobile devices provides a local user-specific view for the exploration of the graphs including their dynamic component. While many studies focuse on the analysis of static data structures, the issue of exploration and visualization of dynamic graphs is adressed by only a few works. This thesis investigates the basic tasks for dynamic graphs and state of research into the interaction space of combined applications of displaywall and mobile device. On this basis the interaction concepts for the exploration of dynamic graphs and the visualization of the changes are developed. The interaction space provides the spatial degrees of freedom for the design of interactions. The resulting set of concepts is the basis for the prototypical implementation in the existing project for the exploration of graphs using the mobile devices.
10

Triangle packing for community detection : algorithms, visualizations and application to Twitter's network / La détection de communautés basée sur la triangulation de graphes : algorithmes, visualisations et application aux réseaux de tweets

Abdelsadek, Youcef 31 March 2016 (has links)
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

Page generated in 0.1423 seconds