NetworkX python : pagerank_numpy, pagerank는 실패하지만 pagerank_scipy는 작동합니다.

Question

가중치가있는 DiGraph에서 PageRank를 실행하고 있는데 nodes = 61634, edges = 28,378입니다.

• pagerank(G)

  는 ZeroDivsionError

• pagerank_numpy(G)

  는 ValueError를 나에게 던져 저를 던졌습니다 : 큰

• pagerank_scipy(G)에 배열 내가 이해할 수

하지만 페이지가 순위 내를 제공하는 pagerank_numpy 오류 것 메모리 제한으로 인한 것이지만 왜 pagerank가 실패합니까? ? 제로 가중치를 사용하여 가장자리에 극한 값을 추가하려고 시도했지만 동일한 문제가 지속됩니다. 일부 포인터가 좋을 것입니다. pagerank_numpy 또는 pagerank_scipy 달리 - 내 GraphML 파일에

링크 - https://mega.co.nz/#!xlYzEDAI!Lyh5pD-NJL61JPfkrNyJrEm0NnFc586A0MUD8OMYAO0

NetworkX 버전 - 1.8.1 파이썬 - 그것은 stochastic_graph를 사용하여 계산을 수행하기 때문에 2.7

Answer 1

pagerank이 실패합니다. 워드 프로세서에서 stochastic_graph이 필요합니다

NetworkX 그래프, (내가 실수라고 생각 전혀 설명되지 않는다) 유효 에지 무게

이 "유효 에지 가중치"지점이 있어야합니다 문제의 근원입니다.

유향 그래프의 경우 stochastic_graph은 각 노드의 out_degree을 사용하여 가장자리를 표준화합니다. 다시 문서에서 :

[out] 정도는 노드에 인접한 가장자리 가중치의 합입니다.

그래서 당신은 제로 무게 또는 음의 무게하는 ZeroDivisionError와 정규화 과정을 바꿈 가장자리가있을 때. 부정적인 가중치가 문제가되는 이유는 긍정적 인 가중치를 취소하여 노드도를 0으로 줄 수 있기 때문입니다. 그렇게 pagerank 실행할 수 만든 작은 양의 에지 무게 그래프에 제로 또는 마이너스 에지 가중치를 교체

>>> G.edges('2123271', data=True) 
[('2123271', '1712899', {'weight': -1L}), 
('2123271', '890839', {'weight': 1L})] 

:

예를 들어, 그래프, 노드 '2123271' 두 0 가중치 합계의 가장자리가

In [1]: import networkx as nx 
In [2]: G = nx.read_graphml("your_graph.graphml") 
In [3]: defaultEdgeWeight = 0.01 
In [4]: for u, v, d in G.edges(data=True): 
      if d['weight'] <= 0: 
       G[u][v]['weight'] = defaultEdgeWeight 
In [5]: P = nx.pagerank(G) 

물론 pagerank은 102 회 반복 후에 수렴하지 않았지만 다른 문제입니다.

Answer 2

@ mtitan8의 답변은 좋지만 이야기가 조금 더 있습니다.NetworkX 코드가 제로 또는 부의 무게 (https://github.com/networkx/networkx/pull/1001)

(가)있을 때 페이지 랭크 (PageRank)(), pagerank_numpy() 및 pagerank_scipy() 모두 같은 대답을 줄 수 있도록 수정 된 원래 질문의 시간 이후

음의 가중치가있을 때 이러한 함수에 의해 생성 된 결과는 아마도 원하는 것이 아닙니다 (전혀 작동하는 경우). 알고리즘이 이제 입력 행렬 (그래프의 가중치 인접 행렬)에서 'Google 매트릭스'를 생성하는 방식을 처리하는 방식은 행이 0이 아니면 행 전체로 나눠집니다 (전체 행이 0으로 설정 됨) . 그 합은 부정적 일 수 있습니다. 결과 매트릭스는 여전히 부정적인 항목으로 끝나는 경우

다음 페론-의 Frobenius 정리는 http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem을 적용하지 않습니다 그리고 당신은 는 긍정적 인 가치 고유 벡터와 고유 가장 큰 고유 값이 보장되지 않습니다.