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.

Graphs are widely used to model complex structured data in many applications. With the proliferation of cloud computing, it is popular to store and query graphs in the cloud. Among others, graph similarity search, which aims to retrieve from a graph database graphs similar to a query graph, has received wide attentions and benefited various domains such as cheminformatics, computer vision, and more. Deploying graph similarity search services on the cloud, however, raises critical privacy concerns on the information-rich graphs. In this article, we initiate the first study on privacy-preserving graph similarity search in cloud computing. We design, implement, and evaluate PrigSim, a novel system allowing the cloud to host an outsourced encrypted graph database and support secure graph similarity search, where the graph similarity is measured by the well-known metric called graph edit distance. PrigSim is built from a customized and delicate synergy of insights on graph modelling, lightweight cryptography, and data encoding and padding, providing protections for the confidentiality of data content associated with graphs, as well as hiding the connections among vertices. Extensive experiments demonstrate that the security design of PrigSim is accuracy-preserving, and presents modest performance overheads (with$9\times$-$15\times$higher query latency than the plaintext baseline).

The well-known benefits of cloud computing have spurred the popularity of database service outsourcing, where one can resort to the cloud to conveniently store and query databases. Coming with such popular trend is the threat to data privacy, as the cloud gains access to the databases and queries which may contain sensitive information, like medical or financial data. A large body of work has been presented for querying encrypted databases, which has been mostly focused on secure keyword search. In this paper, we instead focus on the support for secure skyline query processing over encrypted outsourced databases, where little work has been done. Skyline query is an advanced kind of database query which is important for multi-criteria decision-making systems and applications. We propose SecSkyline, a new system framework building on lightweight cryptography for fast privacy-preserving skyline queries. SecSkyline ambitiously provides strong protection for not only the content confidentiality of the outsourced database, the query, and the result, but also for data patterns that may incur indirect data leakages, such as dominance relationships among data points and search access patterns. Extensive experiments demonstrate that SecSkyline is substantially superior to the state-of-the-art in query latency, with up to$813\times$improvement.

Chaotic systems are suitable for image encryption owing to their numerous intrinsic characteristics. However, chaotic maps and algorithmic structures employed in many existing chaos-based image encryption algorithms exhibit various shortcomings. To overcome these, in this study, we first construct a two-dimensional logistic tent modular map (2D-LTMM) and then develop a new colour image encryption algorithm (CIEA) using the 2D-LTMM, which is referred to as the LTMM-CIEA. Compared with the existing chaotic maps used for image encryption, the 2D-LTMM has a fairly wide and continuous chaotic range and more uniformly distributed trajectories. The LTMM-CIEA employs cross-plane permutation and non-sequential diffusion to obtain the diffusion and confusion properties. The cross-plane permutation concurrently shuffles the row and column positions of pixels within the three colour planes, and the non-sequential diffusion method processes the pixels in a secret and random order. The main contributions of this study are the construction of the 2D-LTMM to overcome the shortcomings of existing chaotic maps and the development of the LTMM-CIEA to concurrently encrypt the three colour planes of images. Simulation experiments and security evaluations show that the 2D-LTMM outperforms recently developed chaotic maps, and the LTMM-CIEA outperforms several state-of-the-art image encryption algorithms in terms of security.

Chaos is known as a natural candidate for cryptography applications owing to its properties such as unpredictability and initial state sensitivity. However, certain chaos-based cryptosystems have been proven to exhibit various security defects because their used chaotic maps do not have complex dynamical behaviors. To address this problem, this paper introduces a cosine-transform-based chaotic system (CTBCS). Using two chaotic maps as seed maps, the CTBCS can produce chaotic maps with complex dynamical behaviors. For illustration, we produce three chaotic maps using the CTBCS and analyze their chaos complexity. Using one of the generated chaotic maps, we further propose an image encryption scheme. The encryption scheme uses high-efficiency scrambling to separate adjacent pixels and employs random order substitution to spread a small change in the plain-image to all pixels of the cipher-image. The performance evaluation demonstrates that the chaotic maps generated by the CTBCS exhibit substantially more complicated chaotic behaviors than the existing ones. The simulation results indicate the reliability of the proposed image encryption scheme. Moreover, the security analysis demonstrates that the proposed image encryption scheme provides a higher level of security than several advanced image encryption schemes.

Investigates the issues of placing a limited number of Web proxies in an environment where the Web server is replicated (i.e. mirrored Web servers). Two different objectives are considered: (a) minimizing the overall access cost by all clients of the Web server, and (b) minimizing the longest delay for any client to access the Web server. The problems are formulated and solved by using a dynamic programming method. This work can: (1) alleviate the amount of Internet traffic incurred by fast-growing Web accesses; (2) improve the response time of Web server accesses; and (3) maximize Web server performance by using a limited number of proxies.