排序方法（Ranking）：适用于任何排名的场景，如网络节点重要性排名、竞赛排名等.

1、适用场景

  网络节点重要性排名、人力资源干部作训排名、小组竞赛打分排名等任何输出为排名结果的系统。下面将以小组竞赛为例介绍常见的排序方法计算过程。

  例1：有7个评委对4个候选人进行强制排名，最后根据评委的排名数据给出4位候选人的综合排名结果7位评委的详细评价数据见表1：

表1

被评价人/评价人	L1	L2	L3	L4	L5	L6	L7
E1	3	1	3	4	2	2	2
E2	1	3	4	3	1	4	3
E3	2	2	2	2	3	3	1
E4	4	4	1	1	4	1	4

2、常见排序方法

  常见的排名方法有“均值法”和“top计数法”等：“均值法”是对候选人的排名（分数）求平均，最后根据平均值的大小进行排序；而“top计数法”是提前设定一个阈值如前2名（分数>80），然后统计大于阈值的评价次数，最后根据次数的大小进行排序。

注：任何方法都会基于一定的假设，所以没有哪种方法是“普适”的，所以任何方法的结果都是可解释的。

均值法

  用均值法求解上述例1的候选人综合排名结果，如下表2所示：

表2

被评价人/结果	排名均值	排名
E1	2.43	2
E2	2.71	3
E3	2.14	1
E4	2.71	3

top计数法

  用均值法求解上述例1的候选人综合排名结果，如下表3所示：

表3

被评价人/结果	top1计数	排名
E1	1	3
E2	2	2
E3	1	3
E4	3	1

由结果可知，“均值法”和“top计数法”都存在相同排名情况。

 尝试解释相同排名情况：由表1，可知被评价人的所有排名数据以及所有评价人给出的排名序列数据，之前的“均值法”和“top计数法”都只用到了被评价人的排名数据，并没有利用相互排名差，这有时候是“不公平”的，并且统计的颗粒度不够细，所以偶尔会导致相同排名结果。

注：若不计较结果的颗粒度，这些结果都是基于各自的假设得出的结好果（均值法基于平均最优即为最优，top计数法基于top计数多为最优），但若要求结果不允许有重复排名的情况，那么这两种方法均不达标。当然，在许多情况下，这些方法都是很好的排序方法。

  那么，是否可以找到一种方法使得大部分情况下不存在结果重复的情况呢？——>SpringRank*：基于弹性势能+针对有向带权重网络>>>求解网络中各节点重要性的弹性势能排序算法。

SpringRank

  SpringRank（SR）针对的场景是有向带权重网络，损失函数是网络中节点间的弹性势能，SR设各节点的重要性因子为未知数，然后利用重要性因子的差值作为形变长度来计算弹性势能，最后最小化所有节点的弹性势能之和，此时整个网络系统对应的能量最低，所以系统最稳定，即得到了节点重要性的最优解。这里对SR不做更详细的介绍，若感兴趣的可以查看原文，在本文最后有引用，需要的自取。

  排序场景都是可以转化为网络场景的，因为排序对象之间是相互关联的，所以可以将排序对象看作是相互连通的网络，这样就可以用SR方法来进行Ranking，下面本文就例1介绍如何应用SR模型进行Ranking，SR模型的求解步骤如下：

• 首先，我们假设被评价人是一些节点，并设他们的排名为节点的重要性；
• 接着，每个评价人都会给出一个被评价人的排名序列，则被评价人间的相互排名可以映射为节点间的连线，连线的权重可以是相互排名的高低次数（频数）或排名差（距离），至此排名场景即转化为了排名网络场景；
• 然后，两两节点间的连线已经连好，下一步需要构造相互排序矩阵，该矩阵记录着两两节点的相对排名高低次数（频数）或排名差（距离）；
• 最后，利用SR模型构造损失函数，并通过求解总能量极小值获得全局最优解——所有被评价人的重要性因子，即被评价人的Ranking结果。

  本文利用python编写了SR模型，带入固定格式的输入数据（表1）即可直接获得Ranking结果，源代码参见下文。例1的结果如下表4所示：

表4 频数SR

被评价人/结果	重要性因子	排名
E1	0.071429	2
E2	-0.214286	3
E3	0.357143	1
E4	-0.214286	3

表5 距离SR

被评价人/结果	重要性因子	排名
E1	0.029605	3
E2	0.037100	2
E3	0.397610	1
E4	-0.330904	4

  从上面的Ranking结果可知，基于频数的SR结果与均值法结果一致，说明SR方法若只利用了相互排名的高低次数，则Ranking结果与均值法一致；基于距离的SR结果不存在重复排名情况，说明SR方法在利用相互排名的排名差时，Ranking结果颗粒度更细，所以基于细颗粒度，基于距离的SR模型更优。

3、总结

距离SR方法利用了相互排名差数据，相均值法、top计数法和频数SR方法更充分的利用了数据中的信息，所以结果颗粒度更细，在多数场景下距离SR方法结果更优。

4、SR源代码

import pandas as pd
import numpy as np

# 线性方程组求解损失函数极小值
# 输入：排名原始数据DataFrame，格式参见表1
# 输出：各节点的重要性因子
def Linear_Algebra(df):
    # 计算每个对象的相对排名出、入度
    Out, In = [], []
    # 遍历对象添加其出入度
    for i in range(len(df)):
        Out_i = df.iloc[:,i].sum() # 计算对象i的出度
        Out.append(Out_i)
        In_i = df.iloc[i,:].sum()  # 计算对象i的入度
        In.append(In_i)
    # 计算稀疏矩阵A_0和常数向量b
    # 将DataFrame格式转化为array格式，np科学计算更方便
    A = pd.DataFrame(df, dtype=np.float).values
    # 系数矩阵A_0由两部分组成，下一步是先添加Part1
    A_0 = A + np.transpose(A)
    # 初始化b
    b = np.ones(len(A))
    # 计算b和添加A_0的Part2
    for i in range(len(df)):
        A_0[i, i] = Out[i] + In[i] - A_0[i, i]
        b[i] = Out[i] - In[i]
    # 求A_0伪逆：因为系数矩阵A_0有可能是奇异阵
    A_1 = np.linalg.pinv(A_0)
    # 求解方程组
    s = np.dot(A_1, b)
    return s

# 读取排名数据
df = df.pd.read_excel('.../排名数据.xlsx')
# 设置被评价人为索引，其中“被评价人/评价人”填自己储存的第一列的表头即可
df_index = df.set_index('被评价人/评价人')
# 创建新DataFrame储存结果数据
df_matrix_nums = pd.DataFrame(columns=df_index.index)                  # 储存频数SR结果数据
for index in df_index.index:
    df_matrix_nums.loc[index] = 0
df_matrix_dis = df_matrix_nums                                         # 储存距离SR结果数据 

# 构造相互排名矩阵
# 遍历所有评价人的打分序列
for col in df_index.columns:
    name_list = df_index.sort_values(col).index.tolist()               # 给打分序列按照升序排序
    # 根据排序结果可以找到被评价人及其前后的竞争对手——>两两匹配可定位到相互排名网络中位置，记录频数或距离
    for i in range(df.shape[0]):
        for j in range(i+1, df.shape[0]):
            df_matrix_nums.loc[name_list[j], name_list[i]] += 1        # 填充频数相互排名矩阵
            df_matrix_dis.loc[name_list[j], name_list[i]]  += j-i      # 填充距离相互排名矩阵

# 基于相互排名网络，利用Linear_Algebra方法计算SR结果
# 频数SR
s_nums = Linear_Algebra(df_matrix_nums)                                # 获得频数SR结果
df_matrix_nums['weight'] = s2                                          # s2为获得的节点重要性因子
df_matrix_nums = df_matrix_nums.sort_values('weight', ascending=False) # 根据s2进行排序
df_matrix_nums['Ranking'] = range(1, len(df_matrix_nums)+1)            # 根据排序结果进行Ranking
# 距离SR
s_dis = Linear_Algebra(df_matrix_dis)                                  # 获得距离SR结果
df_matrix_dis['weight'] = s2                                           # s2为获得的节点重要性因子
df_matrix_dis = df_matrix_dis.sort_values('weight', ascending=False)   # 根据s2进行排序
df_matrix_dis['Ranking'] = range(1, len(df_matrix_dis)+1)              # 根据排序结果进行Ranking
'''
df_matrix_nums:频数SR结果
df_matrix_dis :距离SR结果
'''

有问题的可以留言交流，谢谢！

• Caterina De Bacco, Daniel B. Larremore, Cristopher Moore. A physical model for efficient ranking in networks. Science Advances, 2018; 4 (7): eaar8260 DOI: 10.1126/sciadv.aar8260