📦그래프의 특정 하위 그래프를 추출하는 알고리즘, K-Core

Definition

• K-Core 알고리즘은 그래프 이론에서 사용되는 알고리즘으로, 그래프의 특정 부분을 추출하는 데 사용됩니다.
• K-Core는 각 노드가 최소한 K개의 이웃 노드를 가지는 최대 부분 그래프를 의미합니다.

Motivation

• 소셜 네트워크, 생물학적 네트워크, 인터넷 구조 등 다양한 분야에서 밀집된 하위 구조를 식별하기 위해 등장했습니다. 개인적인 경험에서는 FDS 관련 사기거래를 집단으로 하는 업체를 탐지하기 위해서 활용한 바 있습니다.
• 이는 네트워크의 주요 구성 요소를 분석하고, 중요한 노드들을 식별하는 데 사용됩니다.

Pros & Cons

Pros

1. 밀집된 하위 구조 식별: 그래프 내에서 밀집된 하위 구조를 효율적으로 식별할 수 있습니다.
2. 중요 노드 식별: 네트워크 내에서 중요한 노드를 식별하는 데 유용합니다.
3. 다양한 응용 분야: 소셜 네트워크, 생물학적 네트워크, 인터넷 구조 등 다양한 분야에 적용 가능합니다.

Cons

1. 복잡성: 큰 그래프에 대해 K-Core를 계산하는 것은 복잡할 수 있습니다.
2. 메모리 사용: 큰 그래프를 처리할 때 메모리 사용량이 많을 수 있습니다.
3. 정확도 문제: 밀집된 하위 구조를 식별하는 과정에서 일부 중요한 노드가 누락될 수 있습니다.

Alternatiive

1. Clique: 그래프 내에서 모든 노드가 서로 연결된 부분 그래프를 찾는 알고리즘.
2. Community Detection: 네트워크 내에서 커뮤니티를 발견하는 알고리즘.
3. Modularity Optimization: 네트워크의 모듈성을 최적화하여 커뮤니티를 찾는 방법

Sample

import networkx as nx
import matplotlib.pyplot as plt
from networkx.algorithms.clique import find_cliques
from networkx.algorithms.community import greedy_modularity_communities

def compute_and_visualize_k_core(edges, k):
    # 그래프 생성
    G = nx.Graph()
    G.add_edges_from(edges)
    
    # K-Core 계산
    k_core = nx.k_core(G, k=k)
    
    # 그래프 시각화
    pos = nx.spring_layout(G)
    plt.figure(figsize=(8, 6))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray')
    nx.draw(k_core, pos, with_labels=True, node_color='red', edge_color='black')
    plt.title(f"K-Core (k={k}) of the Graph")
    plt.show()
    
    return k_core.nodes(), k_core.edges()

def find_and_visualize_cliques(edges):
    # 그래프 생성
    G = nx.Graph()
    G.add_edges_from(edges)
    
    # Clique 계산
    cliques = list(find_cliques(G))
    
    # 그래프 시각화
    pos = nx.spring_layout(G)
    plt.figure(figsize=(8, 6))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray')
    for clique in cliques:
        nx.draw_networkx_nodes(G, pos, nodelist=clique, node_color='red')
    plt.title("Cliques in the Graph")
    plt.show()
    
    return cliques

def detect_and_visualize_communities(edges):
    # 그래프 생성
    G = nx.Graph()
    G.add_edges_from(edges)
    
    # 커뮤니티 감지
    communities = list(greedy_modularity_communities(G))
    
    # 그래프 시각화
    pos = nx.spring_layout(G)
    plt.figure(figsize=(8, 6))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray')
    colors = ['red', 'blue', 'green', 'orange', 'purple']
    for i, community in enumerate(communities):
        nx.draw_networkx_nodes(G, pos, nodelist=list(community), node_color=colors[i % len(colors)])
    plt.title("Communities in the Graph")
    plt.show()
    
    return communities

# 예시 데이터
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]

# K-Core 결과
k = 2
nodes, edges = compute_and_visualize_k_core(edges, k)
print("Nodes in k-core:", nodes)
print("Edges in k-core:", edges)

# Clique 결과
cliques = find_and_visualize_cliques(edges)
print("Cliques in the graph:", cliques)

# Community Detection 결과
communities = detect_and_visualize_communities(edges)
print("Communities in the graph:", communities)