Reproduce detectCommunity

[ychen983384]

Runs on the same graph generates different results. Is there a way to make this reproducible on the same graph?

first run

Communities = nk.community.detectCommunities(GData, algo=nk.community.PLM(G=GData,refine=True, gamma=0.5))
Communities detected in 1.21094 [s]
solution properties:

---

communities 10
min community size 12562
max community size 41579
avg. community size 24544.8
imbalance 1.69399
edge cut 404216
edge cut (portion) 0.054895
modularity 0.801823

second run

Communities = nk.community.detectCommunities(GData, algo=nk.community.PLM(G=GData,refine=True, gamma=0.5))
Communities detected in 1.18332 [s]
solution properties:

---

communities 11
min community size 13536
max community size 43623
avg. community size 22313.5
imbalance 1.95496
edge cut 426229
edge cut (portion) 0.0578845
modularity 0.808974

[clstaudt]

@ychen983384 Have you tried turning off parallelism?

PLM(G, par="none")

[ychen983384]

@ychen983384 Have you tried turning off parallelism?

PLM(G, par="none")

@clstaudt
I have not tried that. The reason I tried networkit's PLM is because I have a large graph to work with (~15 million vertices) and hope the parallelism could shorten the runnig time for detect community. I would test turning off parallelism. Do you suggest that the results would not be reproducible with parallelism on?

[fabratu]

Yes, with parallelism the order of execution (in terms of nodes moving from one cluster to the other) is not deterministic. Without parallelism you get the same result for consequetive runs:

import networkit as nk

G = nk.generators.BarabasiAlbertGenerator(5,100).generate()

for par_strat in ["none", "balanced"]:
    PLM = nk.community.PLM(G,par=par_strat)
    PLM.run()
    par1 = PLM.getPartition().getVector()

    PLM = nk.community.PLM(G,par=par_strat)
    PLM.run()
    par2 = PLM.getPartition().getVector()

    print(par1 == par2)

The output is True, False.

[clstaudt]

@ychen983384 As @fabratu has explained, the parallelism makes it nondeterministic. Turning off parallelism for your graph kind of defeats the purpose of using this particular algorithm. We never considered determinism to be an important property when building it.

[ychen983384]

@ychen983384 As @fabratu has explained, the parallelism makes it nondeterministic. Turning off parallelism for your graph kind of defeats the purpose of using this particular algorithm. We never considered determinism to be an important property when building it.

@clstaudt @fabratu Thank you both for the clear explanation and the great tools you developed. Scientific community and journals have been emphasizing more and more on reproducibility of both computational and experimental research work which might make determinism more important. With determinism, the parallel tools you have developed such as PLM and parLeiden would be more attractive to the scientific community since huge data set come from single cell multi-omics technology. Is it feasible to implement these community detection algorithms (such as louvain and leiden) with both parallelism and determinism or it is theoretically impossible?