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

Distributed Memory Implementation of bron-kerbosch algorithm

IEEE ACCESS 2024年 12卷 59575-59588页

作者： Rote, Tejas Ravindra Krishnammorthy, Murugan Bhatia, Ansh Yadav, Rishu Raja, S. P. Vellore Inst Technol Sch Comp Sci & Engn SCOPE Vellore 632014 Tamil Nadu India

This paper proposes a parallel implementation of the bron-kerbosch algorithm, which finds all maximal cliques in large, complex graphs using CPU and thread-level parallelism and distributed memory with multiple cores. With the growing size and complexity of modern graphs, sequential algorithms can become impractical, making parallel computation a promising solution for reducing duration and enhancing scalability. Decomposing the graph into smaller components and distributing the workload across multiple threads using task parallelism is the proposed method. To optimise the algorithm's efficacy across processes, load-balancing techniques are also investigated. The modified bron-kerbosch algorithm is implemented and evaluated on a variety of large graphs, exhibiting significant runtime and scalability enhancements over the sequential version. The conclusion of the paper discusses the prospective applications of the parallel bron-kerbosch algorithm in a variety of domains, including social network analysis, bio informatics, and network security. Overall, this research contributes to the expanding body of work on parallel computing and graph analysis by emphasising the advantages of CPU and thread-level parallelism for efficiently solving complex computational problems.

关键词： Distributed memory bron-kerbosch algorithm parallel computing high-performance computing graph theory maximal cliques social network analysis bio-informatics network security performance optimization scalability compute nodes compute threads

来源：评论

学校读者我要写书评

暂无评论

An asynchronous P system for solving the maximum clique problem with the bron-kerbosch algorithm 10

An asynchronous P system for solving the maximum clique prob...

引用

10th International Symposium on Computing and Networking (CANDAR)

作者： Noguchi, Takuya Fujiwara, Akihiro Kyushu Inst Technol Grad Sch Comp Sci & Syst Engn Iizuka Fukuoka 8208502 Japan

ISBN: (纸本)9781665475327

Membrane computing, which is also known as a P system, is a computational model inspired by the activity of living cells. Several P systems, which work in a polynomial number of steps, have been proposed for solving computationally hard problems. However, most of the proposed algorithms use an exponential number of membranes, and reduction of the number of membranes must be considered in order to make a P system a more realistic model. In the present paper, we propose an asynchronous P system based on the bron-kerbosch algorithm for solving the maximum clique problem with fewer membranes. The proposed P system solves the maximum clique with n vertices in O(n(2)) parallel steps or O(n(2)2(n)) sequential steps. We evaluate the number of membranes used in the proposed P system and compare it with the numbers of membranes used in known P systems. Our experimental results demonstrate the validity and efficiency of the proposed P system.

关键词： membrane computing asynchronous P system maximum clique problem bron-kerbosch algorithm

来源：评论

学校读者我要写书评

暂无评论

Identifying most lethal cliques in disease comorbidity graphs

引用

IISE TRANSACTIONS ON HEALTHCARE SYSTEMS ENGINEERING 2025年

作者： Mohebbi, Parisa Vaghfi Lu, Yajun Miao, Zhuqi Balasundaram, Balabhaskar Kalgotra, Pankush Sharda, Ramesh Oklahoma State Univ Sch Ind Engn & Management Stillwater OK 74078 USA Jacksonville State Univ Dept Management & Mkt Jacksonville AL USA State Univ New York New Paltz Sch Business New Paltz NY USA Auburn Univ Dept Business Analyt & Informat Syst Auburn AL USA Oklahoma State Univ Dept Management Sci & Informat Syst Stillwater OK USA

Mortality rate refers to the overall likelihood of death within a specific population over a defined period. The knowledge of high mortality rate disease clusters can enable healthcare providers and patients to be proactive and develop tailored interventions that improve patient outcomes. In this paper, we introduce a methodology for systematically incorporating electronic health record data in an optimization framework to find cliques of comorbid diseases that correspond to the highest mortality rates among a given patient population. To this end, we introduce the maximum mortality rate clique problem and devise two approaches to solve it: (i) we formulate a mathematical optimization model that maximizes a fractional objective function subject to linear constraints in binary variables, which we reformulate as a mixed-integer linear program and solve using a commercial solver with delayed constraint generation, and (ii) we design an enumerative combinatorial algorithm based on the classical bron-kerbosch algorithm for enumerating maximal cliques. We conduct a detailed computational study and report results from our experiments with both approaches on a test bed of instances derived from millions of de-identified patient electronic health records.

关键词： bron-kerbosch algorithm clique enumeration comorbidity graph fractional programming mortality rate

来源：评论

学校读者我要写书评

暂无评论

On fast enumeration of maximal cliques in large graphs

引用

EXPERT SYSTEMS WITH APPLICATIONS 2022年第0期187卷 115915-115915页

作者： Jin, Yan Xiong, Bowen He, Kun Zhou, Yangming Zhou, Yi Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan Peoples R China East China Univ Sci & Technol Sch Informat Sci & Engn Shanghai Peoples R China Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

Maximal Clique Enumeration (MCE) is a fundamental and challenging problem in graph theory and various network applications. Numerous algorithms have been proposed in the past decades, however, only a few of them focus on improving the practical efficiency in large graphs. To this end, we propose an efficient algorithm called FACEN based on the bron-kerbosch framework. To optimize the memory and time consumption, we apply a hybrid data structure with adjacency list and partial adjacency matrix, and introduce a dynamic pivot selection rule based on the degeneracy order. FACEN is evaluated on a total of 64 benchmark instances from various sources. Computational results indicate that the proposed algorithm is highly competitive with the current leading MCE methods. In particular, our algorithm is able to enumerate all maximal cliques on the tested real-world social networks with millions of vertices and edges. For very large graphs, we provide an additional experiment for solving the MCE variant with lower bound, and investigate the benefits of FACEN.

关键词： Maximal clique enumeration Exact algorithm NP-hard bron-kerbosch algorithm Social network

来源：评论

学校读者我要写书评

暂无评论

Clique-detection algorithms for matching three-dimensional molecular structures

引用

JOURNAL OF MOLECULAR GRAPHICS & MODELLING 1997年第4期15卷 245-253页

作者： Gardiner, EJ Artymiuk, PJ Willett, P Univ Sheffield Dept Informat Studies Sheffield S10 2TN S Yorkshire England Univ Sheffield Krebs Inst Biomolec Res Sheffield S10 2TN S Yorkshire England Univ Sheffield Dept Mol Biol & Biotechnol Sheffield S10 2TN S Yorkshire England

The representation of chemical and biological molecules by means of graphs permits the use of a maximum common subgraph (MCS) isomorphism algorithm to identify the structural relationships existing between pairs of such molecular graphs. Clique detection provides an efficient way of implementing MCS detection, and this article reports a comparison of several different clique-detection algorithms when used for this purpose. Experiments with both small molecules and proteins demonstrate that the most efficient of these particular applications, which typically involve correspondence graphs with low edge densities, is the algorithm described by Carraghan and Pardalos. This is shown to be two to three times faster than the bron-kerbosch algorithm that has been used previously far MCS applications in chemistry and biology. However, the latter algorithm enables all substructures common to a pair of molecules to be identified and not just the largest ones, as with the other algorithms considered here. The two algorithms can usefully be combined to increase the efficiency of database-searching systems that use the MCS as a measure of structural similarity. (C) 1998 by Elsevier Science Inc.

关键词： bron-kerbosch algorithm Carraghan-Pardalos algorithm clique detection graph matching maximal common substructure pharmacophore mapping

来源：评论

学校读者我要写书评

暂无评论

Faster Enumeration of All Maximal Cliques in Unit Disk Graphs Using Geometric Structure

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2015年第3期E98D卷 490-496页

作者： Izumi, Taisuke Suzuki, Daisuke Nagoya Inst Technol Grad Sch Engn Nagoya Aichi 4668555 Japan

This paper considers the problem of enumerating all maximal cliques in unit disk graphs, which is a plausible setting for applications of finding similar data groups. Our primary interest is to develop a faster algorithm using the geometric structure about the metric space where the input unit disk graph is embedded. Assuming that the distance between any two vertices is available, we propose a new algorithm based on two well-known algorithms called bron-kerbosch and Tomita-Tanaka-Takahashi. The key idea of our algorithm is to find a good pivot quickly using geometric proximity. We validate the practical impact of our algorithm via experimental evaluations.

关键词： enumerating maximal cliques bron-kerbosch algorithm Unit disk graph

来源：评论

学校读者我要写书评

暂无评论

Two-stage coalition formation and radio resource allocation with Nash bargaining solution for inband underlaid D2D communications in 5G networks*

引用

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS 2018年 111卷 64-76页

作者： Tseng, Chih-Cheng Shih, Jyun-Yao Natl Ilan Univ Yilan Taiwan

For D2D communications in the inband underlaid 5G networks, to improve the utilization of cellular uplink spectrum, a two-stage coalition formation and resource allocation scheme is proposed to allocate the radio resources based on the numbers of resource blocks (RBs) requested by D2D pairs. Any set of D2D pairs whose pairwise distances longer than a threshold value are organized into a Stage-1 coalition by the bron-kerbosch algorithm. Otherwise, they are organized into Stage-2 coalitions based on the total number of RBs they requested. Since D2D pairs in a Stage-1 coalition are far away from each other, the co-channel interference can be ignored. To Improve the RB utilization, RBs that can be used by D2D pairs in the same Stage-1 coalition are first allocated to that Stage-1 coalition. Then, based on the total number of RBs requested by D2D pairs in a Stage-2 coalition, RBs are allocated to Stage-2 coalitions. Since RBs allocated to a Stage-2 coalition cannot be shared by D2D pairs in that Stage-2 coalition, the Nash bargaining solution (NBS) is used to further allocate RBs to D2D pairs in that Stage-2 coalition. Simulation results show that, the proposed two-stage coalition formation and resource allocation scheme allocates more number of equivalent RBs to D2D pairs than the number of RBs allocated by the greedy algorithm. Specifically, based on the simulation results, the total number of equivalent RBs allocated by the proposed scheme can be up to 325.52% of that allocated by the greedy algorithm.

关键词： 5G networks Device-to-device (D2D) Radio resource allocation Coalition Nash bargaining solution (NBS) bron-kerbosch algorithm

来源：评论

学校读者我要写书评

暂无评论

Enumerating all connected maximal common subgraphs in two graphs

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期250卷 1-30页

作者： Koch, I Walter Friedrich Haus Max Delbruck Ctr MDC D-13092 Berlin Germany

We represent a new method for finding all connected maximal common subgraphs in two graphs which is based on the transformation of the problem into the clique problem. We have developed new algorithms for enumerating all cliques that represent connected maximal common subgraphs. These algorithms are based on variants of the bron-kerbosch algorithm. In this paper we explain the transformation of the maximal common subgraph problem into the clique problem. We give a short summary of the variants of the bron-kerbosch algorithm in order to explain the modification of that algorithm such that the detected cliques represent connected maximal common subgraphs. After introducing and proving several variants of the modified algorithm we discuss the runtimes for all variants by means of random graphs. The results show the drastical reduction of the runtimes for the new algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： graph theory connected maximal common subgraphs cliques bron-kerbosch algorithm

来源：评论

学校读者我要写书评

暂无评论

Separability Assessment of Selected Types of Vehicle-Associated Noise 10th

引用

10th International on Conference Multimedia and Network Information Systems (MISSI)

作者： Kurowski, Adam Marciniuk, Karolina Kostek, Bozena Gdansk Univ Technol Fac Elect Telecommun Narutowicza 11-12 PL-80233 Gdansk Poland Gdansk Univ Technol Informat Multimedia Syst Dept Narutowicza 11-12 PL-80233 Gdansk Poland Gdansk Univ Technol Informat Audio Acoust Lab Narutowicza 11-12 PL-80233 Gdansk Poland

ISBN: (纸本)9783319439822;9783319439815

Music Information Retrieval (MIR) area as well as development of speech and environmental information recognition techniques brought various tools intended for recognizing low-level features of acoustic signals based on a set of calculated parameters. In this study, the MIRtoolbox MATLAB tool, designed for music parameter extraction, is used to obtain a vector of parameters to check whether they are suitable for separation of selected types of vehicle-associated noise, i. e.: car, truck and motorcycle. Then, cross-correlation between pairs of parameters is calculated. Parameters for which absolute value of cross-correlation factor is below a selected threshold, are chosen for further analysis. Subsequently, pairs of parameters found in the previous step are analyzed as a graph of low-correlated parameters with the use of the bron-kerbosch algorithm. Graph is checked for existence of cliques of parameters linked in all-to-all manner related to their low correlation. The largest clique of low-correlated parameters is then tested for suitability for separation into three vehicle noise classes. Behrens-Fisher statistic is used for this purpose. Results are visualized in the form of 2D and 3D scatter plots.

关键词： Vehicle-associated noise Low-level features bron-kerbosch algorithm MIRtoolbox

来源：评论

学校读者我要写书评

暂无评论

Collaboration Network Analysis of Turkey in Regional Basis

Collaboration Network Analysis of Turkey in Regional Basis

引用

2017 International Artificial Intelligence and Data Processing Symposium (IDAP)

作者： Ince, Kenan Karci, Ali Inonu Univ Dept Comp Engn Malatya Turkey

ISBN: (纸本)9781538618806

Modeling of data is an important step in process of interpreting the data and to understand the desired situation more clearly. The topic of social network structures is one of the highly studied subject and modeling is very important for social network mining. One of the modeling tools for such structures is Graphs. Graphs have been used for modeling and visualization tool of many structures such that computer networks, social networks, data structures and parallel programming topologies, etc. In this study, our data is scientific publications of Turkey and the goal is to find the cliques of academic collaboration network of Turkey at regional base via BK (bron-kerbosch) algorithm. By finding cliques, we aim to explore how relations are established between universities of Turkey and to reveal prominent university in each region.

关键词： Social network collaboration graph graph theory bron-kerbosch algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：