[Task] HINRank——一种面向复杂异质信息网络的中心度算法及其在开源软件研发领域的应用

[frank-zsy]

背景

基于网络的中心性算法在中心性评估中有较好的表现，而自 PageRank 提出以来，基于网络拓扑关系的协同中心性排序备受关注，并演化出众多的相关算法。如面向特定领域的 ArticleRank、MovieRank，针对性能优化的 LeaderRank，以及在 2018 年提出的扩展到二部图的BiRank 等，都是对 PageRank 算法的扩展。

但在实际业务场景中，简单的同质图或二部图并不能很好的反映真实世界的网络关系，真实的网络更多是异质信息网络。因此将 PageRank 类算法扩展到泛化异质信息网络，并使其可以支持先验知识，则可以更好的适应真实业务需求，为真实世界的价值评估提供更好的数据与理论支撑。

思路

摘要

介绍开源软件的统计评价方法及其局限性，并介绍基于图网络的中心性算法。

问题

更详细介绍开源软件研发领域的软件中心性评估的问题与意义，介绍开源软件研发领域的数据情况。

方法

• 异质图建模，生产（GitHub 活跃）、消费（生态项目依赖）、社交（GitHub 用户关注关系）网络，并对数据进行时序化处理。
• 对类 PageRank 算法进行数学描述，并对具有先验知识的泛化异质信息网络的迭代收敛性进行证明。
• 对 HINRank 算法的收敛速度进行说明。
• 对算法中 RankSink 问题的改进说明，引入 LeaderRank 中的背景节点方法，在特定节点子集中应用，不仅有利于收敛速度，而且具有相应的业务含义，如 GitHub 开发者生态影响力、特定语言领域影响力等。

实验

• 对GitHub 社交研发网络的基本特征进行说明，如一般的连通性、度分布、图半径等
• 将 HINRank 算法应用于上述构建的网络，对结果进行展示与说明，包括相较统计型指标的评估有效性、鲁棒性等。
• 背景节点，即生态影响力的比较证明，与 Node.js、NPM、Python 生态的发展变化与 TIOBE 历史排行的对比。

未来与规划

• 数学模型上的扩展，例如扩展到 L2 范数规范化等。
• 业务模型上的扩展，例如添加 GitLab、Gitee 数据等。

[will-ww]

我觉得挺好的，几个要点建议，需要：

• 把问题定义好，如价值评估问题、中心性评估等，以及它们之间的关系
• 数据集设计好：一定时间范围、项目范围、数据范围下的，异质图数据
• 实验设计好：特别是比较的对象与指标

[will-ww]

有啥进展不？我可以来帮忙讲故事~ @frank-zsy

[frank-zsy]

这个论文基本就是之前几篇博客的内容，没有什么新的东西，王老师看需不需要输出吧，我倒是觉得不着急

[will-ww]

理解你的不着急，我想如果有空你就搞下呗，应该需要加点实验，这样可以早点准备，也会有些启发的~

[frank-zsy]

这里理解王老师的意思是否是可以做一些图上的基本指标分析实验，例如连通性、度分布、图半径、集聚系数等，其实也非常合适，我感觉整个框架有两条相对独立的脉络，虽然最终是合在一起的，但其实展开时会相对独立和发散。

一条线索是关于开源数据的量化。这块可以从开源导致公开源代码数据激增，从而拉动的新兴学科，例如从 MSR (Mining source repository) 对代码仓库的挖掘，到 DSN (Developer social network) 开发者社交网络分析的兴起。DSN 有可以从最早的邮件交互，到 Mozilla 的 Bug report 平台交互，再到 GitHub 平台上的社交研发网络，也有一个演变的过程。而分析也从最早的网络基本指标的分析到网络结构分析、中心性分析等。所以本篇使用了更加复杂的建图方式，将社交研发、社交关注、仓库依赖关系等统一建图，并对子生态网络可以做一些基础指标的统计分析工作，并使用 HINRank 对多生态的融合异质信息网络进行统一的中心性分析。这是其中一条线索。

另一条线索则是网络中心性算法的演化。这块可以从中心性评估的算法体系说起，例如基于节点邻域信息的度中心度、半局部中心度、K-shell 分解、H 因子，到基于路径信息的接近中心度、介数中心度、离心中心度、Katz 中心度等，再到基于特征向量的如 PageRank、HITS 等。进而到 PageRank 算法的演化，如在不同领域的应用，如 ArticleRank、ObjectRank、MovieRank、PopRank 等，以及重要的几个优化算法，如 LeaderRank 对性能和鲁棒性的提升，BiRank 向二部图的扩展。而 HINRank 则是将 PageRank 扩展到泛化的异质信息网络中，并对收敛性进行了严格证明。并最终使用 DSN 网络信息对 HINRank 的表现进行说明，例如与度中心度、接近中心度等比较。

所以两条路径其实相对独立，虽然最终可以交汇在一起，但扩展的外延几乎完全无关，所以感觉有点难以驾驭，不知道王老师和同学们有没有什么好的建议，是否应该拆成两篇还是可以分章节来做？

另外，对于建图中的事件到边权的压缩，我个人想法在本次中不引入活跃度指标，而是直接使用事件数量作为权重，虽然活跃度指标更加合理，但可能较难解释。关于活跃度权重，个人想法是后续增补一个问卷调研研究来进行。

[will-ww]

这里理解王老师的意思是否是可以做一些图上的基本指标分析实验，例如连通性、度分布、图半径、集聚系数等，其实也非常合适，我感觉整个框架有两条相对独立的脉络，虽然最终是合在一起的，但其实展开时会相对独立和发散。

一条线索是关于开源数据的量化。这块可以从开源导致公开源代码数据激增，从而拉动的新兴学科，例如从 MSR (Mining source repository) 对代码仓库的挖掘，到 DSN (Developer social network) 开发者社交网络分析的兴起。DSN 有可以从最早的邮件交互，到 Mozilla 的 Bug report 平台交互，再到 GitHub 平台上的社交研发网络，也有一个演变的过程。而分析也从最早的网络基本指标的分析到网络结构分析、中心性分析等。所以本篇使用了更加复杂的建图方式，将社交研发、社交关注、仓库依赖关系等统一建图，并对子生态网络可以做一些基础指标的统计分析工作，并使用 HINRank 对多生态的融合异质信息网络进行统一的中心性分析。这是其中一条线索。

另一条线索则是网络中心性算法的演化。这块可以从中心性评估的算法体系说起，例如基于节点邻域信息的度中心度、半局部中心度、K-shell 分解、H 因子，到基于路径信息的接近中心度、介数中心度、离心中心度、Katz 中心度等，再到基于特征向量的如 PageRank、HITS 等。进而到 PageRank 算法的演化，如在不同领域的应用，如 ArticleRank、ObjectRank、MovieRank、PopRank 等，以及重要的几个优化算法，如 LeaderRank 对性能和鲁棒性的提升，BiRank 向二部图的扩展。而 HINRank 则是将 PageRank 扩展到泛化的异质信息网络中，并对收敛性进行了严格证明。并最终使用 DSN 网络信息对 HINRank 的表现进行说明，例如与度中心度、接近中心度等比较。

所以两条路径其实相对独立，虽然最终可以交汇在一起，但扩展的外延几乎完全无关，所以感觉有点难以驾驭，不知道王老师和同学们有没有什么好的建议，是否应该拆成两篇还是可以分章节来做？

另外，对于建图中的事件到边权的压缩，我个人想法在本次中不引入活跃度指标，而是直接使用事件数量作为权重，虽然活跃度指标更加合理，但可能较难解释。关于活跃度权重，个人想法是后续增补一个问卷调研研究来进行。

嗯，明白你的意思。我认为你书的对，是因该作为两个工作，提现到博士论文中也是两个章节的内容。

而且，量化和建图，应该是更加靠前的一个工作，然后有了图以后，甚至可以脱离业务，做一些更加深入的图分析，这种工作就更加理论化了，也是非常好的研究。最后，有回到应用场景中，支撑上层的一些应用。

[frank-zsy]

重拾一下论文实验的内容，目前希望进行的内容如下：

• 量化仅限于特征向量中心性评价，学术论文也常称为影响力
• 数据范围：
  • 仅选择 GitHub 上 2021 年全年项目语言为 TypeScript 和 JavaScript 的项目，约 300W 个
  • 使用 npm 制品库中 GitHub 托管项目的依赖关系数据
  • 使用 GitHub 在 2021 年底的开发者社交关系数据
• 使用上述数据构建 JavaScript/TypeScript 语言开源生态网络
• 定义 OpenRank 计算框架
  • PageRank 向具有初值有关、异质网络的扩展与数学证明
  • 异质网络 OpenRank（节点异质、边异质）的计算框架定义
  • OpenRank 计算框架在 Neo4j 上的实现
• OpenRank 的性质分析
  • 对于数据缺失的算法鲁棒性研究（随机抽离部分数据，观察结果）
  • 对于边权合并策略的敏感度研究（使用不同边权权重观察与统计结果的差异）
• OpenRank 在 JavaScript/TypeScript 开源生态数据中的应用
• OpenRank 的算法效果评价
  • 使用榜单编辑距离评判，寻找相关 2021 年项目排名列表，如 GitHub Trending 等，并和纯协作网络结果进行对比

[bifenglin]

重拾一下论文实验的内容，目前希望进行的内容如下：

• 量化仅限于特征向量中心性评价，学术论文也常称为影响力

• 数据范围：

  • 仅选择 GitHub 上 2021 年全年项目语言为 TypeScript 和 JavaScript 的项目，约 300W 个
  • 使用 npm 制品库中 GitHub 托管项目的依赖关系数据
  • 使用 GitHub 在 2021 年底的开发者社交关系数据

• 使用上述数据构建 JavaScript/TypeScript 语言开源生态网络

• 定义 OpenRank 计算框架

  • PageRank 向具有初值有关、异质网络的扩展与数学证明
  • 异质网络 OpenRank（节点异质、边异质）的计算框架定义
  • OpenRank 计算框架在 Neo4j 上的实现

• OpenRank 的性质分析

  • 对于数据缺失的算法鲁棒性研究（随机抽离部分数据，观察结果）
  • 对于边权合并策略的敏感度研究（使用不同边权权重观察与统计结果的差异）

• OpenRank 在 JavaScript/TypeScript 开源生态数据中的应用

• OpenRank 的算法效果评价

  • 使用榜单编辑距离评判，寻找相关 2021 年项目排名列表，如 GitHub Trending 等，并和纯协作网络结果进行对比

使用异质图进行openrank实验么？那么排名出来的结果对不同类别的对象（仓库、人）单独排名，然后针对repo与Github Trending的排名进行对比评价算法效果？

[frank-zsy]

使用异质图进行openrank实验么？那么排名出来的结果对不同类别的对象（仓库、人）单独排名，然后针对repo与Github Trending的排名进行对比评价算法效果？

是这样的想法，除了 GitHub Trending 外，应该还会再找一些其他的榜单数据来做对比。

[frank-zsy]

研究相关内容持续更新文档：https://www.yuque.com/docs/share/cd343b65-a9b2-42df-9853-ce15fe1a5cfa?# 《NPM 开源生态网络分析》

[will-ww]

昨天的报告，还是非常有启发和收获的。Frank 不仅用供应链数据，讲了真·异质信息网络，以及上面的OpenRank模型，还做了些论文分析与初步推到，从论文角度，已经可以写出很不错的撑过了。

另外还在后面做了未来工作的设想，特别是将影响力值推广到影响力向量，不仅能在数学上引出新的问题（不确定是否有人研究过），同时在实践上是极具意义的，one model fits all，非常优雅~

[frank-zsy]

目前关于在数学层面的创新，我个人感觉是有的。因为经典的 PageRank 是无法引入节点固有属性的，包括之后的各种改进都有类似的性质，所以这些算法的在数学上的收敛性是依赖于随机过程的佩龙一弗罗宾尼斯定理。而 OpenRank 使用了随机矩阵的谱半径性质，但收敛性则依赖于转移矩阵的谱半径和矩阵范数的关系，这种方式是目前没有看到过的。所以这个创新说大也不大，但是确实跳出了之前的套路，这也是为什么 OpenRank 对图的强连通性没有要求。

而影响力向量则是另外一个维度，目前我基本可以确定没有类似的工作，因为我使用multi dimension pagerank，vector pagerank，tensor pagerank 等，都没有看到相关的论文。我的猜测是在机器学习兴起后，PageRank 这种迭代计算的算法已经不受学术界的看重了，所以近些年图机器学习是更热的领域，类似 PageRank 的随机游走采样的图特征采样等方法更加容易出成果，而这种方式对于收敛性并没有要求，只要采样到特征即可做下游任务了。

而后续的工作，除了推广到高维外，还有是直接使用指定参数说明效果，还是使用已有榜单学习参数的问题，我个人的看法是：

• 学习参数的方式更加好出论文，但就像上面所说，其实学习参数就不需要 OpenRank 了，可以直接采用图机器学习的方式来做，对构造的图直接采样特征向量，然后根据榜单相关系数等来构造损失函数，即可学习到一个参数集，再用其他的榜单数据来做验证即可，这是非常符合现在套路的论文方法。
• 但指定参数更符合我个人对于长期落地的判断，因为参数学习的本质是用一个绝对正确的结果去反向推导结果与原始因素之间的因果关系（这也是为什么图像、音频、文本等更合适这类场景）。但在现实世界中，各种榜单本身就是人为因素过重，无论是因为样本偏好的偏差、项目的宣传力度差别或其他的偶然性因素等，所以我希望指定参数本身的想法就是：
  • 1、通过其他方式构造共识参数，之后使用特定的数据加上共识的参数来生成榜单，这个榜单是不具有额外的人为操纵的，如果大家觉得榜单有问题，有两种方式来修正：①更新共识参数集。②新增额外的数据。
  • 2、这种方式的好处是可归因的，就类似我给 InfoQ 介绍时，可以回溯到每个项目的影响力分别来自哪些人，这些人的影响力又来自哪些项目等等，因此本身是具有后续行为上的指导意义的，而黑盒的参数模型虽然可以很好的拟合选择的已有榜单，但却无法对改进提出更多的建设性建议。

所以从出论文投稿的角度来说，我觉得前者是一个好的方式，但从做正确的事的角度出发，我觉得应该是后者的方式。

[frank-zsy]

所以我觉得如果以后者的方式来做，可能可以发布一个调查问卷，收集大家对于不同类型的数据对于影响力影响权重的看法，并汇总得到一个共识参数集，之后根据这个参数集计算结果再和已有的榜单对比做案例说明，应该会是一个好的方式，比起直接指定参数要更加 solid 一些。

[frank-zsy]

目前计划使用问卷方式进行权重调研，在当前图中，已知邮箱地址的用户数为 58,667 个，使用 2021 年活跃时间次数排序取 Top 2W 用户发送调研问卷，按照小雅归档项目研究的问卷回收率 5%，预计可回收问卷约 1000 份。

问卷地址：http://survey.frankzhao.cn/vm/mRoStuy.aspx?sojumpparm=xlab 大家也可以帮忙 review 一下，暂时不要提交。

问卷后的参数是定制的，给每个开发者发送的链接均注入了其对应的 GitHub login 用于追踪填写情况，且对于每个 login 仅可填写一次问卷，回收后的问卷需匹配 login 信息，若出现 login 不匹配则视为无效数据。

后续采用统计方法对问卷结果进行处理，剔除异常离群样本，然后按用户影响力（初始为活跃事件次数）进行加权平均后计算 OpenRank 影响力，然后再按得到的影响力重新计算权重，修正后重新计算 OpenRank 直至 OpenRank 与权重集收敛。

[frank-zsy]

另，上次提到 OpenRank 的实现分为三步：

• 按需抽取原始数据
• 基于抽取数据进行降维构造
• 对构造的图进行 OpenRank 计算

之前在 Neo4j 插件中实现了最后一步，前两步在分析代码中实现，如果要分为两步实现需要升级插件到支持 GDS 2.1 版本，原始版本为 1.7.3。

故 1.7.3 版本打 tag 并发布了一个 release，master 分支已升级到 GDS 2.1.6 版本，后续可进一步开发实现第二步，第一步属于业务侧需求，不是通用需求，需在调用 OpenRank 前自行抽取。

详情见 https://github.com/X-lab2017/openrank-neo4j-gds

[frank-zsy]

十一期间基本完成了问卷发放和回收工作，发送定向邮件的坑挺多，没有完成 2W 用户的发放。

目前共完成约 5000 个用户的问卷发放，回收问卷 175 份，来源分布六大洲 39 个国家，离散性较好。其中中美德法四国人数最多。

具体分布情况见这里。

邮件进行问卷调研的具体坑包括：

• edu.cn 的邮箱每日发送上限约 200 封/天，但具体发送受到墙的影响，gmail 等邮箱无法送达，但 GitHub 公开邮箱中 gmail 用户占比极高，因此直接使用 edu 邮箱发送的送达率非常低
• 后来使用 126、163 等个人邮箱发送，送达较稳定，但依然有每日发送数量上限，约 300 封/天
• 企业服务的个人邮箱一般有反垃圾功能，大量发送可能会被识别为垃圾邮件，被服务器直接拒绝发送，需要少量修改标题和内容后可以重新发送，所以可能需要准备至少两套内容以便交替使用
• 个人邮箱的回收率远不如学校邮箱，edu.cn 邮箱的可信度较高，有多位受访者反馈为什么没有使用 edu 邮箱，也有人直接发信到 edu 邮箱请求确认
• 不知是否收到俄乌战争影响，.ru 类邮箱的退信比例极高，俄境内邮箱服务不稳定，也未收到来自俄罗斯的问卷反馈