In networks of complex human relationships such as social media, school and workplace connections, and collaboration networks, users often want to identify a "close group that a specific person belongs to" rather than finding all groups at once. Typical examples include finding natural members to invite to a New Year gathering or assembling a small team for a project.
However, as networks grow larger, analyzing the entire network to find groups becomes limited in terms of time and cost. Moreover, if the groups identified this way are excessively large, they are difficult to apply in real-world situations where the number of attendees or participants is constrained. This creates a need for technology that focuses on a user of interest while finding meaningful groups within a desired size.
Existing community search studies have addressed this issue, but most required global information about the network or relied on predefined structural conditions, making them difficult to flexibly apply to real data. In particular, the inability to directly reflect a group's "appropriate size" at the problem-definition stage has been a factor limiting practicality.
A research team led by Professor Kim Jung-hoon of the Department of Computer Science and Engineering at the Ulsan National Institute of Science and Technology (UNIST) announced on the 28th that it has developed a new community search technique that finds only meaningful groups within a defined size while always including a user-specified target. Community search is a data analysis technology that identifies groups with strong internal connections within vast network data.
To accurately and practically find the "close group" that a user of interest belongs to in a large-scale relationship network, the research team proposed a methodology that combines a new theoretical criterion at the objective-function level with a local search strategy. This approach is designed to identify groups of a desired size without examining the entire network.
The research team noted that in real relationship networks, a "close group" is not simply a group with many connections, but must have a structure that is dense internally while being clearly distinguished from the outside. Existing methods had the problem of producing unnecessarily large results, which included members not closely tied to the group — so-called "free riders." To solve this, the team proposed a new community quality metric called LSM (Local Sketch Modularity).
LSM evaluates the quality of candidate groups using only local information around the user of interest, and theoretically addresses the limitations of existing metrics that unconditionally favor larger groups. The team designed a search strategy that expands groups in the direction of increasing this metric, while also allowing the group size to be directly constrained. The aim is to deliver results that can be directly used in situations with size constraints, such as gathering attendance limits or project participation caps. In other words, the approach finds "a close group of just the right size" rather than "the largest possible group."
The team also presented a method that expands the group one member at a time, alongside a method that merges structurally dense regions unit by unit, so that the technique operates efficiently even on large-scale networks. By reducing unnecessary exploration and redundant computation, the team demonstrated that close groups around a user of interest can be identified quickly and reliably even in massive networks.
"In real-world network analysis, it is difficult to secure the entire dataset at once, and the size of the group actually needed is usually predetermined," Professor Kim Jung-hoon said. "This research focuses on technology that quickly finds only meaningful relationships around a target the user is interested in, and it can be applied to various fields such as customer segment analysis, fraudulent transaction detection, and biological protein interaction network analysis."
UNIST researcher Kim Da-hee participated as the first author of the study, which was conducted with support from the National Research Foundation of Korea. The findings have been accepted for presentation at "2026 SIGMOD," to be held in Bengaluru, India, from May 31 to June 5. SIGMOD (ACM Special Interest Group on Management of Data) is one of the most prestigious conferences in the database field.
