카츠 유사성 - 행렬/그래프 연산 (JAVA + JUNG)

Question

그래프에서 유사성 메트릭을 테스트하고 있습니다. JUNG API를 사용하여 그래프를 처리하고 있습니다. 필자는 공통 이웃 및 prefferential 첨부와 같은 기본 메트릭을 계산할 수있었습니다. 이제 다음과 같이 katz 메트릭을 계산하려고합니다 : katz (v1, v2) = B.paths_1 (v1, v2) + B^2.paths_2 (v1, v2) + ... + B^n.paths_n (v1, v2) 여기서, paths_n (v1, v2)는 v1과 v2 사이의 길이 "n"의 경로 수이고; B는 스칼라이다. 나는 n을 4로 제한하고 있으므로 마지막 katz 행렬은 다음과 같이 쉽게 계산할 수 있습니다. B.A + (B.A)^2 + ... + (B.A)^4 여기서 A는 그래프의 인접 행렬입니다. 것은 내가 작업하고있는 그래프가 매우 거대하고 전체 katz 행렬을 메모리에 저장할 수 없다는 것입니다. 게다가, 나는 단지 몇 쌍의 노드만을 테스트하기 때문에 모든 점수가 필요하지는 않습니다. 그래도 그래프를 보지 않고도 개별 점수를 계산할 수있는 효율적인 방법을 찾을 수 없습니다. 아이디어가 있으십니까?

Answer 1

개별 점수 ketz(v1,v2)을 계산하려면 v1 또는 v2에서 4 미만의 거리에있는 꼭지점 만 포함하는 인접성 부분 행렬을 고려하면됩니다.

v1 및 v2에서 숨 한 우선 검색을 사용하여 이러한 꼭지점을 찾을 수 있습니다.

v1에서 시작하는 BFS를 수행하는 동안 #paths를 직접 계산하면 실제로 더 잘 수행 할 수 있습니다. v1로부터의 거리와 v2에 도달했는지 여부를 각 정점 검사에서만 기억하면됩니다. 그렇다면 적절한 카운터를 증가시킵니다. 그 (의사 코드) 같은

뭔가 : 당신이 실행 한 후

Queue q = new Queue(); 
q.enqueue((v1, 0)); 
int[] counts = new int[] { 0,0,0,0,0 }; 

while (!q.empty()) { 
    (v, dist) = q.dequeue(); 
    for(Vertex w : v.Neighbors()) { 
     if(dist < 3) 
      q.enqueue((w, dist+1)); 

     if(dist < 4 && w == v2) 
      counts[dist+1]++; 
    } 
} 

그래서, 당신은 N을 위해 counts[n] = paths_n(v1,v2)을해야합니다 = 1, 2, 3, 4