7.3 Data Collection and Sampling

Difficulties in Network Data Collection. 뭔 분야든 통계의 근간은 데이터 수집. 데이터가 IID라면 이 데이터는 sample이나 실험에서 확보한 데이터. 하지만 이는 네트워크 실험에서는 사실상 불가능. 따라서 우리는 샘플을 deal with 하기가 어려우며, 이전에 해왔던 것 대비 일이 무척 어려워짐. 이러한 복잡성은 empirical networks를 다룰 때는 너무나도 자주 무시되고 있어서 안타까운 실정임.

• Sampling Procedures

이상적인 데이터에 해당하는 네트워크 census 를 생각해보자. 이는 모든 node 와 edge 를 기록하고 거기에 오류가 없음. 만약 완벽한 네트워크 census 데이터를 가지고 있는 케이스라면 샘플링 과정 스킵하고 바로 네트워크 formation 모델하는 단계로 넘어갈 수 있음.

하지만 그렇게 운좋을리가. 대다수의 경우에 보유한 네트워크 census 데이터는 불완전함. 보통 이런 실패는 네트워크의 성질과 mesurement process의 디테일 부족에서 옴. Survey 케이스를 생각해보자. survey 질문자, survey 답변자의 성격, survey 질문 구성 등으로 이런건 널뛰기함. 아니면 일부 질문 같은 경우에는 “가장 좋아하는 연예인 3명” 이런 식이라고 치자고. 이러면 4명 이하부터는 censoring 발생해서 이것도 완벽 데이터에서 왜곡됨.

7.3.1 Sampling Designs

우리가 true(참정보, 참값)를 확보하는 것이 불가능하다면, 우리는 IID 통계량에 의해 예시되었던 “population” graph \(G = (V, E)\) 확보를 포기하고 “sample” graph \(G^\ast = (V^\ast, E^\ast)\)를 얻는 쪽으로 선회한다. 이때 \(V^\ast \subset V\), \(E^\ast \subset E\).

이러한 sampled subgraphs를 얻기 위한 다양한 방법들에 대응되는 서로 다른 sampling designs들이 존재한다. 우선 population으로부터의 units들에 대한 simple random sample (SRS)를 이해하는 것이 샘플링을 이해하기 위한 1단계가 된다. 네트워크에서는 단순 랜덤 샘플마저도 복잡한 이해를 거쳐야 한다.

7.3.1.1 Induced and Incident Subgraph

node \(V\)의 Simpl Random Sample (SRS)인 \(V^\ast\)로부터 시작하자. 이로부터 발생시킨 (induced) subgraph \((i, j) \in E^\ast\). 이때 \((i, j) \in E^\ast \Leftrightarrow (i,j) \in E\), \(i \in V^\ast\) and \(j \in V^\ast\) 여야만 함. 이 정제되지 않은 natural 한 과정인 induced subgraph sampling 은 정말 간단한 네트워크 stats 에 대해서도 엄청 biased. bias를 계산해낸 후에 bias 를 보정할 수 있는 경우도 있지만 여하튼 bias 가 크다는게 장점은 아니지.

반면에 우리는 edge의 SRS에서 시작해볼 수도 있다. 이 경우 \(E^\ast\)는 \(E\)의 SRS. 이후 이 edge 양끝에 해당하는 발생을 node로서 잡는다. 이인즉슨 \(\exists j \in V:(i,j) \in E^\ast \Rightarrow i \in V^\ast\). 고전적 survey 에 대해 쌓인 경험에 비추어볼 때 incident-subgraph sampling 는 꽤 괴상해보이지만, 그럼에도 이쪽이 natural 한 경우가 꽤 있기는 함.

7.3.1.1.1 Example of a Bias

우리가 정말정말 간단하기 그지없는 작업인 node 의 랜덤 샘플링을 진행할 때조차도 샘플링이 왜 bias 를 유발해버리는 걸까? 이는 mean degree 를 생각해보면 쉽게 알 수 있다. 직관적으로 생각해보자. induced subgraph 를 하나 가지고 있다. 이때 우리는 induced subgraph 바깥인데 전체 그래프 안에 있는, 즉 induced subgraph 에 포함되지 못한 edge 는 관측할 수가 없다. 따라서 우리가 각 node 에 대해 기록할 수 있는 degree 는 많아봤자 그것들의 degree 참값에 불과할 것이다. 따라서 샘플된 그래프들의 mean degree 는 mean degree 의 참값보다 작아져버리겠지. bias 발생.

let \(k_i = \sum_{j=1}^n A_{ij}\), 즉 \(k_i\)는 node \(i\)의 degree. 이 경우 모든 네트워크에 걸친 mean degree는 $k = {i=1}^n k{i} $. 여기서 \(m\)개의 노드를 SRS 한다면, node \(i\)에게 부여된 확률은 모든 각각의 node에게 부여된 확률과 같으므로, 따라서 \(\pi = \frac{m}{n}\).

여기서 \(Z_i\)를 \(i \in V^\ast\) 여부에 대한 indicator로 정의하자. 그렇다면 node \(i\)가 샘플 안에 있을 경우 \(Z_i = 1\).

또한 관측된 graph \(G^\ast\)는 관측된 adjacency matrix \(A^\ast\)를 보유하며, \(A_{ij}^\ast =1\) iff \(A_{ij}=1\)이며 \(i,j\) 양쪽 모두가 샘플에 있을 경우에만.

그렇다면 plug-in estimate \(\bar k\) from \(G^\ast\)의 기댓값 \(\bar k^\ast\)는 어떻게 되는가?

$$ \[\begin{alignat}{2} E \left( \bar k^\ast \right) &= E \left( \frac{1}{m} \sum_{i \in V^\ast} k_i^\ast \right) &&= E \left( \frac{1}{m} \sum_{i \in V^\ast} \sum_{j \in V^\ast} A_{ij}^\ast \right) \\ &= E \left( \frac{1}{m} \sum_{i=1}^n \sum_{j =1}^n A_{ij}Z_i Z_j \right) &&= \frac{1}{m} \sum_{i=1}^n \sum_{j =1}^n A_{ij} E \left(Z_i Z_j \right) \\ &= \frac{1}{m} \sum_{i=1}^n \sum_{j =1}^n A_{ij} \pi^2 &&=\frac{1}{n \pi} \pi^2 \sum_{i=1}^n \sum_{j =1}^n A_{ij} \\ &= \frac{\pi}{n } \sum_{i=1}^n \sum_{j =1}^n A_{ij} &&= \pi \bar k \end{alignat}\] $$

7.3.1.2 Exploratory Sampling Design

induced 와 incident 이외의 방법론을 쓰고 싶은 경우도 있지 않을까? induced 와 incident 서브그래프 샘플링 양쪽 모두에서 sampling frame 은 실제로 발생하는 그래프에 비하면 약간 좀 거리가 있고 이질적이다. 우리가 SRS 를 사용하는 대상인 population 은 모든 node를 포함하거나, 모든 edge를 포함해야 하지만, but doesn’t use the graph beyond that.

egocentric 디자인에서 우리는 nodes 들을 샘플링한 후에 이렇게 샘플링된 nodes 들의 local 이웃에 대해서만, 혹은 ego network 에 대해서만, 정보를 수집하고 기록한다. 혹은 “ego” 케이스에서 우리는 edge 들이나 initial node 의 이웃들의 edges 들이나 non-edges 들만 기록함; 이는 때때로 star design 이라고 불림. star design 케이스에서 우리는 local 그래프 이웃에 대한 정보를 수집한 후 이들이 중복되는 지점이 있는지를 확인함. 기록 과정을 뭘 쓰느냐에 달려있긴 한데 이 정보는 보통 수집 가능함.

7.3.1.2.1 Snowball Sampling

seed node 로 부터 시작. 이의 직접적인 이웃을 바로 기록. 이후 그 이웃들로 이동한 후 또 직접적인 이웃을 기록. 이 작업을 새로운 node 가 더이상 발견되지 않거나, 정해진 size 에 도달할 때까지 함. 이때 seeds 는 여럿이 있을 수 있음. 이 여럿인 경우에, 가령 seeds 가 2개라면, 진행하다가 서로 다른 seed 로부터 촉발된 2개의 snowball 이 overlap 되는 상황에 마주쳤을 때 어느 snowball을 고를지 결정하는 문제가 생김.

snowball 샘플링은 그래프에 대해, incuded 나 incident 에 의해 얻어지는 것 그 어느것과도 다른 분포를 얻게 되는 결과를 초래함. seed 가 SRS에 의해 정해졌더라도 snowball 에 의해 골라지는 다른 node 들은 랜덤샘플이 아님. initial node 이외의 node 들은 seed 로부터 길을 따라서 도착할 수 있는 node 다 보니, 그들은 적어도 degree 가 1은 보장되어야 하고, 약하게나마 seed 에 연결은 되어 있어야 하마, 일반적으로 평균보다는 높은 degree 를 갖는 경향성을 보임.

7.3.1.2.2 Respondent-driven Sampling

Respondent-driven 샘플링은 소셜네트워크 상황에서 snowball 샘플링의 유의한 변주. 이는 낙인되었거나 혹은 불법적이라 그들의 존재를 관계적으로 잘 발견해내기 어려운 sub-populations 을 찾아내기 위한 방법으로서 태초의 목적은 이것이었음. 이건 연구중인 문제에 해당하는 그룹 안의 멤버를 한둘 골라내서 이들을 이니셜 멤버로 한 뒤 걔들한테 주위 사람들 좀 여기 참가시켜보라고 설득하는 거. 때때로는 이 이니셜 멤버들한테 물리적 토큰(표식)을 준 뒤 이 물리적 표식을 여기 참가하라고 꼬실 대상들한테 뿌리라고 하는 식으로 link 를 트랙하기도 함. 이 물리적 토큰 자체가 인센티브일 수도 있고. 이때 응답자 별로 줄 수 있는 (허락되는) 토큰의 총량이 정해져 있다면 이건 곧 degree 의 censoring 으로 기능함.

7.3.1.2.3 Trace-route Sampling

Trace-route 샘플링은 네트워크를 통과하는 각 route 들을 추적하여 네트워크를 검색함. 절차는 아래와 같다:

1. source node의 set 을 지정
2. target node의 set 을 지정
3. 각각의 source-target의 조합에 대해서, source 에서 target으로 도착하는 path 하나를 찾고, 그후 이 path에서 거친 모든 edge와 node를 기록함.

물론 이 프로세스는 어떤 path 가 탐색되었는가에 크게 의존하긴 하는데 이건 적용 층위의 문제지 메커니즘 자체가 문제가 있다고 할 건 아님. route 추적이 어떻게 이루어졌는지에 따라 연구자는 “실패” (source 에서 target 으로 도착 못했음) 한 route 에 대한 정보를 얻을수도 있고 못얻을수도 있음.

Trace-route 샘플링은 체계적으로 degree 분포를 왜곡하며 모든 종류의 그래프들로 하여금 그들이 heavy-tail 인 것처럼 보이게 할 수 있다. 그들이 실제로 heavy-tail 이었든 아니든.

7.3.2 Coping Strategies

7.3.2.1 Head in Sand

이인즉 샘플링으로 인한 왜곡이나 bias 를 싹 무시하고 우리가 현재 보고 있는 그래프가 그래프의 참값이라고 가정하는 것. 당연히 좋은 생각은 아님. incuded 서브그래프 샘플링의 경우에 mean degree는 real degree 에서 bias 되어 있는데, 이 bias 는 계산 가능함. 실제로 모든 motif에 대해 motif count 의 샘플값도 또한 (얘도 계산 가능한 방법으로) 편향되어 있다. 얘들을 사후적으로 보정하는 건 꽤 쉬운 편. 하지만 다른 놈들은 복잡하게 꼬여있는데, 꼬여있는 놈들 중 일례로 degree 분포의 경우에는 매우 복잡하게 왜곡되어 있어서 사후적으로 보정하기가 드럽게 어렵다. 이건 induced 상황에서도 마찬가지로 복잡해서 사후적 보정이 난해함.

7.3.2.2 Learn Sampling Theory

Classical sampling theory은 통계적 추론에 대한 이론으로, probability assumption은 오직 샘플링 프로세스에 대해서만 (성립)만들어진다는 것을 그 골자로 한다. population의 참값은 unknown 하나 fixed 되어 이 참값이 어떻게 생산되었는지에 대해서는 어떤 stochastic 가정도 만들어지지 않는다. (이를 unknown population 에 대해 조건부를 건다고 생각해도 틀리지 않다.) 모든 probability assumption 들이 샘플링 디자인에 대해서만 논하며, 추론의 타당성은 오직 디자인이 정확히 모델링되었는지 여부에만 의존하므로, 이는 때때로 design-based 추론이라고도 불린다.

크기가 n 인 어떤 finite population 에 대한 어떤 quantity \(X_i\) 의 평균을 a sample of units \(S\) 를 사용해구하고자 하는 상황이라고 해보자. 간단하고 고전적인 해는 Horvitz-Thompson estimator:

\[ \hat \mu_{HT} \equiv \frac{1}{n} \sum_{i \in S}\frac{X_i}{\pi_i} \]

• \(\pi_i\)는 unit \(i\)의 (assumed-known) 포함확률, 즉 unit \(i\)가 샘플에 포함될 확률.

포함 확률은 \(\pi = \frac{|S|}{n}\)로 모두 동일하다는 것을 notice. 즉 우리는 다시 sample mean \(X\)로 되돌아감. 이에 대한 직관은 곧 우리가 1개의 unit을 보았고 그 unit의 포함확률이 \(\pi_i\)라면, 우리가 보지 못한 \(\frac{1}{\pi_i}\)개의 다른 것들이 있다는 것이 골자이다. 더 이론적으로 들어가자면 우리는 이것이 UE임을 보일 수 있다.

indicator 변수 \(Z_i = I(i \in S), i \in 1:n\)을 도입하자. 이를 사용하여 \(\hat \mu_{HT}\)의 기댓값을 구하면

$$ \[\begin{alignat}{2} E \left( \hat \mu_{HT} \right) &= E \left(\frac{1}{n} \sum_{i \in S} \frac{X_i}{\pi_i} \right) &&= E \left(\frac{1}{n} \sum_{i \in 1:n} \frac{X_i}{\pi_i} Z_i \right) \\ &= \frac{1}{n} \sum_{i \in 1:n} \frac{X_i}{\pi_i} E \left( Z_i \right) &&= \frac{1}{n} \sum_{i \in 1:n} \frac{X_i}{\pi_i} P \left( Z_i =1 \right) \\ &= \frac{1}{n} \sum_{i \in 1:n} \frac{X_i}{\pi_i} \pi_i &&= \frac{1}{n} \sum_{i \in 1:n} {X_i} \\ &= \mu \end{alignat}\] $$

또한

\[ Var \left ( \hat \mu_{HT} \right )= \frac{1}{n^2} \sum_{i \in 1:n} \sum_{j \in 1:n} X_i X_j \left( \frac{\pi_{ij}}{\pi_i \pi_j} -1 \right) \]

이때 \(\pi_{ij}\)는 joint 포함확률. 즉슨 \(i,j\)가 한번에 샘플에 들어있을 확률. (\(\pi_{ii} = \pi_i\)로 취급)

모든 \(\pi_i \rightarrow 1\)로 가게 된다면, \(Var \rightarrow 0\).

이 Var 참값을 정확히 계산하는 건 불가능. 우리는 population 안의 모든 unknown units의 합을 구하는건 불가능하기 때문. 그러가 empirical 대체값은 주어져 있다. 이는

\[ \hat {Var} \left ( \hat \mu_{HT} \right) = \frac{1}{n^2} \sum_{i \in 1:n} \sum_{j \in 1:n} X_i X_j \left( \frac{\pi_{ij}}{\pi_i \pi_j} -1 \right) \]

sampling-theory approach는 population quantity의 평균 (혹은 총량) 으로 나타낼 수 있는 대상에게 적합. 혹은 샘플링 디자인에 대한 지식으로부터 포함 (inclusion) 확률을 파악할 수 있는 상황에 대해서도 쓸만하다. 많은 네트워크 stats는 평균으로 표현될 수 있지만 (때때로 “unit”을 정의하여 해결하기도 함, node 의 dyad 같은 거), inclusion 확률을 정확히 계산해내는 건 평균 구하는 것보다는 더 빡셈.

7.3.2.3 Missing Data Tools

다른 방법은 네트워크에서 unobserved 된 부분을 missing data로 처리하고 이를 추론해버리는 것. 이건 simple imputation 전략부터 시작해서, EM 알고리즘과 같이 추론에 대한 복잡한 모델-based 전략에 이르기까지 다양한 것들이 속한다. EM 혹은 성공적인 imputation은 design-based 가 아니라 model-based 이며, 네트워크와 샘플링 프로세스 양쪽 모두에 대한 모델을 필요로 한다. 실전에서 “missing at random” 상황은 진짜 엄청나게 드물며, “missing completely at random” 상황조차도 흔하지 않다. let alone

7.3.2.4 Model the Effective Network

마지막 전략은 observed 네트워크를 모델링하는 것. 즉 observation / 샘플링 프로세스와 실제 네트워크 양쪽 모두를 모델링하지만, 그 후 이 둘을 합치는 것으로 observed 그래프에 대한 확률 분포의 family 를 얻는 것이 가능함. 그 observed 네트워크는 underlying generative 모델의 패러미터에 대해 여전히 informative. 이게 알고 싶은 전부라면, 여기까지만 진행한 후에 종료해버릴 수 있음. 전부가 아니라면 이것 이후에 EM이나 imputation 써서 full 그래프를 복원하고자 시도하게 될 것이고.

7.3.3 Big Data Solves Nothing

“\(n =\) all” 로 설정되고 모든 데이터가 자동적으로 기록된 경우에도 우리가 겪어온 모든 네트워크 샘플링 문제는 여전히 남아있음. 이런 상황에서도 우리가 얻은 데이터는 결국 biased convenience 샘플을 갖고 있는 것이지 가지고 있는 모든 자료가 참값이라고 말할 수가 없기 때문임. 네트워크에서는 특히 아래와 같은 3가지 문제가 두드러짐.

Even when, as the promoters say, “n = all”, and the data are automatically recorded (voluntarily or involuntarily), almost all the network sampling issues we’ve gone over remain. After all, as the promoters do not say, you’re getting all of a biased convenience sample, not all of the truth. Three issues are particularly prominent for network.

1. Entity Resolution
2. Diffusion
3. Performativity

7.3.3.1 Entity resolution

Entity resolution, 혹은 record linkage 라 불리는 것은 데이터 분석에서 메이저한 문제 중 하나. 이는 간단하게 말하면 동일 대상에 대해 서로 다른 시간대에 기록된 자료가 있다면 이 중 무엇을 쓸 것인가 하는 문제. 혹은 겉보기에 같은 대상에 대해 서술하는 것 같은 (co-referent) 기록들이 실제로는 다른 것들에 대해 이야기하고 있는 상황 . 네트워크에서 이는 보통 같은 underlying entity 로 직결되는 2개의 다른 node 들 중에 뭘 고를까 하는 문제가 됨.

7.3.3.2 Diffusion

diffusion은 우리에게 빅데이터를 제공하는 많은 자동적으로 기록된 네트워크들이 다른 오래된 소셜 네트워크로 퍼져나가는 것. provide A with B 예를 들어 페북의 tie는 pre-페북의 소셜 네트워크과 diffusion 프로세스의 결과물이다. 이 결과물을 이해하는데에는 비교적 약간의 노력만이 이루어졌다. diffusion 프로세스가 모든 node 를 균질하게 취겁하더라도, diffusion을 당한 네트워크는 기반 네트워크와 그 특성이 근본적으로 다를 수 있다.

7.3.3.3 Performativity

이론이 자기실현적 예전이 되어버리는 상황을 Performativity라고 함. 온라인 소셜 네트워크를 운영하는 회사들은 사용자들의 크고 조밀한 네트워크를 만들어낼 수 있도록 엄청나게 투자중. 이것이 그들이 link 제안 혹은 link 추천 서비스를 제공하는 이유임. 왜 당신이 아실지도 모르는 친구 이런거. 이러한 추천의 이면에 있는 알고리즘들은 소셜 네트워크가 어떻게 만들어지는지에 대한 이론과 그들이 어떤 link 패턴을 가져야하는지에 대한 이론 등이 반영되어 있다. 유저들이 이러한 추천 친구와 link 를 수락하는 순간 이 알고리즘 이면에 반영된 이론의 입맛에 맞는 케이스가 강화되는 거.