Source-linked AI summary
A k-shell decomposition method for weighted networks
Antonios Garas, Frank Schweitzer, Shlomo Havlin
TL;DR
The paper addresses the limitation that k-shell decomposition and many centrality measures were designed for unweighted graphs, although real networks often contain meaningful link weights. It introduces a weighted k-shell method that combines node weight and degree without arbitrary thresholds, and evaluates it using weighted spreading simulations and an economic network. The method yields more refined partitions and places nodes with higher spreading potential closer to the core than the unweighted method.
Problem
Most centrality measures, including k-core decomposition, are designed for unweighted graphs even though real networks often have meaningful link weights.
Method
The paper generalizes k-shell decomposition by incorporating both node weight and degree, using α = β = 1 in the present study, and evaluates it with weighted SIR simulations.
Results
In four weighted networks, the weighted method places nodes with higher spreading potential in the core or shells closer to the core than the unweighted method.
Takeaways & Limitations
The weighted method provides more refined network partitions without arbitrary weight cut-offs and produces an economically meaningful core while retaining all 206 economic-network nodes.
Takeaways & Limitations
The study uses α = β = 1 and leaves the full exploration of the parameter space for future work.
Abstract
from arXiv · showhide
We present a generalized method for calculating the k-shell structure of weighted networks. The method takes into account both the weight and the degree of a network, in such a way that in the absence of weights we resume the shell structure obtained by the classic k-shell decomposition. In the presence of weights, we show that the method is able to partition the network in a more refined way, without the need of any arbitrary threshold on the weight values. Furthermore, by simulating spreading processes using the susceptible-infectious-recovered model in four different weighted real-world networks, we show that the weighted k-shell decomposition method ranks the nodes more accurately, by placing nodes with higher spreading potential into shells closer to the core. In addition, we demonstrate our new method on a real economic network and show that the core calculated using the weighted k-shell method is more meaningful from an economic perspective when compared with the unweighted one.
1 Introduction
Network analysis increasingly asks how individual nodes contribute to network structure and dynamics, but common centrality methods, including k-core decomposition, are designed for unweighted graphs. The paper introduces a generalized weighted k-shell method to address this limitation without arbitrary weight filtering.
- Network topology influences global properties and the evolution of dynamical processes through individual nodes’ connectivity patterns.
- Centrality measures rank node importance using properties such as degree, eigenvector centrality, betweenness, closeness, and k-core structure.
- Most centrality measures, including k-core decomposition, are designed for unweighted graphs despite real networks having meaningful link weights.
- Filtering links below a threshold can disconnect nodes and remove them from subsequent analysis.
- The paper introduces a generalized k-shell method for weighted networks and evaluates it on real networks and spreading processes.
2 The unweighted k-shell decomposition method
The classic k-shell decomposition recursively removes nodes by degree, assigning shell indices that reveal a network’s layered hierarchy from periphery to core. Because it ignores link weights, the paper calls this procedure the unweighted k-shell method.
- The k-core/k-shell decomposition assigns each node an integer k_s index representing its position in the network’s connectivity hierarchy.
- Low and high k_s values identify peripheral and central nodes, respectively, producing a layered onion-like network structure.
- The algorithm recursively removes degree-1 nodes, assigns k_s = 1, and repeats the process for progressively higher degree values.
- Every node is assigned to a shell until the network is exhausted, without considering link weights.
3 The weighted k-shell decomposition method
The weighted k-shell decomposition method generalizes shell assignment by combining node degree with link weights. It preserves the unweighted partition when weights are absent and can place strongly weighted peripheral nodes closer to the core.
- Method: Wk−shell applies the standard recursive pruning routine using a weighted degree that considers both node degree and link weights.The method assigns each node a weighted degree k′ before performing shell decomposition.
- Method: The study sets α = β = 1, treating link weight and node degree equally, while leaving the full parameter-space analysis for future work.This is the stated parameter choice for the present study.
- Method: When weights are absent, the weighted degree equals the node degree and produces the same partition as the unweighted method.For weighted data, link weights are normalized and discretized so the minimum link weight equals one.
- Illustration: Figure 2 reports average degree by shell distance from the core, with shaded degree ranges and standard-deviation error bars.Insets show distances closer to the core for networks with many shells.
- Illustration: In the illustrative network, Wk−shell moves node B from the unweighted outermost shell ks = 1 to ks = 2 because of its strong link to a core node.The link between A and B has weight wAB = 3, three times the other link weights.
4 Application to real networks
Across four weighted real-world networks, the weighted k-shell method produces finer hierarchies and more selective cores than the unweighted method. In the Corporate Ownership Network, it retains all countries without a weight cutoff and identifies an economically meaningful 11-country core.
- Networks studied: The four case studies comprise corporate ownership, network-science collaboration, C. Elegans neural, and U.S. air-transportation networks, analyzed primarily through their largest connected components.The CON links 206 countries; the AIR network covers 500 major U.S. airports and weights edges by annual available seats.
- Comparing network hierarchies: The Wk−shell method yields a more refined partitioning, with a larger number of k-shells than Uk−shell.This provides more detailed information about internal network structure.
- Comparing network hierarchies: For three of the four networks, Wk−shell produces a smaller core whose nodes are almost entirely contained in the Uk−shell core.The weighted method therefore further separates the most central nodes from the broader unweighted core.
- Node ranking: In Fig. 2, node degree is highly and nonlinearly correlated with k-shell position, but some high-degree nodes are not as central as expected.The Wk−shell ranking is used for this comparison across the four networks.
- Economic-network example: In the CON, Uk−shell identifies a 41-country core, whereas Wk−shell retains all 206 countries without an arbitrary weight cutoff and identifies an 11-country core.The Wk−shell core includes the United States, United Kingdom, France, Germany, Netherlands, Japan, Canada, Italy, Switzerland, Spain, and Belgium.
- Economic-network example: The Wk−shell CON core differs from the comparison core by including Canada while Sweden and Luxembourg move to the second innermost layer.The paper attributes this ordering to Canada’s G7 membership and stronger population and macroeconomic indicators relative to Sweden and Luxembourg.
5 Dynamics: Shell positioning and spreading potential
The study evaluates weighted and unweighted k-shell decompositions by simulating weighted spreading processes and comparing how well shells reflect node spreading potential. Across the tested networks, Wk−shell places higher-potential nodes nearer the core and produces more homogeneous shells.
- Weighted spreading model: The weighted SIR model uses link weights to calculate infection probabilities, with m controlling the amplification or severity of spreading.Each infected node attempts to infect susceptible neighbors, and simulations continue until no infected nodes remain.
- Weighted spreading model: Node spreading potential is scored by the average infected fraction across 100 W-SIR realizations for each starting node and different m values.The study restricts m to [0, 10] because larger values produce outbreaks regardless of the starting node.
- Shell positioning: Wk−shell central shells initiate more severe outbreaks than corresponding Uk−shell shells across all four networks and tested m values.This indicates that Wk−shell places nodes with higher average spreading potential closer to the core.
- Shell homogeneity: The average standard deviation of spreading potential across shells is always lower for Wk−shell than Uk−shell.Lower ⟨σ⟩ indicates shells whose nodes have more similar importance for the spreading process.
- Role of weights: Shuffling the CON’s weights makes k-shells significantly more inhomogeneous, with ⟨σ⟩ always larger than for the original network.The comparison uses 10 shuffled-weight realizations and W-SIR simulations on each.
6 Conclusion
The paper introduces Wk−shell, a weighted generalization that avoids arbitrary weight cutoffs and reduces to classic k-shell structure without weights. Using α = β = 1, the method produced more refined partitions and positioned higher-spreading-potential nodes nearer the core across four networks.
- Method: Wk−shell incorporates link weights without applying an arbitrary cutoff and reproduces the classic k-shell structure when weights are absent.With weights present, it can partition networks more finely.
- Method: The generalized formulation adjusts the relative importance of node weights and degree through exponents α and β.The paper notes that the parameter space was not fully explored.
- Results: Using α = β = 1, Wk−shell positioned higher-spreading-potential nodes in the core or shells closer to it, better than Uk−shell.This result was demonstrated with weighted SIR simulations in four different networks.