.png){kind=icon}
Return
Developing novel theorems in graph theory for computational algorithm enhancement
.png){kind=icon}
PRE
AI
DOI：10.47974/JDMSC-2541.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Graph theory has been a long time tool for the basis of efficient algorithms in many computational domains such as routing, social network analysis and optimization. Traditional methods, however, tend to process dense and complex graph structures and, therefore, add to the computational cost. The existing approaches rarely involve entropy-based insights to selectively collapse graphs without losing essential structural information. Filling in this gap, the current study proposes a new theoretical construct, i.e., the Graph Edge Entropy Theorem (GEET). The theorem assigns to each edge an amount of informational contribution, quantified using the entropy measures formed from the normalized weights, and allowing the pruning of the low-entropy edges before the execution of the algorithm. To authenticate the efficiency of GEET, the Bitcoin Alpha trust network dataset was used. Preprocessing steps taken were edge weight normalization, and conversion into undirected graphs through mutual trust aggregation. GEET was plugged into Dijkstra's algorithm with the results being benchmarked against traditional and partially pruned graphs. Experimental results showed that GEET enhanced model had significantly reduced execution time and memory usage with high path accuracy. To be precise, it delivered 61% faster computation and reduced memory consumption by 47% as compared to the baseline with a small 0.8% in path accuracy deviation. These results support the applicability of the practical efficiency of entropy-based edge evaluation in the computational graph algorithms.
Keywords:
Graph theory
Entropy-based pruning
Computational efficiency
Dijkstra's algorithm
Journal
J
IF:
1.1
Papers:
185
Citations:
0
Organization
View more organizations
Cited Papers
No cited papers available