1. 군집(community) 군집은 다음 두가지 조건을 모두 만족하는 하나의 node 집합이다. 1) 집합에 속하는 node 사이에 충분히 많은 link가 있다.2) 그러한 집합에 속하는 node와 속하지 않는 node 사이에는 충분히 적은 link가 있다. 딱 봐도 수학적인 정의는 아니지만 눈으로 보기에 군집을 구별하는 것은 쉽다 2. example SNS의 군집들은 사회적으로 의미있는 사회적 무리(Social circle)를 형성 실제 SNS에서는 돈을 받고 팔로워를 늘려주는 경우도 많다. 하나의 조직 내 분란으로 인해 군집이 형성 내분으로 동아리가 둘로 나뉘었다는데?? 회사 내 이메일 네트워크나 보고체계를 분석하여 그래프로 나타내면 회사 커뮤니케이션이 얼마나 효율적인지 알아볼 ..
1. connected component connected component란 다음 두 조건을 모두 만족하는 node의 집합 1) 모든 node가 path로 연결이 가능하다 2) 하나의 node를 추가 했을 때 위 조건을 만족해서는 안된다. 쉽게 생각해서 서로 연결되어 모여있는 집합들이 연결요소다. {9} 하나의 경우도 위 network에서 하나의 연결요소다. 두번째 조건이 무슨 말인지 이해하기 어려운데 {1,2,3,4}의 경우 node 5를 추가하면 {1,2,3,4,5}는 첫번째 조건을 만족하므로 {1,2,3,4}는 연결요소가 아니라는 뜻이다. 2. giant connected component In many networks as the network grows the components get gra..
1. 그래프로 표현하는 웹 웹은 웹페이지와 하이퍼링크로 포함된 거대한 방향성 그래프다 웹페이지를 node, 하이퍼링크를 다음 웹페이지를 향하는 link로 볼 수 있다. 물론 웹페이지는 하이퍼링크와 무관한 keyword정보를 포함한다 웹페이지의 하이퍼링크를 클릭하여 링크가 가리키는 다음 웹페이지로 이동할 수 있다 2. pagerank는 왜 등장했을까 2-1) 거대한 디렉토리 수십억에서 수백억개가 있을 것이라고 추측하는 웹페이지에서 원하는 정보를 어떻게 찾을 수 있을까? 먼저 전 세계에 존재하는 모든 웹을 카테고리로 구분하여 하나의 디렉토리로 저장했다. 97년도의 네이버 모습으로 카테고리로 웹을 저장했다는 것이 보인다 시간이 흐르면서 카테고리 수와 깊이는 무한정 증가할 것이고 심지어 카테고리 구분은 모호해지..
1. degree 어떤 node V의 degree란 V에 연결된 link의 수 혹은 V의 neighbor의 수와 같다. 그래서 V의 degree를 $d(V)=\left | N(V) \right | $로 표기 1은 2,5와 연결되어 있어서 1의 연결성은 2이다. 2. direction graph 방향성이 있는 그래프의 경우 나가는 연결성(out degree)와 들어오는 연결성(in degree)을 구분한다. 당연하겠지만 나가는 연결성(out degree)는 특정 node V에서 나가는 방향과 연결된 node의 수이고 $d_{out}(V)=\left | N_{out}(V) \right | $으로 표기 들어오는 연결성(in degree)는 특정 노드 V에 들어오는 방향으로 연결된 node의 수이고 $d_{in..
1. 연결 중심성(degree centrality) 한 node에 연결된 모든 edge의 개수 weighted 그래프의 경우 모든 weight의 합 directed 그래프의 경우 incoming degree는 그 node의 인기도, outcoming degree의 경우 그 node의 영향력 등으로 해석이 다를 수 있다. 2. eigenvector centrality(고유벡터, 위세 중심성) 연결 중심성이 오직 연결된 edge에만 의존한다는 점에서 아쉬워서 다른 node들간의 연관성도 보고 싶다는 것 그래프의 인접행렬 A와 node의 eigenvector centrality를 나타내는 벡터 $C_{e}$에 대하여 $\lambda C_{e} = AC_{e}$ 를 만족시키는 $C_{e}$ $C_{e}$는 A의..
1. path 두 node u와 v사이 path란 다음 두 조건을 모두 만족하는 순열이다. u에서 시작해서 v로 끝난다. 부분순열에서 연속된 두 node는 link되어 있다. 왕복하는 1,4,3,4,6,8도 1에서 8까지 path인데 1에서 시작해서 8로 끝나고 어느 두 연속된 node도 link되어 있어서 그렇다. 5에서 6은 끊어져있으니 1,3,4,5,6,8은 path가 아니다. 2. the length of path 해당 path에 존재하는 모든 link의 길이를 말한다. 1,4,6,8에는 3개의 link가 존재하므로 길이는 3 물론 link 1개의 길이가 1일때 그렇다 3. distance 두 node u와 v사이 distance는 모든 path중 최단경로의 길이 u와 v사이 모든 path를 구해..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
