[Presentation] OpenRank 精讲 - 2023.10.30

[frank-zsy]

Title

OpenRank 精讲

Link

https://blog.frankzhao.cn/static/OpenRank_in_detail.pptx

Author and affiliation

Frank

Selecting Reason

本次将详细分享 OpenRank 相关的数学理论、工程实践及开源应用相关的内容

[will-ww]

补充几个背景资料：

• 活跃度指标：http://blog.frankzhao.cn/how_to_measure_open_source_1/
• 影响力指标：http://blog.frankzhao.cn/how_to_measure_open_source_2/
• 价值流网络：http://blog.frankzhao.cn/how_to_measure_open_source_3/

[will-ww]

补充本月 26 号在 CNCC 大会分论坛上做的一个报告：开源人才发展体系与评价方法 .pdf

[will-ww]

视频已发布：

• OpenRank精讲_上
• OpenRank精讲_下

[huangfan0]

关于评价openrank有效性的想法：使用影响力最大化中的传播算法 影响力最大化是选择一个初始k个活跃节点，其余节点为非活跃节点，然后按一定的传播算法，活跃节点会以一定的概率或规则沿着边影响非活跃节点。如此迭代直至没有新的活跃节点出现。

影响力最大化是要确定找出这个传播算法，使得最后期望的活跃节点的数量是最多的，即影响规模是最大的。在这个研究领域中重点在于怎么建模传播过程，并且理论已经证明这是一个NP难的问题。

而在我们的场景，评价openrank算法的有效性上，不需要纠结那个传播算法好，是可以直接使用不同的传播过程算法，看最后活跃节点的数量规模。因为我们通过openrank值已经找到前100/1000/10000个影响力最大的初始节点，然后套用现在已有的成熟的传播算法，就可以将来比较openrank与其他算法（度中心度算法，PageRank）的好坏，从而验证其有效性。比较的过程是分别将openrank，PageRank的排名前比如100个节点分别作为初始活跃节点，然后在图上使用传播算法，看迭代结束后活跃节点的数量（即规模），如果openrank影响的活跃节点比PageRank最后的活跃节点多，则证明是有效的。除了规模，也可以对比openrank与PageRank迭代收敛的速度，收敛越快的效果越好。

我目前收集到的常用的传播算法模型有下面三个：

1.独立级联模型 （IC)

对每条边引入一个概率值，非活跃节点对连接有边的节点以一定的概率去激活邻居节点，在t时刻的活跃用户以一定的概率去激活在t-1时刻的非活跃节点。只有一次机会，且激活状态和非激活状态在传播一次后不可改变，当没有新的非激活节点变为激活节点时，迭代结束。

2.线性阈值模型(LT)

当足够数量的邻居节点的影响力权重求和的结果超过一个阈值时，该节点就会被激活

与独立级联不同的是，每个被激活都节点都有多次机会去激活自己尚未被激活的邻居节点。

1. 初始化种子节点，然后激活种子节点作为初始激活集合。
2. 寻找尚未被激活且有激活节点作为邻居节点的节点，放入备选节点集合。
3. 依次对备选节点集合中的节点计算激活概率，然后尝试激活，被激活的节点将被放进激活集合。
4. 重复23步骤，直至没有可激活的节点。

3.非渐进模型-传染病模型 上面两个都是渐进模型，另外一类非渐进模型最大的特点是已经激活的节点可以取消激活。（SIR，SIS）在传染病模型中，已经感染的节点就是活跃节点，没有感染的节点就是非活跃节点，但这个还比较复杂，还有易感人群，已经治愈的人群。已经治愈的人群可能还会再次感染。

参考文献 http://read.nlc.cn/yuewen/detail?id=227589 https://ieeexplore.ieee.org/document/8295265 感谢张翔宇学长的指导，欢迎大家补充~

[frank-zsy]

感谢黄帆同学的介绍，看上去确实是可行的。如果要实验的话感觉可以先抛开 NPM 生态的数据，仅从引入初值的角度来看 OpenRank 带来的变化，与传统的度中心度和 PageRank 比较影响力最大化的效果。

基本思路是直接面向当前全域 OpenRank 的计算逻辑来看，依然使用开发者-仓库的协作网络来进行分析，按照同样的方式进行构图，OpenRank 计算时所有节点按照当前策略继承上个月的结果为该节点的初值，而 PageRank 则作为一个初值无关的算法仅计算当月的快照结果，所有节点的初值一样，那么计算得到的结果应该会有所不同。

然后再用 IC 或 LT 的方法对结果进行影响力最大化的验证，这样的好处是一方面是对当前全域 OpenRank 的直接验证，无需引入其他的额外数据和参数，构造的基础比较扎实；另一方面也是对带有初值的有效性有更好的验证。