1. PersonalRank的產(chǎn)生背景
? ? PersonalRank產(chǎn)生于用戶瀏覽網(wǎng)頁的行為的場景，受pageRank算法的啟發(fā)，是一種基于圖的搜索算法，同時(shí)也可以將用戶瀏覽網(wǎng)頁的行為看成是用戶瀏覽物品的行為，這樣就可以針對(duì)用戶接下來最可能瀏覽的物品做推薦。
2. PersonalRank的特點(diǎn)
? ? ?2.1. 圖結(jié)構(gòu)
? ? ?2.2 PageRank
3. PersonalRank的網(wǎng)絡(luò)結(jié)構(gòu)
? ??
????上圖為盜圖
4. PersonalRank的算法
? ? 這里依舊不說話，默默上公式：
? ??
從上述式子看到了一個(gè)很有意思的事情，就拿節(jié)點(diǎn)游走這件事來說，將各個(gè)節(jié)點(diǎn)看作一個(gè)人，將可能性比作重要性，從A節(jié)點(diǎn)到B節(jié)點(diǎn)的可能性即是A對(duì)B的重要性，類比映射即是，自己認(rèn)為自己行不算，得別人說自己行才行，別人還得不是那種見誰都夸的人(別人的出度很大)，還得說自己行的那個(gè)人行才行（別人的PR值大）。那么對(duì)應(yīng)公式就是PR(B)的值的大小取決于：別人的出度大小、別人的重要性大小、別人夸自己的概率。哈哈哈，編不下去了...
5. PersonalRank的代碼
# coding=utf-8
__author__ = 'orisun'
import time
import operator
def PersonalRank(G, alpha, root, max_step):
? ? rank = dict()
? ? rank = {x: 0 for x in G.keys()}
? ? rank[root] = 1
? ? # 開始迭代
? ? begin = time.time()
? ? for k in range(max_step):
? ? ? ? tmp = {x: 0 for x in G.keys()}
? ? ? ? # 取節(jié)點(diǎn)i和它的出邊尾節(jié)點(diǎn)集合ri
? ? ? ? for i, ri in G.items():
? ? ? ? ? ? # 取節(jié)點(diǎn)i的出邊的尾節(jié)點(diǎn)j以及邊E(i,j)的權(quán)重wij, 邊的權(quán)重都為1，歸一化之后就上1/len(ri)
? ? ? ? ? ? for j, wij in ri.items():
? ? ? ? ? ? ? ? # i是j的其中一條入邊的首節(jié)點(diǎn)，因此需要遍歷圖找到j(luò)的入邊的首節(jié)點(diǎn)，
? ? ? ? ? ? ? ? # 這個(gè)遍歷過程就是此處的2層for循環(huán)，一次遍歷就是一次游走
? ? ? ? ? ? ? ? tmp[j] += alpha * rank[i] / (1.0 * len(ri))
? ? ? ? ? ? ? ? #####上面這樣也是沒問題的，本次游走不需要游走的計(jì)算了和它相鄰的游走節(jié)點(diǎn)的 rank[i]也為0，這樣計(jì)算得到它的結(jié)果還是0，并不影響實(shí)際游走動(dòng)作；
? ? ? ? # 我們每次游走都是從root節(jié)點(diǎn)出發(fā)，因此root節(jié)點(diǎn)的權(quán)重需要加上(1 - alpha)
? ? ? ? tmp[root] += (1 - alpha)
? ? ? ? rank = tmp
? ? end = time.time()
? ? print('use time', end - begin)
? ? li = sorted(rank.items(), reverse=True)
? ? for ele in li:
? ? ? ? print("%s:%.3f, \t" % (ele[0], ele[1]))
? ? return rank
if __name__ == '__main__':
? ? alpha = 0.8
? ? G = {'A': {'a': 1, 'c': 1},
? ? ? ? 'B': {'a': 1, 'b': 1, 'c': 1, 'd': 1},
? ? ? ? 'C': {'c': 1, 'd': 1},
? ? ? ? 'a': {'A': 1, 'B': 1},
? ? ? ? 'b': {'B': 1},
? ? ? ? 'c': {'A': 1, 'B': 1, 'C': 1},
? ? ? ? 'd': {'B': 1, 'C': 1}}
? ? PersonalRank(G, alpha, 'b', 50)? # 從'b'節(jié)點(diǎn)開始游走
代碼執(zhí)行結(jié)果如下：
可以看到B節(jié)點(diǎn)為接下來最有可能游走的節(jié)點(diǎn)。
6.參考文獻(xiàn)
https://www.cnblogs.com/zhangchaoyang/articles/5470763.html#mjx-eqn-pr
