메뉴 드롭다운
메뉴 드롭다운
KR EN

대학원 소개

연구성과

UNIST 인공지능대학원의 대학원 및 연구성과를 확인하실 수 있습니다.

Effective and efficient core computation in signed networks (Inf. Sci.), Prof. Junghoon Kim

Effective and efficient core computation in signed networks
Author: Junghoon Kim, Hyun Ji Jeong , Sungsu Lim , Jungeun Kim 

Abstract

With the proliferation of mobile technology and IT development, people can use social network services anywhere and anytime. Among many social network mining problems, identifying cohesive subgraphs has attracted extensive attention from different fields due to its numerous applications. The most widely used among many cohesive subgraph models is k-core, because of its simple and intuitive structure. In this paper, we formulate (p,n)" role="presentation" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">(,)-core in signed networks by extending the k-core model. (p,n)" role="presentation" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">(,)-core is designed to guarantee sufficient internal positive edges and deficient internal negative edges. We formally prove that finding an exact (p,n)" role="presentation" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">(,)-core is NP-hard. Hence, we propose three efficient and effective algorithms to find a solution. We demonstrate the superiority of our proposed algorithms using real-world and synthetic networks.