Trouver des sous-graphes égaux

Compte tenu:Trouver des sous-graphes égaux

un graphe orienté
nœuds ont des étiquettes
la même étiquette peuvent apparaître plus d'une fois
bords ne sont pas des étiquettes

I vouloir trouver l'ensemble des sous-graphes les plus importants (connectés) qui prennent en compte les étiquettes des nœuds.

Le graphique pourrait être énorme (des millions de nœuds) quelqu'un connaît-il une solution efficace pour cela?

Je cherche un algorithme et idéalement une implémentation Java.

Mise à jour: Puisque ce problème est très probablement NP-complet. Je serais également intéressé par un algorithme qui produit une solution approchée.

Cela semble être proche au moins: Frequent Subgraphs

Source

2009-05-08 kohlerm

Peut-être que c'est juste moi, mais je n'ai pas compris le problème. Que voulez-vous dire par "égal"? Il existe une fonction bijective f: Node_subgraph_A -> Node_subgraph_B de sorte que, pour chaque nœud a dans A: f (a) = b ssi label_a == label_b^(pour chaque x dans out_degree (a), f (x) \ dans out_degree (b))? – akappa

Oui, je pense que c'est ça. Je veux trouver des sous-graphes "redondants". A la fin, le graphe serait divisé en ensembles de sous-graphes "égaux". – kohlerm

Je soupçonne fortement que est NP-dur.

Même si toutes les étiquettes sont identiques, elles sont au moins aussi dures que l'isomorphisme des graphes. (Regroupez les deux graphiques sous la forme d'un seul graphe déconnecté. Les plus gros sous-graphes égaux sont-ils les deux graphes originaux?)

Si des étiquettes identiques sont relativement rares, elles peuvent être traitables.

Source

2009-05-08 19:23:55

+1, bonne analyse. –

bon point, n'a pas vu la relation à l'isomorphisme graphique. Mais oui, le nombre d'étiquettes identiques devrait être relativement faible. – kohlerm

Répondre

Questions connexes