Download this notebook

Zachary’s karate club

gradnet concepts demonstrated below

• Initial adjacency A₀ - optimal modifications of an existing network

• Edge removal delta_sign="nonpositive"

• Restricted signs of final edgeweights final_sign="nonnegative"

• Dynamical loss with ODE integration

• Checkpointing

Problem setup

Zachary’s karate club is a classic social network of 34 members whose friendships were recorded by Wayne Zachary in the 970s. A conflict between the instructor and the club president eventually caused the club to split into two factions, making it a standard example for community detection.

In this tutorial, we take an opinion dynamics view: the instructor and president hold fixed, opposing opinions that diffuse through the network. Friendships then rewire to reduce social dissonance, favoring ties between members with similar opinions, which subsequently splits the graph in two components.

The opinion dynamics is given by a simple diffusion process

\[\dot o(t) = -\,L\,o(t).\]

Here \(L\) is the Laplacian, defined as \(L = D - A\) with adjacency matrix \(A\) and the diagonal matrix of node degrees \(D_{ii}=\sum_j A_{ij}\). The opinions of the president and the instructor are fixed \(o_1(t)=1,\;o_N(t)=-1\). The social dissonance is measured by the weighted sum of disagreements with friends:

\[ \mathcal{D} = \frac{\sum_{i,j} A_{ij}\,\big(o_i - o_j\big)^2}{\sum_{i,j} A_{ij}}. \]

Install

install the required dependencies silently

%%capture
!pip install 'gradnet[examples]'

GradNet optimization

from gradnet import GradNet, integrate_ode, fit
from gradnet.utils import plot_graph
import torch
import networkx as nx


karate_net = nx.karate_club_graph()  # Load Zachary's Karate Club graph
adj0 = nx.to_numpy_array(karate_net)  # Get adjacency matrix as a NumPy array
mask = (adj0 > 0).astype(float)  # mask every non-existant edge

N = len(karate_net)
budget = None  # no restriction on budget.

gn = GradNet(num_nodes=N, adj0=adj0, mask = mask, delta_sign="nonpositive", final_sign="nonnegative",
            budget=budget, rand_init_weights=0.0001, strict_budget=False)


def do_dt(t, o, A):
    '''Diffusion of opinions with fixed opinion leaders '''
    L = torch.diag(A.sum(dim=1)) - A
    do = - L@o
    do[0] = 0
    do[-1] = 0
    return do

def dissonans(adj, o):
    o_dif = (o.unsqueeze(-1)-o.unsqueeze(-2))**2
    return (adj*o_dif).sum()/adj.sum()

def loss_fn(gn, relaxation_time=10):
    adj = gn()

    tt = torch.linspace(0, relaxation_time, 50)  # time grid to evaluate the numerical solutions
    o0 = torch.zeros(N)  # set the initial opinions to 0
    o0[0] = 1  # administrator
    o0[-1] = -1  # instructor

    tt, oo = integrate_ode(adj, f=do_dt, x0=o0, tt=tt)  # integrate the ODE
    o = oo[-1]
    
    return dissonans(adj, o), {"used_b": gn.get_delta_adj().sum().item()}  #compute dissonance

_, best_ckpt  = fit(gn=gn, loss_fn=loss_fn, num_updates=250, optim_kwargs={"lr": 0.01}, 
                    accelerator="cpu", enable_checkpointing=True, 
                    checkpoint_dir="./karate_club_checkpoints");

gn_best = GradNet.from_checkpoint(best_ckpt)

/Users/guga/D/University/UWyo/Network_Optimization/GradNet/gradnet/src/gradnet/gradnet.py:106: RuntimeWarning: delta_sign and final_sign request opposite cones; final projection may violate delta_sign and strict budget behavior.
  warnings.warn(
GPU available: True (mps), used: False
TPU available: False, using: 0 TPU cores
HPU available: False, using: 0 HPUs

  | Name | Type    | Params | Mode 
-----------------------------------------
0 | gn   | GradNet | 1.2 K  | train
-----------------------------------------
1.2 K     Trainable params
0         Non-trainable params
1.2 K     Total params
0.005     Total estimated model params size (MB)
`Trainer.fit` stopped: `max_epochs=250` reached.
/Users/guga/D/University/UWyo/Network_Optimization/GradNet/gradnet/src/gradnet/gradnet.py:106: RuntimeWarning: delta_sign and final_sign request opposite cones; final projection may violate delta_sign and strict budget behavior.
  warnings.warn(

# Color nodes based on the club they joined after the split
col = ['orange' if karate_net.nodes[nd]['club']== 'Mr. Hi' else 'green' for nd in range(N)]
plot_graph(gn_best, node_size=100, edge_width_scaling=0.7, draw_kwargs={"node_color": col, "edge_color": (0,0,0,0.75),})

<networkx.classes.graph.Graph at 0x302769450>

The edges represent the friendships after the social dissonance has been minimized. You can see that the network has split into two factions. The node colors, on the other hand, represent the ground truth: which club member sided with who. The network split coming from the opinion diffusion model matches with the ground truth except for one member, who is usually misclassified by most other algorithms.

Compare it with the original network

gn = GradNet(num_nodes=N, adj0=adj0, mask = mask, delta_sign="nonpositive", final_sign="nonnegative",
            budget=budget, rand_init_weights=0, strict_budget=False)
plot_graph(gn, node_size=100, edge_width_scaling=0.7, draw_kwargs={"node_color": col, "edge_color": (0,0,0,0.75),})

/Users/guga/D/University/UWyo/Network_Optimization/GradNet/gradnet/src/gradnet/gradnet.py:106: RuntimeWarning: delta_sign and final_sign request opposite cones; final projection may violate delta_sign and strict budget behavior.
  warnings.warn(

<networkx.classes.graph.Graph at 0x1204074d0>