networkx - k-shell.

2-line summary

• k-shell은 “core number를 k로 가지는 node들의 subgraph, 그리고, (k+1)-core에 존재하지 않는 노드들을 말하죠”
• 사실, 별거 아닌것 같은데, 종종 complex network에서 node들의 계층적인 구조를 구분할 때 사용되는 경우들이 있죠.

k-shell.

• k-shell은 “core number를 k로 가지는 node들의 subgraph”를 말합니다. 다시 풀어서 말한다면, “k-shell”은 내부의 모든 node의 degree가 k보다 크죠. 즉, 3-shell은 graph G의 subgraph이며, 모든 node의 degree가 3보다 큽니다.
• 또한, 동시에, k-shell에 속한 node는 (k+1)-shell에 속해서는 안됩니다.
  • k-core: 모든 node의 degree가 k보다 크거나 같음(degree>=k)
  • k-shell: 모든 node의 degree가 정화갛게 k. (degree==k)
• 어찌 보면 별 것 아닌것 같지만, 논문 - A model of Internet topology using k-shell decomposition에서는 k-shell decomposition을 사용하여, 네트워크에 대한 계층적인 구조를 뽑아내기도 했습니다.

python implementation

• code 자체는 아래에서 보시는 것처럼 매우 간단합니다.
• 그리고, 해당 라이브러리는 이미 networkx에 구현되어 있기도 하죠.

def k_shell(G, k):
    """
    - 그냥 core-number로 k를 가지는 node만 뽑아서 subgraph를 만들어서 리턴합니다.
    """
    # nx.core_number(G): G의 모든 node들에 대한 core_number를 리턴
    core_num_dict = nx.core_number(G)
    # node_have_k_core: core_number를 `k`로 가지는 node들만 뽑음.
    node_have_k_core = [u for u, core_num in core_num_dict.items() if core_num == k]
    # node_have_k_core에 대한 subgraph를 리턴. 
    return nx.subgraph(G, node_have_k_core)

reference

• nx.core.k_shell
• A model of Internet topology using k-shell decomposition