The Impact of the Subgroup Structure on the Evolution of Networks: An Economic Model of Network Evolution

Kibae Kim, Jörn Altmann, 황준석 (2010) · IEEE International Conference on Advanced Information Networking and Applications (AINA) Workshops (IEEE INFOCOM Workshops, NetSciCom)

실증 네트워크의 power-law exponent $\gamma$ 가 이론적 척도 없는 네트워크 의 $[2, 3]$ 보다 훨씬 낮은 — Wikipedia hyperlink $\gamma \approx 1$ (Hendler et al. 2008), Web 2.0 service network $\gamma \approx 0.5$ (The structural evolution of the Web 2.0 service network) — 비정상 을 설명할 evolutionary model 을 네트워크 시뮬레이션 으로 구축한다. Barabasi et al. (2001) 의 모델의 probability 합이 1 초과 결함을 수정한 modified preferential attachment rule + Subgroup-Activity-Factor $\Lambda$ 도입. 검증 결과 두 메커니즘 — (i) 기존 노드 간 추가 링크 (rate $a$ 의 log 와 음의 선형: $\gamma = -0.05 \log a + 2.1$ , $R^2 = 0.99$ ), (ii) subgroup 경계의 closeness ( $\Lambda$ 감소 시 cumulative distribution 이 convex 로 왜곡) — 가 모두 $\gamma$ 를 낮춤. Closeness 효과가 추가 링크 효과보다 강하며, 경계가 강할수록 dominant subgroup 이 다른 subgroup 을 압도 하는 first-mover 효과 출현.

RQ: 실증 자기조직 네트워크의 power-law exponent 가 이론 모형보다 낮은 (γ < 2) 두 가지 메커니즘 — 기존 노드 간 추가 링크 + subgroup 구조 — 를 evolutionary network simulation 으로 어떻게 검증할 것인가
방법론: 네트워크 시뮬레이션 (Java, 20,000 시점 까지 evolution; cumulative degree distribution log-log 회귀), modified 선호적 연결 모형 (Barabasi et al. 2001 의 probability 결함 수정 + Subgroup-Activity-Factor $\Lambda$ 추가)
데이터: Validation 시뮬레이션 — $N_0 = 2$ , $K = 1$ , final $F = 30,000$ , $b = 1, \beta = 1, G = 1, \Lambda = 1$ → 표준 scale-free $\gamma = 2.5$ 재현 ( $R^2 = 0.97$ ). 본 실험: $a \in \{0, 10^{-5}, 10^{-4}, 10^{-3}, 10^{-2}\}$ (추가 링크 비율), $G \in \{1, 10, 10^2, 10^3, 10^4\}$ (subgroup 수), $\Lambda \in \{0, 10^{-4}, 10^{-3}, 10^{-2}, 10^{-1}, 1\}$ (subgroup openness)
주요 발견: (1) 기존 노드 간 추가 링크의 효과: $\gamma = -0.05 \log a + 2.1$ ( $R^2 = 0.99$ , 1% 유의), $a$ 가 증가할수록 $\gamma$ 가 로그적으로 감소 (cumulative distribution concave 왜곡). (2) Subgroup closeness 효과 (Proposition 1): $\Lambda$ 가 감소할수록 cumulative degree distribution 이 convex 로 kink 발생 (예: $a = 0.001, G = 100, \Lambda = 0$ 에서 lower-degree 영역 slope -1.51, higher-degree 영역 -0.40 두 구간). (3) Subgroup 수 효과 (Proposition 2): $G$ 가 증가할수록 (single → 10² → 10³) cumulative distribution 이 bend, dominant subgroup 이 출현 (초기 노드 포함 subgroup 이 first-mover 이점 획득)
시사점: Web 2.0 service provider 는 (i) 새 서비스 출시보다 기존 서비스 재사용 촉진이 단기 이익, (ii) 가장 인기 있는 서비스 보유자는 closeness 가 자기에게 유리하지만 Betamax·Macintosh 의 실패 사례처럼 상대방이 모두 open 일 때 closeness 는 자살 전략. 균형 잡힌 openness 가 합리적

Subgroup 구조의 효과 시각화 — 두 subgroup 이 완전히 closed 일 때 link 생성은 같은 subgroup 내부에서만 발생, 외부 link 차단.

요약

Kibae Kim 박사 라인의 핵심 paper, The structural evolution of the Web 2.0 service network · Measuring and Analyzing the Openness of the Web2.0 Service Network for Improving the Innovation Capacity of the Web2.0 System through Collective Intelligence 의 비정상 power-law exponent (Web 2.0 service network $\gamma \approx 0.5$ , Wikipedia hyperlink $\gamma \approx 1$ ) 의 메커니즘을 evolutionary model 로 설명한다. 표준 선호적 연결 모형 (Barabasi & Albert 1999) 은 새 entrant 노드 한 개당 한 개 링크 생성 + linear preferential attachment 가정 → $\gamma = 3$ 인 scale-free network. 실증 데이터의 $\gamma < 2$ 는 두 가지 추가 메커니즘 의 존재를 시사한다.

본 paper 의 modified preferential attachment rule 은 Barabasi et al. (2001) arXiv 의 second model 의 probability 합이 1 초과 결함을 명시적으로 수정한다 — 원래 식에서 $N(t) \cdot a = 1$ 이면 $\sum \Pi_{ij} = 2$ 가 되는 정의 문제. 본 paper 는 probability 를 $[0, 1]$ 로 제한하고 $\delta_{ij}^{pq}, \delta_i^p$ (시점당 link 증가 수) 변수를 따로 도입해 처리. 핵심 추가 — Subgroup-Activity-Factor $\Lambda_s^t$ ( $s = t$ 면 1, $s \neq t$ 면 $\Lambda$ ). $\Lambda = 1$ 이면 subgroup 효과 무 (openness), $\Lambda > 1$ 이면 cross-subgroup link 가 $\Lambda$ 배 더 자주 생성, $\Lambda < 1$ 이면 within-subgroup link 가 $1/\Lambda$ 배 더 자주 생성 (closeness). $\Lambda = 0$ 이면 cross-subgroup 완전 차단.

검증 결과 두 효과 모두 강건. (i) 기존 노드 간 추가 링크: $a \in \{0, 10^{-5}, 10^{-4}, 10^{-3}, 10^{-2}\}$ 변경시 cumulative distribution 의 intercept 는 4.30 으로 invariant (degree 1 노드 간엔 link 거의 생성 안 됨), lower end 는 2.34 → 4.77 로 이동 (hub 의 degree 강화) → 분포가 concave 왜곡. 회귀: $\gamma = -0.05 \log a + 2.1$ ( $R^2 = 0.99$ , $p = 0.003$ ). (ii) Subgroup closeness (Proposition 1): $a = 0.001, G = 100, \Lambda$ 변동 시 — $\Lambda = 1$ 이면 distribution 이 $G = 1$ 의 결과와 동일 (closeness 효과 없음), $\Lambda = 10^{-2}$ 이나 $\Lambda = 0$ 일 때 distribution 이 convex 로 kink — lower-degree 구간 slope -1.51 vs higher-degree -0.40. 이는 추가 링크의 concave 왜곡과 반대 방향 의 왜곡으로 두 메커니즘이 다른 source 임을 입증. (iii) Subgroup 수 (Proposition 2): $G = 1, 10^2, 10^3$ 비교 시 $G$ 가 클수록 distribution 이 강하게 bend, dominant subgroup (초기 노드를 포함한 subgroup) 이 다른 subgroup 을 압도 (예: $G = 100, \Lambda = 0$ 에서 high-degree 46 노드 중 41 개가 한 subgroup 에 속함).

정책·관리 함의는 Web 2.0 service provider 관점에서 두 가지. 첫째, 기존 서비스 재사용 촉진이 새 서비스 출시보다 단기 이익 — 새 서비스는 네트워크 주변부 (low degree) 에 배치되므로 short-term 수익이 낮다. 둘째, closeness 의 양면성 — 가장 인기 있는 서비스 보유자에게는 closeness 가 dominant subgroup 효과로 유리하지만, 상대방이 모두 open 일 때만 — Sony Betamax 와 Apple Macintosh 의 우수 기술 실패 사례처럼 paranoid closeness 는 자기 파괴 전략. 균형 잡힌 openness (특정 영역만 proprietary, 핵심은 open) 가 합리적. Kibae Kim · Jörn Altmann · 황준석 트리오 웹 2.0 시리즈 3 편의 capstone — 발견 → 측정 → 메커니즘 설명 의 narrative arc 완성.

핵심 결과

Validation	$\gamma$	$R^2$	비고
표준 preferential attachment ( $a = 0, G = 1, \Lambda = 1$ )	2.5	0.97	이론 예측 [2, 3] 재현
Wikipedia (Hendler et al. 2008)	$\approx 1$	—	비정상 ( $\gamma < 2$ )
Web 2.0 service network (The structural evolution of the Web 2.0 service network)	$\approx 0.5$	0.65	비정상 ( $\gamma < 1$ )

메커니즘 1: 기존 노드 간 추가 링크	$a$	$\gamma$
Baseline (entrant only)	0	2.5
약한 추가 링크	$10^{-4}$	$\sim 2.3$
강한 추가 링크	$10^{-2}$	$\sim 2.0$
회귀 식	—	$\gamma = -0.05 \log a + 2.1$ ( $R^2 = 0.99$ )

메커니즘 2: Subgroup closeness (Proposition 1, $a = 0.001, G = 100$ )	Lower-degree slope	Higher-degree slope
$\Lambda = 1$ (open)	-2.5 ~ -2.0 (linear)	(same)
$\Lambda = 0$ (closed)	-1.51	-0.40 (kink)

핵심 명제: 표준 preferential attachment 는 $\gamma = 2.5$ 의 scale-free 를 만들지만, (i) 기존 노드 간 추가 링크는 $\gamma$ 를 로그적으로 감소시켜 distribution 을 concave 왜곡, (ii) subgroup closeness ( $\Lambda < 1$ ) 는 distribution 을 convex 로 kink 시키고 dominant subgroup 효과를 만든다. 두 효과는 반대 방향의 왜곡 이라는 점이 메커니즘이 서로 다름을 입증.

방법론 노트

표준 preferential attachment 는 node $i$ ( $p$ subgroup) 와 node $j$ ( $q$ subgroup) 간 link probability 를 본 paper 가 다음과 같이 modify:

\Pi_{ij}^{pq} = \frac{k_i^p \, k_j^q \, \Lambda_p^q}{\sum_l \sum_{m > l} k_l^u \, k_m^v \, \Lambda_u^v}

여기서 $k_i^p$ = subgroup $p$ 의 node $i$ degree, $\Lambda_p^q$ = Subgroup-Activity-Factor:

\Lambda_s^t = \begin{cases} \Lambda & \text{if } s \neq t \\ 1 & \text{if } s = t \end{cases}

$\Lambda > 1$ 이면 cross-subgroup link 선호 (openness), $\Lambda < 1$ 이면 within-subgroup 선호 (closeness), $\Lambda = 0$ 이면 cross-subgroup 완전 차단. Entrant probability 도 유사하게:

\Pi_i^p = \frac{k_i^p \, \Lambda_p^q}{\sum_j k_j^u \, \Lambda_p^u}

이 두 식은 Barabasi et al. (2001) 의 원래 식 ( $N(t) a \cdot \frac{k_i k_j}{\sum k_l k_m}$ ) 가 probability 의 $[0, 1]$ 정의를 위반하는 결함 (예: $N(t) a = 1$ 이면 $\sum \Pi = 2$ ) 을 수정. Differential attachment rule:

\frac{dk_i^p}{dt} = \delta_i^p + \sum_{j \neq i} \delta_{ij}^{pq}

여기서 $\delta_i^p$ = entrant 와의 link 증가, $\delta_{ij}^{pq}$ = 기존 노드 간 link 증가. Cumulative degree distribution $P(k) = \int p(k) k \, dk$ ( $k$ 부터 $\infty$ 까지) 를 사용해 high-degree 영역의 noise 완화 (Newman 2003, 2004). 식별은 (i) 표준 preferential attachment ( $a = 0, G = 1, \Lambda = 1$ ) 가 $\gamma = 2.5$ 를 재현하는 validation, (ii) $a$ 와 $\Lambda$ 의 factorial 실험으로 두 메커니즘 효과의 직교 분리 에서 온다.

연구 계보

직접 선행: Barabasi & Albert (1999) Science “Emergence of scaling in random networks” — 표준 preferential attachment 정전. Barabasi et al. (2001) arXiv “Evolution of the social network of scientific collaborations” — second model (기존 노드 간 link 추가), 본 paper 가 명시적으로 probability 결함 을 수정 + Subgroup-Activity-Factor 로 확장. Dorogovtsev, Mendes & Samukhin (2000), Krapivsky, Redner & Leyvraz (2000) 의 preferential attachment 정전. Albert & Barabasi (2002) Reviews of Modern Physics — scale-free 정전 review. Newman (2003) SIAM Review, Newman (2004) — cumulative distribution 사용 정전. Fu, Liu & Wang (2008) Physica A, Stefancic & Zlatic (2005) PRE, Park, Lai & Ye (2005) PRE — scale-free network 변형 라인. Hendler et al. (2008) CACM — Wikipedia 의 비정상 $\gamma$ (본 paper 가 설명 대상). The structural evolution of the Web 2.0 service network Online Information Review — 본 paper 의 직접 동기 (Web 2.0 의 $\gamma = 0.53$ ). Galeotti, Goyal & Kamphorst (2003) Essex DP — 이질적 player 의 네트워크 형성 + internal vs external cost 분석. Krackhardt & Stern (1988) SPQ — subgroup 경계 정전. O’Reilly (2007) Web 2.0 정의. Chesbrough (2003) Open Innovation. Gawer & Cusumano (2002) Platform Leadership — Betamax · Macintosh 실패 사례 (closeness 의 자기 파괴). Adamic, Lukose & Huberman (2003), Wang & Sun (2008) — peer-to-peer 네트워크 자기 조직. Wagner & Leydesdorff (2005) Research Policy — 국제 협업 네트워크의 자기 조직. Kibae Kim · Jörn Altmann · 황준석 트리오 웹 2.0 시리즈 3 편의 capstone.

인접 그래프

1-hop 이웃 13개

인물 3
방법론 2
개념 1
주제 2
수록처 1
분류 2
논문 2

휠 = 확대/축소 · 드래그 = 이동 · hover = 라벨 · 클릭 = 페이지 이동

이 문서를 가리키는 페이지

논문 (2)

인물 (1)

Kibae Kim