2023/10/17 by Fan, Chenglin, Li, Ping, Peng, Hanyu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2310.11377
The densest subgraph of a large graph usually refers to some subgraph with the highest average degree, which has been extended to the family of p-means dense subgraph objectives by~\citetveldt2021generalized. The p-mean densest subgraph problem seeks a subgraph with the highest average p-th-power degree, whereas the standard densest subgraph problem seeks a subgraph with a simple highest average degree. It was shown that the standard peeling algorithm can perform arbitrarily poorly on generalized objective when p>1 but uncertain when 0