文章阅读目录大纲
在工作之中可能会遇到需要进行两个网络图对象之间的相似度计算的情形：例如在质谱数据分析的化学信息学计算工作之中，我们在解析SMILES字符串得到分子图之后，可以基于图相似度比较计算方法来比较计算两个代谢物分子图之间的结构上的相似度。
在计算相似度方法上，存在有两种经典的相似度计算方法：我们一般是以cos
问题一：图对象降维为向量
因为cos/jaccard
在进行向量转换问题上，我们首先需要先来回顾一下图对象的数据结构基础。对于一个图对象是由两部分的数据所构成的：
vertexedge
假设对于图数据中的任意一个节点对象而言，在其元数据之中存在有节点类型这一种属性的话，那么我们就可以依据节点类型以及网络的边连接拓扑结构来进行问题转换了。
很幸运的是，在工作中所遇到的图对象中的节点数据都是属于具有节点类型属性的数据，例如：
- 微生物网络图：节点类型可以为微生物的某一个层级上的物种分类
- 代谢物分子图：节点类型可以为原子的标签，例如碳原子，氢原子，氧原子等
- 代谢通路图：节点类型可能为代谢物，蛋白酶
基于上面具有节点类型标签的图对象，我们就可以进行两个图对象之间的jaccard
jaccard(g1, g2) = similar / (similar + distinct)- similar: 两个图对象中，网络连接拓扑结构相似的节点数量
- distinct：两个图对象中，没有找到在所比较的另一个图中具有网络连接拓扑结构相似的节点数量
那现在问题转换为：我们只需要计算出上面的jaccard
节点拓扑结构相似度计算
首先我们会需要从两个图之间的节点与节点之间的拓扑结构相似度开始学习两个图对象之间的相似度计算。
现在我们假设某一个节点类型为A，其在图1之中的网络连接拓扑结构为：A-B,A-C,A-D,A-B；而在图2之中，相同类型的A节点，其在图2之中的网络连接拓扑结构为：A-B,A-C,A-D,A-B,A-E。可以看得见，A节点的网络连接在两个图对象之间差别是在图2之中多了一个E节点连接，那我们怎么才能计算出A节点在两个图对象之间的相似度呢？其实，我们可以先对A节点所连接的邻接节点进行统计，例如，统计结果如下：
| 邻接节点 | 图1 | 图2 |
|---|---|---|
| B | 2 | 2 |
| C | 1 | 1 |
| D | 1 | 1 |
| E | 0 | 1 |
那现在这样子我们是不是就可以将两图之间的A节点的拓扑结构给转换为两个等长的向量了呢。那现在既然拥有了两个等长向量了，那我们就可以很方便的进行cos相似度计算或者杰卡德相似度计算了。基于上面的两个向量，我们可以计算出两个相似度得分值：cos=0.92582, jaccard=0.66667。
图对象拓扑结构相似度计算
基于上面的一个小结的学习，我们可以了解到是如何计算出两个节点之间的相似度的。那现在假设我们有一个阈值，例如0.8，只要两个节点之间的相似度大于这个阈值，就认为两个节点是一样的，这个时候我们就可以认为两个图对象之间具有一个交集节点。
现在，假设我们针对图1中的所有节点进行遍历。同时，针对图2中的节点也进行遍历，计算出图1与图二之中是否存在相同的交集节点。假设存在有，则交集大小增加1。则通过这样子的计算步骤，直到我们遍历完图1之中的所有节点，这个时候我们就拥有了两个图对象之间的交集大小intersect_size。接着我们可以将图1的节点数量加上图2的节点数量的总和减掉交集大小intersect_size即可得到两个图对象之间的并集大小union_size。
既然现在已经有了两个图对象之间的交集大小和并集大小了，那我们实际上就可以计算出两个图对象之间的杰卡德相似度了，下面是一段实现上面所描述的计算流程代码：
Public Function GraphSimilarity(x As NetworkGraph, y As NetworkGraph,
Optional cutoff# = 0.85,
Optional classEquivalent As Func(Of String, String, Double) = Nothing,
Optional topologyCos As Boolean = False) As Double
' JaccardIndex (intersects / union) -> highly similar / (dis-similar + highly similar)
Dim similar%, top#, cos#
If classEquivalent Is Nothing Then
classEquivalent = Function(a, b) If(a <> b, 0, 1)
End If
' 20191231
' X should always greater than Y in graph size
' or vertex count - similar may be negative value
' the negative value will cause union value smaller
' than similar count, result an invalid cos similar
' value which is greater than 1
If x.size.vertex > y.size.vertex Then
Dim tmp = x
x = y
y = tmp
End If
For Each a As Node In x.vertex
top = -99999
For Each b As Node In y.vertex
cos = Similarity.NodeSimilarity(a, b, classEquivalent, topologyCos)
If cos > top Then
top = cos
End If
Next
If top >= cutoff Then
similar += 1
End If
Next
Dim union As Integer = (similar + (x.vertex.Count - similar) + (y.vertex.Count - similar))
Dim jaccardIndex As Double = similar / union
Return jaccardIndex
End Function
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0078360
- 【MZKit】简单自动化组织分区 - 2023年11月5日
- 【MZKit教程】质谱成像原始数据文件查看 - 2023年6月29日
- 生物序列图嵌入算法 - 2023年6月29日
One response
Thx