주어진 그래프의 개별 정점에서부터 점점 군집을 병합해가는 상향식 알고리즘 1. first phase - modularity optimization 처음 주어진 상태에서는 개별 node 1개씩이 하나의 군집이라고 생각 특정 node i를 그것의 이웃(neighbor)인 j에 병합시키면서 modularity의 변화량을 계산함 원래 상태의 modularity와 이웃인 j에 병합시킨 뒤 modularity의 차이를 계산한다. 병합시키면 군집이 생기니까 modularity는 최소한 감소하지는 않음 이 때 최대로 modularity가 증가하는 이웃 j가 있을 것인데 그곳에 i를 포함시킨다. 증가하는 경우가 없다면 어떠한 곳에도 포함시키지 않는다. 다시 다른 node v를 선택하여 위 과정을 반복, 모든 node에..
1. bit와 byte 1bit는 2가지 경우를 표현하는 정보의 단위로 0 아니면 1을 표현한다 1byte는 8bit와 같으며 몇가지를 표현할 수 있을까? 1bit가 2가지를 표현하므로 $2^{8}$가지를 표현할 수 있다 보통 자주 언급되는 bit가 정수를 어디까지 표현할 수 있을까?? 1bit가 0 아니면 1을 표현하므로 0부터 $2^{1} - 1$까지 표현한다고 말한다 2bit는 $2^{2}$가지를 표현하므로 0,1,2,3의 4가지를 생각하여 0부터 $2^{2} - 1$까지 표현한다고 말한다 비슷하게 1byte=8bit는 0부터 $2^{8} - 1$까지 음이 아닌 정수를 표현할 수 있다 음수를 포함하겠다면? 0부터 255까지 256가지를 절반으로 나눠서 128가지씩 나눠가져서 –128부터 127까..
29940번: Sum (acmicpc.net) 배열이 서로 다른 원소들로 이루어져있고 정렬되어 있을때, 여기서 고른 서로 다른 두 수의 합이 s가 되는 경우의 수를 구하는 문제 투 포인터로 어떻게 해결할 수 있을까 보통 투 포인터하면 i = 0, j = 0으로 같은 방향에서 시작해서 j를 1씩 계속 증가시키다가, 특정 조건에서 멈추고 다시 i를 1 증가시키고 다시 j를 계속 증가시키고... 같은 방향으로 움직이지만 두 수 A[i] + A[j] = s가 될려면 i = 0으로 고정되어 있을 때 A[j] = s - A[0]로 확정적으로 구할 수 있다. 그러면 배열 A가 서로 다른 수로 이루어져 있고 정렬되어 있으므로 모든 i = 0,1,2,..,n-1는 작은 수부터 시작하므로 반대편 A[j] = s - A[..
1. viral marketing 소비자들로 하여금 상품에 대해 긍정적인 입소문을 내게하는 기법 효과적으로 상품 정보가 소비자들에게 알려질려면 소문의 시작점이 중요하다. 시작점에 따라 입소문이 전파되는 범위가 달라지기 때문이다. 2. importance of seed set SNS 인플루언서들이 높은 광고비를 받는 이유가 있다. 전파 모형에서 첫 시작점을 seed set이라고 부르는데 viral marketing에서는 이 시작점을 잘 선택해야 광고 효과를 극대화할 수 있다. 케이트 미들턴을 광고 모델로 선택했더니 판매량이 급증했다 선형 임계치 모형에서도 seed set의 중요성을 볼 수 있는데 처음에 u와 v를 선택했을 때 총 9명(7명 전파)이 A를 선택했다. 만약 위 모형에서 다음과 같이 ..
1. idea 군집을 찾는 대표적인 하향식 알고리즘으로 전체 그래프에서 시작하여 군집들이 서로 분리되도록 link를 순차적으로 제거함 서로 다른 군집을 연결하는 다리 역할을 하는 link를 먼저 제거해나가야 군집들이 분리 될 것이다. 2. betweenness centrality 그래프의 임의의 두 node의 최단 경로 위에 특정 link가 몇번이나 놓이는지 계산 link A-B는 양 옆 4개의 node중 하나를 선택하여 만든 최단 경로에 모두 존재해야하므로 4*4=16가지가 있다. 따라서 그림을 보면 직관적으로 betweenness centrality가 높은 link는 두 군집을 연결하는 다리 역할을 할 가능성이 높다. 3. algorithm 주어진 그래프에서 모든 link의 매개 중심성을..
1. 1보다 큰 10진수를 다른 진수로 변환하는 방법 주어진 수를 변환하고자하는 진수의 base로 계속 나누고 나머지를 써둔다 마지막에 저장해둔 나머지 뒤에서부터 가지고옴 예를 들어 133은 3진법으로 변환하면 $11221_{(3)}$이다. 2. 10진수 소수를 진수 바꾸는 방법 반면 소수는 방법이 조금 다른데 base를 계속 곱해나간 뒤 소수점을 넘은 정수는 옆에 따로 저장해두고 정수를 뺀 나머지를 다음 단계로 보낸 뒤 base를 계속 곱해 다음 단계로 보낸 나머지 부분이 0이 될때까지 반복함 정수 변환은 맨 뒤에서부터 앞으로 가지고 왔지만 맨 처음부터 따로 저장한 수를 맨 뒤까지 가지고 오면 끝 예를 들어 0.375는 8진수로 변환하면 $0.3_{(8)}$이고 0.1을 2진수로 변환하면 $0.00..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
