trouver TOUS les cycles dans une énorme matrice clairsemée

Question

Tout d'abord, je suis un débutant en Java, donc je ne sais pas si c'est encore possible! Fondamentalement, j'ai une énorme source de données relationnelles (3 + million) (c.-à-d. A est ami avec B + C + D, B est ami avec D + G + Z (mais pas A - c'est-à-dire non mutuel etc.) et je veux pour trouver chaque cycle dans ce graphe orienté (pas nécessairement connecté).

J'ai trouvé le fil Finding all cycles in graph, qui m'a pointé vers l'algorithme de recherche de cycle (élémentaire) de Donald Johnson qui, superficiellement au moins, a l'air de faire ce que je veux (je vais essayer quand je suis de retour au travail mardi - je pensais que ça ne me ferait pas de mal de demander en attendant!).

J'ai eu une analyse rapide à travers le code de l'implémentation Java de l'algorithme de Johnson (dans ce fil) et il ressemble à une matrice de relations est la première étape, donc je suppose que mes questions sont les suivantes:

a) Java est-il capable de gérer une matrice de 3 + millions * 3 + millions? (prévoyait de représenter A-friends-with-B par une matrice binaire clairsemée)

b) Ai-je besoin de trouver tous les sous-graphes connectés comme premier problème, ou les algorithmes de recherche de cycles gérera-t-il des données disjointes? C) Est-ce une solution appropriée au problème? Ma compréhension des cycles «élémentaires» est que dans le graphique ci-dessous, plutôt que de choisir A-B-C-D-E-F, il faudra choisir A-B-F, B-C-D etc. mais ce n'est pas la fin du monde.

E 
/\ 
    D---F 
/\/\ 
C---B---A 

d) Si nécessaire, je peux simplifier le problème en appliquant dans les relations de réciprocité - A-dire avec des amis-B < ==> B amis avec-A, et si je peux peut-être vraiment nécessaire réduire la taille des données, mais de façon réaliste, il va toujours être autour de la marque 1mil. Z) S'agit-il d'une tâche P ou NP ?! Est-ce que je mords plus que je ne peux mâcher?

Merci à tous, toute aide appréciée! Andy

Answer 1

c) Est-ce réellement une solution appropriée pour le problème? Ma compréhension des cycles "élémentaires" est que dans le graphique ci-dessous, plutôt que de choisir A-B-C-D-E-F, il va choisir A-B-F, B-C-D, etc., mais qui est pas la fin du monde compte tenu de la tâche .

E 
/\ 
    D---F 
/\/\ 
C---B---A 

Non « élémentaire » au sens de l'article de Donald Johnson moyen simple, qui est, aucun noeud apparaît deux fois dans le cercle. Cela signifie que l'algorithme ne choisira pas AFBCDBA, mais choisira ABCDEF.

d) Si nécessaire, je peux simplifier le problème en appliquant la réciprocité dans les relations - à savoir A Amis avec B-< ==> B amis avec A, et si vraiment nécessaire Je peux peut-être réduire la taille des données , mais de façon réaliste, il est va toujours être autour de la marque 1mil.

Les graphes non orientés ont un espace vectoriel de cycles (non simples) (qui a une bonne base, etc.), mais je ne sais pas si ça va vous aider. Z) S'agit-il d'une tâche P ou NP?

C'est un problème d'énumération qui, en lui-même, ne peut pas être dans P ni NP.

Answer 2

La recherche de chaque cycle ne semble pas raisonnable. Il y aura un nombre exponentiel de cycles, tous se chevauchant. Comme pour P ou NP, la partie la plus lente est en train d'énumérer chaque cycle (parce qu'il peut y en avoir beaucoup). S'il n'y a pas de cycles, un algorithme linéaire existe. Peut-être que vous voulez réellement diviser le graphique en composants biconnectés? Voir http://en.wikipedia.org/wiki/Biconnected_component

Aussi il est presque jamais raisonnable de stocker des graphiques dans des matrices. Cela semble bien en théorie, mais pas en pratique, Utiliser des listes d'adjacence à la place (http://en.wikipedia.org/wiki/Adjacency_list)

Answer 3

Ce que vous faites est similaire à un problème très bien étudié dans l'exploration de données, connu sous le nom d'extraction de règle d'association ou plus généralement fréquent extraction d'itemset. Ce que vous pouvez trouver avec l'extraction d'itemset fréquente, est un peu plus spécifique que ce que vous faites, mais aussi plus utile.

Nous irons avec l'extraction d'itemset fréquente fermée, ce que cela fera est de trouver tous les groupes d'amis, où tout le monde est ami avec l'autre. Je vais le dire maintenant, que Java ne peut pas faire ce que vous voulez faire. Il ne peut pas charger autant de mémoire et il n'est pas assez efficace pour traiter ces données dans un laps de temps raisonnable, vous allez avoir besoin d'utiliser C/C++. Je suggère d'utiliser LCM, qui est un mineur d'itemset fermé fréquemment, mais vous aurez également besoin d'établir le support assez haut, à cause de la quantité de données que vous avez.

Une autre chose que vous voudrez peut-être considérer est la lecture sur Large Graph Mining, qui est aussi un assez grand domaine de recherche, mais Java ne va pas le couper. De plus, vous ne pourrez pas trouver tous les cycles dans vos données (à moins qu'il ne soit incroyablement clairsemé), il y en aura beaucoup trop. Ils vont aussi se chevaucher et ne pas être très significatifs, ce que vous allez peut-être être en mesure de trouver est plusieurs des cycles les plus importants.