Jul 2026· Journal of Mathematics and Scientific Computing With Applications· Vol 7, pp. 179-193· 0 citations
TL;DR
Results validate the proposed framework as a robust, scalable pre-processing solution for accelerating exact clique detection in massive PPINs and confirm that the retained modules align with established biological pathways.
Abstract
Finding maximum cliques in protein-protein interaction networks (PPINs) is computationally NP-hard. Large-scale PPINs typically contain dense and redundant interaction structures that exponentially increase search time. To address this computational bottleneck while preserving topological integrity, this study proposes a two-stage pruning strategy. The framework first employs K-core decomposition to filter peripheral noise, followed by a particle swarm-optimized graph attention network (GAT-PSO) that integrates four centrality metrics. This centrality-aware design explicitly captures complex structural dependencies, successfully mitigating the dense-core bias inherent in conventional statistical feature-based pruning and ensuring the retention of critical connector nodes. Evaluation across 12,535 STRING-derived PPINs demonstrated average node and edge reductions of 95.87% and 91.11%, respectively, thereby accelerating the MaxCliqueDyn (MCQD) algorithm by up to 106.73 times. Despite this extreme dimensionality reduction, the pruned networks maintained strong structural fidelity, achieving a clique-size similarity of 97.23% and a Jaccard index of 86.70%. Furthermore, functional enrichment confirmed that the retained modules align with established biological pathways. These results validate the proposed framework as a robust, scalable pre-processing solution for accelerating exact clique detection in massive PPINs.
This work proposes two scalable greedy algorithms based on gradient-guided edge selection that efficiently approximate marginal gains and prune the candidate edge set and achieves optimization performance comparable to exact greedy strategies while substantially reducing computational time.
Runze Zhang, Gengyu Wang, Zhongzhi Zhang· Proceedings of the 32nd ACM...· 0 citations
A novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the network's two-dimensional structural entropy within a potential game framework, and introduces a structural entropy-based node overlapping heuristic for detecting overlapping communities, with a near-linear time complexity.
Experiments show that replacing PageRank with alternative centralities yields similar F1-scores while offering notable runtime savings, and that GraphHD-Order remains competitive with the original GraphHD baseline while providing consistent speedups in encoding time.
Biological networks, characterized by complex interactions among genes, proteins, and metabolites, are often modeled as graphs to study their organizational principles and dynamics. Network motifs-recurring, statistically significant subgraphs provide critical insights into the functional properties and structural organization of these networks. Existing research has explored various facets of motif detection, including enumeration, edge and node independence, dynamic updates, multi-layered networks, and stochastic settings. Although there have been studies in exploring the functionality of individual motif instances, a significant gap remains in understanding how collections of motif instances act as a group to influence the overall functionality of the network. In this paper, we aim to fill this gap. We model the influence of collections of motifs as a novel problem, which we call the Closest $k$-Motif Set Selection problem. We prove that this problem is NP-hard and develop MOSAIC (MOtif Set with mAximal InfluenCe), a novel greedy algorithm to address this problem. MOSAIC operates in two phases: an initialization phase for computing distances between motifs and nodes, and an update phase that incrementally selects motif instances to optimize their collective impact on the network. We prove that MOSAIC is efficient with a low degree polynomial time complexity. Our experimental results demonstrate that MOSAIC achieves optimal or near-optimal results, and scales to the entire human network efficiently. Our experiments on the human transcriptional regulatory network demonstrate that MOSAIC can identify Alzheimer's genes effectively, and select Alzheimer's genes that are missed by state-of-the-art node-based selection methods. This work advances our understanding of motif-based network analysis and opens new avenues for exploring the functional implications of network motifs.
Murat Çalış, Volkan Altuntaş, Tamer Kahveci· IEEE transactions on computa...· 0 citations
Centrality measures are defined for simple graphs -- directed, undirected, weighted or unweighted. Attributed graphs have to be reduced to simple graphs for computing centrality measures. However, when applications with multiple types of relationships are modeled using multilayer networks (MLNs), simple graph algorithms cannot be directly used. Existing approaches typically analyze MLNs by aggregating layers of an MLN into a single graph, which results in the loss of structural and semantic information. The semantic information loss can be more pronounced particularly, in weighted networks. This work focuses on computing degree centrality in weighted homogeneous multilayer networks (HoMLNs) using a decoupling-based framework. The framework performs independent layer-wise analysis on MLNs without reducing them to simple graphs. The decoupling approach allows use of exiting algorithms for each layer and uses minimal information from individual layers for computing degree centrality of HoMLNs. We propose heuristic-based algorithms that strike a balance between accuracy and efficiency. The proposed methods are evaluated against ground truth (GT) results obtained using Boolean OR aggregation and naive baselines. Experimental results on both synthetic and real-world HoMLN datasets demonstrate that the heuristics achieve accuracy comparable to the ground truth while significantly improving computational efficiency, thereby establishing the scalability and effectiveness of the HoMLN algorithms developed using the decoupling approach.
A. Ayowole-Obi, Abhishek Santra, Sharma Chakravarthy· 0 citations
Identifying protein complexes from protein-protein interaction (PPI) networks is a fundamental task in systems biology, offering important insights into cellular organization and molecular function. However, reliable complex detection remains challenging due to the sparsity and noise of PPI data, as well as the need to balance structural compactness, inter-complex separability, and biological coherence. To address these challenges, this study formulates protein complex detection as a tri-objective optimization problem that jointly integrates topological and biological criteria. We propose TF-MOEA$^{+}$, a multi-objective evolutionary framework built on NSGA-II and equipped with two biologically informed search operators. The first is an objective-guided uniform crossover (OG-UX), which biases recombination toward parents with better multi-objective quality while preserving adjacency-feasible inheritance. The second is a self-adaptive topological-functional synergy mutation (TF-SM), which adjusts mutation behavior according to the degree of structural and functional integration of each protein and reassigns weakly integrated proteins using combined topological and GO-based evidence. Comprehensive experiments on four benchmark yeast PPI networks, Yeast-D1, Yeast-D2, Collins-CYC2008, and Collins-MIPS, show that TF-MOEA$^{+}$ consistently outperforms all baseline methods considered in this study in both detection accuracy and functional relevance. Additional ablation, statistical significance, sensitivity, and runtime analyses further demonstrate the robustness and efficiency of the proposed framework.
Mustafa N. Abbas, David Broneske, Gunter Saake· IEEE transactions on computa...· 0 citations