JUNG 그래프 - 방향이 지정되지 않은 그래프와 가중치가있는 가장자리가있는 PageRank

Question

가중치가있는 방향이없는 그래프에서 PageRank를 구현하고 있습니다. 내 이해가 내 그래프 undirected 때문에 가장자리 가중치를 나타내는 확률은 원점 정점에 따라 달라집니다. 확률은 의 경우 정점의 아웃 바운드 엣지에 대해 1을 합계해야하지만, 엣지의 각 정점에는 의 요구 사항이 다를 수 있습니다. 즉, 두 조건 사이에 공통 전환 확률을 가질 수 없습니다. (이 이해가 잘못 되었다면 라고 적어주세요).

그러나 테스트 및 문서의 예제에서는 간단한 가장자리 가중치를 사용하는 반면, 가중치에 맞춰 VertexEdge 쌍이 필요하기 때문에 구현하는 데 문제가 있습니다. VEPair 클래스는 표준 Integer 키가있는 엘리먼트를 대신 할 때 널 포인터 예외를 던집니다.

g.addVertex(0); 
g.addVertex(1); 
g.addVertex(2); 
g.addVertex(3); 

3.

그 다음 그래프, I는 에지 0,1 부가

I는 UndirectedSparseGraph를 만들고, I는 정점 0, 1, 2를 추가하고, 다음과 같다 :

의미론은 2, 3 연결 정점 = 0> = 1> 2 => 3/3 => 0, 즉, I는 각 정점에 대한 0.5의 동일한 에지 무게 추가

g.addEdge(0, 0, 1); 
g.addEdge(1, 1, 2); 
g.addEdge(2, 2, 3); 
g.addEdge(3, 3, 0); 

.

map.put(0, 0.5); 
map.put(1, 0.5); 
map.put(2, 0.5); 
map.put(3, 0.5); 

I 즉 그래프를 사용하여 랭크, 형질 에지 웨이트, 0의 알파 인스턴스화 :

pr = new PageRank(g, MapTransformer.getInstance(map), 0); 

이제 올바른 0.25의 각 정점 점수 결과, 즉 :

을

pr.getVertexScore(0); // 0.25 
pr.getVertexScore(1); // 0.25 

내 문제는 가장자리에 단순히 가장자리 가중치가있을 수 없다는 것입니다. 그래프가 흐트러지기 때문입니다. 버텍스의 모든 아웃 바운드 엣지는 1의 에지 가중치를 가져야하므로 엣지의 가중치는 원점의 꼭지점에 따라 달라야합니다. 따라서 엣지 0의 가중치는 x이지만 그 엣지 0 즉, 위의 정수 대신, 1

그래서, 나는 내 maptransformer에 VEPair 클래스를 사용할 수있을 거라고 생각 정점 정점 0 X의 무게와 y가 있습니다

map.put(new VEPair(0, 0), 0.5); 
map.put(new VEPair(1, 0), 0.5); 
map.put(new VEPair(1, 1), 0.5); 
map.put(new VEPair(2, 1), 0.5); 
map.put(new VEPair(2, 2), 0.5); 
map.put(new VEPair(3, 2), 0.5); 
map.put(new VEPair(3, 3), 0.5); 
map.put(new VEPair(0, 3), 0.5); 

그래서, sematics는 동일합니다. 나는 원점 버텍스가 주어진 각 가장자리의 무게를 명시 적으로 지정하고 있습니다.

호출 pr.evaluate() 그러나 PageRankWithPriors.update의 라인 87()에 널 (null) 포인터 예외가 결과

특히 그 코드가 지정된 첫 번째 에지 무게를 얻기 위해 노력하고, 그것이 null입니다.

VEPair 클래스가 hashCode 또는 equals를 구현하지 않았기 때문에 VEPair를 키로 사용하여 apache.commons에서 일반 MapTransformer를 사용하는 것만으로도 항상 null이됩니다. 따라서 VEPair (0, 0)은 VEPair (0, 0)과 같지 않습니다. 이 클래스를 오버라이드 (override) 해, 동등성의 의미를 제공하면 (자) 간단하게 할 필요가 있습니다. 아니면 잘못된 접근 방식을 전적으로 사용하고 있습니까?

도움 주셔서 감사합니다.

Answer 1

VEPair는 외부 사용에 적합하지 않습니다. 일반적인 경우 (가장자리 가중치가 내재적으로 균일하지 않은 무향 그래프)를 처리하기 위해 내부적으로 많이 사용됩니다.

나는 이미 당신을 위해 효과가 있을지도 모르겠지만 새로운 DirectedGraph를 만들 필요가없는 해결책을 원한다면 PageRank의 getEdgeWeight (V, E) 메소드를 오버라이드 할 수있다. AbstractIterativeScorer에서 구현 됨)를 사용하여 방향이 지정되지 않은 가장자리 가중치의 관점에서 원하는 모든 작업을 수행 할 수 있습니다.