Edge-Based Minimal k -Core Subgraph Search

Ting Wang, Yu Jiang (), Jianye Yang () and Lei Xing
Additional contact information
Ting Wang: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 510700, China
Yu Jiang: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 510700, China
Jianye Yang: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 510700, China
Lei Xing: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 510700, China

Mathematics, 2023, vol. 11, issue 15, 1-17

Abstract: In social networks, k -core is commonly used to measure the stability of a network. When a user in a k -core leaves the network, other users may follow the user to leave. Hence, maintaining a key user is important to keep the stability of a network. It is known that an edge between two users models the relationship between the two users. In some scenarios, maintaining a relationship comes at a cost. Therefore, selectively in maintaining the relationships between users is crucial. In this paper, we for the first time conceive the concept of an edge-based minimal k -core model. An edge-based minimal k -core is a k -core with a minimal number of edges. In other words, removing any edge in an edge-based minimal k -core would make it not be a k -core any more. Based on this model, we proposed two problems, namely, an edge-based minimal k -core subgraph search (EMK-SS) and an edge-based minimal k -core subgraph search with a query node q (EMK- q -SS). Given a graph G , an integer k , and a query node (a key user) q , the EMK- q -SS problem is to find all the edge-based minimal k -cores containing the query node q , and the EMK-SS problem is to find all the edge-based minimal k -cores. We also theoretically prove that the two problems are both NP-complete. To deal with the proposed problems, we design two novel algorithms, namely the edge deletion algorithm and edge extension algorithm. Further, a graph partitioning technique is employed to speed up the computation. Comprehensive experiments on synthetic and real networks are conducted to demonstrate the effect and efficiency of our proposed methods.

Keywords: data management; subgraph search; k -core (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/15/3407/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/15/3407/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:15:p:3407-:d:1210822

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().