如何加快程序，找到两个维基百科文章之间的最短路径

我最近编写了一个程序，找到两个维基百科文章之间的最短路径。问题是获取页面上的所有链接并将其放入图表需要很长时间。寻找路径是一件容易的事情。 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

如何加快程序，找到两个维基百科文章之间的最短路径

回答

相关问题