Расчет индекса Хирша

← →
George © (2011-10-21 13:00) [0]

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

"Индекс вычисляется на основе распределения цитирований работ данного исследователя. Хирш пишет: «Учёный имеет индекс h, если h из его Np статей цитируются как минимум h раз каждая, в то время как оставшиеся (Np — h) статей цитируются не более, чем h раз каждая». Иными словами, учёный с индексом h опубликовал h статей, на каждую из которых сослались как минимум h раз. Так, если у данного исследователя опубликовано 100 статей, на каждую из которых имеется лишь одна ссылка, его h-индекс равен 1. Таким же будет h-индекс исследователя, опубликовавшего одну статью, на которую сослались 100 раз. В то же время (более реалистический случай), если у исследователя имеется 1 статья с 9 цитированиями, 2 статьи с 8 цитированиями, 3 статьи с 7 цитированиями, …, 9 статей с 1 цитированием каждой из них, то его h-индекс равен 5."
Из википедии.

Может кто предложить решение? Язык не дельфи, мне интересен просто алгоритм. Ну и задачка, может быть, интересной для кого-нибудь будет.

← →
И. Павел © (2011-10-21 13:03) [1]

Проход по числу статей бинарным поиском? Например, всего статей A. Выбираете B = A div 2. Если у ученого нет B публикаций с цитированием B раз каждой, то B = B/2, иначе B = 3 * B/4.
Ну или простым перебором от 1 до A.

← →
И. Павел © (2011-10-21 13:06) [2]

> [1] И. Павел © (21.10.11 13:03)

Перед эти лучше упорядочить публикации ученого по числу ссылок, чтобы было проще определить, сколько у ученого публикаций с числом ссылок не меньше N.

← →
TUser © (2011-10-21 14:00) [3]

Что считать-то? Что на вход, что надо получить на выходе?

← →
George © (2011-10-21 14:07) [4]

На входе массив ключ-значение (айдишник публикации - число ее цитирований), на выходе индекс Хирша.

← →
OW © (2011-10-21 14:24) [5]

> если у исследователя имеется 1 статья с 9 цитированиями,
> 2 статьи с 8 цитированиями, 3 статьи с 7 цитированиями,
> …, 9 статей с 1 цитированием каждой из них, то его h-индекс
> равен 5.

так понимаю, это все разные статьи должны быть?
т.е. среди 2х статей по 8 раз нет той, что 9раз цитировалась?
(ну, раз она цитировалась 9 раз, то и меньшее кол-во раз она тоже цитировалась)

← →
George © (2011-10-21 14:46) [6]

Ну вроде как так.

← →
TUser © (2011-10-21 17:08) [7]

> айдишник публикации - число ее цитирований

по этим данным индекс Хирша вычислить невозможно, надо иметь базу публикаций и цитирований

← →
MBo © (2011-10-21 17:13) [8]

Сортировка по цитированию по убыванию.
Искомый индекс - последнее (наибольшее) i, при котором A[i] >=i
Графически - точка пересечения прямой y=x и кривой распределения ссылок, обычно похожей на ветвь гиперболы

← →
Компромисс (2011-10-21 17:20) [9]

> Искомый индекс - последнее (наибольшее) i, при котором A[i]
> >=i

Неверно для 1,1,1,1,5

← →
Компромисс (2011-10-21 17:25) [10]

Компромисс (21.10.11 17:20) [9]

А нет, торможу.

← →
George © (2011-10-21 18:10) [11]

> TUser © (21.10.11 17:08) [7]

Вот она у меня есть.

> Графически - точка пересечения прямой y=x и кривой распределения
> ссылок, обычно похожей на ветвь гиперболы

Берем прямую y = x. Берем две точки с кривой распределения ссылок таких, где y - x = a при наименьшем a, и x - a = b, при наименьшем b. Т.е. две точки, самые близкие к искомой прямой. Через эти две взятые точки проводим прямую и находим точку пересечения с прямой y = x. Затем округляем ее координаты в меньшую сторону и получаем индекс Хирша. Оно? :)

Реализация на PHP получилась такой (под друпал):

// Запрос с выборкой "количеств" цитирований по определенному автору $result = db_query(" SELECT COUNT(fdfr.field_refer_nid) quotes FROM {field_data_field_refer} fdfr INNER JOIN {field_data_field_author} fdfa ON fdfr.field_refer_nid = fdfa.entity_id WHERE fdfa.field_author_nid = :author_id GROUP BY fdfr.field_refer_nid ORDER BY quotes DESC", array(":author_id" => $row->nid))->fetchCol(); // Ну и перебор массива $h = 0; foreach ($result as $key=>$record) { if (($key + 1) > $record) { $h = $key; break; } } if ($h == 0) $h = $key+1; return $h;

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

Особенную прелесть такой задаче на практике придает обилие авторов с малораспространенной в России фамилией Lee/Yang/Wang/etc. Как всех этих Ли отличать друг от друга - на то отдельная наука есть.

> [14] TUser © (22.10.11 10:37)
> Как всех этих Ли отличать друг от друга - на то отдельная
> наука есть.

И на фото они все похожи.

> TUser © (22.10.11 10:37) [14]

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

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

Расчет индекса Хирша Найти похожие ветки