[수리] Collective dynamics of ‘small-world’ networks, Nature
 
1
  146
2019-10-15 16:16:56

소위 좁은세상 효과, 6단계 분리접칙으로 알려진 네트워크 현상에 대해 현재까지 가장 설득력 있는 모델을 제시한 연구입니다.

   
43
Comments
1
2019-10-16 16:08:53

논문을 읽지 않아도 하도 많이 인용된 것을 듣고 봐서 대강의 내용은 알겠는데몇번 읽어도 결과표를 이해를 못하고 있습니다혹시 먼저 읽고 이해하신분이 설명해 주시면 고맙겠습니다. Figure1에서  small-world phenomenon이 completely regular 와  completely random 사이( 0 에 위치한다는 것 까지는 이해하겠는데,  figure2는 뭘 의미하는지 모르겠어요제가 이해 못하는 부분은 The data shown in the figure are averages over 20 random realizations of the rewiring process described in Fig.1, and have been normalized by the values L(0), C(0) for a regular lattice 지점 같습니다. P=0일때 C(p)/ C(0)가 1과 L(p) /L(0)도 1에 근접한 것, P=1일때 C(p)/ C(0)가 “0”인것L(p) /L(0)도 “0”에 근접한 것도 이해되는데 p가 0.001 전후에 L(p) /L(0)는 급격히 떨어지고C(p)/ C(0)거의 변하지 않는 상황이 이해되지 않습니다 (hence C(p) remains practically unchanged for small p even though L(p) drops rapidly. The important implication here is that at the local level(as reflected by C(p)), the transition to a small world is almost undetectable.). 친근한 언어로 설명해주시면 고맙겠습니다...

1
Updated at 2019-10-16 16:54:51

첫 페이지의 아래에서 첫번째 문단에 말씀하신 부분에 대한 설명이 있는 것 같아서 제가 이해한 바를 말씀드리겠습니다.  


 L은 노드를 있는최단경로가 가지고 있는 변의 수를 모든 노드간의 관계에서 구하고 평균낸 것 이고, C는 한 노드 v가 연결된 모든 노드(이웃집단)의 관계에서 최대로 생길수 있는 연결 수 k(k-1)/2로 실제 연결된 변의 수를 나누어준 값 Cv를 모든 노드에 대해 구해 평균낸 것입니다.

Regular한 연결 상태에서 randomize가 일어나 새로운 연결이 생기면 (p가 1쪽으로 가기시작) 이 새로운 연결이 만드는 short cut의 효과가 초반에 매우 강력하다고 설명하고 있습니다.

 예를들어 20개의 노드를 시계방향으로 1부터 20까지 번호붙였다고 쳤을 때, randomize가 발생해 노드1 의 한 변이 노드10과 연결되게 된다면 
노드1은 노드10까지 한번에, 노드11이나 노드9까지는 두번만에 갈수있고 노드2도 노드1을 거쳐 노드10에 두번만에 갈수있습니다.
이와같이 초반에 생기는 short cut일 수록  그 효과가 커 L값에 큰 변화가 일어납니다.
(p가 0.001까지만 가도 L값이 L(0)에 비해 거의 절반으로 떨어지네요!)
 반면 이러한 급격한 변화에 비해 local level에서 측정되는 값인 Cv값들의 평균의 변화는 상대적으로 크지 않습니다.
실제로 위의 상황대로 노드1의 변하나를 옮겨보니 C1값은 7/10에서 5/10이 되는것 같아요!
그렇지만
Fig2의 그래프가 도출된 ring은 Fig1의 ring에 비해 n과 k값이 훨씬 크므로 C값의 상대적인 변화가 더욱 미미할 것으로 예상됩니다.


1
Updated at 2019-10-16 17:55:05

직관적으로 이해하면 처음의 regular 상태에서 p가 증가하여 최초의 short cut이 생기면 각 노드 간의 최단 거리는 민감하게 줄어들고 local level인 C는 말 그대로 local한 성질인데 전체를 평균했기 때문에 p에 대해 L에 비해 덜 민감한 거 같습니다. short cut이 생긴 건 전체에서는 큰일이지만 각 지엽적인 관점에서는 별 영향이 없는 느낌입니다. 예를들어 경부고속도로가 생긴 건 서울-부산의 최단 거리를 확 줄여주지만 서울시 내부의 연결들은 그대로 남아있는 것과 유사한 거 같습니다. https://www.coolmathgames.com/0-mini-metro-london 미니메트로라는 게임입니다.도시에 지하철을 만들어서 승객들을 이동시키는 게임인데 조금 해보시면 정확히 스몰 월드는 아니지만 지름길의 효과를 체감할 수 있을 거 같습니다.


따라서 p의 증가에 L과 C가 반응하는 속도/민감도가 다르다고 생각했습니다. 다만 왜 p가 0.001전후일 때 L(p) /L(0)는 급격히 떨어지고C(p)/ C(0)거의 변하지 않는 상황 이 발생하는지는 정확히 모르겠습니다. 그치만 예상컨대 vertice가 1000개라서 그런 게 아닐까요? short cut의 효과가 L에서 크니까 p가 0.001은 되어야 short cut이 좀 생겨서 그렇게 급격히 줄어든다고 생각합니다.

제가 더 주목하는 부분은 0.001보다는 0.01입니다. 왜냐하면 그 부근에서 C(p) / C(0) 과 L(p) / L (0)의 차이가 가장 크기 때문입니다. small world의 특징이 노드 간의 거리가 작으면서 로컬의 클러스터링이 무너지지 않은 것이라면 이 특성이 극대화되는 부분은 fig2에서 p가 0.01일때인 거 같습니다.

이 논문의 그래프에서 edge의 강도는 언급하지 않지만 short cut들이 weak / bridge tie와 기능이 유사하다면 이런 위크 및 브릿지 타이의 기능을 최적화하고자 하는 목표를 가진 입장에서 적절한 위크타이의 수는 무엇인가에 대한 하나의 해답이 될 수 있다고 보았습니다. 저는 잘 모르지만 이미 적절한 weak tie의 비율에 대한 연구는 많겠죠? 어쨋든 반대로 돼지열병같은 전염병을 막기 위해서는 반대로 short cut들을 없애야겠습니다.
1
Updated at 2019-10-16 18:34:19
  • 고속도로 비유 너무 좋은 것 같아요! 직관적으로 와닿네요
  • p가 0.001전후일 때 L(p) /L(0)는 급격히 떨어지고C(p)/ C(0)거의 변하지 않는 상황 이 발생하는지 모르겠다고 말씀하셨는데, 이것도 바로 위에 말씀하셨던과 같은 원리 아닐까요? short cut이 생긴 건 전체에서는 큰일이지만 각 지엽적인 관점에서는 별 영향이 없기 때문에요!
  • 저도 말씀하신 것처럼 p값이 더 큰쪽에 관심이 가는데, C값이 급격하게 줄어드는 이유를 사실 잘 이해하지 못했기 때문이에요. 사람들이 더 랜덤하게 연결될수록 local cluster를 만들기 어렵기 때문일까요?.?
WR
1
2019-10-16 22:03:40

마지막 질문에 대한 답은: 맞아요. 랜덤하게 연결될수록 local closter들은 생기기 어렵죠. 그런 면에서 사실 (전염병 연구 등에서 가정하던) 랜덤 그래프는 현실적이 아니라는 말을 많이 합니다.

1
Updated at 2019-10-16 22:41:51

사람 수 N이 1000이고, p가 0.001인 상황은,

사람들이 이웃들하고만 끈끈하게 연결된 regular network에서 집단을 가로지르는 1개의 short cut이존재하는 상황인 것 같아요 (기대값).

short cut이 존재하지 않던 집단 사이에 최초의 short cut가 생길 때 발생되는 효과가 크기 때문에 L값이 급격히 떨어진게 아닐까 싶습니다.

>> 앞서 제 답변에 오류가 있었네요. 사람들이 이웃들하고만 끈끈하게 연결된 regular network에서 집단을 가로지르는 1개의 short cut이존재하는 상황은 p=0.0001인 것 같습니다.. p=0.001은 각각의 사람이 평균 1개의 short cut을 가진 상황이 될 것 같아요.
1
1
2019-10-16 23:04:11

마지막에 short cut 1개 존재할 확률 내일 자세히 말해주실 수 있나요? 궁금해요

1
2019-10-16 17:13:40

글을 읽고 드는 몇가지 궁금한 점을 남겨봅니다!

1. Fig3에는 전염병으로 시뮬레이션을 돌렸을 때 x축을 p로두고 인구의 절반이 감염되는데 걸리는 시간의 변화를 본 그래프와(1번) , 인구 전체가 감염되는데 걸리는 시간의 변화를 본 그래프(2번)가 있습니다.

두 그래프 모두 p가 조금만 변화해도 그 소요시간이 급격하게 줄어드는 것을 보여준다는 점에서 공통적인데, 1번그래프에 비해 2번그래프가 상대적으로 더욱 민감하게 줄어드는 것으로 보입니다. p의 변화가 절반 감염시간에 주는 효과 보다 전체감염시간에 주는 효과가 더욱 크다고 봐도될까요? 그렇다면 그이유는 무엇일지 궁금합니다.

2. 저자는 세가지의 네트워크에서 small world net을 발견하여 보여주었는데요, 예쁜꼬마선충의 신경망과 전력망의 경우 네트워크 전체의 차원에서 전파속도나 상호작용 속도가 빠른것이 중요하기 때문에 small world로 구성된 것이 이해가 갑니다. 그에반해 배우들의 연결망은 전체의 관점에서의 조정이나 설계된 네트워크가 아니라 그냥 배우들이 작품에 출연한 결과로 나타난 연결망 같은데 이들의 연결망이 small world net이라는 것을 확인한 것이 어떤 의의가 있는지 잘 모르겠습니다.

3. 마지막으로 short cut의 효과가 어떻게 연결될때 더 클지 고민해보았는데요, 이 연구의 경우 노드에 순서를 붙이고 p를 설정한뒤 시계방향으로 하나씩 randomize를 수행합니다. 그리고 한 변이 새로이 어떤 노드에 연결될 지도 무작위로 결정됩니다. 이렇게 무작위로 short cut을 만드는 경우와 일정한 규칙에 따라 short cut이 생기도록 연결관계에 변화를 주는 경우 (ex, 1번은 10번에연결, 2번은 11번...) 어떤 경우가 전체 차원에서 short cut의 효과가 클지 궁금합니다. (L값의 변화)

1
2019-10-16 17:56:55

short cut의 효과는 L(p)가 최소가 되는 방향으로 만들다보면 가장 효과가 크지 않을까요? 가장 먼 노드 간에 지름길을 만드는 방식으로요

1
2019-10-16 18:28:45

3번에 대해

short cut의 효과는 아무래도 p값에 따라 달린 것이 아닐까 합니다. 프로그래밍 설명을 볼 때, 멀리 있는 두 점을 찾는 것도 랜덤이지만 그 둘 사이가 연결될지 말지는 p가 결정하기 때문입니다.
사실 저는 둘 다 상관없다고 생각하는 편입니다. 어차피 각각의 n들 사이 short cut이 하는 역할은 L값을 낮춰주는 것이기 때문에, 그 short cut이 랜덤하게 연결되던 그렇지 않던 전체 L값에는 영향이 없을 것이라고 생각해요. 대신 C값에 영향을 미칠 수 있다고 생각하는데, C값은 local cluster와 연관되어 있으니 short cut을 형성하는 것에 규칙이 있다면 C값을 올리지 않을까 합니다. 
1
2019-10-16 20:57:38

2.

저는 오히려 사람들이 모여서 만드는 연결망이 small-world network여서 흥미로웠던 것 같아요. 
small-world network는 영화배우들의 연결망뿐만 아니라, 마을연결망, 학교연결망, 경제활동 연결망 등 사람들이 형성하는 사회연결망에서 consistent하게 나타난다고 합니다.

누가 누구와 관계맺도록 explicit하게 강제하는 매커니즘이 있는게 아닌데도,
사람들이 관계맺는 방식이 small-world network로 자기조직화된다는 점이 재미있었는데요.

이에 대한 한 가지 경제학적 해석은, small-world network가 적은 숫자의 관계만으로 (관계를 유지하는데에는 비용이 드니깐요), 끈끈한 집단을 이루면서도 (적절히 높은 C값, 사람들 간의 정서적 지지에 유리), 사람들이 지근거리에 있게 되는 (적절히 낮은 L값, 정보 유통에 유리) 효율적인 구조의 연결망이라서
관계 형성을 위한 비용 대비 효용 (정서적 지지, 정보 유통)이 높은 방향으로 사람들이 관계를 맺다보니, 사람들의 사회연결망이 small-world network가 되었다는 이야기도 있더라구요.

3.
그라노베터의 weak tie 논문에 나타나있듯
특정 short cut이 존재하지 않을 때 돌아가야하는 거리 (degree 값)가 길수록
short cut의 효과가 클 것 같아요.
WR
1
2019-10-16 22:12:22

1. 두 번째 그림에서는 r=1, 즉 maximally infectious disease를 가정한 것도 영향이 있을 겁니다. r을 꽤 작은 값을 주면 심지어 위로 볼록할수도.

2. 이는 수업에서도 얘기하겠지만, 세 가지 예 모두 Figure 1식의 small world는 아닙니다. 그보다는 power-law distribution에 가깝습니다. 솔직한 제 추측은 당시 이 논문이 워낙 흥미로워서 꼼꼼히 안 보고 넘어갔을수도. 
1
Updated at 2019-10-16 19:00:02
"strangers being linked by a short chain of acquaintances" and social capital

small world network의 핵심은 단순히 shortcut들이 생기면 clustering coefficent가 작아지는 것이 아니라, 오히려 shorcut으로 연결되어 더 빠른 전파가 일어날 수 있으면서도 동시에 (무작위 상황에 비해) 상당히 큰 clustering coefficient를 유지할 수 있다는 것이라고 이해했어요. 

이와 관련해서는 퍼트남의 "bowling alone"이 떠올랐습니다. 제가 퍼트남을 잘 이해했다면, 퍼트남은 미국이 잘 나갔었던 이유를 과거에는 가령 호혜성과 같은 사회적 자본(social capital)이 사람들 사이에 원활하게 circulated 되었다는 점에서 찾습니다. 요컨대 한 지역에서 지근거리에 있는 이웃주민들과 밥도 같이 먹고 볼링도 치고, 취미도 공유하고 하면서 사회적 자본이 smooth하게 전파될 수 있었다면, 최근에 들어서는 (가령 결혼도 늦게하고, TV도 보급되고, 맞벌이도 늘고 등등 하면서) 그러한 소위 "get-together" 하는데 까지의 비용이 증가해서 모이지 않게 되고 결과적으로 사회적 자본이 침식해들어가면서 개개인이 고립되고 bowling alone하는 상황까지 벌어진다는 것인데요.  

오히려 이번에 읽은 논문의 논의를 확장해보면(?),  최근들어 겉보기에는 퍼트남의 주장대로 clique가 쇠약해지고 개개인들이 고립되어가는듯 보일 수 있지만, 사실 물리적 거리(proximity)의 차원과는 다른 사회적 거리(affinity)의 차원에도 부합하는 모종의 새로운 clique들의 등장하고, 그에 따라서 social capital의 전파나 순환이 쇠퇴한 것이 (물론 그것이 물리적인 지근거리에서 유용했었던 고전적인 형태의 social capital과는 다른 형태일 수는 있겠지만) 모종의 새로운 형태의 social capital들이 오히려 과거보다도 더 빠른 속도로 circulated 되고 있어서, 그 결과 나름대로 '사회'가 유지될 수 있다는 식으로도 오늘날의 사회변동을 이해할 수 있지 않을까 생각해보았습니다. (제가 이런 식으로 이해해도 되는지 모르겠네요) 

이러한 논의에 따르면, 퍼트남 식의 결론대로 침식되고 있는 clique들을 강제로 현실에 소환시켜 만나게 하고 나아가 고전적인 social capital의 부활을 꾀하려고 부단히 노력하는 것 보다는, 새로운 형태의 clique들의 속성은 무엇이 다르고, 더 빠른 속도로 전파되고 있는 새로운 형태의 social capital이 무엇이며, 빠른속도의 보급 가운데서도 전파의 속도가 꺾이는 지점(예컨대 p=0.01) 바깥에 위치한 (그래서 대체로 늦게 전파되거나 되지 않는) 집단은 누구인지, 나아가 '(사회적 자본뿐만 아니라) 여러가지의 것들'이 제각이 전파되는 과정에서 clique들의 형태나 지위가 어떻게 분화/그룹화/변화하는지 등을 따져보는 것이 중요할 수 있겠다는 생각이 들었습니다.

또 퍼트남의 진단대로 오늘날이 과거와는 다르다면, 그것은 social capital이 부재 때문이 아니라, 너무 많고 다양한 social capital이 빠르게 전파되고 교차/충돌하는 과정에서 초래되는 일종의 불안정성 때문이라고도 생각해볼 수 있을 것 같네요.


너무 제 마음대로 주절주절 한듯하네요!
WR
1
2019-10-16 22:17:20

말씀하신대로 퍼트남식의 "요컨대 한 지역에서 지근거리에 있는 이웃주민들과 밥도 같이 먹고 볼링도 치고, 취미도 공유하고 하면서" 맺는 관계는 Watts의 모델에서 randomly rewired된 먼 거리 관계는 아닐겁니다, 평균적으로. 그보다는 훨씬 동질적이겠죠.

하지만 한편, 퍼트남식 사회자본에 social associations 들이 중요한데, 이는 소박하게는 "인터넷 동호회"도 해당되며 오프라인에서 만나는 관계라면 지리적으로 멀지도 않은 큰 의미의 이웃일수도 있습니다. 즉, social associations이라는게 생각보다 이질적인 집단이 지역사회 내에서 섞이고 신뢰를 쌓는 집단이라고 생각하면 퍼트남식 자본과 와츠식 small world가 생각보다 비슷할 수 있을 듯 합니다.
1
2019-10-16 18:48:03

저의 실력으로는 본 논문에서 제시하는 알고리즘을 제대로 이해하기 어려워 관련내용을 소개한 링크라는 책에 나오는 부분을 잠깐 언급하면서 질문을 드리고자 합니다.


Watts와 Strogatz의 이 논문은 클러스터링과 무작위 그래프의 우연성을 화해시키는 모델을 최초로 제시하였다는 점에서 의의가 있다고 합니다.


노드들을 원주위에 놓고 각 노드들이 바로 이웃 노드와 그 건너 노드들에 직접연결되도록 만든 Regular 형태에서 무작위적으로 선택된 노드쌍들을 연결하는 소수의 링크를 추가하여 Small-world 네트워크가 만들어진다는 것인데요.


링크를 몇개만 추가해도 클러스터링 계수에 큰 변화를 초래하지 않으면서 노드간 평균거리가 급격하게 줄어든다는 점을 일상생활에 접목해 본다면, 소수일지라도 장거리 링크를 유지하고 있는 사람이 있기만 하면 친구를 사귐에 있어서 국지적이더라도 괜찮다는 점을 이야기 해주는 것 같습니다.


완전하게 무작위적인 네트워크와 정규적 격자(regular lattice) 모델을 통합할 수 있는 방법을 제시해준 점에서 의의가 있지만, 인터넷 웹의 구조처럼 특이하게 많은 수의 링크를 갖고 있는 노드, 즉 허브가 존재하는 네트워크에 대해서는 이 알고리즘을 적용할 수 없다는 비판이 있다고 합니다. 특정 노드가 평균적 노드에 비해 훨씬 많은 수의 링크를 갖는 것을 허용하지 않는다는 점이 약점이라고 하는데요


그렇다면 이와 같은 비판을 해결할 수 있는 알고리즘은 어떤 것일지, 누군가 쉽게 설명해주실수 있다면 좋겠습니다. 

1
2019-10-16 20:08:19

알고리즘은 아니지만, "허브"와 관련하여 예전에 보았던 연구사례 중에는, 

(1) Watts-strogatz network model처럼 노드들이 평균적으로 비슷한 수의 연결을 지닌 연결망과
(2) 그런 연결망에 "모두와 관계를 맺는" 허브 노드를 1개 추가한 연결망을
비교하는 접근이 있었던 것 같아요.

이로써 대인 간 연결망에서 일어나는 일과, 
인터넷과 미디어를 통해 모두에게 연결되어 영향을 미치는 "허브" (예. 오피니언 리더)가 존재할 때 일어나는 일을 비교할 수 있었다고 합니다.

Dellaposta, Macy의 "Why Do Liberals Drink Lattes?" 논문의 1497페이지 2문단에 이러한 사례가 있습니다.
WR
1
2019-10-16 22:20:11

말씀하신 바라바시 지적이 맞습니다. 수업에서 나중에 다룰겁니다. 

그러나 허브가 존재하는 경우는 뻔하게 small world라서 흥미롭지 않지요. 현실에서 사람들간 면대면 인간관계가 허브가 존재하기 힘들기에 인간관계망이 전통적으로 small world인 것을 설명하기도 힘들구요.
1
2019-10-16 19:00:34
  • 저는 수학적으로 Ln이 의미하는 바를 정확히 알지 못해서인지, "Specifically, we require n >> k >> ln(n) >>1, where k >> ln(n) guarantees that a random graph will be connected. In this regime, we find that L ~ n/2k >> 1 and C ~ 3/4 as p -> 0, while L ~~ Lrandom ~ ln(n)/ln(k) and C ~~ Crandom ~ k/n 1. Thus the regular lattice at p = 0 is a highly clustered, large world where L grows linearly with n, whereas the random network at p = 1 is a poorly clustered, small world where L grows only logarithmically with n. These limiting cases might lead oneto suspect that large C is always associated with large L, and small C with small L." 부분을 잘 이해하지 못했어요ㅠㅠ
1) 특히 k >> Ln(n)이 어떻게 랜덤 그래프가 잘 연결되도록 해 준다는 것인지 잘 와닿지 않아요.

2) 왜 C값과 L값이 정의 상관관계를 띄는지 모르겠어요. 직관적으로 생각했을 때는 나와 친구인 사람들이 서로 친구일 확률이 높을수록(C값이 클수록), 내가 어떤 사람과 연결되려할 때 더 작은 다리가 필요할수록(L값이 작을수록) 더 잘 연결된 사회라고 생각하는데, 이 둘은 함께 달성하기 어려운 것인가요?

  • 집합의 크기에 따라 p값이 변화하지 않을까요? 그 집합이 전세계 범위일 때 국가와 국가를 가로지르는 short cut의 유무가 각 국가간 연결에 중요한 영향을 미치겠지만(p값이 작고 L이 급격하게 변동), 집합이 만약 수리사회학을 수강하는 우리들이라고 생각했을 때는 short cut의 유무보다 나와 친구인 사람들이 서로 친구일 확률이 더 중요하다(p값이 크고 C가 급격하게 변동)고 생각해요. 때문에, 좀 더 시야를 확장한다면, 어떤 사회를 더 촘촘하게 연결되게끔 개선하려 할 때 그 사회의 크기에 따라서 short cut이 중요한지 아니면 local cluster를 형성하는 것이 중요한지 판단해야 하는 것이 아닐까 합니다.
1
Updated at 2019-10-16 21:08:11
1.1.
제가 알기로는, K (한 노드에 연결되는 tie의 수)가 자연로그 Ln(n)보다 작으면,
사회연결망 상에서 component가 2개 이상으로 쪼개질 수 밖에 없게 됩니다.
사회연결망이 2개의 집단으로 쪼개지고, 2개의 집단 사이에 bridge가 존재하지 않으면 애초에 L값을 계산할 수 없기 때문에, K가 Ln(n)보다는 크다는 조건이 필요한 것 같아요.

1.2.
K값 (한 노드에 연결되는 tie의 수)이 고정된 상태에서는 C와 L이 정의 상관관계일수밖에 없는 것 같습니다.
국도와 고속도로 비유를 사용하면,
만들 수 있는 전체 도로의 수 (K 곱하기 노드 수)가 fix되어있고,
한정된 숫자의 도로를 국도로 더 지을지, 고속도로로 더 지을지 결정해야하는 상황인데,
(1) 국도를 더 짓고 고속도로를 덜 지으면 C값이 올라가고 L값이 올라갈테고,
(2) 고속도로를 더 짓고 국도를 덜 지으면 L값이 내려가고 C값이 내려가는 것이 사례가 아닐까요.

K값 자체를 바꿀 수 있다면, 말씀대로 국도도 많이 짓고 고속도로도 많이 지음으로써 C값도 올리고, L값도 내릴 수 있을 것 같아요. 하지만 관계를 만드는데에는 비용이 드는 만큼, K가 한정될 수 밖에 없는 것 같아요.
인간의 사회연결망을 예로 들면, 사회적뇌 가설에 따르면, 인간의 인지적 한계 때문에 사회연결망에서 K는 150 이상으로 올라갈 수 없다고 합니다.

2.
K값이 고정된 현실에서, 저는 C와 L값의 balance가 중요하다고 생각합니다.
C값이 올라감으로서 얻는 benefit이 따로 있고 (e.g. node 간에 끈끈하고 밀도 높은 지지),
L값이 내려감으로서 얻는 benefit이 따로 있는데 (e.g. 정보의 빠른 유통),
둘을 모두 취하기 위해서는, C값이 적절히 높고 L값이 적절히 낮은 균형점을 찾는 것이 중요한 것 같아요.
WR
1
2019-10-16 22:28:12

1. 김준솔 학생이 잘 설명한 것 같은데 n >> k  부분은 노드의 갯수에 비해서 선의 갯수가 너무 많으면 안 된다는 부분입니다. 그러면 C값도 높으면서 L값이 짧은, 즉 바로 다음 질문에서 언급하신 "나와 친구인 사람들끼리 서로 친구이면서도 전체적으로 잘 연결된" 사회가 되고, 흥미롭지가 않습니다. 

2.  k >> ln(n) 라는 부분은 그렇다고 노드 갯수에 비해 선의 갯수가 너무 작아도 안 된다는 부분입니다. 그럼 아예 전체적으로 연결할 방법이 없구요. 
3. 집합의 크기보다는 노드와 연결 선의 상대적 비율이 중요하다는 것이 n >> k >> ln(n)  식에 표현되어 있기도 합니다. 
 
1
Updated at 2019-10-16 22:22:36

처음 보는 사람인데 알고 보니 내 친구의 친구였더라, 하는 이야기는 많이 들어보았고 소위 세상은 좁다라는 관습적인 말이 있습니다. 이 말이 소위 좁은 세상을 잘 표현합니다. 노드 간의 임의의 p로 선을 그으면 저절로 small world가 생길 수 있다고 이해했습니다. 여기까지는 랜덤 그래프의 모델 형태로 이해가 가능하다고 봅니다. 그러나 과연 사회 네트워크를 랜덤 그래프로만 설명할 수 있을까 라는 의문이 듭니다. 단순히 노드 간의 구분으로 인한 small world를 표현하기에 많은 것을 설명하지 못하는 부분들은, 아마도 그렇다면 분명 사회네트워크 구조에는 소위 말하는 "Global한" 속성이 존재하는데, 우리 “small world”사회의 “a global Property”은 어디서 기인하는가?  이는 어떻게 밝혀낼 수 있는가? 라는 의문을 제기할 수 있습니다.

여기에 Lattice Network까지 고려하여 이 둘의 중간형태를 고려한 Duncan은 그의 모델에 “short cut”이라는 개념을 도입합니다. 논문의 algorithm을 쉽게 말해보자면, regular network에서 p의 확률로 하나의 edge를 random한 edge로 바뀌주는 과정을 반복합니다. 이러한 구조는 regularity (p =0)과 disorder(p=1)의 사이에 tune이 되는데, Lattice Network에 무작위성을 추가하는 방법으로 Random graph와의 결합을 꾀했다고 생각합니다. p가 아주 작은 (제가 생각하기에) 확률임에도 불구하고 path length가 매우 sensitive하게 바뀐다는 점이 흥미로웠고 이 지점에서 본격적인 effect가 나타난다고 이해했습니다.

두 모델을 모두 고려했을 때 Small Network“a global Property”의 속성과 “a local property”속성 모두의 효율성을 갖게 된다고 이해했습니다. "Such 'short cuts' connect vertices that would otherwise be much farther apart than L(Random)"라는 부분에서요. 전자를 특징으로 하는 Random graph와 후자를 특징으로 하는 Lattice Network의 중간형태를 취하게 되면서 두 가지 모델 속성의 중간 수준의 형태를 띄게 된 것 같습니다
 마지막으로, 논문의 함의를 생각해보았을 때 세계화, Global의 존재에 대해 다시 한번 생각해보게 되었습니다. 라투르가 "
흔히 '전 지구적 관점(global perspective)', 세계화라고 부르는 현상은 수많은 지방화가 네트워크를 통해서 확장하는 것일 뿐이다"라고 한 바가 있는데 이 논문의 함의와 맞닿아 있는 점이 있다고 생각합니다.

WR
1
2019-10-16 22:31:52

말씀하신 요약을 다르게 표현해보면, 와츠의 small world 모델은 기가막히게 아름다운 구석이 확실히 있습니다. 현실세계에서 동시에 충족시키기 힘들 것 같은 local property와 global property를 동시에 만족시키는 방법이 있음을 Figure 2로 보여주니까요. 

라투르는 제가 잘 모르지만, 코멘트를 들으니 그럴듯하게 들리네요.^^
1
2019-10-16 19:58:16

정두원 쪽글입니다. (로그인 문제로, 대신 올립니다)

 이전에 small-world에 관한 내용을 처음 접했을 때 들었던 생각은 우리는 우리의 생각보다 small world에 살고 있다이었는데, 이 논문을 읽으면서 접하게 된 cliquishness의 내용이 매우 흥미로웠습니다. 이 논문에는 Crandom ~ k/n 이라는 내용이 나오는데, 이를 통해서 random network에서 n이 증가하면 cliquishness가 감소하고, n이 없어지면 cliquishness가 증가하는 상황을 생각해보았습니다. 이에 대한 예로 재벌가, 정치계, 국가 네트워크가 떠오르는데요, 이 네트워크들에서 새로운 n이 나타나면 cluster의 수는 오히려 이전보다 감소하였고, 반대로 일부의 n이 사라질 때, 오히려 새로운 cluster가 생기는 것을 보아왔던 것 같습니다. 또한 적은 short cut small world를 만든다는 것을 이 네트워크들을 통해 설명 가능해 보입니다. 하지만 이 네트워크들은 일반적으로 촘촘한 네트워크라고 생각되기에, sparse한 네트워크에서 이러한 현상이 나타나는 예시는 조금 더 생각해보아야 할 것 같습니다.

1
Updated at 2019-10-17 10:40:26

2019312285 CYJ

regular world(p = 0)와 random world(p = 1) 사이의 어딘가, 특히 Figure 2를 참고했을 때 p값이 0보단 크고 0.1보다는 작은 구간을 저는 small-world로 이해했는데요,  p값에 따라 L(p)가 먼저 감소하고 약간의 지연시간 후 C(p)가 감소하는 것이 흥미로웠습니다. 약 7년 간(?)의 학부생활 후 얻은 경험은 1학년 1학기 때와 2학기 때의 과 공동체가 다르다는 것입니다. 첫 오티, 새터 자리에서 한번씩 돌아가며 자기소개하는 상황은 regular world와 가깝습니다. 그러나 이후 전공수업 등으로 random encounter를 통해 과내 다른 인간관계가 만들어지면서 L(p)는 빠르게 증가감소하는 반면, 아직 C(p)가 감소하지는 않습니다(아티클에 따르면 이러한 small-world로의 변화는 로컬 수준에서 거의 감지불가능한데, 경험적으로 상당히 그럴 듯합니다.) 이때만 해도 과 공동체에 대한 인식이 높고 과방이 붐비는 때죠. 그러나 L(p)가 점점 더 증가감소하면서 2학기가 되면, 이 article이 제시하듯,  C(p)가 감소하는 순간이 도래합니다. 각자의 소규모 집단으로 찢어져 그들끼리 어울리기 시작하는 거죠. 혹자가 보기엔 공동체의 붕괴이겠지만, 이런 순간에도 동기 중 한 사람만 '족보'를 가지고 있으면 결국 동기 모두가 전체 공유하는 마법같은 일이 벌어집니다. small-world에서 disease가 확산될 확률이 매우 높은 것과 관련있는 현상이지 않을까 싶습니다. 다소 비약같지만 스코프를 조금 넓혀보면, 베네딕트 앤더슨의 "상상의 공동체"라는 거대한 범주가 어떻게 (나름대로) 잘 유지되고 기능하고 있는가라는 의문을 이런 small-world로 이해해볼 수 있을 것 같습니다.
  한편 여기서 흥미로운 파라메터는 p값 같습니다. Figure 2에서 보이듯 0.0001에서 0.1로만 변화해도 L(p), C(p), T(p)에 엄청난 변화가 발생하는데, p값이 경험적으로 가지는 함의가 궁금합니다. 그리고 대부분의 네트워크에서 이 값은 0~0.1 사이로 constraint되어 있겠다는(그래야 네트워크가 유지가 되기라도 하니) 생각도 듭니다. 혼동이 오는 점은, p값이 이 아티클에서는 집단수준으로 제시되는데, 경험적으로는 개인수준(로컬수준)에서 각 vertex마다 다를 수도 있을 것 같다는 생각 때문입니다. 제가 아티클을 잘 이해하지 못한 것 같아 부끄럽습니다. 수업시간에 많이 토론해보고 싶습니다.
WR
1
2019-10-16 22:38:50

1. 학과 예는 흥미로운데 시간이 가면서 L값이 "감소"한다는 건지 "증가"한다는 건지가 좀 헷갈리네요. 더 얘기해보죠. 

2. 제안한대로 p값이 노드마다, 혹 tie마다 다르다면 어떨지 궁금하기도 합니다. 일단은 p의 mean값으로 고정시킨 결과와 비슷하지 않을까 싶습니다. 
1
1
2019-10-17 10:39:47

학과 예시에서 L(p)가 "감소"한다고 쓴다는 것을 "증가"한다고 써버렸네요 ㅠㅠ "감소"의 방향으로 의도하고 쓴 것이 맞습니다! 감사합니다.

1
2019-10-16 21:02:19

세상 반대편에 있는 사람도 6명만 건넌다면 알 수 있다는 말을 매우 자주 접하였음에도 그 주장의 근원이 되었던 이론적 paper를 이제야 읽어 볼 수 있어서 좋았습니다. 반대로 이를 설명하는 방법론의 이해에 어려움이 있었지만, 쪽 글 들을 보며 많은 도움을 받았고, 또 수업시간의 설명을 통해 미흡한 부분을 보완해보도록 하겠습니다.

본 논문을 통해 현실에서 small world network theory가 얼마나 설명 가능한 가에 대해 생각해 보았습니다. 우선 nod의 특성을 일일이 고려하지는 못하더라도 그 nod가 속한 network가 얼마나 정확히 tie를 분석하고, 보다 Hub의 역할을 하는(많은 tie에 연결된) nod의 관리를 어떻게 하는가에 따라 small world network가 갖는 장점이 극대화 될 수도 있고, 그렇지 못 할 수도 있다고 생각합니다. L의 값이 작아짐에 따라 정보 공유의 빠른 확산과 같은 장점도 있지만, 질병의 확산과 같이 부정적 요소의 확산이 쉽게 이루어 진다는 단점도 있습니다. 물론 기본적으로 국가에서 전염성 높은 질병이 발생했을 때 가능한 많은 Hub(예를 들면 유동인구가 많은 장소, 교통의 요지 등)을 통제하려 하겠지만, 이럴수록 하나의 shortcut이 치명적일 수 있고, 이를 제대로 파악하지 못 한다면 앞선 통제들이 큰 효과를 얻지 못할 수 있을 것이라 생각됩니다. 또한 network 내부의 모든 tie를 분석했다고 가정해도, 정보의 교류와 같은 전파가 nod 간의 일방향적으로 진행될 것인 가에 대한 의문도 들었습니다. 공공기관에 어떠한 사항을 문의하려 하면 자신들의 소관이 아니기 때문에 다른 부서로 연락을 해보라는 답장을 받는 경우가 있습니다. 공식적으로 nodnodtie로 묶여있지만, 사실상 simulation에서 예상한 것처럼 원활히 확산이 원활히 진행되지 못하는 예시가 아닐까 합니다. 현실 세계가 이론적인 small world에 비해서 L값이 높게 나온다면 이러한 제도적인 문제점들도 한 몫을 하지 않을까 생각해 보았습니다.

1
Updated at 2019-10-16 22:32:11

 마지막 공공기관의 예시에서 나오는 결론이 굉장히 경험적으로 맞는 말이고, 흥미로운 예시인 것 같습니다. "현실 세계가 아티클에서 제시하는 small world에 비해 L값이 높게 나온다면" 부분에서 L의 분포에 대해 갑자기 드는 생각인데, 
 1) 아티클에서 L의 값은 지수 분포의 모양을 가지고 있습니다. 

 2) 그런데, "L is defined as the number of edges in the shortest path between two vertices"를 살펴보면 edges의 수라는 건 degree와도 어느정도 연관이 있는 듯 하고, 두 nod 사이의 가장 짧은 거리를 만드는 edges, 그리고 모든 nods 쌍 사이의 edges 평균을 낸다고 하는 발상 자체가 마치 sampling이 떠오르고 이들의 분포가 표본의 크기(?)가 클수록 그러니까 고려하는 nod 쌍의 개수가 커질수록 이들 평균의 분포는 중앙으로 집중되는 형태를 보이지 않을까라는 생각을 해봤습니다... (뇌피셜입니다)
3) 차이는 randomness, 무작위성 주입 수준 조절에 의한 short cut 때문에 생기는 것 같기도 하고 아니면 제가 놓친 과정이 있을 수 있습니다.
 
아티클에서 도출한 L의 분포에 대해 다시 한번 생각해보게 되었습니다. 흥미로운 예시 감사합니다.
WR
1
2019-10-16 22:43:25

 Hub의 존재를 가정하는 네트워크로 가면, 바라바시의 를 참조하시는게 좋습니다. 지적하신대로 부정적 요소(질병의 발생, 테러집단의 자기유지)들도 언급합니다. 그런데 위에서도 언급했지만, 허브가 있는 구조는 tirivially small world라서 좁은세상 모델로는 별로입니다.

1
2019-10-16 21:26:02

Small-world network는 macro-level의 현상인데, 이러한 연결망이 어떻게 micro-level에서 emerge했는지 궁금합니다.

위에도 언급했지만, 이에 대한 한 가지 경제학적 해석은, small-world network가 적은 숫자의 관계만으로 (관계를 유지하는데에는 비용이 드니깐요), 끈끈한 집단을 이루면서도 (적절히 높은 C값, 사람들 간의 정서적 지지에 유리), 사람들이 지근거리에 있게 되는 (적절히 낮은 L값, 정보 유통에 유리) 효율적인 구조의 연결망이라서

관계 형성을 위한 비용 대비 효용 (정서적 지지, 정보 유통)이 높은 방향으로 사람들이 관계를 맺다보니, 사람들의 사회연결망이 small-world network가 되었다는 이야기도 있더라구요.

다만 업무 상 관계가 아니라면 사회관계가 그렇게 경제적이고 합리적인 의도로 만들어지는 건 아니니만큼, 어떤 다른 매커니즘을 제기할 수 있을까요.

WR
1
2019-10-16 22:49:06

power law distribution이 사례마다 생성 메커니즘이 다르듯, small world도 다를 수 있을 듯 합니다. 

저자는 논문 말미에서 세 가지 예를 드는데, cellular automata와 phase oscilator에서 저자들의 모델이 performance가 좋다는 얘기를 하긴 합니다. 예로 드신 경제적 효율성이나 이러한 두 가지 예의 performance나 좋은 예이긴한데, 뭔가 목적론적 설명이라 아주 만족스러운 것 같지는 않아요. 
1
1
2019-10-16 22:51:00

저는 스몰월드가 랜덤하게 자연발생하는 거라고 생각합니다. 탈 집중화된 네트워드의 클러스터 간 연결이 존재하는 네트워크 전체가 스몰월드라고 하면 지엽적인 클러스터가 자연스럽게 emerge하는 것은 자명하다고 생각합니다. 여기서 short cut들이 어떻게 생기는지를 설명하면 스몰월드의 emerge도 설명되는 거 아닐까요? 초중고같이 각 학교가 하나의 로컬 클러스터라고 한다면 아무도 전학을 가지 않으면 short cut은 없을 것입니다. 학교 내부와 근처 학교 간에 로컬한 클러스터가 생기는 와중에 노원구 불암중학교에 있던 A학생이 대구 시지중학교로 이사를 갔다면 대구 수성구와 서울 노원구에 short cut이 생긴 것이죠.

충분한지는 모르겠지만 숲의 서로 키가 다른 나무들이 있어도 뭔가 피보나치라든지 황금비같은 수학적 모델을 따르며 상생하는 멋있는 모습을 보이듯이 인간들도 막 살아도 스몰월드의 네트워크를 구축하게 되는 거 아닐까요?
WR
1
2019-10-16 22:54:21

그럴 듯 하네요. "막 사는" 모습을 와츠는 우아하게 random rewiring으로 부른 듯 

1
2019-10-16 21:52:56

설명감사합니다. 그래도 드는 의문은 과연 p값이 뭔지 궁금합니다. 어떤 communituy는 p값이 0.001 이라면 소문이든, 전염병이든 네트웍크를 타고 빨리 퍼지는 건가요?  p값이0.0008인 community보다? 이 p은 community 성격에 따라 정해진건가요? 변하나요? p값이 서로 다른 community사이에서는 어떤 기준으로 전파가 되나요?  이상한 질문인가요? 어느 지점에서 이해가 안되는걸까요? 

WR
1
2019-10-16 22:52:12

p값은 너무 제한적인 local ties에만 묶여있지 않고 새로운 관계를 맺을 확률, 정도로 일반적으로 해석할 수 있을 듯 해요. 물론 이 값은 개인마다, 사회마다, 기술의 발전에 따라 다를 수 있겠지요. 

1
2019-10-16 22:54:00

p값은 시뮬레이션을 위한 변수일 뿐이고 현실에서 중요한 것은 실제 네트워크에서 short cut의 비율이나 분포 아닐까요?

WR
1
2019-10-16 22:55:16

p값에 따라 short cut의 비율이 결정되는 측면이 크지 않나요? 

1
1
2019-10-16 23:07:17

네 맞는데 현실에서는 p값을 구하는거보다 네트워크를 보는 게 더 가능하고 타당할 거 같았습니다. 애초에 와츠가 p값의 의미를 자세히 정의한 게 아니라서요

1
Updated at 2019-10-17 10:55:08

논문을 읽고 동일한 수의 노드와 엣지가 있는 네트워크도 어떠한 구조로 연결되어있는가에 따라 매우 다른 속성을 지닌다는 사실을 알 수 있었습니다. Regular graph의 상태에서 매우 낮은 확률(p)로 몇몇 엣지의 연결 상태를 무작위로 바꿔주면, path leghth 값은 급격히 떨어지는 반면, clustering coefficient 값은 매우 천천히 떨어집니다. 이 같은 small world network 구조에서는 하나의 노드에서 다른 노드로의 경로 거리는 random graph에 가까운 수준으로 매우 짧아지는 반면에, cliquishness는 상당히 높은 수준으로 유지할 수 있습니다. Figure2의 시뮬레이션 결과를 보아도 p가 0.01만 되어도 path length는 매우 늦안 반면, clustering coefficient는 매우 높은 수준으로 유지되고 있다는 사실을 확인할 수 있었습니다. 확률 p에 의해서 rewire된 랜덤한 edge가 약간이라도 생성된 네트워크는, 수업의 첫 시간에 읽었던 그라노베터의 weak tie가 지니는 강력한 힘이 매우 잘 발휘될 수 있는 구조라고 생각했습니다. 특히 이러한 small-world network가 단순히 가상적 상황에서 시뮬레이션을 통해서 만들어진 것 만이 아니라, 영화 배우들의 영화 출연 연결망, 미국 서부 전력망, 꼬마예쁜선충의 신경망에서도 확인할 수 있었다는 점에서 매우 자연스러운 연결망 구조라는 사실도 알 수 있었습니다. 

WR
1
2019-10-16 22:58:08

코멘트 읽다보니 생각나는데, 사실 첫 주 그라노베터 weak tie 글 읽으면서 weak tie가 정보효과는 가져다주는데 어떻게 community 결속을 가져다주는지는 좀 불확실했는데, 이번 논문에서 synchronizing 효과를 보면, weak tie들이 결속도 높일 수 있겠다 하는 생각이 드는게 사실입니다. 

1
2019-10-16 22:56:58

다른 분들도 언급했듯이 우리가 일상생활에서 좁은 세상이라는 효과를 느낍니다. 저는 개인적으로 수학에 대해서 어렸을 때부터 반감을 가졌고 이 논문도 처음에 접했을 때 보다가 수학이 너무 많아서 장을 닫아버리기도 했습니다. 하지만 3쪽도 안 되는 논문이다 보니 한 번 도전하겠다! 생각으로 꼼꼼히 읽어보았습니다. 바로 느꼈던 것은 어떻게 이렇게 elegant한 모델을 생각할 수 있었을까? 어떻게 연결망을 small-world으로 비유할 수 있었을까? 등등 저자들에게 많은 존경을 표하고 싶습니다. 그리고 저는 본 논문을 읽으면서 계속 드는 2가지 생각이 있었습니다. 

1.Short cut에 있는 노드의 특성이 과연 무엇인가? 인간 네트워크로 비유를 하면 Broker들이 누구이고 이 사람들은 다른 노드-인간들과 어떻게 다를까? 어쩐지 brokering하게 되었는지, 서로 다양한 이들을 연결한다는 이 업무는 어떤 비용을 투자하면서 어떤 이득을 보는지 (rational action theory로 설명하자면), 혹은 인간의 행동을 합리적행동이론으로 설명이 어렵다는 지적도 있는데 브로커역할에 올라온 사람들의 행동을 어떻게 설명할 수 있을까? 많은 생각이 들고 제 연구에서도 본 질문을 가지고 있습니다. 
2. Small-world 현상은 전염병 혹은 contagion을 잘 설명해주는 모델이라는 것은 확실합니다. 그리고 Granovettor도 언급한 바에 따르면 결국 weak tie는 integration을 promote할 수 있다고 합니다. 하지만 왜 우리가 다양한 이들을 경계하게 친화했을까? 왜 우리가 기술발전 덕분에 좀 더 small-world 세상에서 살고 있지만 정치적 polarization이 심화되고 있을까? 라는 생각이 들었기에 이에 대한 대답을 주는 연구를 찾아봤더니 Macy (2011)에서 쓴 논문에서 애초에 weak tie연구들이 micro-level에서 positive influence & selection을 가정했기 때문에 본 오해가 생긴 것이고 부정적 moment와 differentiation을 모형에 도입하였을 때 오히려 weak-tie로 서로 high-clustered community들이 연결되어 있는 경우에 polarization효과가 나타냈습니다. 마치 weak tie는 너무 가깝지도 않고 두 그룹 간의 올바른 정보를 전달하는데에 실패해서 두 그룹 간 hostility로 관계가 변하게 되는 것을 제가 이해한 바입니다. 
https://www.tandfonline.com/doi/pdf/10.1080/0022250X.2010.532261?needAccess=true 여기 논문 링크도 달아드리는데 흥미로웠습니다. 
WR
1
2019-10-16 23:27:21

1. Short cut에 있는 노드의 특성이 확실히 다를 수도 있지만, 와츠의 모델은 특별한 노드의 특성이 없어도 short cut이 생길수 있음을 보여줘서 더 elegant하기도 합니다. 즉, 그저 모든 노드들은 각 tie들을 특정 확률 p로 rewire하는데, 어떤 노드는 장거리 rewire를 실행하기도 하고, 어떤 노드는 아무 tie도 rewiire하지 않고 local cluster를 유지하기도 하는거죠.

1
2019-10-16 23:22:25

위에 퍼트남의 볼링 얼론을 언급하신 분이 계셨는데 퍼트남과 반대로 독신주의가 21세기의 가장 거대한 사회변동이라고 말한 Eric Klinenberg의 Going Solo라는 책도 있습니다. 이 사람 말은 솔로로 사는 게 새로운 지배적인 가족구조가 될 것이어서 정책도 이를 맞춰서 바뀌어야 한다는 것인데요.

제가 말하고 싶은 것은 going solo하는 사회는 아무리 클리크를 잘 이뤄봤자 전통 가족의 기능은 대체할 수 없다는 것입니다. 왓츠 그래프로 말하면 p가 아주 높은 구간에 속하는 것이죠.
애초에 독신이 되는 사람들의 유형이 나이 성별 계층 별로 너무 다양할 뿐만 아니라 자발성에서도 갈리기 때문에 이들은 정치적으로 결속하는게 거의 불가능합니다. 따라서 이들을 위한 제도와 정책을 만드는 것도 엄청 어려운 일인데, 이들이 스스로 정치적 요구를 할 힘도 적다는 문제가 있습니다.
실제로 뉴욕의 독신협회 창립자는 골드미스였던 고모를 멘토로 삼았는데, 아무리 친구들이 많아봤자 나이가 들어 병이 나서는 결국 먼 친척 집에서 요양을 하게 되었다고 합니다. 애초에 멋진 싱글은 고소득자만 가능하고 이들이 친구집단을 만들어서 아무리 서로 돌봄을 한다고 하더라도 한계가 분명한 거 같습니다. 애초에 드라마 같은 솔로 인생을 사는 인구 자체가 희박한거부터도 문제입니다만.