캐나다내에서 워크 퍼밋 연장 신청후 이전 워크 퍼밋이 만료되어도 새로운 워크퍼밋을 받기까지 동일한 신분으로 일을 할수 있다. 일반적으로 연장 신청 심사가 대략 2~3달의 시간이 소요되기에, 이전 워크퍼밋이 만료가 되더라고 새로운 워크 퍼밋 연장이 허락되거나 거부되기전까지 “implied status”로서 일할수 있다고 한다. 물론 연장 거부가 되면 그 통보를 받은 후 부터는 일을 못하겠지만....

작년에 implied status로 새로운 워크 퍼밋을 받기전까지 한달간 일한적이 있기에 경험상 명확하다.


그런데 이제 이전 워크퍼밋이 만료되고 새로운 워크퍼밋을 받기전에 잠시동안 캐나다 밖을 나갔다 다시 돌아와야하는 급한 상황이 발생한다면 다시 재입국할때 어떠한 문제가 발생할까?


사실 새로운 워크 퍼밋을 받기 전까지는 캐나다를 떠나면 골치아프다. 가장 좋은 것을 연장 워크 퍼밋을 받고 난 후에 이동하는 것이 가장 깔끔하다. 하지만 정말 어쩔수 없는 상황이라면...

올해 이러한 상황이 발생해서 어쩔수 없이 잠시 해외를 다녀왔다. 캐나다를 출국할때는 만료가 안되었는데 다시 재입국 할때는 워크퍼밋이 만료가 되었고..새로운 워크퍼밋을 아직 받지 못한 상황.. ㅜㅜ

출국하기전에 캐나다 이민국 (CIC)에 문의를 했다.

그쪽에서 설명해 주기를 두가지 경우가 발생할수 있다고 얘기해줬다.

첫번째, 캐나다 재 입국시 공항에서 새 워크퍼밋을 다시 발급해 줄 경우. 이 경우 다시 연장 신청비 ($150)를 내야한단다. (그럼 전에 냈던 신청비는 다시 돌려 받을수 있냐고 물었더니 받을수도 있고 못 받을수도 있고 애매한 답변을 줌)

두번째, 임시 visitor로 입국하는 경우, 단 임시 visitor로 재 입국할 경우 새로운 워크 퍼밋을 받기 전까지는 일할수 있는 권리를 잃어버림, 즉 워크 퍼밋 만료후 캐나다를 떠났기에 implied status의 자격을 상실하게 되어 새로운 워크 퍼밋을 받기 전까지 일할수 없단다 (이 경우는 우리나라 처럼 a visitor visa exempt country에만 해당된다).

입국할때 심사관, 상황에 따라 틀릴 수 있기에 어떤 경우가 될지는 장담은 못한다고 하더라. 하지만 중요한 것은 캐나다 출국 전에 반드시 모든 서류를 챙겨가라고 일러주었다. 워크 퍼밋 연장 신청때 제출했던 증빙 서류들 (offer letter 등), 워크 퍼밋 연장 신청을 했다는 확인 문서 (온라인으로 신청했다면 연장 신청한 confirmation을 다운받을수 있음). 재 입국할때 증빙을 위해서..


이제 재 입국할떄의 나의 상황을 설명하자면...난 밴쿠버를 통해 캐나다를 재 입국했다.

캐나다 세관신고서에 캐나다 거주로 작성해서 입국 심사대에 제출하니. 몇가지 질문을 하더라.

- 캐나다 거주하냐? 그렇다. 포닥으로 일하고 있다. (5~6 번의 경험상 보통은 여기서 워크 퍼밋 확인후 통과함)

- (워크퍼밋이 만료된 것을 확인후) 너 워크 퍼밋 expire 되었는데? 그렇다. 그래서 연장 신청을 했는데 아직 못받았다.

- 언제 신청했냐? 7월 말에 신청했다.

- 너 계속 일하기를 원하는거냐? 그렇다.

- 알았다.

그러더니 내 세관신고서에 도장을 찍는 대신 18(또는 81)이란 숫자를 적더라.

짐을 찾고 환승을 위해 이동하려고 세관신고서를 제출하니 exit immigration으로 안내를 받아 들어 갔다. (처음 캐나다 입국시 워크 퍼밋을 받았던 곳과 다른 곳). 앞에 다른 사람들 검사 하는 것 보니 좀 수상하거나 특별한 검사가 필요한 사람들이 이곳으로 오는듯 싶더라. 짐을 열어 이것저것 검사하기도 하고..이것저것 공격적으로 물어보기도 하고...

나는 간단히 내 상황을 설명하니 그냥 여권을 가지고 연장 신청한 것을 확인하러 다녀왔다. 그리고 새로운 워크 퍼밋 연장이 이미 approve 되었다면서 세관신고서에 도장을 찍어주면서 가라고 하더라. 새로운 워크 퍼밋은 너 집으로 갈꺼라면서..

아직까지 새로운 워크퍼밋이 도착 안한걸 보니 내부적 심사는 완료되었는데 아직 발송이 안된듯 싶다.


결론은 캐나다 내에서 워크퍼밋 연장 신청후 새로운 워크 퍼밋이 나오기전에 (이전 워크퍼밋 기간이 만료되어도) 잠시 캐나다 밖으로 나갔다가 재 입국을 할수는 있기는 하다. 물론 사람, 상황에 따라 틀릴 수 있어 장담은 못하겠다. 또한 이곳저곳 인터넷을 찾아보니 될수 있으면 새로운 워크퍼밋을 받기전에 캐나다를 나가지 말라고 강력히 추천하더라. 나는 어쩔수 없이 나갔다 오긴 했지만, 요즘 한국도 캐나다 입국 심사가 까다로워 졌다고 하는데 별로 권장하지는 않는다.

출국전에 인터넷으로 나름 많이 찾아봤는데 많은 정보가 부족한듯 싶어 글을 남긴다.



저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by HNKim

이전 글에서 폭소노미에 대한 Tripartite 그래프에 대해 기술하였고 그 그래프에 대한 인접행렬(adjacency matrix) A를 구했다.


이번 글에서는 Tripartite 그래프 구조에 대하여 PageRank를 구하는 것에 대하여 기술하겠다. 페이지랭크에 대한 기본적 개념과 그 자세한 계산 방법및 자료/논문들은 웹에 너무나 많으니, 여기서는 전통적인 PageRank의 자세한 설명은 생락하겠다. 웹 하이퍼링크에 대한 그래프가 아닌 폭소노미 그래프에 대하여 계산하는 것을 설명하겠다 (만약 인접행렬 A가 웹 그래프의 하이퍼링크에 대한 것이라면 전통적인 PageRank와 똑같다).

PageRank가 랜덤 워크(Random Walk) 모델을 이용한 랭킹 방법이니 우선 마코브 체인(Markov Chain)의 전이확률 (transition probability)를 표현하는 tripartite 그래프에 대한 전이행렬(transition matrix) P를 구하자. 수학적으로, 인접행렬 A의 각 행 벡터(row vector)에 대하여 L1-norm을 1로 만들면 된다 (각 행의 모든 값의 합이 1이 된다). 다시 말해서 Arow-stochastic 행렬이 tripartite 그래프의 전이행렬 P가 된다.

전이 행렬을 이용하여 (global) PageRank 계산을 수식으로 나타내면 다음과 같다.

 


  • d : damping factor, teleportation probability 등으로 불리며 일반적으로 0.85 값을 이용함
  • PTN × N  전이행렬 P의 전치행렬 (transpose of P)
  • r: 1 × N  PageRank (열) 벡터 (모든 node에 대한 PageRank 값을 가지는 벡터 ). 마코브 체인 관점에서 stationary vector, dominant eigenvector.
  • N : 그래프의 총 노드 갯수 (즉, |U|+|T|+|R|)
  • 1 : 1로만 구성된 1 × N  (열) 벡터


식 (1)이 얼듯 보기에는 복잡해 보이는 수식처럼 보이지만 아래 그림에 보듯이 단순 행렬-벡터 곱이다.

행렬-벡터 곱의 페이지랭크 벡터 계산


솔루션 페이지랭크 벡터 r을 구하는 가장 심플한 방법이 Power method이다. 단순히 Initial 페이지랭크 벡터 r 의 모든 값은 1/N 으로 설정하고 r 의 값들이 더 이상 변동이 없이 수렴(convergence)할때 까지 식(1)을 계속 반복해서 구하면 된다. Page et al. (1999)[각주:1]을 보면 32억개의 웹페이지 링크에 대하여 대략 52번의 반복으로 페이지랭크 벡터 r이 수렴하였다. 또한 행렬 P는 매우 sparse하기에 (sparse matrix) 쉽게 구현이 가능하다. 모든 PageRank 계산이 결국 sparse matrix-vector multiplication 이기에 페이지랭크 계산 복잡도(complexity)가 일반적으로 O(iN2)이 아니라 보통 O(im)[각주:2]라 얘기한다 (i : 반복 횟수, m: 그래프 엣지의 총수).

참고) 특정 웹페이지 (사이트)에 대한 PageRank란 결국 임의의 사용자인 랜덤 서퍼(Random surfer)가 무작위로 하이퍼링크를 따라 웹 페이지(사이트)들을 방문했을 때 그 특정 웹페이지에 도달(방문)할 확률을 의미한다. 따라서 PageRank는 일종의 stationary 분산(확률)이기에 모든 노드의 PageRank 값들의 합은 항상 1이 된다. 식 (1)을 간단한 예제로 계산해봐라. 벡터 r의 L1-norm (r의 모든 값의 합)은 항상 1이 될 것이다.

실 현실에서 수억개 이상의 웹 페이지에 대하여 특정 웹 페이지의 PageRank가 0.1을 넘는 다는 것은 거의 불가능할 것이다. 아마 설령 최고의 값이라 해도 0.01도 쉽게 넘지 못할듯... 구글 툴바에서 제공되는 0~10까지의 점수는 실제 그 사이트에 대한 정확한 PageRank 값이 아니라  PageRank 범위와 구글의 랭킹 전략에 따라 0점에서 10점으로 환산한 점수 일 것이다.


일반 웹 페이지 그래프에 대한 PageRank와 폭소노미 tripartite 그래프에 대한 PageRank의 차이는 다음과 같다.

  1. 폭소노미 그래프는 방향성이 없는 undirected 그래프이다. 따라서 웹페이지의 하이퍼링크와 다르게 A에서 B로의 연결된 엣지가 존재한다면 B에서 A로의 엣지 역시 존재한다. 즉 인접행렬 A대칭 행렬 (Symmetric matrix)이다. 구글 페이지랭크에서 말하는 댕글링(dangling) 노드[각주:3]가 존재하지 않는다. 이러한 undirect 속성은 direct 그래프에 대한 페이지랭크와 조금 다른 결과를 초래한다.
  2. tripartite 그래프이기에 아래 그림과 같이 성질이 서로 다른 세개의 집합에 대한 랭크가 존재할 수 있다: 사용자들에 대한 랭크, 태그들에 대한 랭크, 리소스들에 대한 랭크. 따라서 응용 목적에 따라 다양하게 활용 할 수 있다.


Hotho et al. (2006)[각주:4]는 undirect로 인해 발생되는 문제를 해결하기 위해 FolkRank란 알고리즘을 제안하였다.

포크랭크에 대한 자세한 사항은 시간이 허락한다면 다음에...


  1. Brin, S., Page, L., Motwami, R., and Winograd, T. 1999. The PageRank citation ranking: Bringing order to the Web. Technical Report, Stanford University. [본문으로]
  2. 경우에 따라 compressed sparse format등을 활용하면 O(iN)으로 구현 가능하다. [본문으로]
  3. 다른 노드들로부터 안으로 들어오는 링크가 존재하지만 밖으로 나가는 링크가 하나도 존재하지 않은 노드 [본문으로]
  4. Hotho, A., Jäschke, R., Schmitz, C., and Stumme, G. 2006. Information retrieval in folksonomies: Search and ranking. In Proc. 3rd European Semantic Web Conf., 411–426 [본문으로]
저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by HNKim


티스토리 툴바