在社交媒体(SNS)、学校及公司人脉、协作网络等由众多人际关系交织而成的关系网(网络)中,人们往往并不想一次性找出所有群体,而是希望了解“某个特定人物所属的亲密群体”。寻找适合邀请参加年初聚会的自然成员,或组建共同推进项目的小规模团队,就是典型情形。
然而关系网越大,通过分析整个网络来寻找群体的方式在时间和成本上的局限就越明显。此外,若这样找到的群体过于庞大,在容纳人数或参与人数有限的现实场景中就难以利用。因此需要一种以关注用户为中心、同时在期望规模内找出有意义群体的技术。
以往的社区搜索研究也处理过此类问题,但大多需要网络的全局信息,或依赖预先设定的结构性条件,难以灵活应用于实际数据。尤其是无法在问题定义阶段直接反映群体的“适当规模”,一直是制约实用性的因素。
蔚山科学技术院(UNIST)计算机工程系金正勋教授团队28日表示,已开发出一种新的社区搜索方法,可在必然包含用户指定对象的同时,只在设定规模内找出有意义的群体。社区搜索是一种在庞大网络数据中找出内部连接紧密群体的数据分析技术。
研究团队为在大规模关系网中准确且实用地找出关注用户所属的“亲密群体”,提出了在目标函数层面结合新理论标准与局部搜索策略的方法论。该方法的设计使得无需查看整个网络信息也能识别出所需规模的群体。
研究团队注意到,在现实关系网中,“亲密群体”并非单纯连接众多的集合,而应具备内部密集、同时与外部区分明显的结构。以往方法存在结果不必要地变大、连与群体关系并不紧密的成员(搭便车者)也被纳入的问题。为解决这一问题,研究团队提出了名为LSM(Local Sketch Modularity)的新社区质量指标。
LSM仅利用关注用户周边的局部信息评估候选群体的质量,并在理论上弥补了以往指标中群体越大就无条件越有利的局限。研究团队设计了朝该指标提高的方向扩展群体的搜索策略,同时可直接限制群体规模,以便在聚会人数或项目参与人数等存在规模约束的情况下也能提供可直接使用的结果。也就是说,这是一种寻找“恰好所需规模的亲密群体”而非“一味求大群体”的方法。
此外,为在大规模关系网中也能高效运行,团队同时提出了逐个成员扩展的方式与按单元合并结构密集区域的方式。由此减少了不必要的搜索和重复计算,证明即使在庞大的关系网中也能快速、稳定地识别关注用户周边的亲密群体。
金正勋教授表示:“在现实的网络分析中,很难一次性获取全部数据,实际需要的群体规模通常也是既定的”,“本研究是聚焦于在用户关注对象周边快速找出有意义关系的技术,可应用于客户群分析、异常交易检测、生物学蛋白质关系网分析等多个领域。”
本研究由UNIST研究员金多熙作为第一作者参与,并获得韩国研究基金会的支持。研究成果已被将于5月31日至6月5日在印度班加罗尔举办的“2026 SIGMOD”录用并将进行发表。SIGMOD(ACM Special Interest Group on Management of Data)是数据库领域最具权威的学会之一。






