如何加快程序，找到兩個維基百科文章之間的最短路徑

我最近編寫了一個程序，找到兩個維基百科文章之間的最短路徑。問題是獲取頁面上的所有鏈接並將其放入圖表需要很長時間。尋找路徑是一件容易的事情。 Basicly我在做什麼是這樣的：如何加快程序，找到兩個維基百科文章之間的最短路徑

startingPage = 'Lisbon' 
target = 'Adolf Hitler' 
graph = nx.DiGraph() 
graph.add_node(startingPage) 
found = pages.import_page(graph, startingPage) 

while found != True: 
    for node in list(graph): 
     if graph.out_degree(node) == 0: 
      found = pages.import_page(graph, node) 
     if found == True: 
      break;

而且我import_page功能是這一個：

def import_page(graph, starting, target): 
    general_str = 'https://en.wikipedia.org/w/api.php?action=query&prop=links&pllimit=max&format=json&titles=' 
    data_str = general_str + starting 
    encoded_data_str = data_str.encode('utf-8') #Sanitize input 
    response = url.urlopen(encoded_data_str) 
    data = json.loads(response.read()) 
    pageId = data['query']['pages'].keys() 
    print starting 
    if data['query']['pages'].keys()[0] == '-1': #Check if the page doesn't exist in Wikipedia 
     return False 
    elif data['query']['pages'][pageId[0]].keys()[2] != 'links': #Check if the page has no links in it 
     return False 

    for jsonObject in data['query']['pages'][pageId[0]]['links']: 

     graph.add_node(jsonObject['title']) 
     graph.add_edge(starting, jsonObject['title']) 

     if jsonObject['title'] == target: 
      return True 

    while data.keys()[0] != 'batchcomplete': 

     continueId = data['continue']['plcontinue'] 
     continue_str = data_str + '&plcontinue=' + continueId 
     encoded_continue_str = continue_str.encode('utf-8') #Sanitize input 
     response = url.urlopen(encoded_continue_str) 
     data = json.loads(response.read()) 

     for jsonObject in data['query']['pages'][pageId[0]]['links']: 
      graph.add_node(jsonObject['title']) 
      graph.add_edge(starting, jsonObject['title']) 
      if jsonObject['title'] == target: 
       return True 

    return False

問題對於任何距離大於2/3的鏈接是一個採取一個巨大的多少時間。關於我如何加快速度的任何想法？

來源

2016-11-29 Joaquim Verdasca

爲什麼你關心的邊緣？你不是隻想保留一個活動節點列表和訪問節點列表嗎？另一個問題（可能只是由於我不知道圖形庫而導致）：在遍歷其節點時修改圖形是否有效？ –

另外，它寫在這裏的方式，你的'import_page'確實是'import_Adolf_Hitler_page' :) –

是的，我已經更新了，忘了在這裏更新！ –

我使用@Tgr指出的方法，利用一個小世界。如果您使用加權網絡，則可以將搜索範圍限制爲足夠大的子圖以涵蓋相關的集線器，並且足夠小以便在Web RESTful API中處理。

您可能想查看iGraph模塊而不是networkx，以減少內存佔用。

使用我向您推薦的方法，我能夠獲得連接最多5條查詢維基百科文章的最短路徑，實時創建的內存佔用高達100MB的子圖。兩個主題之間的最短路徑少於1秒。

我很樂意與我的項目分享一個鏈接，該鏈接實際上是爲維基百科計算一個加權知識網絡，以允許搜索多個主題之間的聯繫 - 它是否會打破SO策略，或者可能對OP和討論有用他的問題？

編輯

謝謝@Tgr有關政策述職。

Nifty.works是一個尋找跨學科領域之間聯繫的原型平臺。知識圖是Wikidata與英語維基百科配對的子集。

對於OP的示例，該示例示出5的維基百科文章之間查詢最短路徑：我計算維基百科的知識圖作爲加權網絡subgraph for connections between articles: "Shortest Path Problem", "A star search", "networkx", "knowledge graph" and "semantic network"

。該網絡具有小世界屬性。對文章之間的連接（路徑）的查詢是通過定義知識圖的一部分（子圖）來進行的。

使用此方法，可以足夠快地提供圖表搜索，以提供知識發現的見解，即使在小型服務器上也是如此。

在這裏您可以找到英語維基百科的examples of gamification of shortest paths between two articles，每對的距離大於3個鏈接 - 也就是說，它們不是第一個鄰居：例如，「機器學習」和「生活」 - here a json of the queried subgraph）。

您甚至可能需要添加參數來調整加權子圖的大小，以獲得不同的結果。作爲一個例子，看看之間的區別：

最後，還看這個問題：https://stackoverflow.com/a/16030045/305883

來源

2016-12-04 23:37:03 user305883

分享你自己的作品時，如果主題明確，則絕對符合SO政策。（[查看常見問題。]（http://stackoverflow.com/help/promotion）） – Tgr

感謝您的詳細解答！ –

通過簡單的算法和Web API，找到確定性最短的路徑實際上是不可能的。如果最短路徑具有N個步長，則需要走過長度爲N-1或更小的每條可能路徑。有數百萬篇文章和數十到數百個鏈接，除非你真的很幸運，最短路徑只有1-2個鏈接，否則這是不可行的。如果說離開10步，你就不得不提出數十億次的請求，這需要幾年的時間。

如果你只是想在大多數時間找到一個合理的短路徑，你可以嘗試像A* search algorithm這樣的啓發式。例如，您可以假設某種small-world property，並嘗試確定與其他主題中心相關的主題中心以及該主題中的所有文章。或者你可以對同一主題或與目標相同的歷史時期進行評分。

來源

2016-12-04 21:58:44 Tgr

如何加快程序，找到兩個維基百科文章之間的最短路徑

回答

相關問題