Computation on GraphsGraph partitioningClustering benchmark graphGraphs and Sparse MatricesExample: Web graph and matrixWeb graph: PageRank (Google) [Brin, Page]A Page Rank MatrixSocial Network Analysis in Matlab: 1993Slide 9Slide 10A graph problem: Maximal Independent SetSequential Maximal Independent Set AlgorithmSlide 13Slide 14Slide 15Parallel, Randomized MIS Algorithm [Luby]Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Sparse Adjacency Matrix and GraphSparse matrix data structure (stored by rows)Compressed graph (or sparse matrix) data structure, stored by rowsDistributed graph / sparse matrix data structureStrongly connected componentsRMAT Approximate Power-Law GraphStrongly Connected ComponentsBreadth-First Search: Sparse mat * vecSlide 31Slide 32Sparse Matrix-Vector MultiplicationComputation on GraphsComputation on Graphs2Graph partitioningGraph partitioning•Assigns subgraphs to processors•Determines parallelism and locality.•Tries to make subgraphs all same size (load balance)•Tries to minimize edge crossings (communication).•Exact minimization is NP-complete.edge crossings = 6edge crossings = 10Clustering benchmark graphClustering benchmark graphGraphs and Sparse Matrices Graphs and Sparse Matrices 1 1 12 1 1 13 1 1 14 1 1 5 1 1 6 1 1 1 2 3 4 5 6362154•Sparse matrix is a representation of a (sparse) graph•Matrix entries are edge weights•Diagonal contains self-edges •Number of nonzeros per row is the vertex degreeExample: Web graph and matrixExample: Web graph and matrix•Web page = vertex•Link = directed edge•Link matrix: Aij = 1 if page i links to page j12347651 52 3 4 6 71523467Web graph: PageRank (Google) Web graph: PageRank (Google) [Brin, Page] •Markov process: follow a random link most of the time; otherwise, go to any page at random.•Importance = stationary distribution of Markov process.•Transition matrix is p*A + (1-p)*ones(size(A)), scaled so each column sums to 1.•Importance of page i is the i-th entry in the principal eigenvector of the transition matrix.•But the matrix is 1,000,000,000,000 by 1,000,000,000,000.An important page is one that many important pages point to.A Page Rank MatrixA Page Rank Matrix• Importance ranking of web pages•Stationary distribution of a Markov chain•Power method: matvec and vector arithmetic•Matlab*P page ranking demo (from SC’03) on a web crawl of mit.edu (170,000 pages)Social Network Analysis in Matlab: 1993Social Network Analysis in Matlab: 1993Co-author graph from 1993 HouseholdersymposiumSocial Network Analysis in Matlab: 1993Social Network Analysis in Matlab: 1993 Which author hasthe most collaborators?>>[count,author] = max(sum(A)) count = 32 author = 1>>name(author,:) ans = Golub Sparse Adjacency MatrixSocial Network Analysis in Matlab: 1993Social Network Analysis in Matlab: 1993Have Gene Golub and Cleve Moler ever been coauthors? >> A(Golub,Moler) ans = 0No.But how many coauthors do they have in common? >> AA = A^2; >> AA(Golub,Moler) ans = 2And who are those common coauthors? >> name( find ( A(:,Golub) .* A(:,Moler) ), :) ans = Wilkinson VanLoanA graph problem: Maximal Independent SetA graph problem: Maximal Independent Set18765432• Graph with vertices V = {1,2,…,n}• A set S of vertices is independent if no two vertices in S are neighbors.• An independent set S is maximal if it is impossible to add another vertex and stay independent• An independent set S is maximum if no other independent set has more vertices• Finding a maximum independent set is intractably difficult (NP-hard)• Finding a maximal independent set is easy, at least on one processor.The set of red vertices S = {4, 5} is ind ependent and is maximalbut not maximumSequential Maximal Independent Set AlgorithmSequential Maximal Independent Set Algorithm187654321. S = empty set;2. for vertex v = 1 to n {3. if (v has no neighbor in S) {4. add v to S5. }6. }S = { }Sequential Maximal Independent Set AlgorithmSequential Maximal Independent Set Algorithm187654321. S = empty set;2. for vertex v = 1 to n {3. if (v has no neighbor in S) {4. add v to S5. }6. }S = { 1 }Sequential Maximal Independent Set AlgorithmSequential Maximal Independent Set Algorithm187654321. S = empty set;2. for vertex v = 1 to n {3. if (v has no neighbor in S) {4. add v to S5. }6. }S = { 1, 5 }Sequential Maximal Independent Set AlgorithmSequential Maximal Independent Set Algorithm187654321. S = empty set;2. for vertex v = 1 to n {3. if (v has no neighbor in S) {4. add v to S5. }6. }S = { 1, 5, 6 }work ~ O(n), but span ~O(n)Parallel, Randomized MIS Algorithm Parallel, Randomized MIS Algorithm [Luby][Luby]187654321. S = empty set; C = V;2. while C is not empty {3. label each v in C with a random r(v);4. for all v in C in parallel {5. if r(v) < min( r(neighbors of v) ) {6. move v from C to S;7. remove neighbors of v from C;8. }9. }10. }S = { }C = { 1, 2, 3, 4, 5, 6, 7, 8 }Parallel, Randomized MIS Algorithm Parallel, Randomized MIS Algorithm [Luby][Luby]187654321. S = empty set; C = V;2. while C is not empty {3. label each v in C with a random r(v);4. for all v in C in parallel {5. if r(v) < min( r(neighbors of v) ) {6. move v from C to S;7. remove neighbors of v from C;8. }9. }10. }S = { }C = { 1, 2, 3, 4, 5, 6, 7, 8 }Parallel, Randomized MIS Algorithm Parallel, Randomized MIS Algorithm [Luby][Luby]187654321. S = empty set; C = V;2. while C is not empty {3. label each v in C with a random r(v);4. for all v in C in parallel {5. if r(v) < min( r(neighbors of v) ) {6. move v from C to S;7. remove neighbors of v from C;8. }9. }10. }S = { }C = { 1, 2, 3, 4, 5, 6, 7, 8 }2.6 4.15.93.11.25.89.39.7Parallel, Randomized MIS Algorithm Parallel, Randomized MIS Algorithm [Luby][Luby]187654321. S = empty set; C = V;2. while C is not empty {3. label each v in C with a random r(v);4. for all v in C in parallel {5. if r(v) < min( r(neighbors of v) ) {6. move v from C to S;7. remove neighbors of v from C;8. }9. }10. }S = { 1, 5 }C = { 6, 8 }2.6 4.15.93.11.25.89.39.7Parallel, Randomized MIS Algorithm Parallel, Randomized