TunkRank в Mathematica

Question

Я пробую Mathematica впервые и использую TunkRank в качестве моего алгоритма выбора. Вот что я придумал:

Following = {{2, 3, 4}, {0, 4}, {1, 3}, {1, 4}, {0, 2}}
Followers = {{1, 4}, {2, 3}, {0, 4}, {0, 2}, {0, 1, 3}}
p = 0.05
Influence[x_] := Influence[x] =
    Sum[1 + (p * Influence[Followers[[x, i]]])/(1 + 
        Length[Following[[x]]]), {i, 0, Length[Followers[[x]]]}]

Если вы запустите это в Mathematica, вы увидите, что оно работает не только на узлах подписчиков. Вместо этого рекурсия бесконечна. Что я делаю не так?

Answer 1

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

In[104]:= Do[influence[0][j] = 1, {j, 5}];

influence[j_][x_] := 
 influence[j][x] = 
  Sum[(1 + p*influence[j - 1][followers[[x, i]]])/(1 + 
      Length[following[[followers[[x, i]]]]]), {i, 
    Length[followers[[x]]]}];

In[105]:= Do[Print[influence[j] /@ {1, 2, 3, 4, 5}];, {j, 10}];

During evaluation of In[105]:= {1.,1.,0.875,0.875,1.375}

During evaluation of In[105]:= {1.0625,0.9583333333333333,0.9375,0.8541666666666666,1.354166666666667}

During evaluation of In[105]:= {1.052083333333333,0.9652777777777777,0.9418402777777777,0.8723958333333333,1.3515625}

During evaluation of In[105]:= {1.052806712962963,0.9690393518518517,0.9401041666666666,0.8718171296296295,1.354456018518518}

During evaluation of In[105]:= {1.053915895061728,0.968653549382716,0.94067684220679,0.8716182002314814,1.355076919367284}

During evaluation of In[105]:= {1.053955078125,0.9687158404063785,0.94091897344393,0.871852293917181,1.355118111818416}

During evaluation of In[105]:= {1.053972325370799,0.9687952112268517,0.9409307367353609,0.87189754700628,1.355172407152885}

During evaluation of In[105]:= {1.053994603063289,0.9688047139569401,0.9409419418634972,0.8719016634605767,1.355195333710205}

During evaluation of In[105]:= {1.054000007944524,0.9688072675540123,0.9409485476679453,0.871906315693494,1.355200388285831}

During evaluation of In[105]:= {1.054001275973307,0.9688091438935732,0.9409500657073706,0.8719080922710565,1.35520226486765}

Я думаю, что лучше просто настроить и решить линейную систему.Это можно сделать следующим образом.

In[107]:= NSolve[
 Table[inf[x] == 
   Sum[(1 + p*inf[followers[[x, i]]])/(1 + 
       Length[following[[followers[[x, i]]]]]), {i, 
     Length[followers[[x]]]}], {x, 5}], inf /@ Range[5]]

Out[107]= {{inf[1] -> 1.054002220652064, inf[2] -> 0.9688099323710506,
   inf[3] -> 0.940950842838397, inf[4] -> 0.8719087513879075, 
  inf[5] -> 1.355203391541334}}

Это связано с итеративным подходом, описанным выше, поскольку это единственный метод решения такой линейной системы (это метод Якоби).

Answer 2

Для начала вы можете рассмотреть возможность сделать p параметром со значением по умолчанию (см. документация ). Что-то вроде Influence[x_,p_?Positive:0.05]:= (* definition *).

Во-вторых, вы устанавливаете спецификацию детали i так, чтобы она начиналась с 0. В Mathematica индексы начинаются с 1, а не с 0. В итоге вы получите Head объекта. В этом случае Followers[[x,0]] вернет List. Вам нужно изменить это и увеличить ваши данные на 1.

Following = {{3, 4, 5}, {1, 5}, {2, 4}, {2, 5}, {1, 3}};
Followers = {{2, 5}, {3, 4}, {1, 5}, {1, 3}, {1, 2, 4}};
Influence[x_, P_: 0.05] := 
 Influence[x] = 
  Sum[1 + (P*Influence[Followers[[x, i]]])/(1 + 
      Length[Following[[x]]]), {i, Length[Followers[[x]]]}]

В-третьих, у вас есть некоторая рекурсивность в ваших данных. За человеком 1 следует лицо 2, за которым следуют 3 и 4, за которыми следуют оба. 1. Конечно, это рекурсивно.

follows = Join @@ Thread /@ Thread[Following -> Range@5]
 {3 -> 1, 4 -> 1, 5 -> 1, 1 -> 2, 5 -> 2, 2 -> 3, 4 -> 3, 2 -> 4, 
 5 -> 4, 1 -> 5, 3 -> 5}

GraphPlot[follows, DirectedEdges -> True, VertexLabeling -> True]

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

EDIT

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

(* Following = {{3, 4, 5}, {1, 5}, {2, 4}, {2, 5}, {1, 3}}; *)
Followers = {{2, 5}, {3, 4}, {1, 5}, {1, 3}, {1, 2, 4}};

adjmatrix = PadRight[SparseArray[List /@ # -> 1] & /@ Followers]

{{0, 1, 0, 0, 1},
 {0, 0, 1, 1, 0},
 {1, 0, 0, 0, 1},
 {1, 0, 1, 0, 0},
 {1, 1, 0, 1, 0}}

Это дает бит, эквивалентный операторам Length в вашей версии.

vec1 = Table[1, {5}]  (* {1, 1, 1, 1, 1} *)

adjmatrix.vec1

vec1.adjmatrix

{2, 2, 2, 2, 3}

{3, 2, 2, 2, 2}

Сходимость быстрая.

 NestList[1 + 0.02 * adjmatrix.#1/(1 + vec1.adjmatrix) &, {1, 1, 1, 1, 1}, 5]
{{1, 1, 1, 1, 1}, {1.01, 1.01333, 1.01333, 1.01333, 1.02}, {1.01017, 
 1.01351, 1.01353, 1.01349, 1.02024}, {1.01017, 1.01351, 1.01354, 
 1.01349, 1.02025}, {1.01017, 1.01351, 1.01354, 1.01349, 
 1.02025}, {1.01017, 1.01351, 1.01354, 1.01349, 1.02025}}

Учитывая матрицу смежности, вы можете иметь функцию:

TunkRank[mat_?MatrixQ, p_?Positive] :=
 With[{vec = Table[1, {Length[mat]}]},
 FixedPoint[1 + p * mat.#1/(1 + vec.mat) &, vec]]

Надеюсь, это поможет. Я предполагаю, что это дает правильные ответы.

Answer 3

Цитата из сообщения TunkRank , которое я написал и кто-то еще процитировал:

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

Даже если нет направленных циклов, вы также можете остановить вычисление, когда числа станут достаточно малыми.

Удачи в TunkRank и не стесняйтесь обращаться ко мне по адресу dtunkelang@gmail.com, если у вас есть какие-либо вопросы по этому поводу!

Answer 4

Первая проблема, которую я вижу, состоит в том, что вход для вашей функции равен 0. Рассмотрим термин Followers[[x, i]] в вашем определении Influence. Напомним, что Part 0 выражения дает вам Head.

Таким образом, Following[[0]] (когда x=0) даст вам List и Followers[[0,0]] (это тот случай, когда x=0 и i=0) даст вам Symbol, то есть Head List. Я не думаю, что это то, что вы хотите.

Во-вторых, в таких рекурсивных определениях обычно есть одно или два начальных значения / начальные значения / начальные значения, как бы вы их ни называли. Например, уравнение Фибоначчи в рекурсивной форме:

f[0]=1;
f[1]=1;
f[n_]:=f[n]=f[n-1]+f[n-2]

где вы определили f для первых двух случаев 0 и 1. Однако в вашей функции такой инициализации нет, и есть вероятность, что она просто выполняется по кругу.

Я не могу сказать больше ничего, не зная, что такое алгоритм TunkRank.