用于查找节点最可能祖先的图形算法
Graph algorithm to find the most likely ancestor of a node
我正在研究维基百科类别图 (WCG)。在 WCG 中，每篇文章都关联到多个类别。
例如，文章 "Lists_of_Israeli_footballers" 链接到多个类别，例如：
Lists of association football players by nationality - Israeli footballers - Association football in Israel lists
现在，如果您向后爬类别树，您可能会发现很多路径都爬到了 "Football" 类别，但也至少有一条路径通向 "Science" 例如。
这是有问题的，因为我的最终目标是能够使用它所链接的类别列表来确定一篇文章是否属于给定的类别：现在一个简单的祖先搜索会给出误报（例如：将 "Israeli footballers" 标识为 "Science" 类别的一部分 - 这显然不是预期的结果）。
我想要一个能够找出最有可能的祖先的算法。
我想到了两个主要的解决方案：
统计WCG中将文章的类别顶点链接到候选祖先类别的不同路径数（并使用链接到其他相同深度类别的路径数进行比较）
使用某种聚类算法并在孤立的图形空间中进行祖先搜索查询
这些选项的问题在于，考虑到 WCG 的规模（200 万个顶点 - 甚至更多边），它们似乎非常昂贵。最终，我可以使用一种解决方案，该解决方案使用 O(n) 或更多的预处理算法来稍后实现 O(1)，但我需要查询总体上非常快。
我的问题有现成的解决方案吗？接受所有建议。
Np，感谢您的澄清。像聚类这样的东西可能不是一个好主意，因为这些类型的算法旨在确定尚未与类别相关联的对象的类别。在您的问题中，所有对象（足球运动员文章）已经与不同的类别相关联。
您可能应该对所有文章进行完整搜索，并将与每篇文章匹配的类别保存在散列中 table，这样当您需要为新文章了解该类别信息时，就可以检索该类别信息.
一个类别是否与一篇文章相关对我来说似乎完全是任意的，似乎是你应该自己决定的事情（例如，在确定一个类别的一部分之前确定一个类别的 5 个链接的阈值） .
如果您从维基百科获取这些文章，您可能需要很长时间 运行 遍历整个树，但在我看来，这似乎是您唯一的选择。
使用 DFS 搜索，每次找到 article-category 匹配时，将文章保存在哈希中table（您需要能够将文章缩减为唯一标识符）。
这可能是我在这里发布过的最含糊的回答，您的问题可能过于宽泛...如果您对此没有帮助，请告诉我，以便我考虑将其删除以便避免与未来的读者混淆。
我正在研究维基百科类别图 (WCG)。在 WCG 中，每篇文章都关联到多个类别。 例如，文章 "Lists_of_Israeli_footballers" 链接到多个类别，例如：
Lists of association football players by nationality - Israeli footballers - Association football in Israel lists
现在，如果您向后爬类别树，您可能会发现很多路径都爬到了 "Football" 类别，但也至少有一条路径通向 "Science" 例如。
这是有问题的，因为我的最终目标是能够使用它所链接的类别列表来确定一篇文章是否属于给定的类别：现在一个简单的祖先搜索会给出误报（例如：将 "Israeli footballers" 标识为 "Science" 类别的一部分 - 这显然不是预期的结果）。
我想要一个能够找出最有可能的祖先的算法。
我想到了两个主要的解决方案：
统计WCG中将文章的类别顶点链接到候选祖先类别的不同路径数（并使用链接到其他相同深度类别的路径数进行比较）
使用某种聚类算法并在孤立的图形空间中进行祖先搜索查询
这些选项的问题在于，考虑到 WCG 的规模（200 万个顶点 - 甚至更多边），它们似乎非常昂贵。最终，我可以使用一种解决方案，该解决方案使用 O(n) 或更多的预处理算法来稍后实现 O(1)，但我需要查询总体上非常快。
我的问题有现成的解决方案吗？接受所有建议。
Np，感谢您的澄清。像聚类这样的东西可能不是一个好主意，因为这些类型的算法旨在确定尚未与类别相关联的对象的类别。在您的问题中，所有对象（足球运动员文章）已经与不同的类别相关联。
您可能应该对所有文章进行完整搜索，并将与每篇文章匹配的类别保存在散列中 table，这样当您需要为新文章了解该类别信息时，就可以检索该类别信息.
一个类别是否与一篇文章相关对我来说似乎完全是任意的，似乎是你应该自己决定的事情（例如，在确定一个类别的一部分之前确定一个类别的 5 个链接的阈值） .
如果您从维基百科获取这些文章，您可能需要很长时间 运行 遍历整个树，但在我看来，这似乎是您唯一的选择。
使用 DFS 搜索，每次找到 article-category 匹配时，将文章保存在哈希中table（您需要能够将文章缩减为唯一标识符）。
这可能是我在这里发布过的最含糊的回答，您的问题可能过于宽泛...如果您对此没有帮助，请告诉我，以便我考虑将其删除以便避免与未来的读者混淆。