Détection communautaire sur un très grand graphique

Question

J'ai un très gros graphe orienté (un graphe de réseau social) avec environ 8 millions de nœuds. Je voudrais exécuter un algorithme de détection de la communauté sur le même (il peut être chevauchement ou non-chevauchement).

J'ai jeté un coup d'œil sur InfoMap mais c'est trop lent pour la taille d'un tel graphe - ça pourrait aussi bien prendre des semaines (je pense). BIGCLAM est une autre implémentation dans Stanford SNAP mais c'est seulement pour les graphes non orientés.

J'ai un serveur à ma disposition avec 40 cœurs et 128 Go de RAM (et mon réseau sur le disque est d'environ 60 Go) que je peux tirer parti. Existe-t-il une implémentation ou une recherche susceptible de m'aider?

Answer 1

Si vous possible, installez le langage de programmation R

puis, installez la bibliothèque igraph

il existe de nombreux algorithmes de détection de la communauté,

Infomap est bon, mais il est vraiment lent. Je pense que l'algorithme de Louvain est adapté à votre situation. L'algorithme de Louvain est merveilleusement !!! rapide

essayez-le s'il vous plaît!

Answer 2

Louvain La méthode est rapide! Il existe une implémentation: https://github.com/vtraag/louvain-igraph.

Vous devez d'abord installer la bibliothèque de graphes et la bibliothèque numpy.