networkx - k-core.

2-line summary

• k-core는 graph G에서 최소한 k의 node degree를 가지는 subgraph를 말합니다.
• 그냥 순차적으로 k보다 node degree가 작은 node를 잘라나가면 찾을 수 있습니다(혹은 존재하지 않거나).

what is k-core?

• k-core는 graph G에서, 최소한 k의 degree를 가지는 subtraph를 말합니다.
• 그냥, k보다 degree가 작은 node를 순차적으로 삭제하면서 생성되는 connected component와 같죠.
• 가끔, node-degree와 같은 것 아니야? 라고 생각하시는 분들이 있는데, “특정한 노드가 잘려나가면, edge도 같이 날아가므로, 다른 node의 degree 또한 작아집니다”. 따라서, 생각보다, 존재하는 종류의 k-core는 많지 않아요.

k-core python implementation.

• 물론, 이미, networkx - k-core에 잘 정리되어 있지만, 직접 한번 코딩해봤습니다.
• 이전에 말한 것과 동일하게, k보다 작은 degree의 node를 삭제해나가면서 진행하면 끝나요. 매-우 간단합니다.
• 그리고, 맨 끝에, 만들어진 제가 직접 만든 코드가 유효함을 증명하도록 테스트를 진행하였습니다.

import networkx as nx

def k_core(G, k):
    """
    - 그냥 반복적으로 node degree를 체크해나가면서, 
    - `k` 보다 degree가 작은 node를 모두 삭제함. 
    - 더이상 `k`보다 degree가 작은 node가 없을 경우 리턴.
    """
    G = G.copy()
    while True:
        node_below_k = [n for n, d in nx.degree(G) if d<k]
        if len(node_below_k)==0:
            break
        G.remove_nodes_from(node_below_k)
    return G


N = 50
G = nx.scale_free_graph(n=N, seed=0)
G = nx.Graph(G)
# remove self-edge
self_loop = [(u, v) for u, v in G.edges() if u == v]
G.remove_edges_from(self_loop)

assert nx.is_connected(G)

# 내가 만든 `k_core`함수와
# networkx.k_core의 결과과 같음을 증명함.
for i in range(1, 100):
    i_core = k_core(G=G, k=i)
    nx_i_core = nx.k_core(G, k=i)
    if len(i_core)==0:
        # i_core가 비어 있다는 이야기는 만들 수 없으므로 brerak
        break
    A_edge = set([(u, v) for u in i_core for v in i_core[u]])
    B_edge = set([(u, v) for u in nx_i_core for v in nx_i_core[u]])
    assert set(i_core.nodes()) == set(nx_i_core.nodes())
    assert A_edge == B_edge
print("== complete")

wrap-up

• 보통, 만들어진 Graph로부터, 밀집된 구조를 뽑을 때, community, clustering등을 사용하지만, 비교적 기본적인 k-core도 사용할 수 있을 것 같습니다.

reference

• networkx - k-core