From 1.3.0 louvain cluster results change repeating the analysis on the same graph

[massimoaria]

Describe the bug
After I updated igraph to 1.3.1, cluster_louvain() provides different results (both for modularity values and cluster compositions) when applying the function, repeatedly, on the same graph object.
This does not happen when I try to do that with 1.2.x or the previous igraph version.

To reproduce

# Igraph 1.3.1
g <- graph.famous("Zachary")
cluster_louvain(g)

IGRAPH clustering multi level, groups: 4, mod: 0.4

• groups:
  $1
  [1] 1 5 6 7 11 12 17

  $2
  [1] 2 3 4 8 10 13 14 18 20 22

  $3
  [1] 9 15 16 19 21 23 27 30 31 33 34

  $4

  • ... omitted several groups/vertices

and repeating...

# Igraph 1.3.1
g <- graph.famous("Zachary")
cluster_louvain(g)

IGRAPH clustering multi level, groups: 4, mod: 0.42

• groups:
  $1
  [1] 1 2 3 4 8 10 12 13 14 18 20 22

  $2
  [1] 5 6 7 11 17

  $3
  [1] 9 15 16 19 21 23 27 30 31 33 34

  $4

  • ... omitted several groups/vertices

While with igraph 1.2.x

# Igraph 1.2.11
g <- graph.famous("Zachary")
cluster_louvain(g)

GRAPH clustering multi level, groups: 4, mod: 0.42

• groups:
  $1
  [1] 1 2 3 4 8 10 12 13 14 18 20 22

  $2
  [1] 5 6 7 11 17

  $3
  [1] 9 15 16 19 21 23 27 30 31 33 34

  $4

  • ... omitted several groups/vertices

# Igraph 1.2.11
g <- graph.famous("Zachary")
cluster_louvain(g)

IGRAPH clustering multi level, groups: 4, mod: 0.42

• groups:
  $1
  [1] 1 2 3 4 8 10 12 13 14 18 20 22

  $2
  [1] 5 6 7 11 17

  $3
  [1] 9 15 16 19 21 23 27 30 31 33 34

  $4

  • ... omitted several groups/vertices

Version information
Which version of igraph are you using? 1.3.1

[szhorvat]

This is by design: the Louvain algorithm is now randomized. Previously, it would process vertices in the order of their IDs. Now it chooses a random order for each run. By running it multiple times and looking at how consistent the results are you can form an idea about how solid the community structure is. The change was made here: igraph/igraph#1696 The rationale is described here: igraph/igraph#1633