[데이터마이닝] 5.링크분석(Link analysis) 5.2절 연습문제(Exercise 5.2.1 )

Exercise 5.2.1 

Suppose we wish to store an n × n boolean matrix (0 and 1 elements only). We could represent it by the bits themselves, or we could  represent the matrix by listing the positions of the 1’s as pairs of integers, each
integer requiring ⌈log2 n⌉ bits. The former is suitable for dense matrices; the latter is suitable for sparse matrices. How sparse must the matrix be (i.e., what  fraction of the elements should be 1’s) for the sparse representation to save space?

 

---

(x,x)로 1들의 위치를 표현한다. (여기서 x는 ⌈log2 n⌉ bits 로 표현 가능한 정수)

따라서 하나의 1을 표현할때 필요한 메모리 용량은 2* ⌈log2 n⌉ bits 이며 

전체 n × n boolean matrix에서 총 k개의 1이 있다고 할때 필요한 메모리 용량은 2*k*⌈log2 n⌉ bits 이다. 

따라서 2*k*⌈log2 n⌉ < n^2을 만족하는 만큼의 1의 개수인 k 를 구하면 된다. 

k<  n^2 / 2*⌈log2 n⌉ 

 

 

 

Exercise 5.2.2 

Using the method of Section 5.2.1, represent the transition
matrices of the following graphs:
(a) Figure 5.4.

(b) Figure 5.7.

 

5.2.1절의 방식이란 다음과 같다.

---

We can thus represent a column by one integer for the out-degree, and one integer
per nonzero entry in that column, giving the row number where that entry
is located.

각 노드의 출력 차수와 그 후속자(successors) 리스트로  전이행렬M 을 표현할 수 있다. 

 

 

 Exercise 5.2.3

Using the method of Section 5.2.4, represent the transition matrices of the graph of Fig. 5.3, assuming blocks have side 2.

이것을 5.2.4절의  방식으로 표현해보자

A and B to A and B

C and B to A and B

A and B to C and D

C and D to C and D

 

---

5.2.4절의 방식이란 다음과 같은 방식

 

---

참고

6개의 노드를 3개의 block으로 나움

r_new 전체를 읽으면 cost가 너무 많이 드니까. r_new를 fit in mermoy한 k blocks 나눈다

한 block내에 노드가 0과 1뿐이므로 노드 0의  전체 outgoing degree는 4이지만 block 내 에서는 destination이 0과 1 뿐이다. 따라서 전이행렬 M에서 destination 0,1에 해당하는 값만 읽어오면 된다. 

 

 

Exercise 5.2.4 

Consider a Web graph that is a chain, like Fig. 5.9, with n nodes. As a function of k, which you may assume divides n, describe the representation of the transition matrix for this graph, using the method of  Section 5.2.4