符号网络中的路由策略

Routing Strategies on Signed Networks

摘要: 符号网络是一类具有符号属性的复杂网络，近年来逐渐成为研究热点，但针对符号网络中路由与传输问题的研究尚未涉及。本文构建了基础符号网络，将改进的路由策略应用于该网络，系统研究其路由机制与流量传输特性。人工构建的符号网络可通过无标度网络与随机网络组合连接形成，本文采用同配连接和异配连接两种连接方式，生成不同属性的网络模型。随后，通过调整网络的平均负度，深入探究同配系数、网络平均路径长度与数据包生成率之间的内在关联。最后，在真实符号网络上进行仿真实验，验证了所提路由策略及结论的有效性。

Abstract: Signed network is a kind of complex network with signed attributes. It has gradually become a hot topic in recent years, but the research on routing and transmission on signed network has not been involved yet. In this paper, a basic signed network is constructed, and the improved routing strategy is applied to research the routing strategy and traffic transmission on the signed network. The artificially built signed network can be connected by a combination of scale-free networks and random networks. We use two connection methods, the assortative connection and the disassortative connection, to obtain networks of different properties. Then, we adjusted the average negative degree of the network to study the relationship among the assortativity coefficient, the average path length of the network and the packet generation rate. Finally, we performed simulations on the real signed network to verify the validity of our routing strategy and conclusions.

1. 引言

近年来，复杂网络研究受到学术界的广泛关注。基于各类复杂网络的特性及其与现实场景的紧密联系，诸多待深入探索的科学问题逐步显现。在现实交通网络、计算机网络、通信网络信息传输等背景下，复杂网络中的路由策略与拥塞控制已成为不容忽视的研究热点。

符号网络作为一类具有符号属性的复杂网络，近年逐渐成为研究焦点。本文所构建的符号网络模型，专门针对“两类对立社团结构”的场景设计，网络节点可明确划分为正、负两个对立子群体，子群体内部(同类节点)以正边连接，代表协同、友好或合作关系；子群体之间(异类节点)以负边连接，代表对抗、竞争或对立关系。该模型可应用于：政治领域中不同立场的阵营网络、商业场景中竞争企业与合作企业群体以及社交网络中对立观点的用户社群。现有符号网络模型多关注多社团、动态符号边或无明确对立结构的网络，研究重点集中于拓扑演化、社区检测等；而本文模型通过简化节点类别与边符号的对应关系，聚焦“对立社团间的路由传输问题”，能更深入揭示负边对路由效率的抑制机制，为后续复杂符号网络的路由研究提供基础范式。目前，符号网络的研究主要集中在三个方向：符号网络的静态拓扑特性、社区划分及相关研究、符号网络的演化动力学研究，以及符号网络在实际场景中的应用研究。因此，众多学者致力于探索符号网络中尚未被发掘或深入研究的领域。

已有学者针对复杂网络的路由策略优化开展大量研究，提出多种有效路由算法，如有效路由(ER) [1]、全局动态路由(GDR) [2]、增量路由(IR) [3]、概率路由[4]等。此外，学者们在复杂网络的其他研究领域也取得了丰富成果[5]-[10]。然而，目前尚无学者涉及符号网络中路由策略的研究。

本文聚焦于基础路由策略在符号网络中的可行性，旨在开辟这一新的研究方向。研究目标是通过科学的定义与路由设计，在符号网络上建立流量模型，从而从网络科学视角构建符号网络拥塞分析框架。该框架可推广至其他类型符号网络的流量研究，更重要的是，有望为符号网络研究开辟新路径，使其不再局限于人工符号网络的建模与拓扑分析。具体而言，本文通过仿真实验研究流量模型的基本特性与路由指标，选取真实网络进行仿真实验以验证路由策略与流量模型的可行性，最终完成研究并得出结论。

2. 基础模型与路由算法

2.1. 网络与流量模型

与传统的同质无标记网络相比，符号网络中的节点与边具有异质性。构建符号网络时，需对不同类型节点间的边进行分类处理。由于节点与边的异质性，符号网络中不同类型节点构成的子网络可能具有完全不同的网络结构，而这些子网络的不同拓扑结构会对整个网络的动态特性产生深远影响。本文选取具有代表性的Barabasi-Albert (BA)无标度网络模型[11]与Erdos-Renyi (ER)随机网络模型[12]作为基础网络模型，下文将介绍ER随机网络与BA无标度网络的构建过程。

设定ER模型的节点数量为N，任意两个节点间的连接概率为$p$ ，以此生成随机网络。为不失一般性，本文中设定$p=0.01$ 。BA无标度网络的构建始于$m_0$ 个全连接节点，每次向现有网络中新增一个具有$m\left(m<m_0\right)$ 条边的节点，并且每条新边的另一端节点按照以下概率选择：$p_i=\frac{k_i}{{{\displaystyle \sum }}_j{k}_j}$ 。其中，$k_i$ 和$k_j$ 分别为节点$i$ 和节点$j$ 的度。

本文将网络中的节点分为正节点与负节点两类：正节点与正节点、负节点与负节点为同类节点，定义同类节点间的连接为正边，其度为正值；反之，正节点与负节点为异类节点，异类节点间的连接定义为负边，其度为负值。图1展示了该网络的结构示例。

Figure 1. Signed network structure diagram (“+” indicates the positive edge, “−” indicates the negative edge.)

图1. 符号网络结构图(“+”表示正边，“−”表示负边)

在此基础上，引入负边的“负边抑制权重”($w$ )来描述同类与异类节点间负边对路由传输的抑制作用，定义如下：$w=B_l,l\in L$ 。其中，$L$ 为所有负边的集合，$B_l$ 为边$l$ 的介数。注意：边介数$B_l$ 是在网络的无权重拓扑上预先计算好的一次性静态值，后续的加权最短路径计算均基于此静态权重。

介数反映了对应边或节点在整个网络中的作用与影响力，边介数作为全局几何量，能量化边在网络最短路径中的“桥梁作用”，介数越大的负边，意味着越多最短路径需经过它，其对路由传输的抑制作用若不控制，更易引发全局拥堵，符合“重要负边需重点规避”的路由逻辑。

边$l$ 的介数定义为：

$B_l={\displaystyle \sum }_{s\ne t}\frac{{\sigma }_{st}\left(l\right)}{{\sigma }_{st}}$

其中，${\sigma }_{st}$ 为从节点$s$ 到节点$t$ 的最短路径总数，${\sigma }_{st}\left(l\right)$ 为从节点$s$ 到节点$t$ 且经过边$l$ 的最短路径数量。

介数是重要的全局几何量，具有较强的现实意义，因此$B_l$ 可用于衡量负边的重要性：$B_l$ 越大的负边，其抑制作用越强，对异类节点间的路由传输影响越显著。在计算节点间的路由路径时，正边权重设为1，经过负边时需考虑负边抑制权重$w$ 的大小，使路由尽可能选择$w$ 较小的负边，以降低抑制作用；但在计算路由路径长度时，需忽略$w$ ，仅计算实际路径长度。

两类子网络的连接方式包括同配连接(AC)和异配连接(DC)，本文对这两种连接方式的定义如下：

定义1

1) 构建两个子网络$p$ 和$q$ ，每个子网络均包含$n$ 个节点；

2) 分别对子网$p$ 和子网$q$ 中的节点按度排序；

3) 同配连接(AC)：将两个子网中的节点按正向顺序排列，连接索引相同的节点；

4) 异配连接(DC)：将子网$p$ (或$q$ )中的节点按反向顺序排列，子网$q$ (或$p$ )中的节点按正向顺序排列，连接索引相同的节点；

5) 在两个子网络中，可通过连接索引相近的节点增加边的数量。

将最终连接形成的网络记为$p-q$ 网络，其中$p,q\in \left\{SF, ER\right\}$ 。(SF代表无标度网络，ER代表随机网络。)同配连接(AC)指子网络节点按度排序后，连接度相同或相近的节点；异配连接(DC)指连接度差异较大的节点。通过上述方式得到的边均为负边，可通过控制负边的数量调整符号网络的平均负度。

流量模型基于特定网络结构构建，用于模拟真实网络中动态流量的传输过程。在该模型中，每个节点兼具主机与路由器功能，既能生成数据包，也能转发数据包。每个节点在每一步最多可向其直接邻居节点传递$C$ 个数据包(本文中设定$C=1$ )。在每个时间步内，网络生成$R$ 个数据包，源节点与目的节点随机选择，数据包按先进先出(FIFO)规则在各节点排队，到达目的节点的数据包将被立即移除。若两个节点间存在多条最小代价相同的路径，则随机选择其中一条路径。

网络容量可通过最大数据包生成率$R_c$ 衡量，当数据包生成率达到$R_c$ 时，网络流量发生从自由流到拥堵流的相变。$R_c$ 可通过序参量[13]表示为：$\eta \left(R\right)=\underset{t\to \infty }{\lim }\frac{C}{R}\frac{\langle \Delta W\rangle }{\Delta t}$ 。其中，$\Delta W=W\left(t+\Delta t\right)-W\left(t\right)$ ，$\langle \cdots \rangle$ 表示对宽度为$\Delta t$ 的时间窗口取平均值，$W\left(t\right)$ 表示时刻$t$ 网络中的数据包数量，因此$\eta$ 是以$R$ 为自变量的函数。当$\eta =0$ 时，网络中生成的数据包数量与到达目的节点的数据包数量保持平衡，网络处于无拥堵的自由流状态；当数据包生成率$R$ 足够大时，大量数据包无法到达目的节点并在中心节点堆积，导致网络拥堵，此时$\eta >0$ 。

2.2. 路由算法与同配系数

基于度的有效路由算法，本文构建了一个基于所建符号网络的路由算法。基于度的有效路由算法直接将节点度作为路由代价，本文在此基础上，加入负边的“负边抑制权重”$w$ 作为额外代价。因此，对于节点$i$ 与节点$j$ 之间的任意路径$P\left(i\to j\right):i\equiv x_0{x}_1\cdots x_{n-1}{x}_n\equiv j$ ，定义路径总代价为：$T\left(P\left(i\to j\right):\beta \right)=min{\displaystyle \sum }_{i=0}^{n-1}k{\left(x_i\right)}^{\beta }+{\displaystyle \sum }_{l\in L}{w}_l$ ，其中，$l\in L$ ($L$ 为负边集合)，且边$l$ 属于该路径。

对于任意给定的$\beta$ ，节点$i$ 与节点$j$ 之间的有效路径为使总代价$T\left(P_1\left(i\to j\right):\beta \right)$ 最小的路径。研究结果表明，当$\beta =1$ 时，网络容量达到最大，因此本文直接采用这一参数设置。

同配系数(记为$A$ )是基于“度”的皮尔逊相关系数，用于衡量相连节点对之间的度关联关系，定义为：

$A=\frac{M^{-1}{{\displaystyle \sum }}_{e_{ij}}{k}_i{k}_j-{\left[M^{-1}{{\displaystyle \sum }}_{e_{ij}}\frac{1}{2}\left(k_i+k_j\right)\right]}^2}{M^{-1}{{\displaystyle \sum }}_{e_{ij}}\frac{1}{2}\left(k_i{}^2+k_j{}^2\right)-{\left[M^{-1}{{\displaystyle \sum }}_{e_{ij}}\frac{1}{2}\left(k_i+k_j\right)\right]}^2}$

其中，$k_i,k_j$ 分别为边$e_{ij}$ 的两个节点$v_i$ 与$v_j$ 的度，$M$ 为网络中的边数，$e_{ij}\in E$ ($E$ 为网络的所有边集合)。

由定义可知，同配系数$A$ 的正值表示度相同的节点间存在一定协同关系，负值表示度不同的节点间存在一定关联关系。通常情况下，$A$ 的取值范围为[−1, +1]：+1表示网络具有良好的同配性，0表示网络节点度无关联，−1表示网络节点度呈负相关。

2.3. 流量容量的理论分析

当网络结构与路由策略确定后，任意两个节点间的路径也随之确定，进而可计算节点$V$ 的未归一化路由介数[14] (记为${\text{B}}_{\text{V}}$ )。${\text{B}}_{\text{V}}$ 可用于评估节点$V$ 在网络中的重要性。研究表明，当上述流量模型稳定运行时，经过任意节点$V$ 的数据包数量可表示为：$R{\text{B}}_{\text{V}}/\left(N\left(N-1\right)\right)$ 。

为确保网络不产生拥堵，该数量应小于每个节点的数据包传输速率$C$ 。由此可得到网络的最大容量$R_C$ 为[15]：$R_C\approx \frac{N\left(N-1\right)}{B_{max}}$ ，其中，$B_{max}$ 表示网络中的最大介数，可用于间接评估网络容量$R_C$ 。此外，也可通过流量传输仿真实验得到网络的$R_C$ 。

3. 仿真实验

3.1. 不同符号网络的同配系数

本文通过在$SF-SF$ 、$ER-ER$ 和$SF-ER$ 网络上采用同配连接与异配连接方式，分别构建了节点数$N=1000$ 和$N=2000$ 的两类符号网络，并得到实验结果，图2、图3、图4。为不失一般性，实验中设定$m=2，m_0=5$ 。

可以看出，无论节点数为$N=1000$ 还是$N=2000$ ，$SF-SF$ 网络的平均负度与同配系数均呈正相关关系，即无论采用何种连接方式，网络的同配系数均随平均负度的增加而增大。图3中的曲线呈现出类似的对称分布，这是因为$ER$ 网络本身的同配系数接近0，在不同连接方式下会产生相反变化的曲线，且大型网络$\left(N=2000\right)$ 的变化速率相对较小。图4显示，$N=1000$ 和$N=2000$ 的$SF-ER$ 网络中，同配系数的变化趋势一致，与$ER-ER$ 网络的曲线变化趋势相同，但变化更为平缓。

Figure 2. Comparison of coefficient of homogeneity in SF-SF networks with changes in average degree of the network

图2. SF-SF网络中同配系数随网络平均负度的变化对比

Figure 3. Comparison of coefficient of homogeneity in ER-ER networks with changes in average degree of the network

图3. ER-ER网络中同配系数随网络平均负度的变化对比

Figure 4. Comparison of coefficient of homogeneity in SF-ER networks with changes in average degree of the network

图4. SF-ER网络中同配系数随网络平均负度的变化对比

3.2. 不同符号网络的平均路径长度

本文固定符号网络的节点数$N=1000$ ，计算了不同平均负度下网络的平均路径长度，结果如图5、图6、图7。

实验结果表明，随着平均负度的增加，网络的平均路径长度呈下降趋势。原因在于：符号网络平均负度的增加意味着更多负边的加入，这为数据包传输提供了更多路径选择，选择更短路径会导致平均路径长度降低。另一方面，更长的平均路径长度意味着数据包传输可能避开枢纽节点，从而避免网络拥堵，使网络获得更好的容量与数据包生成率$R$ 。此外，结合图1的结果可知，同配连接方式下符号网络的平均路径长度普遍高于异配连接方式，原因是在异配连接方式下，度较小的节点更易与枢纽节点连接，进而快速到达其他节点，避免了长路径传输。

Figure 5. Comparison of average path length in SF-SF networks with changes in average degree

图5. SF-SF网络中平均路径长度随网络平均负度的变化对比

Figure 6. Comparison of average path length in ER-ER networks with changes in average degree

图6. ER-ER网络中平均路径长度随网络平均负度的变化对比

Figure 7. Comparison of average path length in SF-ER networks with changes in average degree

图7. SF-ER网络中平均路径长度随网络平均负度的变化对比

3.3. 符号网络的流量传输仿真

随后，本文在三类符号网络上开展了流量传输仿真实验。实验中网络节点数$N=1000$ ，平均负度为1，得到数据包生成率$R$ 与参数$\eta$ 的关系曲线，结果如图8、图9、图10。

曲线的临界点即为$R_C$ (最大数据包生成率)：在异配连接方式下，$SF-SF$ 网络的$R_C$ 约为32；在同配连接方式下，$SF-SF$ 网络的$R_C$ 约为51。结合同配系数的实验结果可知，同配连接方式下的符号网络具有更长的平均路径长度，这一特性使其避开了枢纽节点的拥堵，从而提升了网络容量$R_C$ 。$ER-SF$ 网络与$ER-ER$ 网络也呈现出相同的规律：$ER-SF$ 网络在同配连接(AC)和异配连接(DC)方式下的$R_C$ 分别为52和26。此外，由于$ER$ 网络模型的两个主要假设(边的连接相互独立、每条边的连接概率相同)可能不适用于模拟部分现实现象(例如，与许多社交网络不同，$ER$ 网络的聚集系数较低)，因此$SF$ 网络是更优的替代模型。本文中，$ER-ER$ 网络在同配连接和异配连接方式下的$R_C$ 分别为125和110。

Figure 8. Comparison of packet generation rate (R) in SF-SF networks with variations in network parameter $\eta$

图8. SF-SF网络中数据包生成率(R)随网络参数η的变化对比

Figure 9. Comparison of packet generation rate (R) in ER-ER networks with variations in network parameter $\eta$

图9. ER-ER网络中数据包生成率(R)随网络参数η的变化对比

Figure 10. Comparison of packet generation rate (R) in SF-ER networks with variations in network parameter $\eta$

图10. SF-ER网络中数据包生成率($R$ )随网络参数η的变化对比

3.4. 节点负载微观分析

为深入揭示同配连接(AC)和异配连接(DC)方式对符号网络流量动力学的微观调控机制，本文聚焦临界负载率$R\approx R_c$ 场景，分析节点负载与度值的关联特征，实验结果如图11、图12。

仿真中，节点负载定义为节点转发数据包数量与队列积压数据包数量之和。图11、图12为在log-log坐标中同配连接(AC)和异配连接(DC)方式下节点负载–度值分布曲线。结合实验结果可知，在异配连接方式下，枢纽节点的负载随度值增长呈现显著波动上升趋势，这表明流量会集中于少数枢纽节点，使其成为网络拥塞的瓶颈；在同配连接方式下，节点负载随度值增长的增幅大幅放缓：高枢纽节点的负载维持在较低水平，且与低、中度节点的负载差异显著缩小；同配连接通过优化正负子网的连接规则，将枢纽节点的集中负载分散至边缘节点，实现了网络负载的均衡化。同配连接策略通过调整正负子网的连接规则，改变了流量在网络中的传输路径，有效避免了高程度枢纽节点成为流量瓶颈，从微观层面验证了同配连接策略在缓解枢纽拥塞、优化流量动力学特征上的核心优势。

3.5. 真实符号网络中的验证

最后，本文选取了一个真实符号网络[16]，采用第2章提及的路由算法与参数进行仿真实验，结果如图13所示。

Figure 11. Node load distribution for assortative connection in log-log coordinates

图11. log-log坐标下同配策略的节点负载–度值分布

Figure 12. Node load distribution for disassortative connection in log-log coordinates

图12. log-log坐标下异配策略的节点负载–度值分布

Figure 13. On the change curve of packet generation rate R and parameter η

图13. 数据包生成率(R)与参数η的变化曲线

同样，实验得到该符号网络的同配系数$A=-0.1488$ ，平均路径长度为$6.6470$ 。从实验中可得出该网络的$R_C$ 约为10。因此，本文通过构建的路由算法及相关参数，成功完成了符号网络上的基础流量传输。

4. 结论

本文主要研究了符号网络的同配性与路由策略。具体而言，本文将边的介数作为符号网络中负边的；“负边抑制权重”，以反映负边对路由传输过程的抑制作用；通过对$SF$ 网络与$ER$ 网络采用同配连接和异配连接方式，构建了不同的符号网络；随后计算了不同平均负度下符号网络同配系数的变化曲线，并对基于度的有效路由策略进行改进，将其应用于流量传输实验。

研究发现：$SF-SF$ 网络的同配系数与平均负度呈正相关；$ER-ER$ 网络和$SF-ER$ 网络的同配系数与连接方式相关；大型网络的同配系数变化曲线更平缓。此外，同配系数更大的网络具有更长的平均路径长度和更大的数据包生成率临界值$R_C$ ，从而能缓解网络拥堵，获得更优的传输性能与网络容量。最后，本文在真实符号网络上开展了流量传输实验，计算了相关参数并得出结论。

这些结论将为符号网络的路由与传输研究提供参考。然而，本文对路由策略的考虑较为有限，也未涉及大规模网络的传输实验，这些将成为符号网络路由与传输领域未来的研究方向。

基金项目

本文的工作受到了2020年度国家社会科学基金重大项目“我国青少年网络舆情的大数据预警体系与引导机制研究”(20&ZD013)和北京邮电大学教育教学改革项目(2024YB38)的资助。

NOTES

^*第一作者。

^#通讯作者。