经典机器学习算法——Pagerank算法（二）

import matplotlib.pyplot as plt
import networkx as netx  # 网络图库：生成构造网络图，并对网络图进行各类分析
import random
 
random.seed(42)  # 设置随机数种子,让结果可以复现
diGraph = netx.DiGraph()  # 生成有向图
diGraph.add_nodes_from(range(0, 100))  # range生成一个可迭代对象（迭代器：1、访问工具，本身不是具体的数据类型，可以对各种数据类型进行迭代；2、动态生成值，在每一次运行时动态加载到内存）
for i in range(100):
    j = random.randint(0, 100)
    k = random.randint(0, 100)
    diGraph.add_edge(k, j)
 
# 绘图
netx.draw(diGraph, with_labels=True)
plt.show()
 
# 计算并生成PR值
prValue = netx.pagerank(diGraph, max_iter=500, alpha=0.85)  # 生成的对象是一个字典类型
 
# 对PR值进行排序
prValue_list = list(prValue.items())  # 利用items（视图元组，不是实际元组）将字典转为元组，再用list将元组转为列表（可迭代访问对象）
 
# 使用 sorted() 函数对 prValue_list 进行排序，按照值（即 PageRank 值）从大到小排序
sorted_prValue = sorted(prValue_list, key=lambda x: x[1], reverse=True)
 
print(sorted_prValue)
 

import networkx as nx
import matplotlib.pyplot as plt
 
def get_init_pr(dg):
    """
    获得每个节点的初始PR值
    :param dg: 有向图
    """
    nodes_num = dg.number_of_nodes()
    for node in dg.nodes:
        pr = 1 / nodes_num
        dg.add_nodes_from([node], pr=pr)
 
 
def create_network():
    """
    创建有向图
    :return dg: 有向图
    """
    dg = nx.DiGraph()  # 创建有向图
    dg.add_nodes_from(['0', '1', '2', '3', '4'])  # 添加节点
    dg.add_edges_from([('1', '0'), ('2', '1'), ('3', '4'), ('4', '1'), ('3', '1')])  # 添加边
 
    get_init_pr(dg)
 
    return dg
 
 
def draw_network(dg):
    """
    可视化有向图
    :param dg: 有向图
    """
    fig, ax = plt.subplots()
    nx.draw(dg, ax=ax, with_labels=True)
    plt.show()
 

import numpy as np
 
def solve_ranking_leaked(adj_matrix):
    """
    解决Dead Ends问题（也称为排名泄露问题）
    :param adj_matrix: 邻接矩阵
    """
    col_num = np.size(adj_matrix, 1)  # 获得邻接矩阵列数
 
    row_num = 0  # 用来统计矩阵的行数（只有通过出度的问题检查才算）
    for row in adj_matrix:
        # 如果排名泄露，那么修改这个节点对每个节点都有出链
        if sum(row) == 0:  # 这个节点出度为0，表明它存在排名泄露问题
            for col in range(col_num):
                adj_matrix[row_num][col] = 1
        row_num += 1
 
 
def calc_out_degree_ratio(adj_matrix):
    """
    计算每个节点影响力传播的比率，即该节点有多大的概率把影响力传递给下一个节点
    公式：
        out_edge / n
        out_edge: 出边，即这个节点可以把影响力传递给下一个节点
        n: 这个节点共有多少个出度
    :param adj_matrix: 邻接矩阵
    """
    row_num = 0
    for row in adj_matrix:  # 每次都拿出一个行列表
        n = sum(row)  # 求该节点的所有出度
        col_num = 0
        for col in row:
            adj_matrix[row_num][col_num] = col / n  # out_edge / n
            col_num += 1
 
        row_num += 1
 
 
def create_matrix(dg):
    """
    通过有向图生成邻接矩阵
    :param dg: 有向图
    :return adj_matrix: 邻接矩阵
    """
    node_num = dg.number_of_nodes()
 
    adj_matrix = np.zeros((node_num, node_num))
 
    for edge in dg.edges:
        adj_matrix[int(edge[0])][int(edge[1])] = 1
 
    solve_ranking_leaked(adj_matrix)
    calc_out_degree_ratio(adj_matrix)
    # print(adj_matrix)
    return adj_matrix
 
 
def create_pr_vector(dg):
    """
    创建初始PR值的向量
    :param dg: 有向图
    :return pr_vec: 初始PR值向量
    """
    pr_list = []
    nodes = dg.nodes
 
    # 将初始PR值存入列表
    for node in nodes:
        pr_list.append(nodes[node]['pr'])
 
    pr_vec = np.array(pr_list)  # 将列表转换为ndarray对象
 
    return pr_vec

import numpy as np
import matplotlib.pyplot as plt
 
# 设置阻尼因子（跳转因子）防止Spider traps问题
alpha = 0.85  # 跳转因子
 
 
def draw(iter_list, pr_list):
    """
    绘制收敛图
    :param iter_list: 迭代次数列表
    :param pr_list: 每一个向量的值
    :return:
    """
    plt.plot(iter_list, pr_list)
    plt.show()
 
 
def pagerank(adj_matrix, pr_vec):
    """
    pagerank算法:
        V_{i+1} = alpha * V_i * adj + (1 - alpha) * E/ N
        （这个公式和上文介绍的略有不同，但是这两个是等价的）
         按照上文解决Spider Traps的方法，公式应该为：
                V_{i+1} = （alpha  * adj + ((1 - alpha) / N) * E）* V_i
    收敛条件:
        1. V_{i+1} == V_i
        2. 迭代次数200次
    就是说如果PR向量并没有发生改变，那么收敛结束，得到的PR值就是最终的PR值
    但是假设迭代次数过高后且未发生收敛，那么就会陷入死循环等，根据前人总结的经验，设置为迭代20次
    :param adj_matrix: 邻接矩阵
    :param pr_vec: 每个节点PR值的初始向量
    :return:
    """
    num_nodes = np.size(adj_matrix, 1)  # 获得矩阵列数(ie. 节点数)
    jump_value = (1 - alpha) / num_nodes  # 从其他页面跳转入所在页面的概率(标量)
    jump_vec = jump_value * np.ones(num_nodes)  # 向量化
 
    # iter_list = []
    # pr_list = []
 
    for n_iter in range(1, 201):
        pr_new = alpha * np.dot(pr_vec, adj_matrix) + jump_vec
 
        print("第{0}次迭代的PR值:{1}".format(n_iter, pr_new))
 
        # iter_list.append(n_iter)
        # pr_list.append(tuple(pr_new))
 
        if (pr_new == pr_vec).all():
            break
        # else:
        #     # 调试用
        #     test = pr_new - pr_vec
 
        pr_vec = pr_new
 
    # draw(iter_list, pr_list)
 
    print("迭代完成!")
    print("收敛值为:", pr_vec)