나의 큰 O는 log x야

네트워크 이론에서는 전달가능성(Communicability)이라는 개념을 다룹니다. 두 노드가 얼마나 잘 연결되어 있는지를 보는 개념이라고 할 수 있는데요, 이 포스트에서는 전달가능성의 개념과 계산방법 및 그와 관련된 여러 이야기에 대해서 다뤄보겠습니다. 전달 가능성(Communicability)학교에서 소문이 퍼지는 일을 생각해봅시다. 소문은 사람에서 사람에게로 1대1로만 퍼진다고 가정하고, 둘이 친한 사이일수록 더 잘 퍼진다고 합시다. 만약 사람 A가 어떤 정보를 알고 있다고 할때, 이 정보가 다른 사람 B에게 얼마나 잘 퍼지는지 어떻게 계산할 수 있을까요? 만약 A와 B가 직접 친한 사이라면 A가 직접 B에게 그 정보를 전달해줄테니 금방 퍼질거라고 생각할 수 있습니다. 혹은 둘 사이가 전혀 모르는 ..

그냥 공부 2017. 7. 30. 01:49

앞서서 네트워크 이론의 기본적인 개념들을 설명했으니, 실제로 우리 주변에서 찾아볼 수 있는 네트워크들에서 어떤 현상이 일어나는지 살펴보도록 하지요. 실제 세계 네트워크의 성질랜덤 네트워크와 다르게 실제 세상의 네트워크들은 빈익빈 부익부 현상이 있습니다. 즉 다른 녀석들과 많이 연결된 애들이 전체 연결의 대부분을 차지하고, 조금 연결된 녀석들이 엄청나게 많습니다. 마치 20%가 80%의 돈을 가져가고, 나머지 80%가 20%의 돈을 가져가는것처럼 말이죠. 파레토의 법칙이라고도 불리는 이런 현상을 Power-law 분포(멱법칙)라고 합니다. 또한 결집계수(Clustering Coefficient)도 굉장히 높은 편입니다. 즉 내 친구의 친구도 내 친구인 경우가 많다는 거죠. 랜덤으로 그래프를 생성하면 이런일..

그냥 공부 2017. 4. 5. 15:57

앞서 중심성, 결집계수에 대해서 다뤄보았으니, 이제 네트워크 이론에서 두 노드가 얼마나 유사한지를 계산하는 방법에 대해서 논해봅니다. 어떻게 두 노드가 유사한지를 판단할 수 있을까요? 가장 간단한 방법으로는 두 노드의 이웃이 얼마나 겹치는지를 살펴볼 수 있겠죠. 만약 모든 이웃이 겹친다면 두 노드는 아예 똑같은 노드, 겹치는 이웃이 하나도 없다면 전혀 다른 노드라고 봐도 되겠죠? 구조적 등위성(Structural Equivalence)앞서 설명한 겹치는 이웃의 수를 보고 유사도를 판단하는 방법을 구조적 등위성이라고 합니다. SNS를 예시로 설명하자면, 친구가 겹치는 사람이 많을 수록 유사한 유저라고 본다는 것이죠. (N(i)는 노드 i의 이웃 노드들의 집합)이때 i와 j의 단순 유사도는 i의 이웃 집합과..

그냥 공부 2017. 3. 20. 21:05

앞서서 네트워크 상에서 어떤 노드가 중요한지를 알아보는 중심성을 살펴봤는데, 이번에는 네트워크가 얼마나 똘똘 뭉쳐있는지를 알려주는 '결집계수(Clustering Coefficient)'에 대해서 살펴보도록 합시다. 결집계수는 추이성(Transitivity)을 기반으로 합니다. 이는 A->B이고 B->C이면 A->C가 되는 성질을 말합니다. 수학에서 부등호나 등호 같은 경우가 추이성을 가지는 관계지요. 문제는 네트워크 그래프의 노드들은 항상 추이성을 가지지 않을 수도 있다는 것에 있습니다. A가 B와 연결되고, B가 C와 연결되어있다고 하더라도, A가 C와 반드시 연결되지 않을수도 있기 때문이죠. 뭉쳐있는 정도를 얘기하다가 추이성을 꺼낸 이유는, 우리가 노드들이 똘똘 뭉쳐있다는 것을 "추이성" 가지고 정의..

그냥 공부 2017. 3. 17. 13:44

세상의 많은 관계들을 수학적으로 나타내는데에는 그래프만큼 강력한 도구도 없습니다. 관계의 주체가 되는 행위자들은 Node로, 관계들은 Node사이를 연결하는 Edge로 나타낼 수 있기 때문이죠. 이렇게 주변에서 찾아볼 수 있는 관계를 수학적인 형태의 Graph로 바꾸면 여러 가지가 가능해지는데, 그 중 대표적인것이 중심성(Centrality) 계산입니다. 중심성은 그래프 상에서 어떤 Node가 가장 중요한지를 살피는 척도인데요, 여태까지 막연하게 여러가지 계산법이 있을거라고 생각은 했지만, 실제로 공부는 해보지 않았었네요. 그래서 이번에 Social Media Mining을 공부하면서 관련 이론을 정리해보려고 합니다. (다음 내용은 Zafarani, R., Abbash, M.A., & Liu, H, 20..

그냥 공부 2017. 3. 15. 16:50