We propose a heuristic method of using network centralities for constructing small-weight Steiner trees in this paper. The Steiner tree problem in graphs is one of the practical NP-hard combinatorial optimization problems. Given a graph and a set of vertices called terminals in the graph, the objective of the Steiner tree problem in graphs is to find a minimum weight Steiner tree that is a tree containing all the terminals. Conventional construction methods make a Steiner tree based on the shortest paths between terminals. If these shortest paths are overlapped as much as possible, we can obtain a small-weight Steiner tree. Therefore, we proposed to use network centralities to distinguish which edges should be included to make a small-weight Steiner tree. Experimental results revealed that using the vertex or the edge betweenness centralities contributes to making small-weight Steiner trees.
Download full-text PDF |
Source |
|---|---|
| http://www.ncbi.nlm.nih.gov/pmc/articles/PMC11156324 | PMC |
| http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0303764 | PLOS |
Publication Analysis
Top Keywords
Similar Publications
Construction of a random survival forest model based on a machine learning algorithm to predict early recurrence after hepatectomy for adult hepatocellular carcinoma.
BMC Cancer
December 2024
Department of Biochemistry and Molecular Biology, Tongji Medical College, Huazhong University of Science and Technology, Wuhan, China.
Background And Aims: Hepatocellular carcinoma (HCC) exhibits a propensity for early recurrence following liver resection, resulting in a bleak prognosis. At present, majority of the predictive models for the early postoperative recurrence of HCC rely on the linear assumption of the Cox Proportional Hazard (CPH) model. However, the predictive efficacy of this model is constrained by the intricate nature of clinical data.
View Article and Find Full Text PDFThe Steiner tree Prosecutor: Revealing and disrupting criminal networks through a single suspect.
PLoS One
December 2024
Departamento de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago, Chile.
Disrupting a criminal organization requires a significant deployment of human resources, time, information, and financial investment. In the early stages of an investigation, details about a specific crime are typically scarce, often with no known suspect. The literature has shown that an effective approach for analyzing criminal organizations is social network analysis.
View Article and Find Full Text PDFExploration of drug repurposing for Mpox outbreaks targeting gene signatures and host-pathogen interactions.
Sci Rep
November 2024
Department of Biology, Science and Research Branch, Islamic Azad University, Tehran, Iran.
Monkeypox (Mpox) is a growing public health concern, with complex interactions within host systems contributing to its impact. This study employs multi-omics approaches to uncover therapeutic targets and potential drug repurposing opportunities to better understand Mpox's molecular pathogenesis. We developed an in silico host-pathogen interaction (HPI) network and applied weighted gene co-expression network analysis (WGCNA) to explore interactions between Mpox and host proteins.
View Article and Find Full Text PDFA heuristic method for solving the Steiner tree problem in graphs using network centralities.
PLoS One
June 2024
Department of Management Science, Graduate School of Engineering, Tokyo University of Science, Katsushika-ku, Tokyo, Japan.
We propose a heuristic method of using network centralities for constructing small-weight Steiner trees in this paper. The Steiner tree problem in graphs is one of the practical NP-hard combinatorial optimization problems. Given a graph and a set of vertices called terminals in the graph, the objective of the Steiner tree problem in graphs is to find a minimum weight Steiner tree that is a tree containing all the terminals.
View Article and Find Full Text PDFExploring the pathways of drug repurposing and Panax ginseng treatment mechanisms in chronic heart failure: a disease module analysis perspective.
Sci Rep
May 2024
Department of Education, Xiyuan Hospital, China Academy of Chinese Medical Sciences, Beijing, 100091, China.
Chronic Heart Failure (CHF) is a significant global public health issue, with high mortality and morbidity rates and associated costs. Disease modules, which are collections of disease-related genes, offer an effective approach to understanding diseases from a biological network perspective. We employed the multi-Steiner tree algorithm within the NeDRex platform to extract CHF disease modules, and subsequently utilized the Trustrank algorithm to rank potential drugs for repurposing.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!