Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAnalytical Results of k-core Pruning Process on Multi-layer Networks
82
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Multi-layer networks or multiplex networks are generally considered as the networks that have the same set of vertices but different types of edges. Multi-layer networks are especially useful when describing the systems with several kinds of interactions. In this paper we study the analytical solution of $textbf{k}$-core pruning process on multi-layer networks. $k$-core decomposition is a widely used method to find the dense core of the network. Previously the Nonbacktracking Expand Branch (NBEB) is found to be able to easily derive the exact analytical results in the $k$-core pruning process. Here we further extend this method to solve the $textbf{k}$-core pruning process on multi-layer networks by designing a variation of the method called Multicolor Nonbacktracking Expand Branch (MNEB). Our results show that, given any initial multi-layer network, Multicolor Nonbacktracking Expand Branch can offer the exact solution for each intermediate state of the pruning process, these results do not only apply to uncorrelated network, but also apply to networks with either interlayer correlations or in-layer correlations.
rate research
Read More
$k$-core decomposition is widely used to identify the center of a large network, it is a pruning process in which the nodes with degrees less than $k$ are recursively removed. Although the simplicity and effectiveness of this method facilitate its implementation on broad applications across many scientific fields, it produces few analytical results. We here simplify the existing theoretical framework to a simple iterative relationship and obtain the exact analytical solutions of the $k$-core pruning process on large uncorrelated networks. From these solutions we obtain such statistical properties as the degree distribution and the size of the remaining subgraph in each of the pruning steps. Our theoretical results resolve the long-lasting puzzle of the $k$-core pruning dynamics and provide an intuitive description of the dynamic process.
We induce the NonBacktracking Expansion Branch method to analyze the k-core pruning process on the monopartite graph G which does not contain any self-loop or multi-edge. Different from the traditional approaches like the generating functions or the degree distribution evolution equations which are mathematically difficult to solve, this method provides a simple and intuitive solution of the k-core pruning process. Besides, this method can be naturally extended to study the k-core pruning process on correlated networks, which is among the few attempts to analytically solve the problem.
Many real-world networks are coupled together to maintain their normal functions. Here we study the robustness of multiplex networks with interdependent and interconnected links under k-core percolation, where a node fails when it connects to a threshold of less than k neighbors. By deriving the self-consistency equations, we solve the key quantities of interests such as the critical threshold and size of the giant component analytically and validate the theoretical results with numerical simulations. We find a rich phase transition phenomenon as we tune the inter-layer coupling strength. Specifically speaking, in the ER-ER multiplex networks, with the increase of coupling strength, the size of the giant component in each layer first undergoes a first-order transition and then a second-order transition and finally a first-order transition. This is due to the nature of inter-layer links with both connectivity and dependency simultaneously. The system is more robust if the dependency on the initial robust network is strong and more vulnerable if the dependency on the initial attacked network is strong. These effects are even amplified in the cascading process. When applying our model to the SF-SF multiplex networks, the type of transition changes. The system undergoes a first-order phase transition first only when the two layers mutually coupling is very strong and a second-order transition in other conditions.
Multiplex networks are convenient mathematical representations for many real-world -- biological, social, and technological -- systems of interacting elements, where pairwise interactions among elements have different flavors. Previous studies pointed out that real-world multiplex networks display significant inter-layer correlations -- degree-degree correlation, edge overlap, node similarities -- able to make them robust against random and targeted failures of their individual components. Here, we show that inter-layer correlations are important also in the characterization of their $mathbf{k}$-core structure, namely the organization in shells of nodes with increasingly high degree. Understanding $k$-core structures is important in the study of spreading processes taking place on networks, as for example in the identification of influential spreaders and the emergence of localization phenomena. We find that, if the degree distribution of the network is heterogeneous, then a strong $mathbf{k}$-core structure is well predicted by significantly positive degree-degree correlations. However, if the network degree distribution is homogeneous, then strong $mathbf{k}$-core structure is due to positive correlations at the level of node similarities. We reach our conclusions by analyzing different real-world multiplex networks, introducing novel techniques for controlling inter-layer correlations of networks without changing their structure, and taking advantage of synthetic network models with tunable levels of inter-layer correlations.
In this paper, we propose the first optimum process scheduling algorithm for an increasingly prevalent type of heterogeneous multicore (HEMC) system that combines high-performance big cores and energy-efficient small cores with the same instruction-set architecture (ISA). Existing algorithms are all heuristics-based, and the well-known IPC-driven approach essentially tries to schedule high scaling factor processes on big cores. Our analysis shows that, for optimum solutions, it is also critical to consider placing long running processes on big cores. Tests of SPEC 2006 cases on various big-small core combinations show that our proposed optimum approach is up to 34% faster than the IPC-driven heuristic approach in terms of total workload completion time. The complexity of our algorithm is O(NlogN) where N is the number of processes. Therefore, the proposed optimum algorithm is practical for use.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
