networkx - k-crust.

1-line summary

• k-crust는 “k-떨거지”라고 말해도 되는데, 기존 graph G에서, k-core를 제거한 subgraph를 말하죠.

k-crust.

• 즉, k-crust는 k-core를 제거했을 때, 남는 complement graph라고 보셔도 됩니다.
• 다만, networkx에서 정의된 networkx.k_crust는 논문 A model of Internet topology using k-shell decomposition에서 제시된 방법과는 값이 약간 다릅니다.
  • 논문에서는 k-crust를 “k-core를 제거한 graph”라고 정의했다면,
  • networkx에서는 “(k+1)-core를 제거한 graph”라고 정의했죠.
• 왜 이 차이가 발생했는지는 잘 모르겠네요 흠.

python implementation

• 간단합니다. k-core를 찾고, 여기에 속한 노드들을 모두 삭제하고 리턴하면 됩니다(노드를 삭제하면 edge도 자연히 모두 삭제되니까요).

import networkx as nx 
def k_crust(G, k):
    """
    k_crust는 G에서 k_core에 속한 node들을 제거한 것을 말합니다.
    """
    subG_k_core = nx.k_core(G, k+1)
    subG_k_crust = G.copy()
    subG_k_crust.remove_nodes_from(subG_k_core)
    return subG_k_crust

reference

• networkx.algorithms.core.k_crust