期刊
KNOWLEDGE AND INFORMATION SYSTEMS
卷 45, 期 3, 页码 617-643出版社
SPRINGER LONDON LTD
DOI: 10.1007/s10115-014-0800-9
关键词
Triangle minimization; Large networks; FM sketch; Submodular function
资金
- NSFC [61402292]
- Natural Science Foundation of SZU [201438]
- Research Grants Council of the Hong Kong SAR, China [14209314, 418512]
The number of triangles is a fundamental metric for analyzing the structure and function of a network. In this paper, for the first time, we investigate the triangle minimization problem in a network under edge (node) attack, where the attacker aims to minimize the number of triangles in the network by removing edges (nodes). We show that the triangle minimization problem under edge (node) attack is a submodular function maximization problem, which can be solved efficiently. Specifically, we propose a degree-based edge (node) removal algorithm and a near-optimal greedy edge (node) removal algorithm for approximately solving the triangle minimization problem under edge (node) attack. In addition, we introduce two pruning strategies and an approximate marginal gain evaluation technique to further speed up the greedy edge (node) removal algorithm. We conduct extensive experiments over 12 real-world datasets to evaluate the proposed algorithms, and the results demonstrate the effectiveness, efficiency and scalability of our algorithms.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据