THMMY.gr

Συζήτηση για την τέταρτη εργασία.

Σήμερα δεν άνοιξε η 4η; Επειδή στο e-learning ως ημερομηνία παράδοσης έχει 29/12/17-22/01/18, ακριβώς ίδια με την τρίτη.

Ναι. Κάποιο λάθος πρέπει να έχει γίνει.

Γνωρίζει κανείς αν η 4η μπορεί να πάει για Σεπτέμβρη?

Περσυ μπορουσε, για σιγουρια ρωτηστε το Φλωρο ;)

Μάθαμε τελικά αν θα πάει για Σεπτέμβρη ?  :o

Ναι πάει. Υπάρχει σχετική ανακοίνωση στο elearning.

Ευχαριστώ  ;)

ψήνει κανείς να κάνουμε την 4η εργασία μαζί ??

έλεγα να πάρω τώρα πτυχίο αλλά στο τσακ είμαι να πω γάμα το και να την αφήσω για το καλοκαίρι xD  :'(

Ξέρουμε αν θα ξαναπάρει παράταση η 4η εργασία ή να μη την ξεκινήσω καν?

Τα θέματα της 4ης εργασία παραμένουν ίδια μέχρι το Σεπτέμβριο;

Όταν κανονικοποιούμε έναν πίνακα το κάνουμε ανά σειρά Χij/norm(Xi)? Ή συνολικά, δηλαδή για το κάθε στοιχείο Xij/norm(X)?

Εξαρτάται από το τι θες να επιτύχεις και τι εκφράζουν οι σειρές/στήλες του πίνακα. Αν τα στοιχεία του πίνακα εκφράζουν το ίδιο πράμα τότε θα κάνεις το 2ο. Καλύτερα να κάνεις Xij / max(Xij), όπου max(Xij) το στοιχείο του πίνακα X με τη μεγαλύτερη τιμή.

Όλα το ίδιο εκφράζουν απ'ότι κατάλαβα, πιθανότητα μετάβασης από i σε j, άρα μάλλον το δεύτερο, ευχαριστώ!  ;)

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

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

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

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

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

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

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

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. Ναι

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

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

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

0      0      0
1      0      0
1      1      0

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

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

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

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

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

Αν εννοείς το adjacency list που έχουν τα datasets αυτά (http://www.cs.toronto.edu/~tsap/experiments/download/download.html) δε βολεύουν. Αυτά που έχει το Stanford (https://snap.stanford.edu/data/) διαβάζονται πιο εύκολα και γρήγορα νομίζω.
Μόνο πρόσεξε σε αυτά τα datasets ότι τα IDs (τα FromNodeId και ToNodeId) που έχουν μέσα στο αρχείο είναι μεγαλύτερα από τον αριθμό των nodes που σου λέει ότι έχει το graph. Δε ξέρω αν κατάλαβα κάτι λάθος ή τα datasets έχουν λάθος αριθμούς nodes.

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

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

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

ΠΑΛΙ ΚΑΛΑ! :D :D :(


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

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

Έχω το εξής πρόβλημα, ενώ τρέχει σωστά και οι τιμές του pagerank συμφωνούν με αυτές από άλλους κώδικες που βρήκα, μετά από κάποιο σημείο το δ σταματάει να πέφτει και η λούπα δε τελειώνει ποτέ (τουλάχιστον μέχρι μερικές χιλιάδες που το άφησα). Παίζει να βάζω πολύ μικρό αριθμό στο κριτήριο σύγκλισης;
Αν έτρεξε κανείς για τα datasets του Stanford ας δώσει μια βοήθεια. Πχ για το web-google, πόσα iterations θέλει για να συγκλίνει (και με τι κριτήριο σύγκλισης και α);

Επίσης τo pagerank πρέπει να το τρέχουμε σε φάσεις; Αυτό που λέει στη σημείωση για το misconvergence (https://pdfs.semanticscholar.org/ff20/b4a37fd56414c57a246c3898fc8f8a99fcf9.pdf) εννοώ. Εσείς το υλοποιήσατε;

Άντε μια βοήθεια μπας και το σώσουμε...

Νομίζω ότι ως κριτήριο σύγκλισης είναι καλύτερο αυτό που αναφέρει στο paper: xi of page i has converged when |xi(k+1)-xi(k)|/|xi(k)|<10^-3, δηλαδή να μη ξαναυπολογίζεται το pagerank της σελίδας i αν είναι πολύ μικρή η διαφορά xi(k+1)-xi(k) γιατί δεν έχει και πολύ νόημα και έτσι γλιτώνεις πολλούς υπολογισμούς. Εγώ φτιάχνω έναν vector int iters[1xNODES], το αρχικοποιώ με μηδενικά και όταν ισχύει το κριτήριο σύγκλισης για κάποιο node i, αποθηκεύω τον αριθμό των iterations που έχουν γίνει στην θέση iters [ i ].  
Σε κάθε επανάληψη κάνω πρωτα έλεγχο αν το iters [ i ] είναι 0 ή όχι και αν δεν είναι, κάνω continue χωρίς υπολογισμούς. Με αυτό τον τρόπο κρατάς και τον αριθμό των iterations που χρειάστηκε η κάθε σελίδα.

Tην αναπαράσταση του sparse matrix την κάνεις με CSR; Ή με κάποιον άλλο τρόπο; Ή φτιάχνεις τον P; Ή τον P'; Έγω φτιάχνω τον P και τον χρησιμοποιώ κατευθείαν στην σχέση αλλά σίγουρα δεν θα δουλεύει για μεγάλα datasets με τόσα πολλά calloc  :'(.

Στο δ δεν έχει τον παρονομαστή που έγραψες |xi(k)| στο pdf που ακολουθώ, ελπίζω να είναι αυτό γιατί είναι απλή η λύση. Πάντως εγώ δοκίμαζα με δ της τάξης 10^-6, οπότε ίσως είναι και αυτό.

Κάτι παρόμοιο κάνω και εγώ με αυτό που περιγράφεις για τη σύγκλιση, αλλά κρατάω μόνο έναν bool αντί για τον αριθμό των iterations. Το δικό σου είναι καλύτερο, ίσως το κλέψω :P

Φτιάχνω τον P'. Και έχω και έναν άλλο sparse που είναι ο A_CN.
Τον P' τον φτιάχνω σαν απλό COO αρχικά για να διαβάσω το αρχείο, κάνω το transpose και μετά τον μετατρέπω σε CSR (όλα αυτά στην αρχή, πριν τα iterations).
Τον άλλο τον έχω COO, έχει από την αρχή το μέγιστο μέγεθος (number_of_edges) για να μη γίνονται reallocs. Αρχικά έχει 0 σε όλα και καθώς προστίθενται στοιχεία αυξάνει μία μεταβλητή size.