Wie man Programm beschleunigt, das den kürzesten Weg zwischen zwei wikipedia Artikeln findet

Question

Ich habe vor kurzem ein Programm programmiert, das den kürzesten Weg zwischen zwei wikipedia Artikeln findet. Das Problem besteht darin, ALLE Links von einer Seite zu bekommen und sie in ein Diagramm zu schreiben, dauert sehr lange. Den Weg zu finden ist der einfache Teil. Basicly, was ich tue, ist dies:

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; 

Und meine import_page Funktion ist diese:

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 

Das Problem für einen beliebigen Abstand ist größer als 2/3 Links ist eine Einnahme eine immense Zeitraum. Irgendwelche Ideen, wie ich es beschleunigen kann?

Answer 1

Ich habe einen Ansatz als @Tgr verwendet, der eine kleine Welt ausnutzt. Wenn Sie ein gewichtetes Netzwerk verwenden, können Sie die Suche auf einen Subgraphen beschränken, der groß genug ist, um relevante Hubs zu umfassen, und klein genug, um in einer Web-RESTful-API verarbeitet zu werden.

Sie können das iGraph-Modul lieber aus dem Netzwerk heraussuchen, um weniger Speicherbedarf zu haben.

Mit dem von mir vorgeschlagenen Ansatz konnte ich kürzeste Wege für die Verbindung von bis zu 5 abgefragten Wikipedia-Artikeln mit einem Speicherabdruck von bis zu 100 MB Sub-Graph in Echtzeit erstellen. Ein kürzester Pfad zwischen zwei Themen dauert weniger als 1s.

Ich würde gerne einen Link zu meinem Projekt teilen, die tatsächlich eine gewichtete Wissensnetzwerke für die Wikipedia berechnen, um die Suche nach Verbindungen zwischen mehreren Themen zu ermöglichen - wäre es SO Politik brechen oder könnte für die OP und Diskussion über nützlich sein seine Frage?

EDIT

---

Danke @Tgr für Debriefing auf die Politik.

Nifty.works ist eine Prototyp-Plattform für die Suche nach Verbindungen zwischen interdisziplinären Feldern. Das Wissensdiagramm ist eine Untermenge von Wikidata, gepaart mit der englischen Wikipedia.

Als Beispiel für die OP, zeigt dieses Beispiel kürzeste Wege zwischen fünf Wikipedia Artikel abgefragt: subgraph for connections between articles: "Shortest Path Problem", "A star search", "networkx", "knowledge graph" and "semantic network"

ich das Wissen Graph von Wikipedia als gewichtetes Netzwerk berechnet. Das Netzwerk verfügt über Small-World-Eigenschaften. Eine Abfrage nach Verbindungen (Pfaden) zwischen Artikeln wird vorgenommen, indem ein Teil des Wissensgraphen (ein Unterdiagramm) abgegrenzt wird.

Mit diesem Ansatz ist es möglich, eine Graphensuche schnell genug zu bedienen, um Einblicke in die Wissensentdeckung zu geben, sogar auf kleinen Servermaschinen.

Hier finden Sie examples of gamification of shortest paths between two articles der englischen Wikipedia, jedes Paar hat einen Abstand größer als 3 Links - das heißt, sie sind nicht die ersten Nachbarn: z. "Maschinelles Lernen" und "Leben" - here a json of the queried subgraph).

Sie könnten sogar Parameter hinzufügen, um die Größe Ihres gewichteten Sub-Graphen anzupassen, um unterschiedliche Ergebnisse zu erhalten. Als Beispiel sehen Sie die Unterschiede zwischen:

• machine learning - life: query of shortest paths on weighted subgraph of the knowledge graph of English Wikipedia (small-world network) (1)

• machine learning - life: query of shortest paths on weighted subgraph of the knowledge graph of English Wikipedia (small-world network) (2)

schließlich auch auf diese Frage suchen: https://stackoverflow.com/a/16030045/305883

Answer 2

Den kürzesten Weg mit Sicherheit zu finden, ist mit einem einfachen Algorithmus und einer Web-API praktisch unmöglich. Wenn der kürzeste Pfad N Schritte hat, müssen Sie jeden möglichen Pfad mit der Länge N-1 oder weniger gehen, um sicher zu sein. Mit Millionen von Artikeln und Dutzenden bis Hunderten von Links von jedem, das ist nicht möglich, es sei denn, Sie haben wirklich Glück und der kürzeste Weg ist nur 1-2 Links. Wenn es 10 Schritte entfernt ist, müssten Sie Milliarden von Anfragen stellen, was Jahre dauern würde.

Wenn Sie die meiste Zeit nur einen relativ kurzen Pfad finden möchten, können Sie etwas wie eine A* search algorithm mit einer guten Heuristik versuchen. Zum Beispiel könnten Sie eine Art von small-world property hypothetisieren und versuchen, Themen-Hubs zu identifizieren, die nahe an anderen Themen-Hubs und auch an allen Artikeln in diesem Thema liegen. Oder Sie können Kandidaten für dasselbe Thema oder für dieselbe historische Periode wie das Ziel bewerten.