Hurricane in Bipartite Graphs: The Lethal Nodes of Butterflies
- Publisher:
- ACM
- Publication Type:
- Conference Proceeding
- Citation:
- ACM International Conference Proceeding Series, 2020, pp. 1-4
- Issue Date:
- 2020-07-07
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
3400903.3400916 (1).pdf | Published version | 3.96 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Bipartite graphs are widely used when modeling the relationships between two different types of entities, such as purchase relationships. In a bipartite graph, the number of butterflies, i.e., 2 × 2 biclique, is a fundamental metric for analyzing the structures and properties of bipartite graphs. Considering the deletion of critical nodes may affect the stability of bipartite graphs, we propose the butterfly minimization problem, where the attacker aims to maximize the number of butterflies removed from the graph by deleting b nodes. We prove the problem is NP-hard, and the objective function is monotonic and submodular. We adopt a greedy algorithm to solve the problem with 1-1/e approximation ratio. To scale for large graphs, novel methods are developed to reduce the searching space. Experiments over real-world bipartite graphs are conducted to demonstrate the advantages of proposed techniques.
Please use this identifier to cite or link to this item: