График алгоритма для поиска наиболее вероятного предка узла

Question

Я работаю над графиком категорий Википедии (WCG).В WCG каждая статья связана с несколькими категориями.Например, статья «Lists_of_Israeli_footballers» связана с несколькими категориями, такими как:

Lists of association football players by nationality - Israeli footballers - Association football in Israel lists

Теперь, если вы вернетесь назад к дереву категорий, вы, вероятно, найдете многопути, поднимающиеся до категории «Футбол», но есть также, по крайней мере, один путь, ведущий к «Науке», например.

Это проблематично, потому что моя конечная цель - определить, действительно листатья относится к данной категории, используя список категорий, с которыми она связана: сейчас простой поиск по предкам дает ложные срабатывания (например: идентифицирует «израильских футболистов» как часть категории «наука» - что, очевидно, не является ожидаемым результатом).

Мне нужен алгоритм, способный выяснить, кто является наиболее вероятным предком.

Я подумал о двух основных решениях:

• Подсчитать числоразличных путей в WCG, связывающих вершины категории статьи с категорией-предком кандидата (и используйте количество путей linking для сравнения с другими категориями такой же глубины)

• Использовать некоторый алгоритм кластеризации и выполнять поисковые запросы предков в изолированных графовых пространствах

Проблема с этими опциями заключается в том, что они кажутся очень дорогими, учитывая размер WCG (2 миллиона вершин - еще больше ребер).В конце концов, я мог бы работать с решением, которое использует алгоритм предварительной обработки в O (n) или более для достижения O (1) позже, но мне нужно, чтобы запросы были в целом очень быстрыми.

Существуют ли существующие решения длямоя проблема ?Открыто для всех предложений.

Answer 1

Np, спасибо за разъяснения.что-то вроде кластеризации, вероятно, не очень хорошая идея, поскольку алгоритмы такого типа предназначены для определения категории для объекта, который еще не связан с категорией.В вашей задаче все объекты (футболистская статья) уже связаны с разными категориями.

Вам, вероятно, следует выполнить полный поиск по всем статьям и сохранить соответствующие категории для каждой статьи в хэш-таблице, чтобы затем можно было получить информацию об этой категории, когда вам нужно узнать это для новой статьи.

Является ли категория релевантной для статьи, мне кажется совершенно произвольной и кажется, что вы должны решить для себя (например, определить порог в 5 ссылок на категорию, прежде чем она будет определена как часть категории).).

Если вы получаете эти статьи из Википедии, вам, вероятно, придется довольно долго работать над всем деревом, но, на мой взгляд, кажется, что это ваш единственный выбор.

Выполните поиск с помощью DFS, и каждый раз, когда вы найдете совпадение с категорией арктики, сохраняйте статью в хеш-таблице (вам нужно иметь возможность сократить статью до уникального идентификатора).

Это, пожалуй, мой самый расплывчатый ответ, который я когда-либо писал здесь, и ваш вопрос может быть слишком широким ... если вам не помогли, пожалуйста, дайте мне знать, чтобы я мог рассмотреть его в порядкечтобы избежать путаницы с будущими читателями.