graphops

Graph algorithms and node embeddings.

[dependencies]
graphops = "0.1.0"

PageRank

use graphops::{pagerank, PageRankConfig};
use graphops::AdjacencyMatrix;

// Adjacency matrix: edge weights (0.0 = no edge)
let adj = vec![
    vec![0.0, 1.0, 1.0],
    vec![0.0, 0.0, 1.0],
    vec![1.0, 0.0, 0.0],
];

let scores = pagerank(&AdjacencyMatrix(&adj), PageRankConfig::default());
assert_eq!(scores.len(), 3);

Weighted PageRank and convergence diagnostics are available via pagerank_weighted and pagerank_run.

Personalized PageRank (seed-biased ranking) is available via personalized_pagerank.

Random walks

Uniform and biased (node2vec-style) random walks, with optional parallelism:

use graphops::random_walk::{generate_walks, WalkConfig};
use graphops::AdjacencyMatrix;

let adj = vec![
    vec![0.0, 1.0, 1.0],
    vec![1.0, 0.0, 1.0],
    vec![1.0, 1.0, 0.0],
];

let config = WalkConfig {
    length: 10,
    walks_per_node: 5,
    seed: 42,
    ..WalkConfig::default()
};

let walks = generate_walks(&AdjacencyMatrix(&adj), config);
// walks: Vec<Vec<usize>> -- each walk is a sequence of node indices

For node2vec-style biased walks (with return parameter p and in-out parameter q), use generate_biased_walks. Parallel variants (_parallel suffix) are available with the parallel feature.

Reachability

Count how many nodes each node can reach (forward) and be reached from (backward):

use graphops::reachability::reachability_counts_edges;

let edges = vec![(0, 1), (1, 2), (0, 2)];
let (forward, backward) = reachability_counts_edges(3, &edges);
// forward[0] = 2 (node 0 reaches nodes 1 and 2)

Partitioning

Connected components and label propagation community detection:

use graphops::partition::{connected_components, label_propagation};
use graphops::AdjacencyMatrix;

let adj = vec![
    vec![0.0, 1.0, 0.0],
    vec![1.0, 0.0, 0.0],
    vec![0.0, 0.0, 0.0], // isolated node
];

let components = connected_components(&AdjacencyMatrix(&adj));
// components: [0, 0, 1] -- two components

let communities = label_propagation(&AdjacencyMatrix(&adj), 100, 42);

Betweenness centrality

Requires the petgraph feature:

use graphops::betweenness::betweenness_centrality;
use petgraph::prelude::*;

let mut g: DiGraph<(), ()> = DiGraph::new();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
g.add_edge(a, b, ());
g.add_edge(b, c, ());

let scores = betweenness_centrality(&g);
// scores[1] is highest (node b is on the only a->c path)

Examples

cargo run --example pagerank

Feature flags

Optional features: petgraph (petgraph adapters + betweenness centrality), parallel (rayon walk generation), serde.

License

MIT OR Apache-2.0