Как выделить фиксированные ресурсы вершинам графа, но вершины с низкой степенью получают больше?

Question

Мне нужно решить простую проблему, но я застрял и мне нужна ваша помощь. Проблема заключается в следующем:

У меня есть три узла A,B,C со степенью 11, 6, 1, и у меня есть 20 ресурсов для выделения каждому узлу на основе их степени. Я знаю, когда я хочу, чтобы узлы большой степени получали больше ресурсов, формула:

just sum all degrees (11+6+1)=18 and distribute the resources as follows:
A=(20/18)*11 and similar for the other nodes

Что если я хочу, чтобы узел низкой степени получал больше ресурсов, чем большой? Я имею в виду Node C степени 1, чтобы получить больше ресурсов, чем узлы A и B.

Я пробовал это:

A = (20/18)* (11)^r

Так, что когда r=1, большая степень будет иметь больше ресурсов,Но обратное неверно, например, когда r=-1, общий объем ресурсов не составит 20. Что делать?

Есть ли способ, при котором для одной и той же формулы я могу указать разные значения r и дать результаты как для низкой, так и для большой степени?

Ваша помощь будет высоко оценена,Заранее спасибо

Answer 1

Если есть хотя бы 2 узла, это возможно с r=0 для увеличения ресурсов до наивысших степеней или с r=1 для увеличения ресурсов до наименьших степеней:

(degree_sum*r - nodes[n]) * resources / ((num_nodes*r - 1) * degree_sum)

Упрощенно,для r=1 формула будет давать каждый узел пропорционально «сумме всех степеней минус степень текущего узла» (с nodes[n] степенью текущего узла):

(degree_sum - nodes[n]) * resources / ((num_nodes - 1) * degree_sum)
So, this would give:
A: (18 - 11) * 20 / (2 * 18)
B: (18 -  6) * 20 / (2 * 18)
C: (18 -  1) * 20 / (2 * 18)

Вот демонстрационная программа на Python, демонстрирующая идею:

nodes = {'A': 11, 'B': 6, 'C': 1}
resources = 20

degree_sum = sum(nodes[n] for n in nodes)
num_nodes = len(nodes)
print("sum of all degrees:", degree_sum, "- number of nodes", num_nodes)

distribution_highest_more = {n: nodes[n] * resources / degree_sum for n in nodes}
print("higher degrees get more:", distribution_highest_more)
print("  total:", sum(distribution_highest_more[n] for n in distribution_highest_more))

distribution_lowest_more = {n: (degree_sum - nodes[n]) * resources / ((num_nodes - 1) * degree_sum) for n in nodes}
print("lower degrees get more:", distribution_lowest_more)
print("  total:", sum(distribution_lowest_more[n] for n in distribution_lowest_more))

for r in range(2):
    distribution = {n: (degree_sum*r - nodes[n]) * resources / ((num_nodes*r - 1) * degree_sum) for n in nodes}
    print("distribution for r =", r, ":")
    print("  ", distribution)
    print("  total:", sum(distribution[n] for n in distribution))

Который печатает:

sum of all degrees: 18 - number of nodes 3
higher degrees get more: {'A': 12.222222222222221, 'B': 6.666666666666667, 'C': 1.1111111111111112}
  total: 20.0
lower degrees get more: {'A': 3.888888888888889, 'B': 6.666666666666667, 'C': 9.444444444444445}
  total: 20.0
distribution for r = 0 :
   {'A': 12.222222222222221, 'B': 6.666666666666667, 'C': 1.1111111111111112}
  total: 20.0
distribution for r = 1 :
   {'A': 3.888888888888889, 'B': 6.666666666666667, 'C': 9.444444444444445}
  total: 20.0