The Maximum k-Plex Search (MPS) can find the largest k-plex, which is a generalization of the largest clique. Although MPS is commonly used in AI to effectively discover real-world communities of social networks, existing MPS algorithms suffer from high computational costs because they iteratively scan numerous nodes to find the largest k-plex. Here, we present an efficient MPS algorithm called Branch-and-Merge (BnM), which outputs an exact maximum k-plex. BnM merges unnecessary nodes to explore a smaller graph than the original one. Extensive evaluations on real-world social networks demonstrate that BnM significantly outperforms other state-of-the-art MPS algorithms in terms of running time.

k nearest neighbor (kNN) query is an essential graph data management tool to find relevant data entities suited to a user-specified query node. Graph indexing methods have the potential to achieve a quick kNN search response, the graph indexing methods are one of the promising approaches. However, they struggle to handle large-scale complex networks since constructing indexes and to querying kNN nodes in the large-scale networks are computationally expensive. In this paper, we propose a novel graph indexing algorithm for a fast kNN query on large networks. To overcome the aforementioned limitations, our algorithm generates two types of indexes based on the topological properties of complex networks. Our extensive experiments on real-world graphs clarify that our algorithm achieves up to 18,074 times faster indexing and 146 times faster kNN query than the state-of-the-art methods.

How can the most appropriate community be found given an attributed graph and a user-specified query node? The community search algorithm is currently an essential graph data management tool to find a community suited to a user-specified query node. Although community search algorithms are useful in various web-based applications and services, they have trouble handling attributed graphs due to the strict topological constraints of traditional algorithms. In this paper, we propose an accurate community search algorithm for attributed graphs. To overcome current limitations, we define a new attribute-driven community search problem class called the Flexible Attributed Truss Community (F-ATC). The advantage of the F-ATC problem is that it relaxes topological constraints, allowing diverse communities to be explored. Consequently, the community search accuracy is enhanced compared to traditional community search algorithms. Additionally, we present a novel heuristic algorithm to solve the F-ATC problem. This effective algorithm detects more accurate communities from attributed graphs than the traditional algorithms. Finally, extensive experiments are conducted using real-world attributed graphs to demonstrate that our approach achieves a higher accuracy than the state-of-the-art method.

Given a bi-type information network, which is an extended model of well-known bipartite graphs, how can clusters be efficiently found in graphs? Graph clustering is now a fundamental tool to understand overviews from graph-structured data. The RankClus framework accurately performs clustering for bi-type information networks using ranking-based graph clustering techniques. It integrates a graph ranking algorithms such as PageRank or HITS into graph clustering procedures to improve the clustering quality. However, this integration incurs a high computational cost to handle large bi-type information networks since RankClus repeatedly computes the ranking algorithm for all nodes and edges until the clustering procedure converges. To overcome this runtime limitation, herein we present a novel RankClus algorithm that reduces the running time for large bi-type information networks. Our proposed method employs dynamic graph processing techniques into the ranking procedures included in RankClus. By dynamically updating ranking results, our proposal reduces the number of computed nodes and edges during repeated ranking procedures. We experimentally verify using real-world datasets that our proposed method successfully reduces the running time while maintaining the clustering quality of RankClus.