IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i15p3407-d1210822.html
   My bibliography  Save this article

Edge-Based Minimal k -Core Subgraph Search

Author

Listed:
  • 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)

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.

Suggested Citation

  • Ting Wang & Yu Jiang & Jianye Yang & Lei Xing, 2023. "Edge-Based Minimal k -Core Subgraph Search," Mathematics, MDPI, vol. 11(15), pages 1-17, August.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:15:p:3407-:d:1210822
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/15/3407/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/15/3407/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Cicerone, Serafino & Di Stefano, Gabriele & Klavžar, Sandi, 2023. "On the mutual visibility in Cartesian products and triangle-free graphs," Applied Mathematics and Computation, Elsevier, vol. 438(C).
    2. Li, Huichun & Zhang, Xue & Zhao, Chengli, 2021. "Explaining social events through community evolution on temporal networks," Applied Mathematics and Computation, Elsevier, vol. 404(C).
    3. Fang, Aili, 2021. "The influence of communication structure on opinion dynamics in social networks with multiple true states," Applied Mathematics and Computation, Elsevier, vol. 406(C).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kareeva, Yulia & Sedakov, Artem & Zhen, Mengke, 2023. "Influence in social networks with stubborn agents: From competition to bargaining," Applied Mathematics and Computation, Elsevier, vol. 444(C).
    2. Koopo Kwon & Jaeryong So, 2023. "Future Smart Logistics Technology Based on Patent Analysis Using Temporal Network," Sustainability, MDPI, vol. 15(10), pages 1-17, May.
    3. Li, Xianghua & Zhen, Xiyuan & Qi, Xin & Han, Huichun & Zhang, Long & Han, Zhen, 2023. "Dynamic community detection based on graph convolutional networks and contrastive learning," Chaos, Solitons & Fractals, Elsevier, vol. 176(C).
    4. Han, Weiwei & Zhang, Zhipeng & Sun, Junqing & Xia, Chengyi, 2022. "Role of reputation constraints in the spatial public goods game with second-order reputation evaluation," Chaos, Solitons & Fractals, Elsevier, vol. 161(C).
    5. Manuel, Paul & Brešar, Boštjan & Klavžar, Sandi, 2023. "Geodesic packing in graphs," Applied Mathematics and Computation, Elsevier, vol. 459(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:15:p:3407-:d:1210822. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.