有哪些指标可以描述两个图（graph）的相似度？
描述两个图（graph）的相似度是一个非常重要且广泛的研究领域，尤其在网络分析、社交网络分析、生物信息学、化学信息学、计算机视觉等领域有重要应用。由于图的结构可以非常复杂，没有一个单一的指标能够完美地描述所有类型的相似度。因此，通常需要根据具体的应用场景和对相似度关注的方面来选择合适的指标。
以下是一些描述两个图相似度的常见指标，我会尽量详细地讲解它们：
1. 基于图结构的相似度 (Structural Similarity)
这类指标主要关注图的节点和边的连接方式。
1.1. 节点属性和连接模式的比较
节点匹配 (Node Matching) / 图同构 (Graph Isomorphism):
概念: 这是最严格的相似度定义。如果两个图是同构的，意味着它们在结构上是完全相同的，只是节点标签可能不同。也就是说，存在一个从一个图的节点到另一个图的节点的双射（一一对应），使得如果两个节点在第一个图中相邻，那么它们对应的节点在第二个图中也相邻。
优点: 提供了一个绝对的相似度判断。
缺点: 图同构问题是NP完全问题，对于大规模图来说计算成本非常高昂，几乎不可行。因此，实际应用中很少直接使用图同构来衡量近似相似度。
变种: 图近似同构 (Approximate Graph Isomorphism) 试图找到“最接近”同构的映射，但这仍然是一个困难的问题。
节点中心性度量比较 (Comparison of Node Centrality Measures):
概念: 衡量两个图中关键节点的分布是否相似。常见的中心性度量包括：
度中心性 (Degree Centrality): 节点的连接数。
介数中心性 (Betweenness Centrality): 节点作为最短路径上的节点所占的比例。
接近中心性 (Closeness Centrality): 节点到图中所有其他节点最短路径长度的平均倒数。
特征向量中心性 (Eigenvector Centrality): 基于节点邻居的中心性来衡量自身中心性。
方法:
1. 计算两个图的节点中心性度量。
2. 将这两个中心性度量向量进行比较，例如使用余弦相似度 (Cosine Similarity)、皮尔逊相关系数 (Pearson Correlation Coefficient) 或欧氏距离 (Euclidean Distance)。
优点: 可以捕捉到图中“重要”节点分布的相似性，即使整体结构不完全相同，如果重要节点的位置和角色相似，也可以认为图是相似的。
缺点: 只关注了节点的度量，可能忽略了整体的连接模式。
图嵌入 (Graph Embedding) / 图表示学习 (Graph Representation Learning):
概念: 将图或图中的节点映射到低维向量空间，使得在向量空间中的距离或相似度能够反映图或节点在原图中的结构和属性。
方法: 有许多图嵌入方法，例如：
DeepWalk, node2vec: 基于随机游走 (Random Walk) 的方法，将节点序列转化为词袋模型或序列模型，然后使用 Skipgram 等技术学习节点嵌入。
Graph Neural Networks (GNNs): 如 GCN, GAT, GraphSAGE 等，通过消息传递机制聚合邻居信息来学习节点表示。
图级别的嵌入: Graphlevel embedding 方法直接学习整个图的表示向量，例如 GraRep, DiffPool, Graph2Vec 等。
如何衡量图相似度:
1. 为每个图学习一个图级别的嵌入向量。
2. 计算这两个图嵌入向量之间的相似度，常用余弦相似度或欧氏距离。
优点: 能够捕捉到复杂的结构信息，并能处理节点属性。在大规模图上表现较好，并且可以作为下游任务（如图分类、图回归）的特征输入。
缺点: 嵌入效果很大程度上取决于所选的嵌入方法和参数。
1.2. 子图和模式的匹配 (Subgraph and Pattern Matching)
子图同构 (Subgraph Isomorphism):
概念: 判断一个图是否包含另一个图的子集（具有相同的连接结构）。如果图 G1 包含图 G2 的子图同构，意味着 G1 中存在一组节点和边，其连接方式与 G2 完全相同。
衡量相似度: 可以通过寻找两个图之间最大的公共子图 (Maximum Common Subgraph, MCS) 来衡量相似度。MCS 的大小（节点数或边数）越大，则图越相似。
优点: 能够识别出图中相似的局部结构模式。
缺点: 子图同构问题也是NP完全问题，计算复杂度极高。寻找 MCS 的算法也相当耗时。
频繁子图挖掘 (Frequent Subgraph Mining):
概念: 找到在两个图中都频繁出现的子图模式。两个图中共享的频繁子图模式越多，则认为它们越相似。
方法: 使用如 gSpan, Gaston 等算法挖掘频繁子图。然后比较两个图中发现的频繁子图集合，例如计算它们之间的交集大小或使用 Jaccard 相似度。
优点: 可以发现图中重复出现的、具有意义的结构单元，这在识别生物网络或化学分子时很有用。
缺点: 对频繁度阈值的选择敏感，且挖掘过程本身也可能耗时。
1.3. 基于图距离的度量 (Graph Distance Measures)
图编辑距离 (Graph Edit Distance, GED):
概念: 将一个图转换为另一个图所需的最少编辑操作次数。常见的编辑操作包括：节点插入/删除/替换，边插入/删除/替换。每个操作都有一个成本。
衡量相似度: GED 的值越小，两个图越相似。相似度可以表示为 $1 / (1 + GED)$ 或 $max_possible_GED GED$。
优点: 能够捕捉到图的整体结构差异，并允许自定义编辑操作的成本。
缺点: GED 的计算是一个NP难问题，即使对于节点和边数量较小的图，其计算复杂度也很高。在实际应用中，通常使用近似算法来估算 GED。
最大公约数 (Maximum Common Subgraph, MCS) 的距离:
概念: 如前所述，计算两个图的最大公共子图的大小，并将其转化为距离。例如，$1 |MCS| / max(|G_1|, |G_2|)$。
优点: 直接关注了图共享的结构。
缺点: 计算 MCS 的复杂度很高。
2. 基于图属性的相似度 (Attribute Similarity)
如果图的节点或边带有属性（例如节点的标签、权重、社区信息等），那么这些属性也可以用来衡量图的相似度。
2.1. 节点属性比较
节点属性向量相似度 (Node Attribute Vector Similarity):
概念: 如果两个图的节点具有可比的属性向量（例如，节点的度、年龄、兴趣标签等），可以将每个图的节点属性向量聚合起来，然后比较聚合后的向量。
方法:
1. 节点属性聚合: 对一个图的所有节点属性向量进行聚合，例如求和、平均、最大值等，得到一个代表整个图属性的向量。
2. 向量相似度: 使用余弦相似度、欧氏距离等度量两个聚合向量的相似度。
优点: 简单易行，能快速捕捉到节点整体属性的相似性。
缺点: 忽略了图的结构信息，只关注属性的集合。
节点属性分布相似度 (Node Attribute Distribution Similarity):
概念: 比较两个图中节点属性的分布。
方法:
1. 构建属性直方图: 对于每个属性（如节点的度范围、年龄段），在两个图中分别统计属于该属性范围的节点比例，生成直方图。
2. 比较直方图: 使用如卡方距离 (Chisquared distance)、Wasserstein 距离 (Earth Mover's Distance, EMD) 等度量方法比较两个直方图的相似度。
优点: 对属性的顺序不敏感，能反映属性的整体分布特征。
缺点: 同样忽略了图的结构。
2.2. 边属性比较
如果边具有权重，可以比较两个图的边权重分布，或比较两个图的邻接矩阵（如果图结构相同且有标签）。
3. 基于图全局统计信息的相似度 (Global Statistical Similarity)
这类指标不直接比较节点或边，而是关注图的宏观统计特性。
度分布相似度 (Degree Distribution Similarity):
概念: 比较两个图中节点度数的分布情况。
方法: 计算两个图的度分布直方图，然后使用统计距离度量（如 KolmogorovSmirnov 距离、Wasserstein 距离）来比较这两个分布。
优点: 可以捕捉到图中连接“紧密程度”或“稀疏程度”的相似性，计算简单高效。例如，幂律分布 (powerlaw distribution) 常见的网络（如社交网络）与其度分布相似度会较高。
缺点: 忽略了节点的具体连接方式，只关注了度数的统计。
聚类系数分布相似度 (Clustering Coefficient Distribution Similarity):
概念: 比较图中节点聚类系数的分布。聚类系数衡量了节点邻居之间互相连接的紧密程度。
方法: 计算每个节点的局部聚类系数，然后比较两个图中聚类系数的分布。
优点: 可以捕捉到图中“社区化”或“群集”的程度。
缺点: 对结构细节不敏感。
平均路径长度和直径 (Average Path Length and Diameter):
概念: 计算图的平均路径长度（任意两点之间最短路径长度的平均值）和直径（图中任意两点之间最短路径长度的最大值）。
方法: 如果这两个统计量相似，则认为图在“可达性”或“连接性”方面相似。
优点: 提供了一种快速的全局结构洞察。
缺点: 对细微的结构差异不敏感。
连通分量分析 (Connected Components Analysis):
概念: 比较图中连通分量的数量、大小分布等。
优点: 对于处理稀疏图或有明显社区结构的图有意义。
缺点: 只关注了图的连通性信息。
4. 基于图核函数的相似度 (Graph Kernelbased Similarity)
概念: 图核函数是将图映射到一个（通常是无限维的）特征空间，使得在这个特征空间中可以计算核函数值来衡量相似度，而无需显式地计算特征向量。
常见图核函数:
随机游走核 (Random Walk Kernel): 计算两个图中所有可能的随机游走路径的相似度。
子图核 (Subgraph Kernel): 计算两个图中共享的子图数量。
图谱核 (Graphlet Kernel): 基于图中特定大小（k个节点）的子图（图元，graphlet）的数量来衡量相似度。
WeisfeilerLehman (WL) Kernel: 是一种流行的图核，通过迭代更新节点标签（基于其邻居的标签）来捕捉局部结构信息，并在多轮迭代后比较标签分布。
如何衡量图相似度: 直接计算图核函数的值，通常核值越大，图越相似。
优点: 能够捕捉到复杂的结构信息，并与支持向量机 (SVM) 等机器学习算法结合，用于图分类等任务。WL 核在许多任务上表现出色。
缺点: 计算核函数可能非常耗时，特别是对于一些复杂的核函数。
5. 混合方法和多模态相似度
概念: 结合结构信息和属性信息，或者结合不同的结构度量方法。
方法:
加权组合: 将不同相似度指标的得分进行加权求和，得到一个综合的相似度得分。
多任务学习: 使用图嵌入方法同时学习结构和属性的表示。
基于图匹配算法的扩展: 例如，在节点匹配时考虑节点属性的相似性（带属性的图同构或近似同构）。
如何选择合适的指标？
选择哪种图相似度指标取决于：
1. 应用场景: 你想解决什么问题？例如，在社交网络中你可能更关注用户行为模式的相似性（节点属性和连接模式），而在生物网络中你可能更关注功能模块的相似性（子图结构）。
2. 图的特性: 图的大小、密度、是否有节点/边属性、属性的类型等都会影响指标的选择。
3. 计算资源: 像图编辑距离和子图同构的计算成本非常高，对于大规模图不适用。
4. 对相似度的定义: 你更关注图的整体结构、局部结构、节点重要性、属性信息还是全局统计特性？
总结一下，从最严格到最宽松，以及关注点不同，可以大致分为几类：
严格结构相似度: 图同构、子图同构、最大公共子图。
结构局部相似度: 图核函数 (WL, Graphlet)、频繁子图挖掘。
结构全局/统计相似度: 度分布、聚类系数分布、平均路径长度。
节点/属性中心相似度: 中心性度量比较、节点属性向量/分布比较。
低维表示相似度: 图嵌入 (DeepWalk, node2vec, GNNs)。
整体结构距离: 图编辑距离。
通常，更复杂的指标能够捕捉到更丰富的相似度信息，但也伴随着更高的计算成本。因此，需要在准确性和效率之间进行权衡。在实践中，探索性数据分析和领域知识的结合是选择合适指标的关键。
以下是一些描述两个图相似度的常见指标，我会尽量详细地讲解它们：
1. 基于图结构的相似度 (Structural Similarity)
这类指标主要关注图的节点和边的连接方式。
1.1. 节点属性和连接模式的比较
节点匹配 (Node Matching) / 图同构 (Graph Isomorphism):
概念: 这是最严格的相似度定义。如果两个图是同构的，意味着它们在结构上是完全相同的，只是节点标签可能不同。也就是说，存在一个从一个图的节点到另一个图的节点的双射（一一对应），使得如果两个节点在第一个图中相邻，那么它们对应的节点在第二个图中也相邻。
优点: 提供了一个绝对的相似度判断。
缺点: 图同构问题是NP完全问题，对于大规模图来说计算成本非常高昂，几乎不可行。因此，实际应用中很少直接使用图同构来衡量近似相似度。
变种: 图近似同构 (Approximate Graph Isomorphism) 试图找到“最接近”同构的映射，但这仍然是一个困难的问题。
节点中心性度量比较 (Comparison of Node Centrality Measures):
概念: 衡量两个图中关键节点的分布是否相似。常见的中心性度量包括：
度中心性 (Degree Centrality): 节点的连接数。
介数中心性 (Betweenness Centrality): 节点作为最短路径上的节点所占的比例。
接近中心性 (Closeness Centrality): 节点到图中所有其他节点最短路径长度的平均倒数。
特征向量中心性 (Eigenvector Centrality): 基于节点邻居的中心性来衡量自身中心性。
方法:
1. 计算两个图的节点中心性度量。
2. 将这两个中心性度量向量进行比较，例如使用余弦相似度 (Cosine Similarity)、皮尔逊相关系数 (Pearson Correlation Coefficient) 或欧氏距离 (Euclidean Distance)。
优点: 可以捕捉到图中“重要”节点分布的相似性，即使整体结构不完全相同，如果重要节点的位置和角色相似，也可以认为图是相似的。
缺点: 只关注了节点的度量，可能忽略了整体的连接模式。
图嵌入 (Graph Embedding) / 图表示学习 (Graph Representation Learning):
概念: 将图或图中的节点映射到低维向量空间，使得在向量空间中的距离或相似度能够反映图或节点在原图中的结构和属性。
方法: 有许多图嵌入方法，例如：
DeepWalk, node2vec: 基于随机游走 (Random Walk) 的方法，将节点序列转化为词袋模型或序列模型，然后使用 Skipgram 等技术学习节点嵌入。
Graph Neural Networks (GNNs): 如 GCN, GAT, GraphSAGE 等，通过消息传递机制聚合邻居信息来学习节点表示。
图级别的嵌入: Graphlevel embedding 方法直接学习整个图的表示向量，例如 GraRep, DiffPool, Graph2Vec 等。
如何衡量图相似度:
1. 为每个图学习一个图级别的嵌入向量。
2. 计算这两个图嵌入向量之间的相似度，常用余弦相似度或欧氏距离。
优点: 能够捕捉到复杂的结构信息，并能处理节点属性。在大规模图上表现较好，并且可以作为下游任务（如图分类、图回归）的特征输入。
缺点: 嵌入效果很大程度上取决于所选的嵌入方法和参数。
1.2. 子图和模式的匹配 (Subgraph and Pattern Matching)
子图同构 (Subgraph Isomorphism):
概念: 判断一个图是否包含另一个图的子集（具有相同的连接结构）。如果图 G1 包含图 G2 的子图同构，意味着 G1 中存在一组节点和边，其连接方式与 G2 完全相同。
衡量相似度: 可以通过寻找两个图之间最大的公共子图 (Maximum Common Subgraph, MCS) 来衡量相似度。MCS 的大小（节点数或边数）越大，则图越相似。
优点: 能够识别出图中相似的局部结构模式。
缺点: 子图同构问题也是NP完全问题，计算复杂度极高。寻找 MCS 的算法也相当耗时。
频繁子图挖掘 (Frequent Subgraph Mining):
概念: 找到在两个图中都频繁出现的子图模式。两个图中共享的频繁子图模式越多，则认为它们越相似。
方法: 使用如 gSpan, Gaston 等算法挖掘频繁子图。然后比较两个图中发现的频繁子图集合，例如计算它们之间的交集大小或使用 Jaccard 相似度。
优点: 可以发现图中重复出现的、具有意义的结构单元，这在识别生物网络或化学分子时很有用。
缺点: 对频繁度阈值的选择敏感，且挖掘过程本身也可能耗时。
1.3. 基于图距离的度量 (Graph Distance Measures)
图编辑距离 (Graph Edit Distance, GED):
概念: 将一个图转换为另一个图所需的最少编辑操作次数。常见的编辑操作包括：节点插入/删除/替换，边插入/删除/替换。每个操作都有一个成本。
衡量相似度: GED 的值越小，两个图越相似。相似度可以表示为 $1 / (1 + GED)$ 或 $max_possible_GED GED$。
优点: 能够捕捉到图的整体结构差异，并允许自定义编辑操作的成本。
缺点: GED 的计算是一个NP难问题，即使对于节点和边数量较小的图，其计算复杂度也很高。在实际应用中，通常使用近似算法来估算 GED。
最大公约数 (Maximum Common Subgraph, MCS) 的距离:
概念: 如前所述，计算两个图的最大公共子图的大小，并将其转化为距离。例如，$1 |MCS| / max(|G_1|, |G_2|)$。
优点: 直接关注了图共享的结构。
缺点: 计算 MCS 的复杂度很高。
2. 基于图属性的相似度 (Attribute Similarity)
如果图的节点或边带有属性（例如节点的标签、权重、社区信息等），那么这些属性也可以用来衡量图的相似度。
2.1. 节点属性比较
节点属性向量相似度 (Node Attribute Vector Similarity):
概念: 如果两个图的节点具有可比的属性向量（例如，节点的度、年龄、兴趣标签等），可以将每个图的节点属性向量聚合起来，然后比较聚合后的向量。
方法:
1. 节点属性聚合: 对一个图的所有节点属性向量进行聚合，例如求和、平均、最大值等，得到一个代表整个图属性的向量。
2. 向量相似度: 使用余弦相似度、欧氏距离等度量两个聚合向量的相似度。
优点: 简单易行，能快速捕捉到节点整体属性的相似性。
缺点: 忽略了图的结构信息，只关注属性的集合。
节点属性分布相似度 (Node Attribute Distribution Similarity):
概念: 比较两个图中节点属性的分布。
方法:
1. 构建属性直方图: 对于每个属性（如节点的度范围、年龄段），在两个图中分别统计属于该属性范围的节点比例，生成直方图。
2. 比较直方图: 使用如卡方距离 (Chisquared distance)、Wasserstein 距离 (Earth Mover's Distance, EMD) 等度量方法比较两个直方图的相似度。
优点: 对属性的顺序不敏感，能反映属性的整体分布特征。
缺点: 同样忽略了图的结构。
2.2. 边属性比较
如果边具有权重，可以比较两个图的边权重分布，或比较两个图的邻接矩阵（如果图结构相同且有标签）。
3. 基于图全局统计信息的相似度 (Global Statistical Similarity)
这类指标不直接比较节点或边，而是关注图的宏观统计特性。
度分布相似度 (Degree Distribution Similarity):
概念: 比较两个图中节点度数的分布情况。
方法: 计算两个图的度分布直方图，然后使用统计距离度量（如 KolmogorovSmirnov 距离、Wasserstein 距离）来比较这两个分布。
优点: 可以捕捉到图中连接“紧密程度”或“稀疏程度”的相似性，计算简单高效。例如，幂律分布 (powerlaw distribution) 常见的网络（如社交网络）与其度分布相似度会较高。
缺点: 忽略了节点的具体连接方式，只关注了度数的统计。
聚类系数分布相似度 (Clustering Coefficient Distribution Similarity):
概念: 比较图中节点聚类系数的分布。聚类系数衡量了节点邻居之间互相连接的紧密程度。
方法: 计算每个节点的局部聚类系数，然后比较两个图中聚类系数的分布。
优点: 可以捕捉到图中“社区化”或“群集”的程度。
缺点: 对结构细节不敏感。
平均路径长度和直径 (Average Path Length and Diameter):
概念: 计算图的平均路径长度（任意两点之间最短路径长度的平均值）和直径（图中任意两点之间最短路径长度的最大值）。
方法: 如果这两个统计量相似，则认为图在“可达性”或“连接性”方面相似。
优点: 提供了一种快速的全局结构洞察。
缺点: 对细微的结构差异不敏感。
连通分量分析 (Connected Components Analysis):
概念: 比较图中连通分量的数量、大小分布等。
优点: 对于处理稀疏图或有明显社区结构的图有意义。
缺点: 只关注了图的连通性信息。
4. 基于图核函数的相似度 (Graph Kernelbased Similarity)
概念: 图核函数是将图映射到一个（通常是无限维的）特征空间，使得在这个特征空间中可以计算核函数值来衡量相似度，而无需显式地计算特征向量。
常见图核函数:
随机游走核 (Random Walk Kernel): 计算两个图中所有可能的随机游走路径的相似度。
子图核 (Subgraph Kernel): 计算两个图中共享的子图数量。
图谱核 (Graphlet Kernel): 基于图中特定大小（k个节点）的子图（图元，graphlet）的数量来衡量相似度。
WeisfeilerLehman (WL) Kernel: 是一种流行的图核，通过迭代更新节点标签（基于其邻居的标签）来捕捉局部结构信息，并在多轮迭代后比较标签分布。
如何衡量图相似度: 直接计算图核函数的值，通常核值越大，图越相似。
优点: 能够捕捉到复杂的结构信息，并与支持向量机 (SVM) 等机器学习算法结合，用于图分类等任务。WL 核在许多任务上表现出色。
缺点: 计算核函数可能非常耗时，特别是对于一些复杂的核函数。
5. 混合方法和多模态相似度
概念: 结合结构信息和属性信息，或者结合不同的结构度量方法。
方法:
加权组合: 将不同相似度指标的得分进行加权求和，得到一个综合的相似度得分。
多任务学习: 使用图嵌入方法同时学习结构和属性的表示。
基于图匹配算法的扩展: 例如，在节点匹配时考虑节点属性的相似性（带属性的图同构或近似同构）。
如何选择合适的指标？
选择哪种图相似度指标取决于：
1. 应用场景: 你想解决什么问题？例如，在社交网络中你可能更关注用户行为模式的相似性（节点属性和连接模式），而在生物网络中你可能更关注功能模块的相似性（子图结构）。
2. 图的特性: 图的大小、密度、是否有节点/边属性、属性的类型等都会影响指标的选择。
3. 计算资源: 像图编辑距离和子图同构的计算成本非常高，对于大规模图不适用。
4. 对相似度的定义: 你更关注图的整体结构、局部结构、节点重要性、属性信息还是全局统计特性？
总结一下，从最严格到最宽松，以及关注点不同，可以大致分为几类：
严格结构相似度: 图同构、子图同构、最大公共子图。
结构局部相似度: 图核函数 (WL, Graphlet)、频繁子图挖掘。
结构全局/统计相似度: 度分布、聚类系数分布、平均路径长度。
节点/属性中心相似度: 中心性度量比较、节点属性向量/分布比较。
低维表示相似度: 图嵌入 (DeepWalk, node2vec, GNNs)。
整体结构距离: 图编辑距离。
通常，更复杂的指标能够捕捉到更丰富的相似度信息，但也伴随着更高的计算成本。因此，需要在准确性和效率之间进行权衡。在实践中，探索性数据分析和领域知识的结合是选择合适指标的关键。
网友意见
作为纯数出身的人，从数学角度思考题主的问题。如果是喜欢图论又关注数学的人，应该听说过近几年的热点方向：“graph limit”。数学界三大奖之一沃尔夫奖获得者，L. Lovasz[1]对这个方向做出了很大贡献，并且graph limit无论是在数论，分析，概率这些纯数方向，还是CS，算法这些应数方项都有很多应用。
极限的定义大家都知道，不严谨的说极限是描述一种无限接近的状态，那graph limit不可避免的要定义不同的图之间的距离。从几何上考虑，如果要定义两个图G和H距离很近，那么他们应该在局部足够相似。也就是说如果我从G上面撕下来一块相对大的碎片，那我应该能从H上找到一个局部和我刚撕下来的那块graph很“几乎同构”。用数学的语言描述，首先定义 图F到G同构的个数，然后定义同构密度，于是 ，。
如果稍微思考几秒钟我上面说的话，你就会发现..我说的是废话。因为这个定义只是直观的几何描述，对解决问题没有任何帮助。..接下来是正经的定义（虽然实际上和上面的直观定义是一回事）。首先对于两个定义在同一个点集上的图，直观的看，如果我们从中找任意两个子集，这两个子集之间的边的数量在上差不多，我们就可以认为这两个图很相似。也就是说，定义是图中之间的边的数量，我们用描述两个图的距离。我们把这种距离叫做cut distance。注意的是这个定义也在adjacency matrix上有良好的表示。
有了这个定义，那么对于拥有相同vertex数但是不同点集的两个图，我们可以对其中一个图重新编号；对于vertex数不同的两个图，我们可以blow-up。比较令人惊讶的是，这样得来的距离定义和我们一开始的直观定义相同。
接下来，这个距离的定义有什么用？
我注意到题主貌似是cs的，那我着重说一下我了解的cs方向的应用。作为背景，Szemeredi's regularity lemma目前是图论中最重要的定理之一，同时在数论，分析，概率，理论CS中有非常多的应用。粗略的说，这个引理描述的是每个很大的图都可以被划分为几部分，使得几乎任意两部分形成的二部图“random-like”。大概在95年左右，Friez和Kannan做出了一个regularity lemma的弱化版本，目前称为FK-regularity lemma（或者weak regularity lemma）：他们构造了一个的算法，input任意一个非常大的图（有个点 ），output一个非常regular的图，使得。
有了这个定理，我们可以快速（ ）的找到很多NP问题的近似解。这个方向的研究现在非常活跃。举个例子，判定一个图是否包含子图是至少NP-complete的，但是我们可以快速找出图中子图的近似数量[2]。找到一个图的rectilinear crossing number是NP-hard的，但是我们可以快速找出他的近似值，甚至可以给出一个构造[3]。大致思路很简单，给定一个大图，先作用FK算法找到一个划分，我们先遍历小图（constant time），然后再blow-up，利用两个图cut-distance相近来近似得到的结果。
强调一下这个方法我认为应该只对dense graph有效。对于稀疏图，我们的近似太粗暴了。L. Lovasz[1]最近倒是有研究graphs with bounded degree这种相对稀疏的图，不过具体方法不是很了解，大家有兴趣可以看参考资料。
Reference
[1]. L. Lovasz, Large networks and graph limits, American Mathematical Society, 2012.
[2]. J. Fox, L.M. Lovasz and Y. Zhao, On regularity lemmas and their algorithmic applications, arXiv[math.CO] 1604:0733.
[3]. J. Fox, J. Pach and A. Suk, Approximating the rectilinear crossing number, arXiv[cs.CG] 1606:3752
类似的话题
-
描述两个图（graph）的相似度是一个非常重要且广泛的研究领域，尤其在网络分析、社交网络分析、生物信息学、化学信息学、计算机视觉等领域有重要应用。由于图的结构可以非常复杂，没有一个单一的指标能够完美地描述所有类型的相似度。因此，通常需要根据具体的应用场景和对相似度关注的方面来选择合适的指标。以下是一............. -
TR西服面料：实用性与性价比的平衡之道TR面料，顾名思义，是涤纶（Polyester，简称T）和人造丝（Rayon，也称粘胶纤维，简称R）混纺而成的一种面料。它以其独特的性能组合，在西服领域占据着一席之地，尤其受到追求实用性和性价比的消费者的青睐。 TR西服面料的优缺点TR面料之所以受欢迎，在于它巧.............
-
长期投资，就像是种下一棵树，需要耐心、适合的土壤和适时的照料。对于行业指数基金来说，选择对的“树种”至关重要，这样才能让你的投资在岁月中茁壮成长。何为行业指数基金？首先，我们得搞清楚什么是行业指数基金。简单来说，它就是一种追踪特定行业股票表现的基金。比如，你可能听说过新能源汽车指数、半导体指数、消费.............
-
咱们聊聊现代处理器这玩意儿，到底一秒能折腾多少条最简单的 `MOV` 指令。这事儿啊，说起来简单，但背后涉及的门道可不少，而且数字也不是一成不变的，就像人每天吃的饭量会因为各种情况不一样一样。大概能干多少事？我跟你说，要是就一门心思地、纯粹地、一遍又一遍地执行最最简单的 `MOV` 指令，比如把内存.............
-
.......
-
“公知”这个词，近些年在中国舆论场上可以说是一把双刃剑，既有人将其奉为启蒙者、社会良心，也有人视其为汉奸、卖国贼。到底是个什么群体？他们的危害性又在哪儿？这事儿，说起来复杂，也得从头捋捋。“公知”是啥米？“公知”这个词，本意上是“公共知识分子”的缩写。最初，这词儿带着点褒义，指的是那些在某个领域有专.............
-
在人机交互（HCI）领域，衡量用户体验（UX）是一个至关重要但又充满挑战的任务。UX并非一个单一维度的概念，而是用户在使用产品或服务时，其感知、情感、态度以及行为等一系列复杂因素的综合体现。为了更客观、系统地评估和改进UX，研究者和实践者们开发了各种各样的衡量指标。下面，我将详细阐述其中一些关键的指.............
-
在中国政府部门，官员的考核体系非常复杂，它不仅仅是数字上的KPI，更是一个多维度、与政治目标紧密结合的评价系统。这些考核直接关系到官员的升迁、晋级、奖惩，甚至政治生命，其影响之深远，不可小觑。核心KPI的类别与内涵理解我国政府部门的KPI，首先要明白其服务的根本目的：维护国家稳定、促进经济发展、保障.............
-
自我指涉，简单来说，就是事物指向自身。在不同学科和领域里，这种“照镜子”般的现象以各种令人着迷的方式出现，它们挑战着我们的理解，也揭示着事物的内在逻辑。语言学和逻辑学：文字的游戏在语言学和逻辑学中，自我指涉是构建悖论的温床。最经典的莫过于“说谎者悖论”： “这句话是假的。”如果这句话是真的，那么.............
-
“提升自我，成为更好的人”，这话说起来容易，但真要落实起来，却是一条需要细细打磨、步步为营的道路。它不是一蹴而就的口号，而是无数细微改变汇聚成的洪流，流向那个更成熟、更强大、更圆满的自己。那么，具体来说，这条路指向哪里？有哪些 tangible 的方向可以让我们去追寻？1. 认知的深度与广度：打破思.............
-
委托，这个C中的基石之一，它的强大之处在于能够将方法像变量一样传递和调用。但凡事皆有代价，委托也不例外。理解它的性能开销，以及如何在实践中规避这些开销，是写出更高效C代码的关键。我们先来拆解委托的“内功心法”，看看它到底做了什么，以及在这个过程中可能产生的“损耗”。委托的幕后：方法调用的“代理人”本.............
-
合唱指挥和交响乐团指挥，虽然都站在音乐的顶端，用肢体语言挥洒出生命的乐章，但他们所掌舵的音乐海洋，其特质却有着天壤之别。两者之间，既有异曲同工的指挥艺术精髓，又有因乐器和声部不同而产生的显著差异。相同之处：灵魂的引领者，音乐的塑造者抛开具体的乐器编制，两位指挥最核心的共同点在于他们都是音乐的灵魂引领.............
-
嘿，各位即将踏入科技浪潮的同学们！我是个在科技圈摸爬滚打多年的老兵，看着一批又一批新鲜血液涌入，心中既激动又感慨。想当年，我也是那个带着满腔热血和一丝迷茫的菜鸟，所以今天就想掏心窝子地跟大家聊聊，希望能给你们少走些弯路，更快地找到属于自己的那片天。首先，也是最最重要的一点：别怕犯错，但要学会从错误中.............
-
要列举出“临证水平高”的国内名中医，这确实是个需要斟酌的问题，因为“名”和“高”的标准有很多维度，而且医学的传承和发展是连续的，每个时代都有杰出的人物。另外，中医的“临证水平”很大程度上是个人经验的积累，很难完全量化。不过，我们可以从几个角度来理解并尝试列举一些大家公认的、在临床实践中具有深厚造诣和.............
-
说起曹操，这位三国时期的风云人物，那留下的金句可真是不少，而且句句都蕴含着他那个时代特有的豪迈、权谋和哲学思考。我这就跟你好好捋一捋，力求让你听起来像是老朋友聊天一样，不是那种冷冰冰的AI报告。要说曹操最广为人知的，那肯定得是他在《短歌行》里的那几句：“对酒当歌，人生几何？”这句话出自他的人生感慨，.............
-
在音乐界，指挥家是连接作曲家宏伟蓝图与现场乐团精彩演绎的灵魂人物，他们用手势与情感，引导着乐音的流淌与情绪的起伏。而衡量一位指挥家技艺与潜质的至高舞台，莫过于那些声名卓著的国际音乐指挥比赛。这些比赛不仅是新星闪耀的舞台，更是音乐传承与创新的重要熔炉。要说国际上享有盛誉的指挥比赛，不得不提的便是：1..............
-
自北伐战争打响以来，蒋介石军事生涯中的胜仗不少，每一场胜利背后都凝聚着复杂的战略考量、对战场局势的判断以及对军队的调度运用。北伐战争伊始，蒋介石初挑大梁，指挥国民革命军一路向北进军。他在广东的军事基地稳固后，面对的是盘踞北方的军阀势力。其中，他指挥的 汀泗桥战役 和 贺胜桥战役 是早期北伐中至关重要.............
-
《促进制造业有序转移的指导意见》最近的发布，无疑是国家在产业布局和区域协调发展上又一次重要的战略部署。这份文件之所以值得我们深入关注，是因为它触及了制造业发展的核心问题，并为未来相当长一段时间内的产业梯度转移指明了方向。一、 明确了“有序转移”的内在逻辑：文件最核心的亮点，在于它不再简单地鼓励“转移.............
-
二战中，撤退作战从来都不是件容易的事。它考验着指挥官的胆识、智慧、临机应变的能力，更考验着部队的纪律性和战斗意志。很多时候，一场成功的撤退，其难度和重要性丝毫不亚于一场辉煌的进攻。在波澜壮阔的二战史中，涌现出了不少在撤退战中表现出色的将领，他们的名字和事迹至今仍被津津乐道。隆美尔：北非战场上的“沙漠.............
-
在第二次世界大战的硝烟中，日军涌现出不少以其卓越的作战指挥才能而闻名的将领。他们或在太平洋战场上掀起惊涛骇浪，或在亚洲大陆上纵横捭阖，其战术思想和临场指挥能力至今仍为军史研究者津津乐道。下面，我们就来详细聊聊几位在战争中表现突出的日军指挥官，试着从他们的实际指挥经历中，窥见他们的过人之处。1. 山本.............
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有