Papers^γ

Hello, are you aware of any open source implementation of this algorithm ?

Some nice presentations on the topic: - https://www.irif.fr/~habib/Documents/cours_4-2015.pdf - http://igm.univ-mlv.fr/AlgoB/algoperm2012/04Paul.pdf - http://www.lirmm.fr/~paul/Talks/talk-06-algo-sem-McGill.pdf

> Hello, are you aware of any open source implementation of this algorithm ? Yannis found this: https://github.com/antonovvk/decmod It seems that a function to read a graph from file needs to be added. Just a code to test on a random graph is provided. I was not sure how to compile the code: ``` gcc -c -o dm.o dm.c gcc -c -o random.o random.c gcc -o prog random.o dm.o ``` works. It seems to scale well. I gave a quick try on a random graph with 100k nodes and approx. 10M edges (I think): ``` time ./prog 100000 2000 > res.txt real 0m50,539s ``` and 1M nodes and 100M edges (note that the algo to generate the random graph is in $\Omega(n^2)$, so probably it takes most of the time): ``` time ./prog 1000000 200 > res.txt real 57m52,202s ``` However, the output says: ``` Statistiques sur l'arbre de decomposition: La racine est Premier Niveau 1: 0 modules (S-P-Pr= 0 - 0 - 0) et 100000 feuilles ``` It seems that there are only trivial modules in such large random graphs. The suggested command: ``` ./prog 100 20000 > res.txt ``` gives: ``` Statistiques sur l'arbre de decomposition: La racine est Parrallele Niveau 1: 3 modules (S-P-Pr= 2 - 0 - 1) et 12 feuilles Niveau 2: 8 modules (S-P-Pr= 1 - 7 - 0) et 72 feuilles Niveau 3: 0 modules (S-P-Pr= 0 - 0 - 0) et 16 feuilles ``` I've forked it and added a piece of code to read the input graph from a text file: https://github.com/maxdan94/decmod I ran it on some large real world graphs. It does scale well. For example, on LiveJournal: http://snap.stanford.edu/data/com-LiveJournal.html ``` time ./dm ../DATA/LiveJournal/net.txt Reading edgelist from file ../DATA/LiveJournal/net.txt Number of nodes: 4036538 Number of edges: 34681189 Building the adjacency list Statistiques sur l'arbre de decomposition: La racine est Parrallele Niveau 1: 1 modules (S-P-Pr= 0 - 0 - 1) et 2 feuilles Niveau 2: 132514 modules (S-P-Pr= 20434 - 110993 - 1087) et 3704505 feuilles Niveau 3: 5459 modules (S-P-Pr= 4513 - 242 - 704) et 318444 feuilles Niveau 4: 439 modules (S-P-Pr= 227 - 166 - 46) et 12337 feuilles Niveau 5: 38 modules (S-P-Pr= 23 - 4 - 11) et 1133 feuilles Niveau 6: 7 modules (S-P-Pr= 4 - 3 - 0) et 95 feuilles Niveau 7: 1 modules (S-P-Pr= 1 - 0 - 0) et 17 feuilles Niveau 8: 0 modules (S-P-Pr= 0 - 0 - 0) et 5 feuilles real 2m40,243s user 2m34,102s sys 0m6,031s ```

Wow, it is really impressing ! [The paper](https://arxiv.org/pdf/1811.10705.pdf#subsection.3.2) of Ludeña, Mendez and Bolivar suggests that random graphs have many primes and the connected component is often just about a big prime. See table 3 from https://arxiv.org/abs/1811.10705

>See table 3 from https://arxiv.org/abs/1811.10705 This is with $n=50$ nodes. It seems that the behavior is not the same for $n$ large: - I think that in a large ER, if the proba of connection $p$ is not too large or too small, then it is rare to find a group of nodes with the same neighbors outside the group (i.e. find a module). Can you prove that? - I don't think that the code https://github.com/antonovvk/decmod is buggy.

[Almost all finite graphs are asymmetric](https://en.wikipedia.org/wiki/Asymmetric_graph#Random_graphs). There is no pair of vertices with common neighborhood.