Блог

Определение индекса H, используемого в этом алгоритме

Предположим, что реляционное выражение представлено в виде y = F(x1, x2, . . . , xn), где F возвращает целое число, большее 0, и функция должна найти максимальное значение y, удовлетворяющее условию, что существуют по крайней мере элементы y, значения которых не меньше y. Следовательно, индекс H любого узла i определяется как

H(i) = F(kj1 ,kj2 ,…,k jki)

где kj1, kj2, . . . , kjki представляют набор степеней соседних узлов узла i.

Теперь я хочу найти индекс H узлов следующих графиков, используя алгоритм, приведенный ниже :

График :

Код (написан на Python и NetworkX) :

 def hindex(g, n):
  nd = {}
  h = 0
  # print(len(list(g.neighbors(n))))
  for v in g.neighbors(n):
    #nd[v] = len(list(g.neighbors(v)))
    nd[v] = g.degree(v)
    snd = sorted(nd.values(), reverse=True)
    for i in range(0,len(snd)):
      h = i
      if snd[i] < i:
        break
  #print("H index of "   str(n)  " : "   str(h))
  return h
 

Проблема :
Этот алгоритм возвращает неправильные значения узлов 1, 5, 8 и 9

Фактические Значения :

Узел 1 — 6 : Индекс H = 2

Узел 7 — 9 : Индекс H = 1

Но для узлов 1 и 5 я получаю 1, а для узлов 8 и 9 я получаю 0.

Любые зацепки о том, где я ошибаюсь, будут высоко оценены!

Попробуй это:

 def hindex(g, n):
    sorted_neighbor_degrees = sorted((g.degree(v) for v in g.neighbors(n)), reverse=True)
    h = 0
    for i in range(1, len(sorted_neighbor_degrees) 1):
        if sorted_neighbor_degrees[i-1] < i:
            break
        h = i

    return h
 

Нет необходимости во вложенном цикле; просто составьте уменьшающийся список и вычислите индекс h, как обычно.

Причина «i — 1» заключается в том, что наши массивы индексируются на 0, в то время как индекс h основан на ранжировании (т. е. на k наибольших значениях), которые индексируются на 1.

Из определения h-индекса: Для нерастущей функции f h(f) — это max i >= 0, такой, что f(i) >>= i. Это, эквивалентно, min i >>>= 1, такой, что f(i) >>> Конечно, существует множество других способов (с различными требованиями к времени и пространству) вычисления h.