1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
use crate::leiden::fast_local_moving::FastLocalMoving;
use crate::leiden::local_merging::LocalMerging;
use crate::leiden::{Clustering, Network, SimpleClustering, ZeroVec};
use rand::rngs::SmallRng;
use rand::{RngExt, SeedableRng};
use rayon::prelude::*;
/// Perform the Leiden clustering algorithm
pub struct Leiden {
resolution: f64,
randomness: f64,
/// Drives the sequential local moving, and hands every subnetwork
/// refinement its own seed before the refinements run in parallel.
rng: SmallRng,
local_moving: FastLocalMoving,
num_nodes_per_cluster_reduced_network: Vec<usize>,
}
impl Leiden {
/// Initialize the Leiden algorithm with the given resolution and randomness parameters.
/// An optional random seed can be supplied, otherwise a seed of 0 will be used.
#[must_use]
pub fn new(resolution: f64, randomness: f64, seed: Option<usize>) -> Leiden {
let seed = seed.unwrap_or_default() as u64;
Leiden {
resolution,
randomness,
rng: SmallRng::seed_from_u64(seed),
local_moving: FastLocalMoving::new(resolution),
num_nodes_per_cluster_reduced_network: Vec::new(),
}
}
/// Iterate the Leiden algorithm one step. Returns true if cluster labels were updated, otherwise returns false.
pub fn iterate<C: Clustering>(&mut self, n: &Network, c: &mut C) -> bool {
// Update the clustering by moving individual nodes between clusters.
let mut update = self.local_moving.iterate(n, c, &mut self.rng);
if c.num_clusters() == n.nodes() {
return update;
}
let subnetworks = n.create_subnetworks(c);
let nodes_per_cluster = c.nodes_per_cluster();
// clear clustering
c.clear();
self.num_nodes_per_cluster_reduced_network
.zero_len(subnetworks.len());
let mut cluster_counter = 0;
// Refine every subnetwork in parallel: they are independent, and each
// gets its own stream, seeded in order from the sequential one — a
// function of the seed and the call order, however rayon schedules.
let seeds: Vec<u64> = (0..subnetworks.len()).map(|_| self.rng.random()).collect();
let sub_clusterings: Vec<SimpleClustering> = subnetworks
.par_iter()
.zip(&seeds)
.map_init(
|| LocalMerging::new(self.randomness, self.resolution),
|local_merging, (sub, &seed)| {
local_merging.run(sub, &mut SmallRng::seed_from_u64(seed))
},
)
.collect();
for (i, sub_clustering) in sub_clusterings.iter().enumerate() {
for (j, &node) in nodes_per_cluster[i]
.iter()
.enumerate()
.take(subnetworks[i].nodes())
{
c.set(node, cluster_counter + sub_clustering.get(j));
}
cluster_counter += sub_clustering.num_clusters();
self.num_nodes_per_cluster_reduced_network[i] = sub_clustering.num_clusters();
}
c.remove_empty_clusters();
// Create an aggregate network based on the refined clustering of
// the non-aggregate network.
let reduced_n = n.create_reduced_network(c);
// Create an initial clustering for the aggregate network based on the
// non-refined clustering of the non-aggregate network.
let mut clusters_reduced_network = vec![0; c.num_clusters()];
let mut i = 0;
for (j, num_nodes) in self
.num_nodes_per_cluster_reduced_network
.iter()
.enumerate()
{
for cluster in clusters_reduced_network.iter_mut().skip(i).take(*num_nodes) {
*cluster = j;
}
i += num_nodes;
}
let mut clustering_reduced_network = C::new_from_labels(&clusters_reduced_network);
// Recursively apply the algorithm to the aggregate network,
// starting from the initial clustering created for this network.
update |= self.iterate(&reduced_n, &mut clustering_reduced_network);
// Update the clustering of the non-aggregate network so that it
// coincides with the final clustering obtained for the aggregate
// network.
c.merge_clusters(&clustering_reduced_network);
update
}
}