检索结果-内蒙古大学图书馆

graph data science and machine learning for the detection of COVID-19 infection from symptoms

PEERJ COMPUTER SCIENCE 2023年 9卷 e1333页

作者： Alqaissi, Eman Alotaibi, Fahd Ramzan, Muhammad Sher King Abdulaziz Univ Fac Comp & Informat Technol Jeddah Saudi Arabia King Khalid Univ Informat Syst Abha Saudi Arabia

Background: COVID-19 is an infectious disease caused by SARS-CoV-2. The symptoms of COVID-19 vary from mild-to-moderate respiratory illnesses, and it sometimes requires urgent medication. Therefore, it is crucial to detect COVID-19 at an early stage through specific clinical tests, testing kits, and medical devices. However, these tests are not always available during the time of the pandemic. Therefore, this study developed an automatic, intelligent, rapid, and real-time diagnostic model for the early detection of COVID-19 based on its ***: The COVID-19 knowledge graph (KG) constructed based on literature from heterogeneous data is imported to understand the COVID-19 different relations. We added human disease ontology to the COVID-19 KG and applied a node-embedding graph algorithm called fast random projection to extract an extra feature from the COVID-19 dataset. Subsequently, experiments were conducted using two machine learning (ML) pipelines to predict COVID-19 infection from its symptoms. Additionally, automatic tuning of the model hyperparameters was ***: We compared two graph-based ML models, logistic regression (LR) and random forest (RF) models. The proposed graph-based RF model achieved a small error rate = 0.0064 and the best scores on all performance metrics, including specificity = 98.71%, accuracy = 99.36%, precision = 99.65%, recall = 99.53%, and F1-score = 99.59%. Furthermore, the Matthews correlation coefficient achieved by the RF model was higher than that of the LR model. Comparative analysis with other ML algorithms and with studies from the literature showed that the proposed RF model exhibited the best detection ***: The graph-based RF model registered high performance in classifying the symptoms of COVID-19 infection, thereby indicating that the graph data science, in conjunction with ML techniques, helps improve performance and accelerate innovations.

关键词： COVID-19 Knowledge graph graph algorithm Machine learning Symptoms Detection Automatic tuning Ontology

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of Vertex-Disjoint Shortest Paths on graphs 17th

Reconfiguration of Vertex-Disjoint Shortest Paths on Graphs

引用

17th International Conference and Workshops on algorithms and Computation

作者： Saito, Rin Eto, Hiroshi Ito, Takehiro Uehara, Ryuhei Tohoku Univ Grad Sch Informat Sci Sendai Miyagi Japan Kyushu Inst Technol Sch Comp Sci & Syst Engn Iizuka Fukuoka Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Japan

ISBN: (纸本)9783031270505;9783031270512

We introduce and study reconfiguration problems for (internally) vertex-disjoint shortest paths: Given two tuples of internally vertex-disjoint shortest paths for fixed terminal pairs in an unweighted graph, we are asked to determine whether one tuple can be transformed into the other by exchanging a single vertex of one shortest path in the tuple at a time, so that all intermediate results remain tuples of internally vertex-disjoint shortest paths. We also study the shortest variant of the problem, that is, we wish to minimize the number of vertex-exchange steps required for such a transformation, if exists. These problems generalize the well-studied SHORTEST PATH RECONFIGURATION problem. In this paper, we analyze the complexity of these problems from the viewpoint of graph classes, and give some interesting contrast.

关键词： Combinatorial reconfiguration graph algorithm Vertex-disjoint paths

来源：评论

学校读者我要写书评

暂无评论

A review of clique-based overlapping community detection algorithms

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2022年第8期64卷 2023-2058页

作者： Gupta, Sumit Kumar Singh, Dhirendra Pratap Choudhary, Jaytrilok Maulana Azad Natl Inst Technol Dept Comp Sci & Engn Bhopal 462001 MP India

Detection of communities is one of the prominent characteristics of vast and complex networks like social networks, collaborative networks, and web graphs. In the modern era, new users get added to these complex networks, which results in an expansion of application-generated networks. Extracting relevant information from these large networks has become one of the most prominent research areas. Community detection tries to reduce the application-generated graph into smaller communities in which nodes within the community are similar. Most of the recent proposals are focused on detecting overlapping communities in the network with higher accuracy. An integral issue in graph theory is the enumeration of cliques in a larger graph. As clique is a group of completely connected nodes which shows the explicit communities means these nodes share the same types of information. Clique-based community detection algorithm utilizing the clique property of the graph also identifies the implicit communities, which is not directly shown in the graph. Many overlapping community detection algorithms are proposed by researchers that rely on cliques. The goal of this paper is to offer a comparative analysis of clique-based community detection algorithms. This paper provides a pervasive survey on research works identifying the cliques in a network for detecting overlapping communities. We bring together most of the state-of-the-art clique-based community detection algorithms into a single article with their accessible benchmark data sets. It presents a detailed description of methods based on K-cliques, maximal cliques, and triad percolation methods and addresses these approaches' challenges. Finally, the comparative analysis of overlapping community detection methodologies is also reported.

关键词： graph algorithm Community detection algorithm Clique-based algorithm Maximal clique-based algorithm Clique percolation method Triad percolation method Overlapping community detection algorithm

来源：评论

学校读者我要写书评

暂无评论

Triangle Counting on Large graphs

Triangle Counting on Large Graphs

引用

作者： Hu, Yang The George Washington University

学位级别：Ph.D., Doctor of Philosophy

Triangle counting is a fundamental graph algorithm. It is also used in a wide range of applications such as thematic structures, link recommendation, social network analysis, spam detection, and e-commerce. In addition, it is used as a building block in other graph related problems, such as graph isomorphism (subgraph matching), k-truss, and clustering coefficient. Various triangle counting algorithms are studied for decades. However, the conventional algorithms are designed for sequential execution and have difficulties to scale to high volume of parallelism device such as GPUs or distributed systems. Since the worst case time complexity of this algorithm is high, it takes a long time to execute for big graphs. Also, as graph size increases, external execution takes a large amount of disk I/O operations which as a result is slow. Existing solutions face several drawbacks of suboptimal I/O complexity, limited parallelism, and low scalability. My dissertation research strives to provide high performance solutions of fast triangle counting on big graphs. We identify the most emerging needs for fast triangle counting on large graphs which are two folds. First, scalable parallel triangle counting algorithm designed for GPUs and distributed systems is a key for fast processing on large graphs. Second, external memory algorithm to minimize disk I/Os for the graphs larger than memory size is also important for many large datasets. As a consequence, my dissertation research aims to solve the challenges described above. My first project TriCore is a new GPU based high-performance and scalable triangle counting system that consists of three main techniques. First, we designed a binary search based counting algorithm that tremendously increases both thread parallelism and memory performance. Second, TriCore exploits a 2-D partition method to distribute the CSR representation across multiple GPUs, combined with a new streaming buffer to load the edge list from outside of GPUs.

关键词： Triangle counting graph algorithm Subgraph matching

来源：评论

学校读者我要写书评

暂无评论

Certifying Induced Subgraphs in Large graphs 17th

Certifying Induced Subgraphs in Large Graphs

引用

17th International Conference and Workshops on algorithms and Computation

作者： Meyer, Ulrich Tran, Hung Tsakalidis, Konstantinos Goethe Univ Frankfurt Frankfurt Germany Univ Liverpool Liverpool Merseyside England

ISBN: (纸本)9783031270505;9783031270512

We introduce I/O-effiient certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input graph is a member of the respective class, the certifying algorithm returns a certificate that characterizes this class. Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership. On a graph with n vertices and m edges, our algorithms take O(SORT(n + m)) I/Os in the worst case for split, threshold and trivially perfect graphs. In the same complexity bipartite and bipartite chain graphs can be certified with high probability. We provide implementations for split and threshold graphs and provide a preliminary experimental evaluation.

关键词： Certifying algorithm graph algorithm External memory

来源：评论

学校读者我要写书评

暂无评论

Mutual-visibility in distance-hereditary graphs: a linear-time algorithm 12

Mutual-visibility in distance-hereditary graphs: a linear-ti...

引用

12th Latin-American algorithms, graphs and Optimization Symposium (LAGOS)

作者： Cicerone, Serafino Di Stefano, Gabriele Univ Aquila Dipartimento Ingn & Sci Informaz & Matemat I-67100 Laquila Italy

The concept of mutual-visibility in graphs has been recently introduced. If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u, v-path P such that V(P) boolean AND X subset of {u, v}. If every two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G. It is known that computing the mutual-visibility number of a graph is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and grids. In this paper, we study the mutual-visibility in distance-hereditary graphs and show that the mutual-visibility number can be computed in linear time for this class. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://***/licenses/by-nc-nd/4.0)

关键词： Mutual visibility graph classes graph invariant graph algorithm Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Injective coloring of subclasses of chordal graphs

引用

THEORETICAL COMPUTER SCIENCE 2025年 1023卷

作者： Panda, B. S. Ghosh, Rumki Indian Inst Technol Delhi Dept Math New Delhi 110016 India

An injective k-coloring of a graph G=(V,E) is a function f:V ->{1,2,& mldr;,k} such that for every pair of vertices u and v having a common neighbor, f(u)not equal f(v). The injective chromatic number chi(i)(G) of a graph G is the minimum k for which G admits an injective k-coloring. Given a graph G and a positive integer k, Decide Injective Coloring Problem is to decide whether G admits an injective k-coloring. Decide Injective Coloring Problem is known to be NP-complete for chordal graphs. In this paper, we strengthen this result by proving that Decide Injective coloring Problem remains NP-complete for undirected path graphs, a proper subclass of chordal graphs. Moreover, we show that it is not possible to approximate the injective chromatic number of an undirected path graph within a factor of n1/3-epsilon in polynomial time for every epsilon>0 unless ZPP = NP. On the positive side, we prove that the injective chromatic number of an interval graph is either Delta(G) or Delta(G)+1, where Delta(G) is the maximum degree of G. We also characterize the interval graphs having chi(i)(G)=Delta(G) and chi(i)(G)=Delta(G)+1. As a consequence of this characterization, we obtain a linear time algorithm to find the injective chromatic number of an interval graph.

关键词： Coloring Polynomial time algorithm NP-complete APX-complete graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Orienting undirected phylogenetic networks

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 140卷

作者： Huber, Katharina T. van Iersel, Leo Janssen, Remie Jones, Mark Moulton, Vincent Murakami, Yukihiro Semple, Charles Univ East Anglia Sch Comp Sci Norwich NR4 7TJ England Delft Univ Technol Delft Inst Appl Math Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands Univ Canterbury Sch Math & Stat Private Bag 4800 Christchurch 8140 New Zealand

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions.(c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Phylogenetic network graph orientation graph algorithm Fixed-parameter tractability Polynomial-time algorithm Characterization Computational biology Phylogenetics

来源：评论

学校读者我要写书评

暂无评论

2-norm Flow Diffusion in Near-Linear Time 62

2-norm Flow Diffusion in Near-Linear Time

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Chen, Li Peng, Richard Wang, Di Georgia Tech Atlanta GA 30332 USA Google Res Mountain View CA USA

ISBN: (纸本)9781665420556

Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs. In this paper, we study computationally efficient diffusion primitives beyond random walk. We design an near-linear time randomized algorithm for the 2-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice. Examples include finding locally-biased low conductance cuts. Using a known connection between the optimal dual solution of the flow diffusion problem and the local cut structure, our algorithm gives an alternative approach for finding such cuts in nearly linear time. From a technical point of view, our algorithm contributes a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of nearly linear time Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and accelerated proximal gradient methods with inexact proximal mapping computation.

关键词： graph algorithm flow diffusion near linear time nonnegative quadratic programming

来源：评论

学校读者我要写书评

暂无评论

A Node-Embedding Features Based Machine Learning Technique for Dynamic Malware Detection 5

A Node-Embedding Features Based Machine Learning Technique f...

引用

5th IEEE Conference on Dependable and Secure Computing (IEEE DSC)

作者： Rai, Sudhir Kumar Mittal, Ashish Mittal, Sparsh Indian Inst Technol IIT Roorkee Roorkee Uttar Pradesh India

ISBN: (数字)9781665421416

ISBN: (纸本)9781665421416

As the malware menace exacerbates, dynamic malware detection (DMD) has become even more critical. In this paper, we present a machine-learning-based DMD technique. We propose generating node embedding features (NEFs) from process execution chains. We use NEFs and other features based on the command line, file path, and action taken by a process and feed them to our machine learning (ML) classification algorithms. We evaluated two ML classifiers, viz., light gradient boosting machine (LGBM) and XGBoost. We perform experiments on a real-world dataset provided by a leading anti-virus company. Our technique achieves high accuracy, and the use of NEFs improves the predictive performance of ML classification algorithms. Also, NEFs are found to be highly important in both these algorithms.

关键词： Dynamic malware detection Node2Vec graph algorithm machine learning classification

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：