Core decomposition

Network structure review

Recall: Assortative networks

Connected components

  • Connected Networks: A network where, for any node, there exists a path by which you can reach any other node

  • You can think of connected components as islands, within the network

    • If a network is not connected, we say that it is disconnected;
  • Recall density: i.e. a measure of graph’s connectivity.

    • The following is often true, but not always.
    • higher the density —> more likely to be connected
    • lower the density —> less likely to be connected
  • Core: The core is a special name for the largest connected component

Code example

  • Note: nx.connected_components(G) returns a generator object (not ordered by size).
    • We can use the next function to get just the first item from the generator.
  • The generator can be converted to a list using list(nx.connected_components(G))
    • The length of this list is the number of connected components:
  • Each component is provided as a set of node names:
import matplotlib.pyplot as plt 
import numpy as np
import networkx as nx

def check_connectivity(G):
    print("----------------")
    print("Connected:",nx.is_connected(G))
    print("Density:",np.round(nx.density(G),3))
    print("Connected components:",list(nx.connected_components(G)))
    print("Number of connected components:",len(list(nx.connected_components(G))))

    # CC=nx.connected_components(G)
    # print(next(nx.connected_components(G)))
    nx.draw(G, with_labels=True, font_color="white")
    plt.show()

G = nx.complete_graph(10)
check_connectivity(G)

G = nx.star_graph(10)
check_connectivity(G)

G = nx.gnp_random_graph(10, 0.5, seed=10374196)
check_connectivity(G)

G = nx.gnp_random_graph(10, 0.2, seed=10374196)
check_connectivity(G)
----------------
Connected: True
Density: 1.0
Connected components: [{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}]
Number of connected components: 1

----------------
Connected: True
Density: 0.182
Connected components: [{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}]
Number of connected components: 1

----------------
Connected: True
Density: 0.578
Connected components: [{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}]
Number of connected components: 1

----------------
Connected: False
Density: 0.133
Connected components: [{0, 3}, {1, 2, 4, 6}, {8, 5}, {9, 7}]
Number of connected components: 4

Core decomposition

Overview

  • Core Decomposition Definition: A method to decompose a network into nested subgraphs, called k-cores, where each node is connected to at least k other nodes within the subgraph.
  • K-Core: A maximal subgraph in which each vertex has at least degree k.
  • Importance: Helps identify central and cohesive areas in a network.
  • Algorithm: Typically involves iteratively removing nodes with degrees less than k until no such nodes remain.
  • Applications: Used in social network analysis, biology, computer networks, and more to reveal the structure and hierarchies within networks.

Use-case: Visualizing the core

  • When analyzing or visualizing a large network, it is often useful to focus on its denser portion (the core)
  • Degree shells: The degree can be used to separate a network into distinct portions, called shells, based on their position in the core
    • Low-degree: outer shells on the periphery.
    • High-degree: core nodes
  • As low degree nodes are removed, what remains is a denser and denser sub-network (i.e. the core)
  • Core decomposition is particularly helpful in practice for filtering out peripheral nodes when visualizing large networks.

Core decomposition algorithm

Formally, the \(k\)-core decomposition algorithm starts by setting \(k=0\). Then it proceeds iteratively. Each iteration corresponds to a value of \(k\) and consists of a few simple steps:

  1. Recursively remove all nodes of degree \(k\), until there are no more left.
  2. The removed nodes make up the \(k\)-shell and the remaining nodes make up the \((k+\) 1)-core, because they all have degree \(k+1\) or larger.
  3. If there are no nodes left in the core, terminate; else, increment \(k\) for the next iteration.
  • NetworkX has functions for core decomposition:

Example: Political network

  • Filtering by \(k\)-core decomposition. We start from the full Twitter political retweet network \((k=1)\).
  • As we increase \(k\), peripheral nodes are removed and the remaining core becomes smaller and denser.
  • The innermost core contains only red nodes, corresponding to conservative accounts; each has at least \(k=20\) neighbors.

Example: Physical network

Code example

Recall relevant functions

Utility function

import networkx as nx
import matplotlib.pyplot as plt

#FUNCTION FOR NETWORK PLOTTING 
# def draw_network(G):
#     #CUSTOMIZE GRAPH A BIT
#     pos= nx.circular_layout(G)

#     nx.draw(G,
#         with_labels=True,
#         node_color='blue',
#         node_size=1600,
#         pos=pos,
#         font_color='white',
#         font_size=16,
#         )
#     plt.show()


def draw_network(G):
    #COMPUTE DEGREE: --> "LIST" WITH NODE DEGREES
    G_DEGREE=G.degree(); #print(G_DEGREE,G_DEGREE[5],type(G_DEGREE)) 

    # #LABELS (DICT)
    # labels={}
    # for n,d in G_DEGREE: labels[n]=d #str(n)+"-"+str(d) 

    #SORT DEGREE AND STORE IN LIST 
    degree_sequence = sorted((d for n, d in G_DEGREE), reverse=True)
    dmax = max(degree_sequence)   #MAX DEGREE

    #INITIALIZE MPL FIGURE+AX
    fig = plt.figure("Degree of a random graph", figsize=(12, 12))
    # Create a gridspec for adding subplots of different sizes
    axgrid = fig.add_gridspec(5, 4)

    #PLOT NETWORK IN UPPER GRID SPACES 
    ax0 = fig.add_subplot(axgrid[0:3, :])
    # pos = nx.spring_layout(G)
    # pos= nx.circular_layout(G)
    nx.draw(G,
        with_labels=True,
        # labels=labels,
        node_color='blue',
        node_size=500,
        font_color='white',
        font_size=16,
        pos=pos,ax=ax0
        )
    ax0.set_title("Network Graph: G")

    #PLOT RANK (IMPORTANCE BASED ON DEGREE) VS DEGREE)
    ax1 = fig.add_subplot(axgrid[3:, :2])
    ax1.plot(degree_sequence, "b-", marker="o")
    ax1.set_title("Degree Rank Plot")
    ax1.set_ylabel("Degree")
    ax1.set_xlabel("Rank")

    #PLOT RANK HISTOGRAM
    ax2 = fig.add_subplot(axgrid[3:, 2:])
    ax2.bar(*np.unique(degree_sequence, return_counts=True))
    ax2.set_title("Degree histogram")
    ax2.set_xlabel("Degree")
    ax2.set_ylabel("# of Nodes")
    ax0.set_aspect('equal', 'box')
    fig.tight_layout()
    plt.show()

Create and visualize network

Lets start with a random network with a density of 0.2 and add some singletons

N=20
G = nx.gnp_random_graph(N, 0.2, seed=10374196)
G.add_nodes_from([N+1,N+2,N+3])
pos= nx.circular_layout(G) # define globally
draw_network(G )

Core-Shell example: K=0

Gk=nx.k_core(G,0)
print(Gk)
draw_network(Gk)
Graph with 23 nodes and 38 edges

Gk=nx.k_shell(G,0)
print(Gk)
draw_network(Gk)
Graph with 3 nodes and 0 edges

print(nx.core_number(G))
print(max(nx.core_number(G).values()))
{0: 3, 1: 1, 2: 3, 3: 3, 4: 3, 5: 3, 6: 2, 7: 3, 8: 3, 9: 3, 10: 3, 11: 3, 12: 3, 13: 3, 14: 3, 15: 3, 16: 2, 17: 3, 18: 3, 19: 3, 21: 0, 22: 0, 23: 0}
3

Core-Shell example: K=1

Gk=nx.k_core(G,1)
print(Gk)
draw_network(Gk)
Graph with 20 nodes and 38 edges

Gk=nx.k_shell(G,1)
print(Gk)
draw_network(Gk)
Graph with 1 nodes and 0 edges

Compare to GCC

Notice how this is the same as K=1 (since removing the singletons leaves the GCC in this case)

def isolate_GCC(G):
    # get list of CC and return the first one in sorted list, i.e the larges one
    comps = sorted(nx.connected_components(G),key=len, reverse=True) 
    nodes_in_giant_comp = comps[0]
    # return subgraph
    return nx.subgraph(G, nodes_in_giant_comp)

GCC=isolate_GCC(G)
draw_network(GCC)

Core example: K=2

Gk=nx.k_core(G,2)
print(Gk)
draw_network(Gk)
Graph with 19 nodes and 37 edges

Gk=nx.k_shell(G,2)
print(Gk)
draw_network(Gk)
Graph with 2 nodes and 0 edges

Crust of K=2 shell

The crust in core-shell decomposition refers to the subset of nodes in a network that belong to the outermost layers or lower-order cores.

  • Nodes with the fewest connections
  • Found in the outer layers of the network
  • Less central and less influential
  • Compared to nodes in higher-order cores
  • Provides insight into the peripheral structure of the network
  • Important for understanding network disintegration and interactions of peripheral nodes
crust=nx.k_shell(G,3)
print(crust)
draw_network(crust)
Graph with 17 nodes and 33 edges

Shell example: K=3

Gk=nx.k_core(G,3)
print(Gk)
draw_network(Gk)
Graph with 17 nodes and 33 edges

Gk=nx.k_shell(G,3)
print(Gk)
draw_network(Gk)
Graph with 17 nodes and 33 edges

Coding from scratch

  • Let’s explore why the algorithm stops at k=3.
  • From the plots below, we can see that after k=3, removing nodes with 4 neighbors results in a graph where the degree of some remaining nodes is decreased by the removal.
  • This is why the code terminates when it does.
  • Removal condition appears to be that degree of nodes in remaining core is the same as the original network

# original network
draw_network(G)
print(nx.degree(G))

[(0, 3), (1, 1), (2, 3), (3, 5), (4, 3), (5, 4), (6, 2), (7, 3), (8, 3), (9, 5), (10, 5), (11, 4), (12, 4), (13, 6), (14, 5), (15, 6), (16, 2), (17, 4), (18, 3), (19, 5), (21, 0), (22, 0), (23, 0)]
# Gk=nx.k_shell(G,3)
for k in range(0,4+1):
    nodes_to_remove=[]
    print("------------------------------ k = "+str(k)+" -------------------------------")
    for node in G.nodes():
        if(nx.degree(G,node)<k):
            print(node,nx.degree(G,node))
            nodes_to_remove.append(node)
# print(nodes_to_remove)

    tmp=G.copy()
    tmp.remove_nodes_from(nodes_to_remove)
    print(tmp)
    draw_network(tmp)
    print(nx.degree(tmp))
    # draw_network(nx.k_core(G,k))
------------------------------ k = 0 -------------------------------
Graph with 23 nodes and 38 edges

[(0, 3), (1, 1), (2, 3), (3, 5), (4, 3), (5, 4), (6, 2), (7, 3), (8, 3), (9, 5), (10, 5), (11, 4), (12, 4), (13, 6), (14, 5), (15, 6), (16, 2), (17, 4), (18, 3), (19, 5), (21, 0), (22, 0), (23, 0)]
------------------------------ k = 1 -------------------------------
21 0
22 0
23 0
Graph with 20 nodes and 38 edges

[(0, 3), (1, 1), (2, 3), (3, 5), (4, 3), (5, 4), (6, 2), (7, 3), (8, 3), (9, 5), (10, 5), (11, 4), (12, 4), (13, 6), (14, 5), (15, 6), (16, 2), (17, 4), (18, 3), (19, 5)]
------------------------------ k = 2 -------------------------------
1 1
21 0
22 0
23 0
Graph with 19 nodes and 37 edges

[(0, 3), (2, 3), (3, 5), (4, 3), (5, 4), (6, 2), (7, 3), (8, 3), (9, 5), (10, 5), (11, 4), (12, 4), (13, 6), (14, 4), (15, 6), (16, 2), (17, 4), (18, 3), (19, 5)]
------------------------------ k = 3 -------------------------------
1 1
6 2
16 2
21 0
22 0
23 0
Graph with 17 nodes and 33 edges

[(0, 3), (2, 3), (3, 4), (4, 3), (5, 4), (7, 3), (8, 3), (9, 3), (10, 5), (11, 4), (12, 4), (13, 6), (14, 4), (15, 6), (17, 4), (18, 3), (19, 4)]
------------------------------ k = 4 -------------------------------
0 3
1 1
2 3
4 3
6 2
7 3
8 3
16 2
18 3
21 0
22 0
23 0
Graph with 11 nodes and 16 edges

[(3, 2), (5, 4), (9, 1), (10, 3), (11, 2), (12, 3), (13, 5), (14, 2), (15, 4), (17, 3), (19, 3)]

References

Disclaimer: This document is not an original work. It contains content from many sources and is for educational purposes only.