[Παράλληλα και Διανεμημένα Συστήματα] Εργασία 4 - 2017

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Πληροφορίες Καθηγητών]

Πληροφορίες Καθηγητών

[Argirios]

Απ'ότι κατάλαβα, το P'' δεν το υπολογίζουμε, σωστά? Εγω το υπολόγισα και μετά έκανα κανονικά Α*x χωρίς gauss-seidel και το pagerank βγαίνει σωστά μάλλον. Αλλά όταν το κάνω με Gauss-Seidel που ζητάει ο Πιτσιάνης, βρίσκωντας το A*x χρησιμοποιώντας to P για τον υπολογισμό του γινομένου και όχι το P'', όπως λέει το pdf(αλγόριθμος 1), το pagerank τελειώνει/συγκλίνει σε ένα iteration με λάθος αποτέλέσματα, ξέρει κανείς τι παίζει?

εδιτ: είχα σβήσει καταλάθως την αρχικοποίηση του διανύσματος v όταν το άλλαζα σε gauss-seidel, δούλεψε μάλλον!!!!!!!!!! 

[Jimfullmetal13]

Εσείς τι έχετε χρησιμοποιήσει για να φτιάξετε το adjastency matrix? Ο καθένας τα έχει αλλιώς γραμμένα, άλλοι τα έχουν σε γράφους άλλοι σε adjastency list...
Εγώ το έκανα με τa adjastency list με τον αλγόριθμο που είχε σε ένα λινκ στο pdf της εργασίας http://www.cs.toronto.edu/~tsap/experiments/download/list2matrix.c

Είχε πει στο μάθημα κάτι, άμα προτιμάει κάποιο τρόπο συγκεκριμένο?

Επίσης, πολλά pagerank μου βγαίνουν ακριβώς ίδια, ειδικά αυτά που έχουν πολύ χαμηλό σκόρ, εσάς είναι όλα διαφορετικά? Μπορεί και να φταίει ότι τα αποθηκεύω σε double και χάνει κάποια ακρίβεια.

Τι directory έβαλες σαν όρισμα στην list2matrix και σου δούλεψε; Εγώ τρέχω ./list2matrix  /home/.../adj_list  και μου χτυπάει error ότι δεν μπορεί να βρεί το /home/.../adj_list/graph/nodes.

[Argirios]

Τι directory έβαλες σαν όρισμα στην list2matrix και σου δούλεψε; Εγώ τρέχω ./list2matrix  /home/.../adj_list  και μου χτυπάει error ότι δεν μπορεί να βρεί το /home/.../adj_list/graph/nodes.

'
Φτιάξε έναν φάκελο με ένα όνομα, και βάλε μέσα ένα φάκελο graph που να περιέχει το nodes και το adj_list, και σαν όρισμα βάλε τον αρχικό φάκελο.
Αλλά για το list2matrix.c νομίζω πρέπει να χρησιμοποιήσεις τα dataset εκείνης της σελίδας, δε ξέρω αμα δουλεύει σε άλλα εκτός αμα έχουν ίδια δομή.

[Jimfullmetal13]

Απ'ότι κατάλαβα, το P'' δεν το υπολογίζουμε, σωστά? Εγω το υπολόγισα και μετά έκανα κανονικά Α*x χωρίς gauss-seidel και το pagerank βγαίνει σωστά μάλλον. Αλλά όταν το κάνω με Gauss-Seidel που ζητάει ο Πιτσιάνης, βρίσκωντας το A*x χρησιμοποιώντας to P για τον υπολογισμό του γινομένου και όχι το P'', όπως λέει το pdf(αλγόριθμος 1), το pagerank τελειώνει/συγκλίνει σε ένα iteration με λάθος αποτέλέσματα, ξέρει κανείς τι παίζει?

εδιτ: είχα σβήσει καταλάθως την αρχικοποίηση του διανύσματος v όταν το άλλαζα σε gauss-seidel, δούλεψε μάλλον!!!!!!!!!! 

1. Στο pdf του Kamvar ο πίνακας P είναι αυτός με τα 0 και 1 (υπάρχει / δεν υπάρχει link από το i στο j) που διαβάζουμε από το file του datasets?
2. To deg(i) είναι το outdegree του node i? Δηλαδή, ο αριθμός των link που "φεύγουν" από την σελίδα i?

[Argirios]

1. Στο pdf του Kamvar ο πίνακας P είναι αυτός με τα 0 και 1 (υπάρχει / δεν υπάρχει link από το i στο j) που διαβάζουμε από το file του datasets?
2. To deg(i) είναι το outdegree του node i? Δηλαδή, ο αριθμός των link που "φεύγουν" από την σελίδα i?

1. Όχι, ο P είναι ο πίνακας με τις πιθανότητες μετάβασης από το i στο j, θα πρέπει να τον φτιάξεις εσύ.
2. Ναι

[Jimfullmetal13]

1. Όχι, ο P είναι ο πίνακας με τις πιθανότητες μετάβασης από το i στο j, θα πρέπει να τον φτιάξεις εσύ.
2. Ναι

Οπότε, δεν χρειάζεται καν να αποθηκεύσουμε τον πίνακα με τα {0,1} του file. Απλώς να ξέρουμε μόνο πόσα links/outdegree φεύγουν από κάθε node.

[Argirios]

Οπότε, δεν χρειάζεται καν να αποθηκεύσουμε τον πίνακα με τα {0,1} του file. Απλώς να ξέρουμε μόνο πόσα links/outdegree φεύγουν από κάθε node.

Δεν είμαι απόλυτα σίγουρος σε αυτό αλλά χρειάζεσαι τα 0 και 1 γιατι στα κελιά που ο adjacency matrix έχει 0 θα έχει και το P 0. Οπότε πρέπει να τον έχεις αποθηκευμένο μέχρι να φτιάξεις τον P.

[Apostolof]

Αν το adjastency matrix είναι πχ:

0      0      0
1      0      0
1      1      0

Ο πίνακας P θα είναι ο παρακάτω;

0      0      0
1      0      0
0,5   0,5     0

Απ'ότι κατάλαβα, το P'' δεν το υπολογίζουμε, σωστά? Εγω το υπολόγισα και μετά έκανα κανονικά Α*x χωρίς gauss-seidel και το pagerank βγαίνει σωστά μάλλον. Αλλά όταν το κάνω με Gauss-Seidel που ζητάει ο Πιτσιάνης, βρίσκωντας το A*x χρησιμοποιώντας to P για τον υπολογισμό του γινομένου και όχι το P'', όπως λέει το pdf(αλγόριθμος 1), το pagerank τελειώνει/συγκλίνει σε ένα iteration με λάθος αποτέλέσματα, ξέρει κανείς τι παίζει?

εδιτ: είχα σβήσει καταλάθως την αρχικοποίηση του διανύσματος v όταν το άλλαζα σε gauss-seidel, δούλεψε μάλλον!!!!!!!!!!  

Τελικά όντως δε χρειάζεται ο υπολογισμός του P''; Έχω το ίδιο ακριβώς πρόβλημα, μετά το πρώτο iteration το δ είναι 0.

[Argirios]

Δεν έχω κάνει ακόμα έλεγχο ορθότητας για να ξέρω αν είναι σωστό, παίζει να είναι και λάθος τα αποτελέσματά μου. Αλλά ναι δεν υπολόγισα το P'' με αυτά που έχει στο "Preliminaries", χρησιμοποίησα τον αρχικό πίνακα P και τον έχω βάλει στον αλγόριθμο 1 για τα γινόμενα όταν χρειάζομαι το A*x.

[papoudaa]

Στην εργασία με τον Pagerank για την εισαγωγή των δεδομένων βολεύει το αρχείο να είναι σε μορφή adjacency list?

[Apostolof]

Στην εργασία με τον Pagerank για την εισαγωγή των δεδομένων βολεύει το αρχείο να είναι σε μορφή adjacency list?

Αν εννοείς το adjacency list που έχουν τα datasets αυτά δε βολεύουν. Αυτά που έχει το Stanford διαβάζονται πιο εύκολα και γρήγορα νομίζω.
Μόνο πρόσεξε σε αυτά τα datasets ότι τα IDs (τα FromNodeId και ToNodeId) που έχουν μέσα στο αρχείο είναι μεγαλύτερα από τον αριθμό των nodes που σου λέει ότι έχει το graph. Δε ξέρω αν κατάλαβα κάτι λάθος ή τα datasets έχουν λάθος αριθμούς nodes.

Τι αναπαράσταση χρησιμοποιείτε για τον sparse matrix; LIL, CSR, κάτι άλλο; Έχω δοκιμάσει 3 διαφορετικές και κάθε φορά έχω προβλήματα (το ένα δε βολεύει στο transpose, το άλλο δεν είναι δυναμικό κλπ).

[papoudaa]

Απο τα δεδομένα του Stanford μόνο το Web-google έχει ids μεγαλύτερα από τον αριθμό των κόμβων τα αλλα νομιζω είναι καλά μήπως πρόκειται για λάθος ?

[whatevah]

Η εργασία πήρε παράταση για τέταρτη 3/10

[Apostolof]

Η εργασία πήρε παράταση για τέταρτη 3/10

ΠΑΛΙ ΚΑΛΑ!

Απο τα δεδομένα του Stanford μόνο το Web-google έχει ids μεγαλύτερα από τον αριθμό των κόμβων τα αλλα νομιζω είναι καλά μήπως πρόκειται για λάθος ?

Όντως μόνο αυτό έχει

[papoudaa]

Για τον Gauss seidel η παραλληλοποίηση γίνεται ουσιαστικά στα δύο αθροίσματα της σχέσης ή πρεπει να χρησιμοποιηθει κάποια έτοιμη μέθοδος όπως red black ή wave front method