Overlapping community structure is a significant feature of large-scale complex networks. Some existing community detection algorithms cannot be applied to large-scale complex networks due to their high time or space complexity. Label propagation algorithms were proposed for detecting communities in large-scale networks because of their linear time complexity, however most of which can only detect non-overlapping communities, or the results are inaccurate and unstable. Aimed at the defects, we proposed an improved overlapping community detection algorithm, LPANNI (Label Propagation Algorithm with Neighbor Node Influence), which detects overlapping community structures by adopting fixed label propagation sequence based on the ascending order of node importance and label update strategy based on neighbor node influence and historical label preferred strategy. Extensive experimental results in both real networks and synthetic networks show that, LPANNI can significantly improve the accuracy and stability of community detection algorithms based on label propagation in large-scale complex networks. Meanwhile, LPANNI can detect overlapping community structures in large-scale complex networks under linear time complexity.

Most of existing virtual network embedding (VNE) algorithms only consider how to construct virtual networks more efficiently on a physical infrastructure, without considering the possibility that the constructed virtual networks may be further virtualized to multiple smaller ones. We define the former scenario as single-layer VNE and the later as multi-layer VNE. As the increasing popularity of deploying large datacenter networks and wide area networks with Software Defined Network (SDN) architectures, it becomes a new requirement and possibility to provide multi-layer encapsulated network services for large tenants who have hierarchical organizational structures or need fine-grained service isolation. However, existing VNE algorithm are not specifically designed for the above requirement and not flexible enough to deal with mapping virtual network requirements (VNRs) to a physical network and smaller VNRs to a mapped virtual network. In this paper, we aim to propose a unified and flexible multi-layer VNE algorithm combining with reinforcement learning to solve the embedding of multi-layer VNRs, which can better distinguish the differences between VNRs and physical networks. Simulation results show that our algorithm achieves good performance both in single-layer and multi-layer VNE scenarios.

Many existing virtual network embedding (VNE) algorithms adopt the greedy embedding strategies, which embed the in-progress virtual network requests (VNRs) onto the substrate nodes and links with more residual resources. However, the previous VNRs may overconsume the critical substrate resources and lead to the resource fragmentation problem in the substrate networks, thus reducing the acceptance ratio of the latter VNRs. To address this problem, we propose a novel collaborative VNE algorithm based on resource importance measures, RIM-ViNE, in which the global node importance and link importance in the initial substrate network are measured using multiple topological attributes and are used to set the embedding cost of VNRs. Then, the VNE problem is defined as a linear programming model and is solved by minimizing the total embedding cost, which could bring about the coordinative embedding between different VNRs, and thus preventing the critical resources from being over occupied by the previous VNRs with small requirements and improving the resource fragmentation problem. Moreover, we propose a dynamic reconfiguration mechanism based on critical nodes protection (CNP-Re) to improve the resource fragmentation problem further. Extensive experiments are conducted under two network scenarios, and the results show that the proposed algorithms outperform the VNE algorithms that only consider the coordination between node mapping and link mapping or only measure the node importance in the residual substrate network, and the average VNR acceptance ratio, average revenue, and average resource utilization ratio are effectively improved.