What is it about?
Dense parts of networks, a.k.a. dense subgraphs, often reveal interesting patterns with important applications. There are several mathematical definitions of such dense subgraphs. One such definition is called "pseudo-clique" which has many applications, as shown below. We devised the fastest-ever exact algorithm to compute pseudo-cliques in a large sparse graph/network.
Featured Image
Photo by JJ Ying on Unsplash
Why is it important?
This algorithm has been successful to identify protein complexes in protein-protein interaction networks. It can also be used to identify disease-related genes/RNAs, communities in society, repurposed drugs (identifying drugs used for one disease that can be applied to another new disease), etc.
Perspectives
While there are algorithms to compute pseudo-cliques, most of them are heuristic algorithms and, as such, may miss true pseudo-cliques and/or report false pseudo-cliques. We have shown here that exact/non-heuristic computation of pseudo-cliques is better able to reveal protein-complexes in protein-protein interaction networks than a popular heuristic used for this purpose. We have also designed an exact algorithm for computing pseudo-cliques and shown that it is a magnitude faster than all existing exact algorithms designed for this purpose. Our algorithm is an ideal candidate to identify pseudo-cliques from networks and it has the potential to reveal valuable insights that would be missed by heuristic algorithms.
Dr. Ahsanur Rahman
Read the Original
This page is a summary of: A Fast Exact Algorithm to Enumerate Maximal Pseudo-cliques in Large Sparse Graphs, August 2024, ACM (Association for Computing Machinery),
DOI: 10.1145/3637528.3672066.
You can read the full text:
Resources
Contributors
The following have contributed to this page
