Page 188 - 《软件学报》2026年第5期

潘伟丰 等: 基于动态分析和引力公式的关键类识别 2067

1.2 GEN 指标的构建
如前所述, 尽管目前已有很多指标用于度量类的重要性, 但是大部分均未考虑类之间的间接 (非接触) 耦合和
邻居节点度分布的多样性对类重要性的影响, 导致无法准确、全面地刻画软件网络中类节点的结构特征以及类的
重要性. 为了解决上述问题, 我们引入了引力公式和信息论中的熵.
万有引力可用来描述两个物体之间由于质量而产生的非接触相互作用 [32,33] . 引力公式可用于计算两物体之间
的引力. 此外, 信息论中的熵可用来度量系统的多样性和不确定性 [34] . 熵值越大, 系统的多样性越高、不确定性越
大. 因此, 我们借鉴万有引力和熵的概念, 构建度量指标刻画类之间的间接 (非接触) 耦合以及邻居节点度分布的
多样性对类重要性的影响. 具体而言, 我们基于引力公式和熵构建了一个用于度量类重要性的指标引力熵 GEN.
节点 GEN(i) 的定义如下:
i 的引力熵
∑
GEN(i) = INF i,j (5)
j∈sib o (i)
其中, GEN(i) 表示节点 i 的引力熵, sib o (i) 表示与节点 i 最短路径长度小于等于 o 的所有节点构成的集合, INF i,j 表
示节点 j 对节点 i 的间接影响力. 从公式 (5) 可知, GEN (i) 通过聚合集合 sib o (i) 内节点 j 对节点 i 的间接影响力来
量化节点 i 的重要性. 理论上, o 的最小取值是 1, 最大取值是网络的直径 (网络中节点对之间最短路径的最大值).
在本文中, o 取值为 3, 主要出于两点原因: 1) 相关研究表明, 类主要受其 3-阶内的邻居的影响 [35,36] ; 2) 我们需要计
算任意两节点间的最短路径, 过大的 o 值会显著降低指标的计算效率.
公式 (5) 中, 节点 j 对节点 INF i,j 的定义如下:
i 的间接影响力
IE i ×IE j
d i,j
INF i,j = r × (6)
i,j 2
d i,j
其中, d i,j 表示节点 i 和节点 j 之间的最短路径长度; r d i,j 表示节点 j 的重要性传递到节点 i 的概率; IE i 是从熵的角
i,j
度计算得到的类 i 的重要性值.
r d i,j 的定义如下:
i,j
p d i,j
r d i,j = ∑ i,j (7)
i,j d i,j
p
h∈V∧ j,h h,j
∑
其中, p d i,j 表示节点 i 和节点 j 之间的 d i,j 阶路径数量; V 是 CCN 的节点集; p d i,j 表示节点 j 和 V 中其他节点
i,j
h,j
h∈V∧ j,h
h 之间的 d i,j 阶路径总数. 因此, r d i,j 实际上量化的是节点 i 到节点 j 的 d i,j 阶路径数占节点 j 到其他所有节点的 d i,j
i,j
阶路径数的比例. r l 值越大, 表明相比于其他节点, 节点 j 更容易将其重要性传递给节点 i.
i,j
IE i 的定义如下:

deg w
P w = ∑ , x,w ∈ V (8)
deg
x∈sib(w) x

∑
e w = − P x lnP x , x,w ∈ V (9)
x∈in(w)

 
∑    
  w vw  
IE w = e w +  ∑ e v , u,v,w ∈ V (10)



 
 
v∈in(w) w vu
u∈on(v)
其中, deg w 表示类节点 w 的加权度 (CCN 中与节点 w 相连的边的权和); sib(w) 表示节点 w 及其 1-阶邻居节点构
成的集合; P w 表示节点 w 的加权度占其 1-阶邻域内节点加权度总和的比例, 用以刻画节点 w 在其 1-阶邻域内的
相对重要性; in(w) 表示 CCN 中类 w 入边上的邻居节点的集合; e w 表示 P x 的熵; on(v) 表示 CCN 中类 v 出边上的
邻居节点的集合; w vw 表示有向边 ⟨v,w⟩ 的边权值. 从公式 (10) 可知, 在求解 IE w 的过程中, 我们不但考虑了类 w 自
身的 e w , 还考虑了类 w 入度上的邻居 v 传递过来的部分 e v .