Dependencies

The only necessary dependency are networkx and numpy.

Quick tour

The following minimal example first assigns scores to nodes with a one-dimensional spectral embedding and then retrieves an optimal linear clustering from this embedding using dyvider.

import networkx as nx
import dyvider as dy
import numpy as np

# create a graph
g = nx.stochastic_block_model([10, 10], [[0.5, 0.05], [0.05, 0.5]], seed=42)

# generate a 1-d embedding with the leading eigenvector of the modularity matrix
eigenvals, eigvenvecs = np.linalg.eig(nx.linalg.adjacency_matrix(g).todense())
score = {v: float(eigvenvecs[v, 0]) for v in g.nodes()}

# set the node positions
nx.set_node_attributes(g, score, 'score')

# run dyvider
g = dy.utilities.preprocess(g)
objective_function = dy.objectives.Modularity()
solution, Q = dy.algorithms.run(g, objective_function)

print(solution)

The expected output is:

>>> [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]]

Our tutorial goes into more detail and demonstrates all the API calls.

Paper

If you use this code, please consider citing:

“Exact and rapid linear clustering of networks with dynamic programming” Alice Patania, Antoine Allard and Jean-Gabriel Young. arXiv:2301.10403.

Author information

Code by Jean-Gabriel Young. Don’t hesitate to get in touch at jean-gabriel.young@uvm.edu, or via the issues!