In the Biomedical Internet of Things (Bio-IoT), integrating large-scale multi-omics data into Protein-Protein Interaction (PPI) networks provides a foundation for analyzing cellular mechanisms. A critical computational task in this context is identifying protein complexes, which are cohesive groups of interacting proteins that represent functional modules. However, existing dense subgraph models often ignore user-specified size requirements, yielding results that are either trivially small or excessively large for biological interpretation. To address this limitation, we formulate the Size-constrained Protein Complex Search (SPCS) problem. Given a query protein, SPCS aims to identify a protein complex within a specific size range [l, h] that maximizes cohesiveness, measured by the minimum degree. We formally prove that SPCS is NP-hard, making exact enumeration computationally prohibitive for time-sensitive Bio-IoT applications. Consequently, we propose two efficient heuristic algorithms. The first, Heu-Basic, utilizes a greedy expansion strategy based on global degree centrality. To overcome its tendency to get trapped in local optima, we develop Heu-Pro, an advanced heuristic that incorporates local neighborhood connectivity and a multi-round expansion strategy. Experiments on real-world PPI networks demonstrate that Heu-Pro consistently identifies protein complexes with superior cohesiveness compared to unconstrained methods and baseline heuristics, balancing solution quality with the real-time efficiency required by Bio-IoT systems.

Cohesive subgraph mining has been extensively studied and finds numerous graph mining applications such as link farm identification, community detection, and product recommendation. Among various cohesive subgraph structures, the$k$-truss is particularly notable for its strong structural cohesiveness based on triangles. However, the classical$k$-truss problem aims to find the$k$-truss with the maximum number of vertices, which is often extremely large and complex in practice. To fully leverage the benefits of the$k$-truss, we consider a novel problem called theminimum$k$-truss problem, which seeks to identify a$k$-truss with the minimum number of vertices, where$k\geq 2$is a positive integer. We first formally prove the NP-hardness of the problem. We then design a baseline algorithmMTEnumthat is based on the vertex enumeration and a heuristic method for computing an upper bound. Despite these efforts,MTEnumstill faces practical efficiency issues which may be due to the fact that the$k$-truss lacks the hereditary property. To address this issue, we develop a novel decomposition-based frameworkDSA, which elegantly transforms the problem into a sequence of problems that are based on a new cohesive subgraph model callededge-based$s$-plex ($s$-eplex). With the hereditary property of$s$-eplex, we design a branch-and-bound algorithm with several customized techniques for the newly formulated problem. Extensive experiments demonstrate the effectiveness of our studied problem and the efficiency of our proposed algorithmDSA. In particular,DSAruns up to five orders of magnitude faster than the baselineMTEnum.

The s -bundle, as a cohesive subgraph model which relaxes the clique, remains connected whenever fewer than n-s vertices are removed, where n is the number of vertices inside. Finding the largest s -bundle is a fundamental problem and has diverse applications in various fields such as social network analysis, graph visualization, and bioinformatics. Existing studies for solving the problem follow the same branch-and-bound framework and improve the efficiency by developing pruning techniques. As a result, all share the same worst-case time complexity of O* (2 n ), where O* suppresses the polynomial factors. In this paper, we propose a new branch-and-bound algorithm, called SymBD, which achieves improved theoretical guarantees and practical performance. It adopts the existing Symmetric-BK branching strategy whose performance highly depends on the ordering of vertices. We explore various vertex orderings for improving the performance. In particular, we propose two novel vertex orderings based on the local vertex connectivity. With the proposed vertex orderings, SymBD improves the worst-case time complexity to O* (λ n s ) where λ s is strictly less than 2. To further boost the practical efficiency, we introduce a heuristic algorithm for computing a large initial solution and a divide-and-conquer strategy. Extensive experiments on 664 graphs demonstrate that our algorithm is up to five orders of magnitude faster than existing solutions.

Community search has widespread applications in areas such as advertising, friend recommendation, and protein complex identification. In this paper, we revisit the Size-bounded Community Search (SCS) problem, which aims to identify a connected subgraph containing a query vertex q and between l and h vertices, while maximizing the minimum degree of the subgraph. Existing state-of-the-art exact solutions for SCS face challenges in practical efficiency due to ineffective strategies for searching candidate solutions and suboptimal method for finding optimal solution. To address these challenges, we propose a novel branch-and-bound algorithm that efficiently locating a subset of candidate solutions with favorable structural properties, forming the basis for three progressively refined frameworks to determine the optimal solution. Furthermore, we enhance practical performance through a new heuristic, two reduction rules, and a query decomposition technique. Extensive experiments on 12 large real-world graphs demonstrate that our most efficient framework significantly outperforms state-of-the-art methods, achieving an average speedup of two orders of magnitude while consistently identifying communities with higher cohesion.

The$k$-vertex connected ($k$-VC) subgraph, which remains connected with fewer than$k$vertices being removed, is an essential structure in graph mining. It has found many applications, such as survivable network design and web search optimization. However, existing studies focus on mining maximal$k$-VCs, which are excessively large yet less cohesive in real applications. In this paper, we study theminimum$k$-VC search (MinVC)problem, seeking to find a$k$-VC with the minimum number of vertices. We formally prove that this problem is NP-hard and then propose two algorithms to obtain the exact solution. The basic method, calledEnum, follows a branch-and-bound framework with some pruning rules, which directly enumerates all possible vertex sets. Nonetheless, it suffers from the efficiency issues due to the non-hereditary property of the$k$-VC model. To address this challenge, we propose an advanced method, calledVCtoB, which divides theMinVCproblem into several new sub-problems, called thefixed-size$k$-VCproblems. Each of them can be solved efficiently by exploiting the hereditary property of the$s$-bundle model. Finally, our empirical experiments on 139 real-world networks demonstrate thatVCtoBachieves performance improvement of up to six orders of magnitude over the baseline.

Clustering routing is one of the most prevailing approaches for saving energy in Wireless Sensor Networks (WSNs). However, many existing clustering protocols have the problem of node premature death. This is primarily due to the frequent selection of some advantageous nodes as cluster heads (CHs), which bear the responsibility of data aggregation and forwarding, resulting in higher energy consumption. To address this problem, this paper proposes a dual-CH clustering routing model and introduces an interval-based CH reelection mechanism to reduce the energy consumption associated with frequent cluster formation. In addition, a comprehensive consideration of residual energy and base station distance in CH election facilitates the design of an improved hybrid swarm intelligence optimization algorithm termed GWOA-CH, which combines Gray Wolf Optimization (GWO) and Whale Optimization Algorithm (WOA) to obtain a more effective CH election scheme. To verify the effectiveness of the proposed algorithm, extensive experiments are conducted between GWOA-CH and some state-of-the-art WSNs routing protocols, including ModifyGA, NCOGA, ARSH-FATICHS and MMROR. Experimental results demonstrate the superior energy saving capabilities of the proposed clustering protocol compared to its alternatives.

Underwater acoustic sensor network (UASN) is a highly practical and popular sensor network extensively utilized for marine environmental monitoring and underwater exploration. Due to the high frequency of node usage, limited energy resources and high QoS performance requirements in UASN, it is necessary to adopt a comprehensive and integrated routing algorithm. In this paper, an innovative comprehensive clustering routing model is designed to accurately reflect the practical usage of UASN. Furthermore, a novel clustering routing algorithm, namely multi-objective differential chaotic shuffled frog leaping algorithm (MDCSFLA), is proposed. This algorithm effectively extends the network lifetime, greatly optimizes network energy balance, and improves network QoS performance. Additionally, by designing a novel differential local search strategy and chaotic perturbation strategy, the global optimization capability is significantly enhanced, and the convergence speed of the algorithm is effectively improved. Through a series of experiments, it is demonstrated that compared to LEACH-C, Q-LEACH, OptGACHE, and UCPSO, the proposed approach demonstrates a significant improvement in network lifetime and throughput, with an increase of at least 22.70% and 27.51%, respectively. Additionally, it achieves substantial reductions of at least 5.92% in average data transmission latency and 16.04% in packet loss rate.

The wireless sensor network (WSN) profoundly impacts the routing technology of the Internet of Things, which has received tremendous attention in terms of energy cost, quality of service (QoS) and security. In this way, it is particularly significant to find a multi-hop path with low energy consumption, delay, delay jitter, packet loss rate and high bandwidth, credibility in WSN. However, the existing energy-efficient secure QoS routing problem has been proven to be an NP-hard that forces a trade-off between energy cost, communication quality and security. To address this problem, a new energy-efficient secure QoS routing model is designed, which precisely replicates the communication scenario of WSN and comprehensively considers energy cost, latency, delay jitter, bandwidth, credibility, and packet loss rate. Subsequently, a novel energy-efficient secure QoS routing algorithm based on elite niche clonal evolutionary computing (ESQRA-ENCEC) is proposed, which includes three novel operators named niche selection, clone operator and elite optimization. These operators are designed to significantly increase the quality of solutions, vigorously develop convergence speed and successfully avoid local optima. The suggested algorithm not only considerably lowers energy consumption, delay, delay jitter and packet loss rate, but also effectively increases bandwidth and credibility. The simulation of ESQRA-ENCEC is performed in different scenarios. Experiment results reveal that the ESQRA-ENCEC has improved by 5.21%, 11.26% in energy cost, 5.31%, 7.94% in bandwidth, 6.44%, 10.80% in delay, 5.85%, 12.79% in delay jitter, 8.58% 14.39% in packet loss rate and 8.03%, 15.58% in credibility compared with two existing algorithms, respectively.

With the widespread application of the Industrial Internet of Things (IIoT), the requirements for sensing equipment to collect data and information continue to increase, and industrial wireless sensor networks (IWSNs) with industrial information perception capabilities have emerged as the times require. The data stream transmission of important value information requires the network to provide safe and reliable service quality assurance. Therefore, it is imperative to meet the requirements of end-to-end delay and reliable service between nodes and solve the problems of high energy consumption and poor security of the existing Quality-of-Service (QoS) routing protocols. To this end, considering the QoS constraints of end-to-end delay, security, and energy consumption, a multiobjective secure routing model based on trust awareness is designed. Subsequently, using the advantages of the proposed model, a novel QoS-secure routing algorithm based on multiobjective chaotic elite adaptive ant colony optimization (ACO) (i.e., MCEAACO-QSRP) is proposed. Specifically, a chaotic optimization strategy is designed to initialize the population, which increases the diversity of the population and enhances the ability of the algorithm to jump out of the local optimal. In addition, the adaptive optimization strategy is designed to dynamically adjust the algorithm trend, which effectively improves the algorithm convergence speed. The performance of the proposed algorithm is evaluated in different scale scenarios. The simulation results show that compared with other state-of-the-art QoS routing solutions, the proposed MCEAACO-QSRP has obvious advantages, which can effectively improve routing security, reduce network energy consumption, and satisfy multi-QoS constrains for the end-to-end delay and reliable service.

Compared with conventional wireless sensor networks (WSNs), industrial WSNs (IWSNs) have stricter requirements in real-time data transmission, energy consumption, and energy uniformity. To fulfill these requirements, a new energy-efficient clustering approach using quantum-related bioinspired optimization, i.e., quantum elite gray wolf optimization (QEGWO), is proposed to improve the performance of IWSNs. Innovatively, a new quantum operator, including quantum probability amplitude, quantum rotation gate, and quantum NOT gate, is designed in QEGWO to enhance its global search capability. This quantum operator need not query the quantum rotation angle table in updating quantum probability amplitude with the quantum rotation gate, which reduces the computational complexity of introducing quantum optimization into the clustering problem of IWSNs. Moreover, to enhance the convergence performance of the clustering algorithm, a multielite strategy is proposed to preserve the historical optimal individuals generated in the iterative process by establishing a dynamic elite pool. Compared with the state-of-the-art clustering approaches, extensive simulations in four different scenarios are carried out, and the results demonstrate that the proposed QEGWO outperforms other comparison approaches in delay, energy consumption, and energy uniformity.