Distributed Node Covering Optimization for Large Scale Networks and Its Application on Social Advertising

Combinatorial optimizations are usually complex and inefficient, which limits their applications in large-scale networks with billions of links. We introduce a distributed computational method for solving a node-covering problem at the scale of factual scenarios. We first construct a genetic algorithm and then design a two-step strategy to initialize the candidate solutions. All the computational operations are designed and developed in a distributed form on $\mathit{\text{Apache}}\mathit{\text{Spark}}$ enabling fast calculation for practical graphs. We apply our method to social advertising of recalling back churn users in online mobile games, which was previously only treated as a traditional item recommending or ranking problem.