{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:28:59Z","timestamp":1773246539843,"version":"3.50.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>In a social network, the strength of relationships between users can significantly affect the stability of the network. In this paper, we use the k-truss model to measure the stability of a social network. To identify critical connections, we propose a novel problem, named k-truss minimization. Given a social network G and a budget b, it aims to find b edges for deletion which can lead to the maximum number of edge breaks in the k-truss of G. We show that the problem is NP-hard. To accelerate the computation, novel pruning rules are developed to reduce the candidate size. In addition, we propose an upper bound based strategy to further reduce the searching space. Comprehensive experiments are conducted over real social networks to demonstrate the efficiency and effectiveness of the proposed techniques.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/677","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:05Z","timestamp":1564285565000},"page":"4874-4880","source":"Crossref","is-referenced-by-count":27,"title":["Pivotal Relationship Identification: The K-Truss Minimization Problem"],"prefix":"10.24963","author":[{"given":"Weijie","family":"Zhu","sequence":"first","affiliation":[{"name":"East China Normal University, China"},{"name":"Zhejiang Lab, Hangzhou, China"}]},{"given":"Mengqi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang Gongshang University, China"}]},{"given":"Chen","family":"Chen","sequence":"additional","affiliation":[{"name":"East China Normal University, China"}]},{"given":"Xiaoyang","family":"Wang","sequence":"additional","affiliation":[{"name":"Zhejiang Gongshang University, China"}]},{"given":"Fan","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"East China Normal University, China"},{"name":"Zhejiang Lab, Hangzhou, China"},{"name":"The University of New South Wales, Australia"}]}],"member":"10584","event":{"name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","theme":"Artificial Intelligence","location":"Macao, China","acronym":"IJCAI-2019","number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2019,8,10]]},"end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:50:59Z","timestamp":1564285859000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/677"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/677","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}