PersonalRank

1. PersonalRank的产生背景

    PersonalRank产生于用户浏览网页的行为的场景，受pageRank算法的启发，是一种基于图的搜索算法，同时也可以将用户浏览网页的行为看成是用户浏览物品的行为，这样就可以针对用户接下来最可能浏览的物品做推荐。

2. PersonalRank的特点

     2.1. 图结构

     2.2 PageRank

3. PersonalRank的网络结构

    

    上图为盗图

4. PersonalRank的算法

    这里依旧不说话，默默上公式：

    

从上述式子看到了一个很有意思的事情，就拿节点游走这件事来说，将各个节点看作一个人，将可能性比作重要性，从A节点到B节点的可能性即是A对B的重要性，类比映射即是，自己认为自己行不算，得别人说自己行才行，别人还得不是那种见谁都夸的人(别人的出度很大)，还得说自己行的那个人行才行（别人的PR值大）。那么对应公式就是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()}

        # 取节点i和它的出边尾节点集合ri

        for i, ri in G.items():

            # 取节点i的出边的尾节点j以及边E(i,j)的权重wij, 边的权重都为1，归一化之后就上1/len(ri)

            for j, wij in ri.items():

                # i是j的其中一条入边的首节点，因此需要遍历图找到j的入边的首节点，

                # 这个遍历过程就是此处的2层for循环，一次遍历就是一次游走

                tmp[j] += alpha * rank[i] / (1.0 * len(ri))

                #####上面这样也是没问题的，本次游走不需要游走的计算了和它相邻的游走节点的 rank[i]也为0，这样计算得到它的结果还是0，并不影响实际游走动作；

        # 我们每次游走都是从root节点出发，因此root节点的权重需要加上(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'节点开始游走

代码执行结果如下：

可以看到B节点为接下来最有可能游走的节点。

6.参考文献

https://www.cnblogs.com/zhangchaoyang/articles/5470763.html#mjx-eqn-pr