Answers are grounded in this paper and cite their sources.
Two algorithms improve reliability and density of subgraphs in protein-protein interaction networks, indicating enhanced graph mining approaches.
Graphs are widely used as essential modeling tools to represent protein-protein interaction networks. However, they are often subject to uncertainty due to noise or incomplete data collection. This research aims to address the challenges associated with uncertain weighted graphs, where each edge is characterized by both a probability of existence and a numerical weight. We propose two novel greedy algorithms, GreedyUWDS and GreedyBWDS, designed to extract dense and reliable subgraphs from uncertain weighted graphs. GreedyUWDS optimizes subgraph density by leveraging the expected weighted density metric, whereas GreedyBWDS introduces a flexible reliability threshold parameter to effectively balance density and reliability, enabling users to adjust the algorithm to prioritize either highly reliable subgraphs at the expense of density or greater density at the expense of reliability, thereby addressing a critical trade-off that previous methods have not effectively managed. Experimental validation on protein-protein interaction networks demonstrates that the proposed algorithms outperform existing techniques in terms of weighted edge density and subgraph reliability. Specifically, GreedyBWDS achieves approximately a 20% improvement in graph density over GreedyUWDS, while reducing runtime by a factor of 2.5. GreedyBWDS consistently identifies subgraphs with higher values for the combined density and reliability objective, and demonstrates significantly greater computational efficiency. These results underscore the flexibility and efficiency of our proposed approaches, offering practical solutions for analyzing uncertain weighted graphs in biological contexts, with a primary focus on protein-protein interaction networks. This research advances the field of graph mining by enabling users to fine-tune the balance between density and reliability according to their specific application requirements.
No takes yet. Share an insight, caveat, or question.
Duong et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: