Heavy Nodes in a Small Neighborhood: Exact and Peeling Algorithms With Applications

We introduce a weighted and unconstrained variant of the well-known minimum <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> union problem: Given a bipartite graph <inline-formula><tex-math notation="LaTeX">$\mathcal {G}(U,V,E)$</tex-math></inline-formula> with weights for all nodes in <inline-formula><tex-math notation="LaTeX">$V$</tex-math></inline-formula>, find a set <inline-formula><tex-math notation="LaTeX">$S\subseteq V$</tex-math></inline-formula> such that the ratio between the total weight of the nodes in <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> and the number of their <i>distinct</i> adjacent nodes in <inline-formula><tex-math notation="LaTeX">$U$</tex-math></inline-formula> is maximized. Our problem, which we term <i>Heavy Nodes in a Small Neighborhood</i> (<small>HNSN</small>), finds applications in marketing, team formation, and money laundering detection. For example, in the latter application, <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> represents bank account holders who obtain illicit money from some peers of a criminal and route it through their accounts to a target account belonging to the criminal. We prove that <small>HNSN</small> can be solved exactly in polynomial time via linear programming. We also develop several algorithms offering different effectiveness/efficiency trade-offs: an exact algorithm, based on node contraction, graph decomposition, and linear programming, as well as three peeling algorithms. The first peeling algorithm is a near-linear time approximation algorithm with a tight approximation ratio, the second is an iterative algorithm that converges to an optimal solution in a very small number of iterations in practice, and the third is a near-linear time greedy heuristic. In addition, we formalize a money laundering scenario involving multiple target accounts and show how our algorithms can be extended to deal with it. Our experiments on real and synthetic datasets show that our algorithms find (near-)optimal solutions, outperforming a natural baseline, and that they can detect money laundering more effectively and efficiently than two state-of-the-art methods.