rnbrw 0.1.5

Renewal Non-Backtracking Random Walk (RNBRW) for community detection

RNBRW

RNBRW (Renewal Non-Backtracking Random Walks) is a Python package for estimating edge-level importance in networks using random walks that restart upon cycle closure. These weights can be used to improve community detection algorithms like Louvain.

Based on:

Moradi, B., Shakeri, H., Poggi-Corradini, P., & Higgins, M.
New methods for incorporating network cyclic structures to improve community detection
arXiv:1805.07484

---

Installation

pip install rnbrw

Features

• Parallel RNBRW edge weight estimation
• Seamless integration with Louvain
• Based on Moradi-Jamei et al., 2019

Parallelization & HPC Useage

rnbrw supports parallel execution of the RNBRW simulations using joblib. This allows for efficient simulation on multi-core machines or High-Performance Computing (HPC) clusters.

You can control parallelism via the n_jobs parameter:

G = compute_weights(G, nsim=1000, n_jobs=-1)

n_jobs=-1: use all available CPU cores

n_jobs=4: use 4 parallel jobs

n_jobs=1: run sequentially

HPC Batching (Only-Walk Mode)

For large-scale jobs (e.g. SLURM), you can split nsim across jobs by using only_walk=True. Each job computes partial walk counts, and you later aggregate them.

Step 1: Run RNBRW Walks in Parallel Jobs

SLURM Example Here’s a basic SLURM job array script:rnbrw_job.sh

#!/bin/bash
#SBATCH --job-name=rnbrw_walk
#SBATCH --output=logs/rnbrw_%A_%a.out
#SBATCH --error=logs/rnbrw_%A_%a.err
#SBATCH --array=0-19              # 20 total jobs
#SBATCH --ntasks=1
#SBATCH --cpus-per-task=1
#SBATCH --mem=2G
#SBATCH --time=00:10:00

module load python/3.10
source activate rnbrw-env

# Run the Python script with job array index
python run_rnbrw_batch.py $SLURM_ARRAY_TASK_ID

Python Script: run_rnbrw_batch.py

python Copy Edit

import sys
import numpy as np
import networkx as nx
from rnbrw.weights import compute_weights

job_id = int(sys.argv[1])
seed = 1000 + job_id

# Load the graph (shared across all jobs)
G = nx.read_gpickle("mygraph.gpickle")

# Single walk using only_walk mode
G = compute_weights(G, nsim=1, seed=seed, only_walk=True)

# Extract edge counts
m = G.number_of_edges()
T = np.zeros(m)
for u, v in G.edges():
    T[G[u][v]['enum']] = G[u][v]['ret']

np.save(f"T_partial_{job_id}.npy", T)

Step 2 – Aggregate outputs (on head node):

import numpy as np

T_total = sum(np.load(f"T_partial_{i}.npy") for i in range(num_jobs))

Step 3 – Assign Weights to Graph

import networkx as nx
import numpy as np
from rnbrw.utils import assign_rnbrw_weights

G = nx.read_gpickle("mygraph.gpickle")
T_total = np.load("T_total.npy")

# Assign raw + normalized weights to the graph
G = assign_rnbrw_weights(G, T_total)

Step 4: Run Louvain

from rnbrw.community import detect_communities_louvain

partition = detect_communities_louvain(G, weight_attr='ret_n')

This makes rnbrw especially suitable for research environments where cycles and edge roles must be computed across very large networks.

Local Usage

Use compute_weights directly with multi-threading:

import networkx as nx
from rnbrw.weights import compute_weights
from rnbrw.community import detect_communities_louvain

# Create or load a graph
G = nx.karate_club_graph()

# Compute RNBRW weights
G = compute_weights(G, nsim=1000, n_jobs=4)
# Edge weights (normalized)
weights = [G[u][v]['ret_n'] for u, v in G.edges()]

# Detect communities
from rnbrw.community import detect_communities_louvain

partition = detect_communities_louvain(G, weight_attr='ret_n')

API Reference

compute_weights(G, nsim=1000, seed=None, n_jobs=1, init_weight=0.01, only_walk=False)

Simulates RNBRW on graph G to assign edge importance scores as weights.

Parameter Type Description

Parameter	Type	Description
G	networkx.Graph	Input undirected graph
nsim	int	Number of RNBRW simulations (default = 1000)
seed	int or None	Random seed for reproducibility
n_jobs	int	Number of parallel jobs (-1 uses all CPUs)
init_weight	float	Initial placeholder weight for edges (default = 0.01)
only_walk	bool	If True, run a single walk without accumulation (for HPC batch use)

detect_communities_louvain(G, weight_attr='rnbrw_weight')

Runs Louvain on G using edge weights.

Parameter	Type	Description
G	networkx.Graph	Weighted input graph
weight_attr	str	Edge weight attribute used for Louvain (default = 'ret_n')

|

normalize_edge_weights(G, weight='rnbrw_weight')

Normalizes the weights to sum to 1 across all edges.

Parameter	Type	Description
G	networkx.Graph	Graph whose edge weights are to be normalized
weight	str	Edge attribute to normalize (default = 'ret')

Citation

If you use this package in your research, please cite:

@article{moradi2018new, title={New methods for incorporating network cyclic structures to improve community detection}, author={Moradi, Behnaz and Shakeri, Heman and Poggi-Corradini, Pietro and Higgins, Michael}, journal={arXiv preprint arXiv:1805.07484}, year={2018} } Or use the “Cite this repository” button above.

License

This project is licensed under the MIT License © 2025 Behnaz Moradi-Jamei.

Documentation

Full documentation is available at Read the Docs.