# Calculate the K-Core of a Graph

## Introduction to K-Core of a Graph

A K-Core of a graph is a subgraph where all vertices have a degree greater than or equal to K. The K-Core decomposition of a graph is a method that helps to identify the connectivity and robustness of a network. This can be useful in various applications such as social network analysis, recommender systems, and network resilience.

In this tutorial, we will learn how to calculate the K-Core of a graph, and understand its applications in various real-world scenarios. We will also provide a code solution to help you implement K-Core decomposition in your projects.

## Real-World Examples and Scenarios

In social network analysis, K-Core decomposition can help identify influential users in a network, as well as detect the presence of tightly-knit communities.

In a recommender system, K-Core decomposition can be used to identify the most popular items and users who have rated a large number of items. This information can then be used to improve recommendations for users.

In the field of network resilience, K-Core decomposition can be used to identify critical nodes whose removal would result in the disintegration of the network.

## Real-World Scenario: Social Network Analysis

Let's consider a social network where users are connected based on their friendship. The problem is to identify influential users who are well-connected in the network. We can use the K-Core decomposition to solve this problem.

## Problem Statement

Given a graph G(V, E), where V is the set of vertices (users) and E is the set of edges (friendships), find the K-Core decomposition of the graph.

## Solution: K-Core Decomposition Algorithm

The K-Core decomposition algorithm works by iteratively removing vertices with a degree less than K until no such vertices remain. The remaining subgraph is the K-Core of the original graph. Here's a high-level overview of the algorithm:

- Initialize the K-Core subgraph as the original graph.
- While there are vertices with a degree less than K: a. Remove a vertex with a degree less than K from the subgraph. b. Update the degrees of the remaining vertices.
- Return the K-Core subgraph.

## Code Solution

Here's a Python implementation of the K-Core decomposition algorithm:

```
from collections import defaultdict
def k_core_decomposition(graph, k):
"""
Perform K-Core decomposition on the given graph.
:param graph: A dictionary where keys are vertices and values are lists of adjacent vertices.
:param k: The minimum degree of vertices in the K-Core subgraph.
:return: The K-Core subgraph as a dictionary.
"""
# Initialize the K-Core subgraph as the original graph
k_core = defaultdict(list)
for vertex, neighbors in graph.items():
k_core[vertex] = neighbors[:]
# Function to update degrees of vertices
def update_degrees(vertex):
for neighbor in k_core[vertex]:
k_core[neighbor].remove(vertex)
# Iterate until all vertices have a degree greater than or equal to K
while True:
low_degree_vertices = [v for v, neighbors in k_core.items() if len(neighbors) < k]
if not low_degree_vertices:
break
vertex = low_degree_vertices.pop()
update_degrees(vertex)
del k_core[vertex]
return k_core
```

## Example: Social Network Analysis

Let's use the K-Core decomposition function to analyze a social network:

```
# A sample social network represented as an adjacency list
social_network = {
'A': ['B', 'C', 'D'],
'B': ['A', 'C', 'D', 'E'],
'C': ['A', 'B', 'D', 'E'],
'D': ['A', 'B', 'C', 'E'],
'E': ['B', 'C', 'D', 'F'],
'F': ['E']
}
# Perform K-Core decomposition with K = 3
k_core = k_core_decomposition(social_network, 3)
print("K-Core Subgraph: ", k_core)
```

Output:

```
K-Core Subgraph: {'A': ['B', 'C', 'D'], 'B': ['A', 'C', 'D', 'E'], 'C': ['A', 'B', 'D', 'E'], 'D': ['A', 'B', 'C', 'E'], 'E': ['B', 'C', 'D']}
```

## Conclusion

In this tutorial, we learned about the K-Core decomposition of a graph and its applications in various real-world scenarios. We also provided a Python implementation of the K-Core decomposition algorithm and demonstrated its usage in social network analysis.

The K-Core decomposition algorithm can be applied to other problems as well, such as analyzing the robustness of a network, or identifying popular items in a recommender system. By understanding and implementing this algorithm, you can add valuable insights to your projects and solve complex problems in various domains.