관찰 쌍 사이의 1 차 및 2 차 연결을 생성하는 논리

Question

각 팀마다 8 명 또는 9 명의 플레이어가 있습니다 (실제 데이터에는 8 명에서 16 명까지의 팀이 수천 명이 있습니다). 두 팀 간의 연결 유형을 확인하고 싶습니다. 첫 번째 주문 연결은 두 팀 간의이며 두 팀 모두 동일한 플레이어가 사용됩니다. 이 연결을 올바르게 생성 할 수 있습니다 (아래 참조). 의 경우 두 번째 순서 연결 각 팀의 최소 한 명 이상의 선수가 세 번째 팀에서 함께 경기를합니다. 아래 예에서 팀 a의 경우 플레이어 a가 재생되고 팀 b의 경우 플레이어 b가 재생되고 팀 c의 경우 플레이어 a와 b가 모두 재생되므로 팀 a와 "b"는 이차 순서 연결입니다.

아래 코드는 1 차 연결을 올바르게 처리합니다. 또한 2 차 연결 (팀 "c"를 통해 팀 "a"와 "b"사이)을 올바르게 처리하지만 동일한 팀을 통해 연결을 계산하여 잘못된 2 차 연결을 플래그합니다. 나는이 경우를 무시하는 논리를 이해할 수 없다. 수천 팀의 실제 데이터에서 이러한 사례를 수동으로 무시할 수는 없습니다.

아이디어가 있으십니까? 감사!

# generic data 
dat <- data.frame(team=rep(letters[1:3], 
          length.out=26), 
        man=letters) 
# dat$man[2] <- "a" # one first-order connection 
dat$man[3] <- "a" # one second-order connection 
dat$man[6] <- "b" # one second-order connection 

# first order 
temp1 <- merge(x=dat, y=dat, by=NULL) 
temp2 <- temp1 
temp1$sameMan <- 1*with(temp1, man.x == man.y) 
order1 <- aggregate(sameMan ~ team.x + team.y, 
        data=temp1, 
        FUN=sum) 
subset(order1, team.x != team.y) 

# second order 
temp2$sameTeam <- 1*with(temp2, (team.x == team.y)) 
temp2 <- aggregate(sameTeam ~ man.x + man.y, 
        data=temp2, 
        FUN=sum) 
temp2 <- merge(x=temp1, y=temp2) 
order2 <- aggregate(sameTeam ~ team.x + team.y, 
        data=temp2, 
        FUN=sum) 
subset(order2, team.x != team.y) 

# here the correct output is: 
order2$sameTeamCorrect <- 0 
order2$sameTeamCorrect[c(2, 4)] <- 1 
subset(order2, team.x != team.y) 

이 수율 :

> subset(order2, team.x != team.y) 
    team.x team.y sameTeam sameTeamCorrect 
2  b  a  1    1 
3  c  a  17    0 
4  a  b  1    1 
6  c  b  17    0 
7  a  c  17    0 
8  b  c  17    0 

Answer 1

이것은 기본적으로 문제가 네트워킹 이론에서.

우리가 k 팀에 분산 n 선수가 있다면, 우리는 (행 선수, 열에서 팀) n 행과 k 열이있는 매트릭스 M을 정의 할 수 있습니다. 그런 다음 플레이어 i이 팀 j에있는 경우 M[i,j] = 1, 그렇지 않으면 0입니다. 이 정의는 행렬

A = M ^T × M

는 대각 요소가 각 팀의 선수의 수는 대칭 k x k 행렬이며 A[i,j]는 수를 제공 팀 i과 팀 j은 공통점이 있습니다. 따라서 A[i,j] > 0 인 경우 i 팀과 j 팀이 1 차 연결을 유지합니다. 여러분이 공통적으로 사용하는 플레이어의 수가 아니라면 연결되어 있는지 신경 써야합니다. 따라서 대각선을 제로로 만들고 A> 0을 1로 변환하여 A를 정규화합니다. 이것은 1 차 연결 행렬입니다.

C ⁽¹⁾ = 기호 (A - DIAG (A))

2 차 연결 후

로 발견 될 수

C ⁽¹⁾ × C ⁽¹⁾

팀 i과 팀 j에 2 차 연결이있는 경우이 행렬의 [i,j] 요소가> 0이됩니다. 하지만 문제가 있습니다. 2 차 연결이있는 팀도 1 차 연결을 가질 수 있습니다. 나는 당신이 그것을 할인하고 싶어한다고 가정합니다. 그렇게하기 위해 우리는 전에 정규화하고 C.1 (첫 번째 순서 연결을 가짐)을 뺍니다. 결과의> 0 요소는 1 차 연결이없는 2 차 연결을 나타냅니다. (대문자로 팀을 지정) 귀하의 예제의 약간 수정 된 버전을 사용

,

dat <- data.frame(team=rep(LETTERS[1:3],length.out=26), 
        man=letters) 
dat$man[3] <- "a" # one second-order connection 
dat$man[6] <- "b" # one second-order connection 
# team - player matrix 
M <- matrix(0,nr=length(unique(dat$man)),nc=length(unique(dat$team))) 
rownames(M) <- unique(dat$man) 
colnames(M) <- unique(dat$team) 
M[as.matrix(dat[,2:1])] <- 1 
head(M) 
# A B C 
# a 1 0 1 
# b 0 1 1 
# d 1 0 0 
# e 0 1 0 
# g 1 0 0 
# h 0 1 0 

인접 행렬, 제 1 및 제 2 차 연결.

A <- t(M) %*% M 
A 
# A B C 
# A 9 0 1 
# B 0 9 1 
# C 1 1 8 

C.1 <- sign(A) - diag(nc=ncol(A),nr=nrow(A)) 
C.1 # A and C connected; B and C connected; A and B not connected 
# A B C 
# A 0 0 1 
# B 0 0 1 
# C 1 1 0 

C.2 <- C.1 %*% C.1 - C.1 
C.2 <- ifelse(C.2>0,1,0) - diag(nc=ncol(A),nr=nrow(A)) 
C.2 # A and B have a second order connection, but not first order 
# A B C 
# A 0 1 0 
# B 1 0 0 
# C 0 0 0 

마지막으로, 당신은 igraph 객체로 A matric 인접성을 변환 한 후 직접 neighbors(...) 기능을 사용하여 제 1 및 제 2 차 연결을 식별 할 igraph 패키지를 사용할 수 있습니다. 만약 당신이 많은 것을하고 있다면, 그 패키지를 배우는 데 시간을 투자 할 것을 제안합니다.

Answer 2

그래서 ... 우려 다음, 왜 안 첫 번째와 세 번째 열에있는 항목 인 경우는 :

> order2 <- aggregate(sameTeam ~ team.x + team.y, 
+      data=temp2, subset= team.x != team.y, 
+      FUN=sum) 
> subset(order2, team.x != team.y) 
    team.x team.y sameTeam 
1  b  a  0 
2  c  a  0 
3  a  b  0 
4  c  b  0 
5  a  c  0 
6  b  c  0 
>