No description available.

Network embedding or representation learning is important for analyzing many real-world applications and systems, i.e., social networks, citation networks and communication networks. It targets at learning low-dimensional vector representations of nodes with preserved graph structure (e.g., link relations) and content (e.g., texts) information. The derived node representations can be directly applied in many downstream applications, including node classification, clustering and visualization. In addition to the complex network structures, nodes may have rich non structure information such as labels and contents. Therefore, structure, label and content constitute different aspects of the entire network system that reflect node similarities from multiple complementary facets. This thesis focuses on multifaceted network embedding learning, which aims to efficiently incorporate distinct aspects of information such as node labels and node contents for cooperative low-dimensional representation learning together with node topology. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2020. / FAU Electronic Theses and Dissertations Collection

abstract: Attributes - that delineating the properties of data, and connections - that describing the dependencies of data, are two essential components to characterize most real-world phenomena. The synergy between these two principal elements renders a unique data representation - the attributed networks. In many cases, people are inundated with vast amounts of data that can be structured into attributed networks, and their use has been attractive to researchers and practitioners in different disciplines. For example, in social media, users interact with each other and also post personalized content; in scientific collaboration, researchers cooperate and are distinct from peers by their unique research interests; in complex diseases studies, rich gene expression complements to the gene-regulatory networks. Clearly, attributed networks are ubiquitous and form a critical component of modern information infrastructure. To gain deep insights from such networks, it requires a fundamental understanding of their unique characteristics and be aware of the related computational challenges. My dissertation research aims to develop a suite of novel learning algorithms to understand, characterize, and gain actionable insights from attributed networks, to benefit high-impact real-world applications. In the first part of this dissertation, I mainly focus on developing learning algorithms for attributed networks in a static environment at two different levels: (i) attribute level - by designing feature selection algorithms to find high-quality features that are tightly correlated with the network topology; and (ii) node level - by presenting network embedding algorithms to learn discriminative node embeddings by preserving node proximity w.r.t. network topology structure and node attribute similarity. As changes are essential components of attributed networks and the results of learning algorithms will become stale over time, in the second part of this dissertation, I propose a family of online algorithms for attributed networks in a dynamic environment to continuously update the learning results on the fly. In fact, developing application-aware learning algorithms is more desired with a clear understanding of the application domains and their unique intents. As such, in the third part of this dissertation, I am also committed to advancing real-world applications on attributed networks by incorporating the objectives of external tasks into the learning process. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2019

Avec l’avènement de l’ère intellectuelle et de l’Internet of Everything (IoE), les besoins de la communication mondiale et des applications diverses ont explosé. Cette révolution exige que les futurs réseaux de communication soient plus efficaces, intellectuels, agiles et évolutifs. De nombreuses technologies réseau sont apparues pour répondre à la tendance des réseaux de communication de nouvelle génération tels que les réseaux optiques élastiques (EONs) et la virtualisation de réseau. De nombreux défis apparaissent avec les apparences de la nouvelle architecture et de la nouvelle technologie, telles que le routage et l’allocation de ressource spectrale (RSA) dans les EONs et l’intégration de réseaux virtuels (Virtual Network Embedding ou VNE) dans la virtualisation de réseau.Cette thèse traite la conception et l’analyse d’algorithmes d’approximation dans trois problèmes d’optimation du RSA et du VNE : les impacts de la distribution du trafic et de la topologie du réseau sur le routage tout optique, de l’allocation de ressource spectrale, et du VNE dans les topologies des chemins et cycles. Pour le routage tout optique, le premier sous-problème du RSA, il y a toujours un problème en suspens concernant l’impact de la distribution du trafic et de la topologie EON. Comme le routage tout optique joue un rôle essentiel pour la performance globale de la RSA, cette thèse fournit une analyse approfondi théorique sur ces impacts. Pour le deuxième sous-problème du RSA, l’allocation de ressource spectrale, deux chemins optiques quelconques partageant des fibres optiques communes pourraient devoir être isolés dans le domaine spectral avec une bande de garde appropriée pour empêcher la diaphonie et / ou réduire les menaces de sécurité de la couche physique. Cette thèse considère le scénario dans lequel les exigences de bandes de garde réelles optiques sont différentes pour différentes paires de chemins, et étudie comment affecter les ressources spectrales efficacement dans une telle situation. L’hétérogénéité de la topologie des demandes de réseau virtuel (VNR) est un facteur important qui entrave les performances de la VNE. Cependant, dans de nombreuses applications spécialisées, les VNR ont des caractéristiques structurelles communes par exemple, des chemins et des cycles. Pour obtenir de meilleurs résultats, il est donc essentiel de concevoir des algorithmes dédiés pour ces applications en tenant compte des caractéristiques topologiques. Dans cette thèse, nous prouvons que les problèmes VNE dans les topologies de chemin et de cycle sont NP-difficiles. Afin de les résoudre, nous proposons des algorithmes efficaces également analysons leurs ratios d’approximation / With the coming of intellectual era and Internet of Everything (IoE), the needs of worldwide communication and diverse applications have been explosively growing. This information revolution requires the future communication networks to be more efficient, intellectual, agile and scalable. Many technologies have emerged to meet the requirements of next generation communication networks such as Elastic Optical Networks (EONs) and networking virtualization. However, there are many challenges coming along with them, such as Routing and Spectrum Assignment (RSA) in EONs and Virtual Network Embedding (VNE) in network virtualization. This dissertation addresses the algorithm design and analysis for these challenging problems: the impacts of traffic distribution and network topology on lightpath routing, the distance spectrum assignment and the VNE problem for paths and cycles.For lightpath routing, the first subproblem of the RSA, there is always a pending issue that how the changes of the traffic distribution and EON topology affect it. As the lightpath routing plays a critical role in the overall performance of the RSA, this dissertation provides a thoroughly theoretical analysis on the impacts of the aforementioned two key factors. To this end, we propose two theoretical chains, and derive the optimal routing scheme taking into account two key factors. We then treat the second subproblem of RSA, namely spectrum assignment. Any two lightpaths sharing common fiber links might have to be isolated in the spectrum domain with a proper guard-band to prevent crosstalk and/or reduce physical-layer security threats. We consider the scenario with diverse guard-band sizes, and investigate how to assign the spectrum resources efficiently in such a situation. We provide the upper and lower bounds for the optimal solution of the DSA, and further devise an efficient algorithm which can guarantee approximation ratios in some graph classes.The topology heterogeneity of Virtual Network Requests (VNRs) is one important factor hampering the performance of the VNE. However, in many specialized applications, the VNRs are of some common structural features e.g., paths and cycles. To achieve better outcomes, it is thus critical to design dedicated algorithms for these applications by accounting for topology characteristics. We prove the NP-Harness of path and cycle embeddings. To solve them, we propose some efficient algorithms and analyze their approximation ratios.

O atual sucesso da Internet vem inibindo a disseminação de novas arquiteturas e protocolos de rede. Especificamente, qualquer modificação no núcleo da rede requer comum acordo entre diversas partes. Face a isso, a Virtualização de Redes vem sendo proposta como um atributo diversificador para a Internet. Tal paradigma promove o desenvolvimento de novas arquiteturas e protocolos por meio da criação de múltiplas redes virtuais sobrepostas em um mesmo substrato físico. Adicionalmente, aplicações executando sobre uma mesma rede física podem ser isoladas mutuamente, propiciando a independência funcional entre as mesmas. Uma de suas mais promissoras vantagens é a capacidade de limitar o escopo de ataques, através da organização de uma infraestrutura em múltiplas redes virtuais, isolando o tráfego das mesmas e impedindo interferências. Contudo, roteadores e enlaces virtuais permanecem vulneráveis a ataques e falhas na rede física subjacente. Particularmente, caso determinado enlace do substrato seja comprometido, todos os enlaces virtuais sobrepostos (ou seja, alocados neste) serão afetados. Para lidar com esse problema, a literatura propõe dois tipos de estratégias: as que reservam recursos adicionais do substrato como sobressalentes, protegendo contra disrupções; e as que utilizam migração em tempo real para realocar recursos virtuais comprometidos. Ambas estratégias acarretam compromissos: o uso de recursos sobressalentes tende a tornar-se custoso ao provedor de infraestrutura, enquanto a migração de recursos demanda um período de convergência e pode deixar as redes virtuais inoperantes durante o mesmo. Esta dissertação apresenta ORE (Opportunistic Resilience Embedding – Mapeamento com Resiliência Oportunística), uma nova abordagem de mapeamento de redes para proteger enlaces virtuais contra disrupções no substrato físico. ORE é composto por duas estratégias: uma proativa, na qual enlaces virtuais são alocados em múltiplos caminhos para mitigar o impacto de uma disrupção; e uma reativa, a qual tenta recuperar, parcial ou integralmente, a capacidade perdida nos enlaces virtuais afetados. Ambas são modeladas como problemas de otimização. Ademais, como o mapeamento de redes virtuais é NP-Difícil, ORE faz uso de uma meta-heurística baseada em Simulated Annealing para resolver o problema de forma eficiente. Resultados numéricos mostram que ORE pode prover resiliência a disrupções por um custo mais baixo. / Recently, the Internet’s success has prevented the dissemination of novel networking architectures and protocols. Specifically, any modification to the core of the network requires agreement among many different parties. To address this situation, Network Virtualization has been proposed as a diversifying attribute for the Internet. This paradigm promotes the development of new architectures and protocols by enabling the creation of multiple virtual networks on top of a same physical substrate. In addition, applications running over the same physical network can be isolated from each other, thus allowing them to coexist independently. One of the main advantages of this paradigm is the use of isolation to limit the scope of attacks. This can be achieved by creating different, isolated virtual networks for each task, so traffic from one virtual network does not interfere with the others. However, routers and links are still vulnerable to attacks and failures on the underlying network. Particularly, should a physical link be compromised, all embedded virtual links will be affected. Previous work tackled this problem with two main strategies: using backup resources to protect against disruptions; or live migration to relocate a compromised virtual resource. Both strategies have drawbacks: backup resources tend to be expensive for the infrastructure provider, while live migration may leave virtual networks inoperable during the recovery period. This dissertation presents ORE (Opportunistic Resilience Embedding), a novel embedding approach for protecting virtual links against substrate network disruptions. ORE’s design is two-folded: while a proactive strategy embeds virtual links into multiple substrate paths in order to mitigate the initial impact of a disruption, a reactive one attempts to recover any capacity affected by an underlying disruption. Both strategies are modeled as optimization problems. Additionally, since the embedding problem is NP-Hard, ORE uses a Simulated Annealing-based meta-heuristic to solve it efficiently. Numerical results show that ORE can provide resilience to disruptions at a lower cost.

La virtualisation de réseau permet de créer des réseaux logiques, dits virtuels sur un réseau physique partagé dit substrat. Pour ce faire, le problème d’allocation des ressources aux réseaux virtuels doit être résolu efficacement. Appelé VNE (Virtual Network Embedding), ce problème consiste à faire correspondre à chaque nœud virtuel un nœud substrat d’un côté, et de l’autre, à tout lien virtuel un ou plusieurs chemins substrat, de manière à optimiser un objectif tout en satisfaisant un ensemble de contraintes. Les ressources de calcul des nœuds et les ressources de bande passante des liens sont souvent optimisées dans un seul réseau substrat. Dans le contexte multi-domaine où la connaissance de l’information de routage est incomplète, l’optimisation des ressources de nœuds et de liens est difficile et souvent impossible à atteindre. Par ailleurs, pour assurer la continuité de service même après une panne, le VNE doit être réalisé de manière à faire face aux pannes. Dans cette thèse, nous étudions le problème d’allocation de ressources (VNE) sous diverses exigences. Pour offrir la virtualisation dans le contexte de réseau substrat multi-domaines, nous proposons une méthode de mappage conjoint des liens inter-domaines et intra-domaines. Avec une information réduite et limitées annoncées par les domaines, notre méthode est capable de mapper simultanément les liens intra-domaines et les liens inter-domaines afin d’optimiser les ressources. De plus, pour améliorer la robustesse des réseaux virtuels, nous proposons un algorithme d’évitement des pannes qui minimise la probabilité de panne des réseaux virtuels. Des solutions exactes et heuristiques sont proposées et détaillées pour des liens à bande passante infinie ou limitée. En outre, nous combinons l’algorithme d’évitement des pannes avec la protection pour proposer un VNE robuste et résistant aux pannes. Avec cette nouvelle approche, les liens protégeables puis les liens les moins vulnérables sont prioritairement sélectionnés pour le mappage des liens. Pour déterminer les liens protégeables, nous proposons une heuristique qui utilise l’algorithme du maxflow afin de vérifier etdedéterminerlesliensprotégeablesàl’étapedumappagedesliensprimaires. Encasd’insuffisance de ressources pour protéger tous les liens primaires, notre approche sélectionne les liens réduisant la probabilité de panne. / Network virtualization allows to create logical or virtual networks on top of a shared physical or substrate network. The resource allocation problem is an important issue in network virtualization. It corresponds to a well known problem called virtual network embedding (VNE). VNE consists in mapping each virtual node to one substrate node and each virtual link to one or several substrate paths in a way that the objective is optimized and the constraints verified. The objective often corresponds to the optimization of the node computational resources and link bandwidth whereas the constraints generally include geographic location of nodes, CPU, bandwidth, etc. In the multi-domain context where the knowledge of routing information is incomplete, the optimization of node and link resources are difficult and often impossible to achieve. Moreover, to ensure service continuity even upon failure, VNE should cope with failures by selecting the best and resilient mappings. Inthisthesis,westudytheVNEresourceallocationproblemunderdifferentrequirements. To embed a virtual network on multi-domain substrate network, we propose a joint peering and intra domain link mapping method. With reduced and limited information disclosed by the domains, our downsizing algorithm maps the intra domain and peering links in the same stage so that the resource utilization is optimized. To enhance the reliability of virtual networks, we propose a failure avoidance approach that minimizes the failure probability of virtual networks. Exact and heuristic solutions are proposed and detailed for the infinite and limited bandwidth link models. Moreover, we combine the failure avoidance with the failure protection in our novel protection-level-aware survivable VNE in order to improve the reliability. With this last approach, the protectable then the less vulnerable links are first selected for link mapping. To determine the protectable links, we propose a maxflow based heuristic that checks for the existence of backup paths during the primary mapping stage. In case of insufficient backup resources, the failure probability is reduced.

O atual sucesso da Internet vem inibindo a disseminação de novas arquiteturas e protocolos de rede. Especificamente, qualquer modificação no núcleo da rede requer comum acordo entre diversas partes. Face a isso, a Virtualização de Redes vem sendo proposta como um atributo diversificador para a Internet. Tal paradigma promove o desenvolvimento de novas arquiteturas e protocolos por meio da criação de múltiplas redes virtuais sobrepostas em um mesmo substrato físico. Adicionalmente, aplicações executando sobre uma mesma rede física podem ser isoladas mutuamente, propiciando a independência funcional entre as mesmas. Uma de suas mais promissoras vantagens é a capacidade de limitar o escopo de ataques, através da organização de uma infraestrutura em múltiplas redes virtuais, isolando o tráfego das mesmas e impedindo interferências. Contudo, roteadores e enlaces virtuais permanecem vulneráveis a ataques e falhas na rede física subjacente. Particularmente, caso determinado enlace do substrato seja comprometido, todos os enlaces virtuais sobrepostos (ou seja, alocados neste) serão afetados. Para lidar com esse problema, a literatura propõe dois tipos de estratégias: as que reservam recursos adicionais do substrato como sobressalentes, protegendo contra disrupções; e as que utilizam migração em tempo real para realocar recursos virtuais comprometidos. Ambas estratégias acarretam compromissos: o uso de recursos sobressalentes tende a tornar-se custoso ao provedor de infraestrutura, enquanto a migração de recursos demanda um período de convergência e pode deixar as redes virtuais inoperantes durante o mesmo. Esta dissertação apresenta ORE (Opportunistic Resilience Embedding – Mapeamento com Resiliência Oportunística), uma nova abordagem de mapeamento de redes para proteger enlaces virtuais contra disrupções no substrato físico. ORE é composto por duas estratégias: uma proativa, na qual enlaces virtuais são alocados em múltiplos caminhos para mitigar o impacto de uma disrupção; e uma reativa, a qual tenta recuperar, parcial ou integralmente, a capacidade perdida nos enlaces virtuais afetados. Ambas são modeladas como problemas de otimização. Ademais, como o mapeamento de redes virtuais é NP-Difícil, ORE faz uso de uma meta-heurística baseada em Simulated Annealing para resolver o problema de forma eficiente. Resultados numéricos mostram que ORE pode prover resiliência a disrupções por um custo mais baixo. / Recently, the Internet’s success has prevented the dissemination of novel networking architectures and protocols. Specifically, any modification to the core of the network requires agreement among many different parties. To address this situation, Network Virtualization has been proposed as a diversifying attribute for the Internet. This paradigm promotes the development of new architectures and protocols by enabling the creation of multiple virtual networks on top of a same physical substrate. In addition, applications running over the same physical network can be isolated from each other, thus allowing them to coexist independently. One of the main advantages of this paradigm is the use of isolation to limit the scope of attacks. This can be achieved by creating different, isolated virtual networks for each task, so traffic from one virtual network does not interfere with the others. However, routers and links are still vulnerable to attacks and failures on the underlying network. Particularly, should a physical link be compromised, all embedded virtual links will be affected. Previous work tackled this problem with two main strategies: using backup resources to protect against disruptions; or live migration to relocate a compromised virtual resource. Both strategies have drawbacks: backup resources tend to be expensive for the infrastructure provider, while live migration may leave virtual networks inoperable during the recovery period. This dissertation presents ORE (Opportunistic Resilience Embedding), a novel embedding approach for protecting virtual links against substrate network disruptions. ORE’s design is two-folded: while a proactive strategy embeds virtual links into multiple substrate paths in order to mitigate the initial impact of a disruption, a reactive one attempts to recover any capacity affected by an underlying disruption. Both strategies are modeled as optimization problems. Additionally, since the embedding problem is NP-Hard, ORE uses a Simulated Annealing-based meta-heuristic to solve it efficiently. Numerical results show that ORE can provide resilience to disruptions at a lower cost.

O atual sucesso da Internet vem inibindo a disseminação de novas arquiteturas e protocolos de rede. Especificamente, qualquer modificação no núcleo da rede requer comum acordo entre diversas partes. Face a isso, a Virtualização de Redes vem sendo proposta como um atributo diversificador para a Internet. Tal paradigma promove o desenvolvimento de novas arquiteturas e protocolos por meio da criação de múltiplas redes virtuais sobrepostas em um mesmo substrato físico. Adicionalmente, aplicações executando sobre uma mesma rede física podem ser isoladas mutuamente, propiciando a independência funcional entre as mesmas. Uma de suas mais promissoras vantagens é a capacidade de limitar o escopo de ataques, através da organização de uma infraestrutura em múltiplas redes virtuais, isolando o tráfego das mesmas e impedindo interferências. Contudo, roteadores e enlaces virtuais permanecem vulneráveis a ataques e falhas na rede física subjacente. Particularmente, caso determinado enlace do substrato seja comprometido, todos os enlaces virtuais sobrepostos (ou seja, alocados neste) serão afetados. Para lidar com esse problema, a literatura propõe dois tipos de estratégias: as que reservam recursos adicionais do substrato como sobressalentes, protegendo contra disrupções; e as que utilizam migração em tempo real para realocar recursos virtuais comprometidos. Ambas estratégias acarretam compromissos: o uso de recursos sobressalentes tende a tornar-se custoso ao provedor de infraestrutura, enquanto a migração de recursos demanda um período de convergência e pode deixar as redes virtuais inoperantes durante o mesmo. Esta dissertação apresenta ORE (Opportunistic Resilience Embedding – Mapeamento com Resiliência Oportunística), uma nova abordagem de mapeamento de redes para proteger enlaces virtuais contra disrupções no substrato físico. ORE é composto por duas estratégias: uma proativa, na qual enlaces virtuais são alocados em múltiplos caminhos para mitigar o impacto de uma disrupção; e uma reativa, a qual tenta recuperar, parcial ou integralmente, a capacidade perdida nos enlaces virtuais afetados. Ambas são modeladas como problemas de otimização. Ademais, como o mapeamento de redes virtuais é NP-Difícil, ORE faz uso de uma meta-heurística baseada em Simulated Annealing para resolver o problema de forma eficiente. Resultados numéricos mostram que ORE pode prover resiliência a disrupções por um custo mais baixo. / Recently, the Internet’s success has prevented the dissemination of novel networking architectures and protocols. Specifically, any modification to the core of the network requires agreement among many different parties. To address this situation, Network Virtualization has been proposed as a diversifying attribute for the Internet. This paradigm promotes the development of new architectures and protocols by enabling the creation of multiple virtual networks on top of a same physical substrate. In addition, applications running over the same physical network can be isolated from each other, thus allowing them to coexist independently. One of the main advantages of this paradigm is the use of isolation to limit the scope of attacks. This can be achieved by creating different, isolated virtual networks for each task, so traffic from one virtual network does not interfere with the others. However, routers and links are still vulnerable to attacks and failures on the underlying network. Particularly, should a physical link be compromised, all embedded virtual links will be affected. Previous work tackled this problem with two main strategies: using backup resources to protect against disruptions; or live migration to relocate a compromised virtual resource. Both strategies have drawbacks: backup resources tend to be expensive for the infrastructure provider, while live migration may leave virtual networks inoperable during the recovery period. This dissertation presents ORE (Opportunistic Resilience Embedding), a novel embedding approach for protecting virtual links against substrate network disruptions. ORE’s design is two-folded: while a proactive strategy embeds virtual links into multiple substrate paths in order to mitigate the initial impact of a disruption, a reactive one attempts to recover any capacity affected by an underlying disruption. Both strategies are modeled as optimization problems. Additionally, since the embedding problem is NP-Hard, ORE uses a Simulated Annealing-based meta-heuristic to solve it efficiently. Numerical results show that ORE can provide resilience to disruptions at a lower cost.

The investigation of the latent geometrical space behind complex network topologies is a fervid topic in current network science and the hyperbolic space is one of the most studied, because it seems associated to the structural organization of many real complex systems. The popularity-similarity-optimization (PSO) generative model is able to grow random geometric graphs in the hyperbolic space with realistic properties such as clustering, small-worldness, scale-freeness and rich-clubness. However, it misses to reproduce an important feature of real complex systems, which is the community organization. Here, we introduce the nonuniform PSO (nPSO) generative model, a generalization of the PSO model with a tailored community structure, and we provide an efficient algorithmic implementation with a O(EN) time complexity, where N is the number of nodes and E the number of edges. Meanwhile, in recent years, the inverse problem has also gained increasing attention: given a network topology, how to provide an accurate mapping into its latent geometrical space. Unlike previous attempts based on a computationally expensive maximum likelihood optimization (whose time complexity is between O(N^3) and O(N^4)), here we show that a class of methods based on nonlinear dimensionality reduction can solve the problem with higher precision and reducing the time complexity to O(N^2).

No description available.