属性化有向二部网络模体普查、显著性检验与比较的Python工具包attrimotif

《SoftwareX》：attrimotif: A Python package for motif census, significance testing, and comparison in attributed directed bipartite networks

　　

： 对买家-品牌、游客-目的地或用户-物品等有向二部网络（directed bipartite network）的经验研究通常会依次提出四个问题：哪些局部模体（motif）出现、这些模体是否超出仅由度序列（degree sequence）所蕴含的水平、分类节点类型所承载的结构是否存在差异、以及该结构是否随条件或时期而变化。如今回答这些问题需要将模体计数、度保持随机化（degree-preserving randomization）和图比较等独立工具拼接在一起。attrimotif是一个小巧、采用宽松许可、可通过pip安装的Python包，它将上述步骤整合为一个可复现的工作流程，专门用于属性化有向二部网络。该包提供规模为3和规模为4的二部模体普查、节点类别分层（node-category stratification），以及一个属性算子（attribute operator），用于报告数值型边属性在各模体类别上的分布；它还提供度保持零模型（degree-preserving null），并附带一个显式的零模型可识别性诊断（null-identifiability diagnostic），用于标记零模型无法评估的统计量；此外还提供面板级Portrait Divergence及其置换检验（permutation test）。该包不声称提出新算法，其贡献在于集成、可识别性诊断，以及一个依赖精简的实现，其中内置的Portrait Divergence已与netrd交叉验证，测试套件达到99%的语句覆盖率。该包发布在PyPI上并归档于Zenodo，在Linux、Windows和macOS上通过持续集成（continuous integration）运行检查。所有附带数据均为合成数据或公开数据。

论文解读文章：

一、研究背景与问题

网络模体（network motif），即频繁出现的小规模子图，是分析复杂网络局部结构的标准视角。在许多应用场景中，网络天然具有有向（directed）和二部（bipartite）结构：买家指向品牌、游客指向目的地、参与者指向讨论主题、用户指向物品。针对这类属性化有向二部网络，实证研究通常需要依次回答四个问题：第一，哪些局部模体出现；第二，这些模体的出现是否显著超出仅由度序列所决定的数量；第三，当节点携带类别属性（如品牌类别、目的地类型）时，模体结构是否因类型而异；第四，该结构是否在不同时期、面板或实验条件下发生变化。

然而，当前回答这些问题需要拼接多个独立工具：有向模体计数可由NetworkX和graph-tool提供，但被广泛引用的独立模体查找工具已不再维护，而ORCA等轨道计数器本质上仅适用于无向图；度保持随机化来自NetworkX的交换操作、graph-tool的random_rewire以及专门的xswap包，二部情形下有Curveball算法和BiRewire的R实现；Portrait Divergence这一全尺度图比较方法在netrd距离库中提供；带类型或着色的模体计数虽有清晰的方法论文献，但据研究人员所知，尚无通用Python包执行属性化二部模体普查并集成显著性检验。netrd比较图但不计数模体，xswap随机化但不比较，DotMotif每次只匹配一个属性约束的模体查询而非普查，着色三元组普查则是仅限于三元组的R例程。另一条研究路线通过低秩分解读取属性化图，但返回的是软节点分组而非具名子图的计数，无法提供本文所用的度保持模体计数零模型。

attrimotif正是针对这一空白而开发。该包限定于固定规模3和规模4模板上的属性化有向二部模体，这一限制的代价在结论部分说明，同时使包保持小巧、MIT宽松许可、依赖精简（仅numpy、scipy、networkx，netrd为可选）。其贡献有三：将普查、分层、零模型显著性和面板比较整合为一个工作流程；提供属性算子，读取数值边属性在各模体类别上的分布而非仅计数；以及显式的零模型可识别性诊断，报告度保持零模型无法评估哪些请求的统计量，其中四个精确统计量有证明，其余为观测所得。

二、研究内容与结论

attrimotif组织为四个分析模块和一个datasets辅助模块，基于一个统一的数据容器。BipartiteDiGraph容器持有有向弧（agent到object）、可选的agent和object类别类型，以及每条弧上的一个数值边属性。四个分析模块分别为：census（模体计数，并透传NetworkX的三元组普查用于单部情形）、typed（分层和属性算子Φ）、nulls（交换操作、显著性检验、可识别性诊断和多重性校正）以及compare（Portrait Divergence，内置或经netrd，以及面板置换检验）。第五个模块datasets提供示例所用的确定性生成器。所有公开入口点均从顶层命名空间导出，附带类型提示和说明输入、输出及局限的文档字符串。测试套件对包模块达到99%的语句覆盖率。

可复现性依赖于三项被检验而非仅声明的事项。高层工作流各自从显式整数种子构建局部numpy.random.default_rng，包不启动工作线程或进程，因此带种子的运行是确定性的并受测试覆盖；用户并行化重复实验时必须用SeedSequence.spawn派生流，因为跨工作线程复用同一种子会产生相同而非独立的重复。内置生成器由测试固定，契约刻意分为两部分：弧序列和节点类型以SHA-256在所有支持的平台上断言固定，这是推断所依赖的一半，因为交换链按索引抽取边，列表置换会改变固定种子下的零模型；边属性从rng.normal抽取，持续集成显示这些值在不同构建间并非逐位一致，macOS上与Linux和Windows值在小数点后第九位以下不同，而弧序列完全一致，因此固定到小数点后九位，既能捕捉真实变化又不至于捕捉末位噪声。读者在其他环境重跑时，零模型结果应完全一致，属性算子Φ摘要应达到该精度的一致。最后，requirements-lock.txt记录参考环境的精确解析版本；pyproject.toml刻意仅保留下限约束，因为库不应固定其使用者的传递依赖图。

三、关键技术方法

研究人员主要使用了以下关键技术方法：其一，模体普查算法，基于二部邻接矩阵B，扇出（fan-out）和扇入（fan-in）计数是度序列的二项式系数之和，规模4扇计数由规模3扇计数乘以3得到，重叠（2×2双团）计数通过集合交集计算，构建去重邻接集的时间复杂度为O(|E|)，空间复杂度为O(|E|+n_A+n_O)；其二，度保持零模型，采用交换链（swap chain）进行度保持随机化，并配套显著性检验、多重性校正和零模型可识别性诊断；其三，属性算子Φ，读取数值边属性在各模体类别上的分布；其四，Portrait Divergence图比较方法，内置实现与netrd交叉验证，用于面板级比较并配合置换检验。

四、研究结果

模体普查。对于二部agent-object图，普查返回规模3扇出和扇入计数、规模4扇计数以及规模4重叠（2×2双团）计数，全部在简单二部图上计算。扇计数是度序列的二项式系数之和，重叠计数通过集合交集计算，构建去重邻接集的时间复杂度为O(|E|)，空间复杂度为O(|E|+n_A+n_O)。

属性分层与属性算子。typed模块提供按节点类别分层的能力，以及属性算子Φ，该算子报告数值边属性在各模体类别上的分布，而非仅计数。这一设计使研究者能够考察边属性（如购买金额、访问频率）在不同模体结构中的分布差异。

度保持零模型与可识别性诊断。nulls模块提供交换操作进行度保持随机化，配套显著性检验和多重性校正。关键的创新是可识别性诊断：它显式报告度保持零模型无法评估哪些统计量，其中四个精确统计量有证明，其余为观测所得。这一诊断防止了常见的推断错误，即对零模型无法评估的统计量进行显著性解读。

面板级Portrait Divergence比较。compare模块提供Portrait Divergence，内置实现或经netrd调用，并配套面板置换检验。该方法用于回答第四个问题：图结构是否在不同面板、时期或实验条件间发生变化。内置的Portrait Divergence已与netrd交叉验证。

五、讨论与结论

讨论部分指出，attrimotif的贡献不在于提出新算法，而在于将普查、分层、零模型显著性和面板比较整合为一个可复现的工作流程，并提供显式的零模型可识别性诊断。该包限定于固定规模3和规模4的二部模体模板，这一限制的成本在结论中说明，但使包保持小巧、MIT许可、依赖精简。所有附带数据均为合成或公开数据，不捆绑或要求专有数据。

结论部分可概括为：attrimotif是一个小巧、宽松许可、可通过pip安装的Python包，它将属性化有向二部网络的模体普查、节点类别分层、度保持零模型显著性检验和面板级Portrait Divergence比较整合为一个可复现的工作流程。其贡献在于集成、可识别性诊断和依赖精简的实现，内置Portrait Divergence与netrd交叉验证，测试套件达到99%语句覆盖率，在Linux、Windows和macOS上通过持续集成，发布于PyPI并归档于Zenodo。