PDF Publication Title:
Text from PDF Page: 139
With the setup of looking at graphs as adjacency matrices, we next discuss why these adjacency matrices are the natural graph data structures in the Matlab environment and briefly review what can be done with graphs in Matlab with only small snippets of code (section 6.2). 6.2 graphs in matlab Although Matlab lacks an explicit set of graph algorithms, it does provide a rich set of techniques that are often effective surrogates. Given the represen- tation of a graph as an adjacency matrix, and the efficient implementation of sparse matrices in Matlab [Gilbert et al., 1992], this is not greatly surprising. To be more concrete, many operations on graphs correspond precisely to an operation on the adjacency matrix. Operations on large, sparse graphs are efficient if the operation is also efficient on a sparse matrix. For example, computing in- and out-degrees is just an application of the sum command. din = sum(spones(A),1); % compute in-degrees dout = sum(spones(A),2); % compute out-degrees A more complete list of these equivalences is enumerated in Gilbert et al. [2008, Table 1]. Because Matlab already has efficient sparse matrices that easily handle millions of rows and columns with tens of millions of non-zeros on a single processor, re-using these sparse matrices as adjacency matrices of large graphs seems prudent. Let’s examine two more complicated examples. Clustering coefficients are measures of the local connectivity density around a vertex [Watts and Strogatz, 1998]. The key computation to compute clustering coefficients is counting the number of triangles around a vertex and dividing by the maximum possible triangle count.3 On a symmetric adjacency matrix A, the following Matlab code returns the clustering coefficients. A1=spones(A); A1=A1-diag(diag(A1)); % remove weights and self-loops d=sum(A1,2); d(d<2)=2; % avoid divide by zeros cc=diag(A1^3)./(d.*(d-1)); % return clustering coefficients Second, the dmperm function computes the Dulmage-Mendelsohn permu- tation by finding a maximum cardinality matching between the rows and columns when viewed as vertices of a bipartite graph. In the meshpart toolkit [Gilbert and Teng, 2002], this behavior is exploited to compute the strongly connected components of a graph. While each of these approaches demonstates a particular algorithm or computation in terms of primitive Matlab operations, each approach is also inefficient compared to a straightforward implementation on a graph.4 In the case of computing degrees, the in-degree counts are stored inside the Matlab sparse matrix type: we should not need to compute anything. In the case of clustering coefficients, we need only compute the diagonal elements of A3, and not the entire matrix. Finally, in the case of connected components, the dmperm function solves a bipartite matching problem instead of a simple linear pass over the graph edges using a standard connected component algorithm. Nonetheless, the issue with these computations is the algorithm implemen- tation and not the data structure. Thus, much as others in the literature, we represent graphs as sparse matrices in Matlab. Let’s review the sparse matrix data structure in Matlab. 3 For a vertex with degree d, it could form d(d − 1) with its neighbors. 6.2 ⋅ graphs in matlab 119 4 While these implementations are in- efficient on a single processor, graph operations are notoriously difficult to parallelize. Gilbert et al. [2007] posits that these “inefficient” implementations are better for parallel graph computa- tions.PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
| CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com | RSS | AMP |