如果排名系統的值爲正數k，我該如何刪除排名系統中的值？

Question

假設我有以下代碼：

def compute_ranks(graph, k): 
    d = .8 #dampening factor 
    loops = 10 
    ranks = {} 
    npages = len(graph) 
    for page in graph: 
     ranks[page] = 1.0/npages 
    for c in range(0, loops): 
     newranks = {} 
     for page in graph: 
      newrank = (1-d)/npages 
      for node in graph: 
       if page in graph[node]: 
        newrank = newrank + d * (ranks[node]/len(graph[node])) 
      newranks[page] = newrank 
     ranks = newranks 
    return ranks 

好吧，那麼現在假設我想不允許，可以相互串通的任何項目。如果我有一個項目錄

g = {'a': ['a', 'b', 'c'], 'b':['a'], 'c':['d'], 'd':['a']} 

對於任何路徑A ==> B，我不希望允許的B路徑==>一個是在距離等於或低於我的數k。

例如如果k = 0，則我不會允許的唯一路徑是A ==>一種。

然而如果k = 2，則我將不允許鏈接A ==> A作爲之前，但還鏈接如d ==> A，B ==> A，或者A ==>℃。

我知道這是非常混亂，大多數我的問題來自於不瞭解究竟這是什麼意思。

這裏的問題的轉錄產物：

# Question 2: Combatting Link Spam 

# One of the problems with our page ranking system is pages can 
# collude with each other to improve their page ranks. We consider 
# A->B a reciprocal link if there is a link path from B to A of length 
# equal to or below the collusion level, k. The length of a link path 
# is the number of links which are taken to travel from one page to the 
# other. 

# If k = 0, then a link from A to A is a reciprocal link for node A, 
# since no links needs to be taken to get from A to A. 

# If k=1, B->A would count as a reciprocal link if there is a link 
# A->B, which includes one link and so is of length 1. (it requires 
# two parties, A and B, to collude to increase each others page rank). 

# If k=2, B->A would count as a reciprocal link for node A if there is 
# a path A->C->B, for some page C, (link path of length 2), 
# or a direct link A-> B (link path of length 1). 

# Modify the compute_ranks code to 
# - take an extra input k, which is a non-negative integer, and 
# - exclude reciprocal links of length up to and including k from 
#  helping the page rank. 

Answer 1

我想通了：

def Colluding(p1,p2,itemDict,k, time): 
if k >= len(itemDict)/2: 
    return True 
if k == 0: 
    if time == 0: 
     if p1 == p2 and p1 in itemDict[p2]: 
      return True 
     else: 
      return False 
    if time == 1: 
     if p1 in itemDict[p2]: 
      return True 
     else: 
      return False 
for p in itemDict[p1]: 
    if Colluding(p1,p,itemDict,k-1,1) and p == p2: 
     return True 
    else: 
     return False 
return False 

def compute_ranks(graph, k): 
    d = 0.8 # damping factor 
    numloops = 10 
    ranks = {} 
    npages = len(graph) 
    for page in graph: 
     ranks[page] = 1.0/npages 
    for i in range(0, numloops): 
     newranks = {} 
     for page in graph: 
      newrank = (1 - d)/npages 
      for node in graph: 
       if page in graph[node] and not Colluding(page, node, graph, k,0): 
        newrank = newrank + d * (ranks[node]/len(graph[node])) 
      newranks[page] = newrank 
     ranks = newranks 
    return ranks 

感謝@Ken指着我在正確的方向。

Answer 2

一種可能的解決辦法是引入其檢測共謀遞歸方法。喜歡的東西：

def Colluding(p1,p2,itemDict,k): 
    if p1 == p2: 
     return True 
    elif k == 0: 
     return False 
    else p2 in itemDict[p1]: 
     return True 
    for p in itemDict[p1]: 
     if Colluding(p1,p,itemDict,k-1): 
      return True 
    return False 

然後在那裏說：if item in itemDict[node]你會if item in itemDict[node] and not Colluding(item,node,itemDict,k)或類似的東西。

這樣做depth-first search如果有一個很小的深度（比如A-> B-> A）有很多共謀鏈接，可能不是最好的選擇，因爲他們可能只有幾次全深度搜索後才能找到。在這種情況下，您可能會找到另一種方法來做breadth-first search。此外，如果您有很多鏈接，則可能值得嘗試轉換爲循環，因爲如果使用遞歸，Python可能會遇到堆棧溢出問題。遞歸算法是我首先想到的，因爲使用遞歸遍歷樹似乎很自然。

注：由於這是家庭作業幫助，我沒有測試它與一些比較可能不是很正確，需要以某種方式進行調整。

Answer 3

我也參加了這個課程..我提出了以下解決方案。基本上，我們需要的只是「所有相互聯繫」。下面的過程計算所有的互惠鏈接，給出一個圖和k級。它返回一個元組列表，表示一個相互連接（node1，node2）。所有你需要做的就是檢查（節點，頁面）是否不在這個列表中計算排名。

def get_reciprocal_links(graph, k): 
reci=[] 
for node in g: 
    for ele in g[node]: 
     got = False 
     work = [] 
     i=0 
     if node == ele and i == k: 
      reci.append((node,ele)) 
      break 
     if ele in g: 
      for e in g[ele]: 
       work.append(e) 

     while i < k: 
      if node in work: 
       reci.append((node,ele)) 
       got = True 
       break 
      else: 
       i=i+1 
       check=work.pop() 
       if check in g: 
        for e in g[check]: 
         work.append(e) 
     if got == True: 
      continue 
return reci