.png){kind=icon}
返回
Developing novel theorems in graph theory for computational algorithm enhancement
.png){kind=icon}
PRE
AI
DOI：10.47974/JDMSC-2541.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
图论长期以来一直是许多计算领域（如路由、社交网络分析和优化）中高效算法的基础工具。然而，传统方法倾向于处理密集和复杂的图结构，从而增加了计算成本。现有方法很少涉及基于熵的见解来选择性压缩图结构而不丢失关键结构信息。为填补这一空白，本研究提出一个新的理论构建，即图边熵定理（GEET）。该定理为每条边分配一定的信息贡献量，利用归一化权重形成的熵度量进行量化，并允许在算法执行前修剪低熵边。为验证GEET的效率，使用了Bitcoin Alpha信任网络数据集。预处理步骤包括边权重归一化和通过相互信任聚合转换为无向图。将GEET整合到Dijkstra算法中，并将结果与传统和部分修剪的图进行比较。实验结果表明，GEET增强模型显著减少了执行时间和内存使用，同时保持了高路径准确性。具体而言，与基线相比，它实现了61%更快的计算速度，内存消耗降低了47%，且路径准确率偏差仅为0.8%。这些结果支持了基于熵的边评估在计算图算法中实用效率的应用。
Keyword:
Graph theory
Entropy-based pruning
Computational efficiency
Dijkstra's algorithm
查看更多机构