Mesure de la proximité dans un graphe et recherche de sous graphes de proximité; algorithmes de graphes

56 views
Skip to first unread message

Jean-Marc Vanel

unread,
Dec 18, 2014, 6:25:43 AM12/18/14
to deduct...@googlegroups.com
Bonjour

Je suis tombé sur ce papier de Chris Volinsky,
qui est le lauréat du prix NetFlix:

Measuring and Extracting Proximity Graphs in Networks
Yehuda Koren, Stephen C. North and Chris Volinsky
AT&T Labs – Research http://www2.research.att.com/~volinsky/papers/tkdd-revision.pdf

Ils ont une formule cohérente et un algorithme pour mesurer une proximité dans un graphe, qui tient compte à la fois de la longueur des chemins possibles, et de la combinatoire de ces chemins possibles.
A partir de là ils peuvent extraite un graphe significatif autour d'un nœud, ou entre 2 nœuds (graphe de proximité).

Hélas, pas de code avec cet article !
Et , comme toujours, écrire du code à partir de l'article demande une lecture approfondie.

La métrique s'appelle "CYCLE-FREE EFFECTIVE CONDUCTANCE (CFEC)" .
Je n'ai pas trouvé ça dans les librairies classiques de graphes en Java :


mais ça peut se trouver ...

Il y a aussi des librairies de graphe en Scala :


Et il y aussi blueprints, qui est un écosystème à lui tout seul, car c'est une collection d'interfaces et implémentations pour leur modèle de données de graphes. Blueprints est analogue à JDBC, mais pour les bases de données de graphes.

Par exemple la base RDF BigData(R) implémente blueprints:

Et blueprints a sa librairie d'algorithmes: 








Pierre-Alexandre Voye

unread,
Dec 28, 2014, 5:51:12 AM12/28/14
to deduct...@googlegroups.com
En OCaml, il y a OcamlGraph qui est très puissante et générique http://ocamlgraph.lri.fr/

--

---
Vous recevez ce message, car vous êtes abonné au groupe Google Groupes "Déductions et EulerGUI en Français".
Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse deductions-f...@googlegroups.com.
Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.


--
---------------------
https://twitter.com/#!/ontologiae/
http://linuxfr.org/users/montaigne

Jean-Marc Vanel

unread,
Jan 20, 2016, 11:26:49 AM1/20/16
to Déductions et EulerGUI en Français
Merci Ontologiae

Je vois qu'il y a ceci pour exécuter du OCAML sur une JVM :

Cependant, ce ne sera peut-être pas nécessaire.
L'ingrédient essentiel est un algorithme pour le problème:
"K shortest path routing"
pour lequel il doit exister des implémentations dans les librairies Java et Scala existantes énumérées ci-dessus.

De plus, une première étape peut être de simplement énumérer tous les chemins de longueur 2, 3, ou 4 à partir du départ, et d'appliquer la formule (8) de Volinski .
Et ensuite on peut brancher un algorithme pour les k plus courts chemins.

Si on fait ça comme un sous projet de semantic_forms, on utilisera Banana-RDF comme API pour RDF.

Les 2 articles sur "K shortest path routing" cités dans Volinski ne sont pas accessibles, mais il y en a des plus récents qui  sont  accessibles:

Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse deductions-fr+unsubscribe@googlegroups.com.

Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.

Pierre-Alexandre Voye

unread,
Jan 20, 2016, 11:51:37 AM1/20/16
to deduct...@googlegroups.com
Bonjour Jean-Marc,

Tu peux regarder du côté de Neo4J, qui est muni q'une sorte de SQL orienté graphe : Cypher. C'est puissant, pratique, bien intégré

Merci Ontologiae
Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse deductions-f...@googlegroups.com.

Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.

--

---
Vous recevez ce message, car vous êtes abonné au groupe Google Groupes "Déductions et EulerGUI en Français".
Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse deductions-f...@googlegroups.com.

Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.

Jean-Marc Vanel

unread,
Jan 28, 2016, 11:50:49 AM1/28/16
to Déductions et EulerGUI en Français
Je connais Neo4J,mais c'est du semi-open source.
De plus,il utilise son propre language Cypher, alors qu'il y a gremlin et tinkerpop .
Blazegraph par exemple est dans cet écosytème .

Pour l'heure je m'appuie sur ce projet en Scala ( existe aussi en C++ ) : 
qui fait le job en 400 lignes.
J'ai déjà fait un pull request qui a été pris :) .

J'ai implémenté l'algorithme de l'article dans ce projet, qui s'appuie sur le projet k-shortest-paths :
https://github.com/deductions/graph_proximity

Ainsi j'espère que ce sera indépendant de toute technologie sous-jacente pour représenter le graphe.
Restera à faire la liaison avec un graphe RDF, via l'API Banana - RDF .




Jean-Marc Vanel

unread,
Mar 24, 2016, 2:51:56 PM3/24/16
to Déductions et EulerGUI en Français
L'article en question se trouve maintenant ici:
https://www.semanticscholar.org/paper/Measuring-and-extracting-proximity-in-networks-Koren-North/4b64e093e34a29092ca0f6ac3eed904eb9d1a099

A noter qu'il y a aussi un brevet US associé, mais je crois qu'en France on ne brevète pas les algorithmes, mais une utilisation qu'on en fait.

Reply all
Reply to author
Forward
0 new messages