PDF Publication Title:
Text from PDF Page: 138
118 6 ⋅ software 6.1 adjacency matrices Throughout this chapter, we work with graphs. Each graph G = (V,E) consists of two sets: V = {1, . . . , n} is a set of vertices and E is a set of edges. Eachedge(u,v)= e ∈E isanorderedpairofverticeswithu ∈V,v ∈V. Each vertex is already identified by a numeric index, and we identify graphs with their binary adjacency matrix: ⎧ ⎪1 (i,j)∈E A=[Aij] Aij =⎨ (6.1) ⎪⎩0 otherwise. An undirected graph has both (i, j) and (j, i) in E. Hence, when G is undirected, then A is symmetric. All of the following generalizations of the binary adjacency matrix maintain this property. We handle graphs with weighted edges in two cases. In both cases, we consider the weights as elements from R. Let w(e) be a map from edges e ∈ E to weights in R. When all the weights exclude the value 0, our first case, then the weighted adjacency matrix is ⎧ ⎪w(e) e=(i,j)∈E A=[Aij] Aij =⎨ (6.2) ⎪⎩0 otherwise. This approach obviously fails when the edge weights can include the value 0. In this second case, we store the graph as a pair of matrices: a value matrix A and a structure matrix S. This setup yields and A=[Aij] S=[Sij] ⎧ ⎪w(e) e=(i,j)∈E Aij =⎨ ⎪⎩0 otherwise ⎧ ⎪1 (i,j)∈E Sij =⎨ ⎪⎩0 otherwise. (6.3) (6.4) By encoding the graph structure in S and leaving the values in A, we can dis- tinguish where edges occur and their values. A similar encoding for structural and weight matrices is described in Latora and Marchiori [2001]. In the remainder of the chapter, the type of the adjacency matrix—whether it is binary, weighted, or paired—is determined by the type of graph. To summarize, when G is unweighted, A is a binary adjacency matrix; G has edge weights in R − {0}, A is a weighted adjacency matrix; and G has edge weights in R, (A, S) is weighted adjacency matrix pair. We do not consider multi-graphs.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 |