Scalable algorithm finds tight communities around many nodes fast
Improved Methods for k-core Community Search
Social and Information Networks
Summary
Finding groups of connected friends or items around specific people in huge networks is hard. Past methods struggled with very large networks or only worked well for certain group shapes. The authors created SteinerKCore, a new method that quickly finds strong, tightly connected groups including many chosen people. They also made Par-ShellStruct, a fast way to prepare necessary network information using multiple computers. Their tools work well on extremely large networks using reasonable memory and time.
What this means in practice
- •For network operations teams: Identify resilient subnetworks including specific nodes quickly in large communication graphs for monitoring and diagnosis purposes.
- •For social media platform engineers: Extract cohesive user groups containing multiple specified individuals to improve targeted recommendations or content moderation workflows.
Authors
Ian Chen, Haotian Yi, Arun Sharma, George Chacko, Tandy Warnow
Abstract
Community search based on user-specified query nodes is complementary to community finding or graph clustering. Prior work in community search is divided into optimizing for external separate- ness or internal cohesiveness, which does not scale well networks of over a billion edges. We present SteinerKCore, a new scalable k-core based community search algorithm for multi-vertex queries. We also present Par-ShellStruct, a parallel algorithm for building the ShellStruct data structure used for k-core community search. We show that our implemen- tations in Icebug, an open-source toolkit for large-scale network analysis, are both more efficient and more scalable than comparative tools, being able to perform on a benchmark network of 273M and 5.1B edges using just 64GB RAM and under 4 hours runtime with 16 CPUs.