Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUsing NonBacktracking Expansion to Analyze k-core Pruning Process
63
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
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.
The application of Network Science to social systems has introduced new methodologies to analyze classical problems such as the emergence of epidemics, the arousal of cooperation between individuals or the propagation of information along social networks. More recently, the organization of football teams and their performance have been unveiled using metrics coming from Network Science, where a team is considered as a complex network whose nodes (i.e., players) interact with the aim of overcoming the opponent network. Here, we combine the use of different network metrics to extract the particular signature of the F.C. Barcelona coached by Guardiola, which has been considered one of the best teams along football history. We have first compared the network organization of Guardiolas team with their opponents along one season of the Spanish national league, identifying those metrics with statistically significant differences and relating them with the Guardiolas game. Next, we have focused on the temporal nature of football passing networks and calculated the evolution of all network properties along a match, instead of considering their average. In this way, we are able to identify those network metrics that enhance the probability of scoring/receiving a goal, showing that not all teams behave in the same way and how the organization Guardiolas F.C. Barcelona is different from the rest, including its clustering coefficient, shortest-path length, largest eigenvalue of the adjacency matrix, algebraic connectivity and centrality distribution.
Community detection is expensive, and the cost generally depends at least linearly on the number of vertices in the graph. We propose working with a reduced graph that has many fewer nodes but nonetheless captures key community structure. The K-core of a graph is the largest subgraph within which each node has at least K connections. We propose a framework that accelerates community detection by applying an expensive algorithm (modularity optimization, the Louvain method, spectral clustering, etc.) to the K-core and then using an inexpensive heuristic (such as local modularity maximization) to infer community labels for the remaining nodes. Our experiments demonstrate that the proposed framework can reduce the running time by more than 80% while preserving the quality of the solutions. Recent theoretical investigations provide support for using the K-core as a reduced representation.
We consider the random interlacements process with intensity $u$ on ${mathbb Z}^d$, $dge 5$ (call it $I^u$), built from a Poisson point process on the space of doubly infinite nearest neighbor trajectories on ${mathbb Z}^d$. For $kge 3$ we want to determine the minimal number of trajectories from the point process that is needed to link together $k$ points in $mathcal I^u$. Let $$n(k,d):=lceil frac d 2 (k-1) rceil - (k-2).$$ We prove that almost surely given any $k$ points $x_1,...,x_kin mathcal I^u$, there is a sequence ofof $n(k,d)$ trajectories $gamma^1,...,gamma^{n(k,d)}$ from the underlying Poisson point process such that the union of their traces $bigcup_{i=1}^{n(k,d)}tr(gamma^{i})$ is a connected set containing $x_1,...,x_k$. Moreover we show that this result is sharp, i.e. that a.s. one can find $x_1,...,x_k in I^u$ that cannot be linked together by $n(k,d)-1$ trajectories.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
