Dissertations / Theses on the topic 'Node embeddings'

Goal of this master's thesis was in cooperation with the company Avast to design a system, which can extract knowledge from a database of graphs. Graphs, used for data mining, describe behaviour of computer systems and they are anonymously inserted into the company's database from systems of the company's products users. Each graph in the database can be assigned with one of two labels: clean or malware (malicious) graph. The task of the proposed self-learning system is to find clusters of graphs in the graph database, in which the classes of graphs do not mix. Graph clusters with only one class of graphs can be interpreted as different types of clean or malware graphs and they are a useful source of further analysis on the graphs. To evaluate the quality of the clusters, a custom metric, named as monochromaticity, was designed. The metric evaluates the quality of the clusters based on how much clean and malware graphs are mixed in the clusters. The best results of the metric were obtained when vector representations of graphs were created by a deep learning model (variational  graph autoencoder with two relation graph convolution operators) and the parameterless method MeanShift was used for clustering over vectors.

There are many machine learning techniques that cannot be performed on graph-data. Techniques such as graph embedding, i.e mapping a graph to a vector, can open up a variety of machine learning solutions. This thesis addresses to what extent static graph embedding techniques can capture important characteristics of an IT-architecture graph, with the purpose of embedding the graphs in a common euclidean vector space that can serve as the state space in a reinforcement learning setup. The metric used for evaluating the performance of the embedding is the security of the graph, i.e the time it would take for an unauthorized attacker to penetrate the IT-architecture graph. The algorithms evaluated in this work are the node embedding methods node2vec and gat2vec and the graph embedding method graph2vec. The predictive results of the embeddings are compared with two baseline methods. The results of each of the algorithms mostly display a significant predictive performance improvement compared to the baseline, where the F1 score in some cases is doubled. Indeed, the results indicate that static graph embedding methods can in fact capture some information about the security of an IT-architecture. However, no conclusion can be made whether a static graph embedding is actually the best contender for posing as the state space in a reinforcement learning framework. To make a certain conclusion other options has to be researched, such as dynamic graph embedding methods.
Det är många maskininlärningstekniker som inte kan appliceras på data i form av en graf. Tekniker som graph embedding, med andra ord att mappa en graf till ett vektorrum, can öppna upp för en större variation av maskininlärningslösningar. Det här examensarbetet evaluerar hur väl statiska graph embeddings kan fånga viktiga säkerhetsegenskaper hos en IT-arkitektur som är modellerad som en graf, med syftet att användas i en reinforcement learning algoritm. Dom egenskaper i grafen som används för att validera embedding metoderna är hur lång tid det skulle ta för en obehörig attackerare att penetrera IT-arkitekturen. Algorithmerna som implementeras är node embedding metoderna node2vec och gat2vec, samt graph embedding metoden graph2vec. Dom prediktiva resultaten är jämförda med två basmetoder. Resultaten av alla tre metoderna visar tydliga förbättringar relativt basmetoderna, där F1 värden i några fall uppvisar en fördubbling. Det går alltså att dra slutsatsen att att alla tre metoder kan fånga upp säkerhetsegenskaper i en IT-arkitektur. Dock går det inte att säga att statiska graph embeddings är den bästa lösningen till att representera en graf i en reinforcement learning algoritm, det finns andra komplikationer med statiska metoder, till exempel att embeddings från dessa metoder inte kan generaliseras till data som inte var använd till träning. För att kunna dra en absolut slutsats krävs mer undersökning, till exempel av dynamiska graph embedding metoder.

L’informatique en nuage (Cloud computing) est une technologie prometteuse facilitant la réservation et de l'utilisation des ressources d’une manière flexible et dynamique. En plus des ressources informatiques traditionnelles, les utilisateurs du Cloud attendent à ce que des ressources réseaux leurs soient dédiées afin de faciliter le déploiement des fonctions et services réseau. Ils souhaitent pouvoir gérer l'ensemble d'un réseau virtuel (VN) ou infrastructure. Ainsi, les fournisseurs du Cloud doivent déployer des solutions de provisionnement des ressources dynamiques et adaptatives afin d’allouer des réseaux virtuels qui reflètent les besoins variables dans le temps des applications hébergés dans le Cloud. L’état de l’art sur l’allocation des réseaux virtuels s’est uniquement intéressé au problème de mapping des nœuds et liens virtuels composant une demande de réseau virtuel dans les nœuds et chemins du réseau de physique (infrastructure Cloud), connu sous le nom du problème de virtual network embedding (VNE). Peu d'attention a été accordée à la gestion des ressources allouées pour répondre en permanence aux besoins variables des réseaux virtuels hébergés dans le réseau physique et afin d'assurer une utilisation efficace des ressources. L'objectif de cette thèse est de permettre l'allocation des réseaux virtuels d’une manière dynamique et préventive pour faire face aux fluctuations de la demande au cours de la durée de vie du réseau virtuel, et pour améliorer l'utilisation des ressources du substrat. Pour atteindre ces objectifs, la thèse propose d'adaptation des algorithmes d'allocation des ressources pour répondre à l’évolution des demandes du réseau virtuel. Premièrement, nous allons étudier en profondeur l'extension d'un nœud virtuel, à savoir le cas où un nœud virtuel hébergé nécessite plus de ressources alors le nœud physique qui l’héberge n'a pas assez de ressources disponibles. Deuxièmement, nous allons améliorer la proposition précédente afin de considérer la rentabilité du réseau de substrat. Et enfin, nous allons gérer la variation de la demande en bande passante dans les liens virtuels. Par conséquent, la première partie de cette thèse fournit un algorithme heuristique qui traite la fluctuation de la demande dans les nœuds virtuels. L'idée principale de l'algorithme est de réallouer un ou plusieurs nœuds virtuels co-localisés dans du nœud de substrat, qui héberge le nœud en évolution pour libérer des ressources (ou faire de la place) pour le nœud en évolution. En plus de réduire le coût de réaffectation, notre proposition prend en compte et réduit l'interruption de service pendant la migration. L'algorithme précédent a été étendu pour concevoir un algorithme de reconfiguration préventif pour améliorer la rentabilité du réseau physique. En fait, notre proposition profite de la perturbation de la demande de ressources pour ranger le réseau physique à un coût minimal et sans perturbations. Lors de la réaffectation des nœuds virtuels pour faire place pour le nœud en extension, nous réaffectant les liens virtuels les plus congestionnées dans des ressources physiques moins saturées afin d’équilibrer la charge sur le réseau. Notre proposition offre le meilleur compromis entre le coût de réaffectation et l'équilibrage des charges. Enfin, un framework distribué, parallèle et à vue locale a été mis au point pour traiter toutes les formes de fluctuations de la demande en bande passante dans les liens virtuels. Elle se compose d'un contrôleur et trois algorithmes exécutés dans chaque nœud du substrat d'une manière distribuée et parallèle. Le framework est basé sur l'auto-stabilisation, et peut gérer de nombreuses et différentes formes de variations de la demande de bande passante simultanément
Cloud computing is a promising technology enabling IT resources reservation and utilization on a pay-as-you-go manner. In addition to the traditional computing resources, cloud tenants expect compete networking of their dedicated resources to easily deploy network functions and services. They need to manage an entire Virtual Network (VN) or infrastructure. Thus, Cloud providers should deploy dynamic and adaptive resource provisioning solutions to allocate virtual networks that reflect the time-varying needs of Cloud-hosted applications. Prior work on virtual network resource provisioning only focused on the problem of mapping the virtual nodes and links composing a virtual network request to the substrate network nodes and paths, known as the Virtual network embedding (VNE) problem. Little attention was paid to the resource management of the allocated resources to continuously meet the varying demands of embedded virtual networks and to ensure efficient substrate resource utilization. The aim of this thesis is to enable dynamic and preventive virtual network resources provisioning to deal with demand fluctuation during the virtual network lifetime, and to enhance the substrate resources usage. To reach these goals, the thesis proposes adaptive resource allocation algorithms for evolving virtual network requests. We adress the extension of an embedded virtual node requiring more resources and consider the substrate network profitability. We also deal with the bandwidth demand variation in embedded virtual links. We first provide a heuristic algorithm to deal with virtual nodes demand fluctuation. The work is extended by designing a preventive re-configuration scheme to enhance substrate network profitability. Finally, a distributed, local-view and parallel framework was devised to handle embedded virtual links bandwidth fluctuations. The approach is composed of a controller and three algorithms running in each substrate node in a distributed and parallel manner. The framework is based on the self-stabilization approach, and can manage various forms of bandwidth demand variations simultaneously

There has been an explosion of network data in the physical, chemical, biological, computational, and social sciences in the last few decades. Node embeddings, i.e., Euclidean-space representations of nodes in a network, make it possible to apply to network data, tools and algorithms from multivariate statistics and machine learning that were developed for Euclidean-space data. Random walk node embeddings are a class of recently developed node embedding techniques where the vector representations are learned by optimizing objective functions involving skip-bigram statistics computed from random walks on the network. They have been applied to many supervised learning problems such as link prediction and node classification and have demonstrated state-of-the-art performance. Yet, their properties remain poorly understood. This dissertation studies random walk based node embeddings in an unsupervised setting within the context of capturing hidden block structure in the network, i.e., learning node representations that reflect their patterns of adjacencies to other nodes. This doctoral research (i) Develops VEC, a random walk based unsupervised node embedding algorithm, and a series of relaxations, and experimentally validates their performance for the community detection problem under the Stochastic Block Model (SBM). (ii) Characterizes the ergodic limits of the embedding objectives to create non-randomized versions. (iii) Analyzes the embeddings for expected SBM networks and establishes certain concentration properties of the limiting ergodic objective in the large network asymptotic regime. Comprehensive experimental results on real world and SBM random networks are presented to illustrate and compare the distributional and block-structure properties of node embeddings generated by VEC and related algorithms. As a step towards theoretical understanding, it is proved that for the variants of VEC with ergodic limits and convex relaxations, the embedding Grammian of the expected network of a two-community SBM has rank at most 2. Further experiments reveal that these extensions yield embeddings whose distribution is Gaussian-like, centered at the node embeddings of the expected network within each community, and concentrate in the linear degree-scaling regime as the number of nodes increases.
2023-09-24T00:00:00Z

碩士
國立臺灣大學
資訊網路與多媒體研究所
105
Multi-relational networks are ubiquitous in real world. It is, however, difficult to be analyzed due to the complex structure of the network. A plausible approach to analyze such network is to embed the entity information as an informative feature vector. However, present embedding methods either consider only single-relational information, or neglect the importance of structural information. In addition, some of them require fine-tuning of hyperparameters, which might not be feasible for an unsupervised embedding generation task. In this work we propose MUSE, a Multi-relational Unsupervised link-Structure preserving Embeddings method, which learns the representations for each node and relation by maximizing the likelihood of observations on the given network. Additional node attributes are also preserved under our design. Besides, MUSE features less sensitive hyperparameters and scalablility by edge-sampling strategy. The extensive experiments on various real-world applications also demonstrate the effectiveness and robustness of our model.

abstract: Recently, a novel non-iterative power flow (PF) method known as the Holomorphic Embedding Method (HEM) was applied to the power-flow problem. Its superiority over other traditional iterative methods such as Gauss-Seidel (GS), Newton-Raphson (NR), Fast Decoupled Load Flow (FDLF) and their variants is that it is theoretically guaranteed to find the operable solution, if one exists, and will unequivocally signal if no solution exists. However, while theoretical convergence is guaranteed by Stahl’s theorem, numerical convergence is not. Numerically, the HEM may require extended precision to converge, especially for heavily-loaded and ill-conditioned power system models. In light of the advantages and disadvantages of the HEM, this report focuses on three topics: 1. Exploring the effect of double and extended precision on the performance of HEM, 2. Investigating the performance of different embedding formulations of HEM, and 3. Estimating the saddle-node bifurcation point (SNBP) from HEM-based Thévenin-like networks using pseudo-measurements. The HEM algorithm consists of three distinct procedures that might accumulate roundoff error and cause precision loss during the calculations: the matrix equation solution calculation, the power series inversion calculation and the Padé approximant calculation. Numerical experiments have been performed to investigate which aspect of the HEM algorithm causes the most precision loss and needs extended precision. It is shown that extended precision must be used for the entire algorithm to improve numerical performance. A comparison of two common embedding formulations, a scalable formulation and a non-scalable formulation, is conducted and it is shown that these two formulations could have extremely different numerical properties on some power systems. The application of HEM to the SNBP estimation using local-measurements is explored. The maximum power transfer theorem (MPTT) obtained for nonlinear Thévenin-like networks is validated with high precision. Different numerical methods based on MPTT are investigated. Numerical results show that the MPTT method works reasonably well for weak buses in the system. The roots method, as an alternative, is also studied. It is shown to be less effective than the MPTT method but the roots of the Padé approximant can be used as a research tool for determining the effects of noisy measurements on the accuracy of SNBP prediction.
Dissertation/Thesis
Masters Thesis Electrical Engineering 2018

碩士
國立交通大學
資訊科學系
89
In this thesis, we propose a variation of Honeycomb Torus, called Honeycomb Rectangular Torus Networks.The Honeycomb Rectangular Torus is Hamlitonian and to remove a pair of nodes from each partite sets of graph, still has Hamlitonian cycle. Honeycomb Rectangular Torus Network is homogeneous graph. This property is very helpful, because we can reduce the complexity of the Honeycomb Rectangular Torus. The Honeycomb Rectangular Torus HReT(m,n) is defined in the paper written by Stojmenovic Honeycomb Rectangular Torus has many good properties including homogeneous graph, 3-regular graph, Bipartite graph , hamiltonian cycle, 1-p hamiltonian cycle, hamiltonian connectivity etc. Since $HReT(m,n)$ is regular of degree 3, it can tolerate at most two node faults in the worst case in order to construct a hamiltonian cycle. In this paper, we will prove that all the honeycomb rectangular torus have hamiltonian cycle, when any one pair nodes fault.

Thesis (Ph. D.)--University of New Orleans, 2004.
Title from electronic submission form. "A dissertation ... in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Special Education and Habililative Services."--Dissertation t.p. Vita. Includes bibliographical references.

碩士
國立臺灣科技大學
電機工程研究所
82
The generalized Fibonacci cubes ( abbreviated to GFCs ) were recently proposed as a class of interconnection topologies, which cover a spectrum ranging from regular graphs such as the hypercube to semi-regular graphs such as the second order Fibonacci cube. It has been shown that the kth order GFC of dimension n + k is equivalent to an n cube for 0 .ltoreq. n < k; and it is a proper subgraph of an n-cube for n. gtoreq. k. Thus, a kth order GFC of dimension n + k can be obtained from the n-cube for all n.gtoreq. k by removing certain nodes from an n-cube. This problem is very simple when no faulty node exists in an n-cube; but it becomes very complex if some faulty nodes appear in an n-cube. In this paper, first, we concern the following open problem: How to identify a maximal ( in terms of the number of nodes ) generalized Fibonacci cube from a faulty hypercube which can also be considered as a Fault-tolerant embedding in hypercubes. Then, we shall show how to directly embed a GFC into a faulty hypercube and prove that if no more than three faulty nodes, then an [ n / 2 ]th order GFC of dimension n + [ n / 2 ] can be directly embedded into an n-cube in the worst case, for n = 4 or n.gtoreq. 6.

abstract: The holomorphic embedding method (HEM) applied to the power-flow problem (HEPF) has been used in the past to obtain the voltages and flows for power systems. The incentives for using this method over the traditional Newton-Raphson based nu-merical methods lie in the claim that the method is theoretically guaranteed to converge to the operable solution, if one exists. In this report, HEPF will be used for two power system analysis purposes: a. Estimating the saddle-node bifurcation point (SNBP) of a system b. Developing reduced-order network equivalents for distribution systems. Typically, the continuation power flow (CPF) is used to estimate the SNBP of a system, which involves solving multiple power-flow problems. One of the advantages of HEPF is that the solution is obtained as an analytical expression of the embedding parameter, and using this property, three of the proposed HEPF-based methods can es-timate the SNBP of a given power system without solving multiple power-flow prob-lems (if generator VAr limits are ignored). If VAr limits are considered, the mathemat-ical representation of the power-flow problem changes and thus an iterative process would have to be performed in order to estimate the SNBP of the system. This would typically still require fewer power-flow problems to be solved than CPF in order to estimate the SNBP. Another proposed application is to develop reduced order network equivalents for radial distribution networks that retain the nonlinearities of the eliminated portion of the network and hence remain more accurate than traditional Ward-type reductions (which linearize about the given operating point) when the operating condition changes. Different ways of accelerating the convergence of the power series obtained as a part of HEPF, are explored and it is shown that the eta method is the most efficient of all methods tested. The local-measurement-based methods of estimating the SNBP are studied. Non-linear Thévenin-like networks as well as multi-bus networks are built using model data to estimate the SNBP and it is shown that the structure of these networks can be made arbitrary by appropriately modifying the nonlinear current injections, which can sim-plify the process of building such networks from measurements.
Dissertation/Thesis
Doctoral Dissertation Electrical Engineering 2017

碩士
國立勤益科技大學
資訊管理系
102
In computer science, network topology is important and widely discussed by researchers since it is essential for parallel and distributed computation. Recently, many network topologies have been proposed. Among these topologies, the hypercube is one of the most popular topologies since it has good properties such as regularity, symmetry, small diameter, strong connectivity, recursive structure, flexible partition, and relatively low link complexity. Not only is it ideally suited to both special-purpose and general-purpose tasks, but it can efficiently simulate many other networks. The crossed cube has a structure similar to the hypercube, including recursive structure, the same number of vertices, and the same number of edges. However, the diameter of the crossed cube is only about one half of that of the hypercube. The diameter is an important factor for parallel computing speed. 　　In this study, we improve the previous result of Meijie Ma et al. that an n-dimensional crossed cube with up to n – 3 faults has a fault-free path of various length satisfying 2n-1－1 to the number of all vertices minus the faulty vertices and minus one. We also improve the result of Jung-Heum Park et al. that an n-dimensional HL-graph with up to n – 3 that has a fault-free path of various lengths with minimum 2n－3. In our main result, we prove that an n-dimensional crossed cube with up to n – 3 faulty vertices has a fault-free path of various length short than 2n－3. 　　The result of this study indicates that for an n-dimensional crossed cube with up to n – 3 faulty vertices, where n ≥ 5, there exists a fault-free path of various length satisfying 2n – 5 to 2n – f – 1, where f denotes the number of faulty vertices.