PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Methods for k-core Community Search

Ian Chen, Haotian Yi, Arun Sharma, George Chacko, Tandy Warnow

arXiv:2609.17822v1cs.SI

TL;DR

Scalability on very large networks has not been sufficiently evaluated for existing community-search methods, and some support only single-node queries. The paper presents SteinerKCore and Par-ShellStruct for k-core community search. The authors report that both outperform prior methods and scale to larger networks.

  • Problem

    Scalability and computational performance on very large networks have not been sufficiently evaluated, and some existing methods support only single-node queries.

    Source: §1 · p. 2

  • Method

    SteinerKCore incrementally builds query components by coreness, while Par-ShellStruct constructs a ShellStruct index in parallel for query answering.

    Source: §2.1 · p. 3, §2.2 · p. 4

  • Results

    SteinerKCore and Par-ShellStruct are faster than CSK and ShellStruct and scale to networks with approximately 273 million nodes and 5 billion edges.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The authors describe these methods as an advance in practical tools for community search on large networks.

    Source: §4 · p. 11

    The methods assume connected, simple, undirected, unweighted input graphs, although extension to multiple components is described as straightforward.

    Source: §2 · p. 3

Abstract

from arXiv · show

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.

1 Introduction

The introduction motivates k-core community search as a query-focused alternative to community detection and identifies limited scalability evaluation and single-node-only methods as gaps. It presents SteinerKCore and Par-ShellStruct, reporting better performance and scalability than prior methods on large networks.

1 Introduction

  • Community search answers queries about a specified node set, unlike community detection’s disjoint partitioning, and can address overlapping community structures.Communities are described as internally cohesive subsets with relatively few edges to the rest of the network.Source: §1 · p. 1
  • For a query set Q, k-core community search seeks the unique maximal k-core containing Q for the largest possible k.A k-core is a connected induced subgraph in which every vertex has at least k neighbors within it.Source: §1 · pp. 1–2
  • Global search repeats graph peeling per query, local search is limited to single-vertex queries, and ShellStruct offers output-proportional queries but can be costly to build.Source: §1 · p. 2
  • Scalability and computational performance on very large networks had not been sufficiently evaluated, and some methods, such as CSK, support only single-node queries.Source: §1 · p. 2
  • The authors introduce SteinerKCore for few queries and Par-ShellStruct for many queries; their LocalKCore approach underperformed both and is not presented.Source: §1 · pp. 2–3
  • SteinerKCore and Par-ShellStruct are faster than CSK and ShellStruct and scale to networks with approximately 273 million nodes and 5 billion edges.The introduction also notes that some additional results are on the GitHub site.Source: §1 · p. 3

2 Our New Methods

The methods use Icebug and assume a connected, simple, undirected, unweighted input graph. SteinerKCore incrementally builds query components by coreness, while Par-ShellStruct constructs a ShellStruct index in parallel for query answering.

2 Our New Methods

  • Both methods use Icebug, and the stated input assumption is a connected, simple, undirected, unweighted graph.The authors say extension to graphs with multiple components is straightforward.Source: §2 · p. 3

2.1 SteinerKCore

  • SteinerKCore is named for its relationship to the Steiner max-min tree problem, whose largest tree for a query corresponds to the k-core community when edge weights encode endpoint core numbers.Source: §2.1 · p. 3
  • SteinerKCore adds vertices in decreasing coreness rounds and returns each query’s component when its query vertices first become connected.A union-find structure tracks components and query connectivity.Source: §2.1 · pp. 3–4
  • SteinerKCore answers ℓ queries in O(|E|α(|V|) + L log ℓ) time, where L is the output size.Source: §2.1 · p. 4

2.2 Par-ShellStruct

  • Par-ShellStruct builds the ShellStruct tree and an LCA table offline, then answers each query by returning the subtree of the queries’ lowest common ancestor.Its reported runtime includes both index construction and query answering.Source: §2.2 · p. 4
  • Par-ShellStruct processes each k-shell in bulk with parallelizable steps, using a concurrent union-find variant to avoid data races.The procedure builds the index bottom-up and is based on the union-find procedure in.Source: §2.2 · pp. 4–5
  • Par-ShellStruct is work-efficient and has O(ρ(G) polylog(|V|)) span with high probability in the Parallel RAM model.ρ(G) is the peeling-complexity defined in.Source: §2.2 · p. 5

3 Experimental Study

Across the tested networks and query workloads, the study compares core-decomposition choices and proposed k-core search methods with prior methods, then examines runtime, memory, and scalability.

3.1 Study Design

  • The study compares four community-search methods on ten cleaned networks, evaluating runtime, peak memory, and scalability under limits of 16 cores, 128 GB RAM, and four hours.Queries were sampled from nodes in the same connected component within the top 1% by degree; network sizes ranged from approximately 4.8 million to 273 million nodes.Source: §3.1 · pp. 5–6

3.2 Results

  • Icebug and UCR were fastest on the two approximately 14-million-node networks, with GBBS close behind; Icebug had a substantial advantage over UCR on abm14.The study selected Icebug for core decomposition.Source: Figure 1 · p. 7, §3.2 · p. 7
  • SteinerKCore and Par-ShellStruct outperform CSK and ShellStruct on inputs where the methods complete; CSK runs out of memory on the three largest networks, while ShellStruct fails on all three.CSK also does not support multi-node queries.Source: §3.2 · p. 7, Figure 2 · p. 8
  • Increasing CPU count tends to reduce runtime more on the large network than on the medium and small networks, with Par-ShellStruct benefiting more than SteinerKCore.The online phase parallelizes only across queries.Source: Figure 3 · p. 9, §3.2 · p. 9
  • 2 hours 45 minutes and 116GB: SteinerKCore finished the final network; Par-ShellStruct took 3 hours 31 minutes and 45GB.The network has approximately 273 million nodes and 5.1 billion edges; about half of each method’s runtime is core decomposition.Source: Figure 4 · p. 10, §3.2 · p. 10
  • Above 10^6 nodes, memory scales as |V|^0.77 for Par-ShellStruct and |V|^0.71 for SteinerKCore; runtime exponents shift from 0.33/0.39 below 5×10^7 to 1.64/1.65 beyond.The runtime exponents are 0.33 for Par-ShellStruct and 0.39 for SteinerKCore below the threshold, then 1.64 and 1.65, respectively, above it.Source: §3.2 · p. 10

3.3 Comparing SteinerKCore and Par-ShellStruct

  • SteinerKCore is consistently faster for one query, Par-ShellStruct is faster at 100 queries, and results at 10 queries are mixed; memory use favors Par-ShellStruct.On the large network, Par-ShellStruct is slower than SteinerKCore at eight or fewer CPUs and faster only at 64 CPUs.Source: §3.3 · pp. 10–11

4 Conclusion

The authors present SteinerKCore and Par-ShellStruct as practical tools for k-core community search on large networks. They report better computational performance than state-of-the-art methods and completion with limited resources where competing methods fail due to memory requirements.

  • The methods show better computational performance on large networks, up to 273 million nodes, than state-of-the-art methods.Source: §4 · p. 11
  • The methods can complete quickly with limited resources, while competing methods fail due to memory requirements.Source: §4 · p. 11
  • SteinerKCore and Par-ShellStruct advance practical tools for community search on large networks.Source: §4 · p. 11

Use of Artificial Intelligence

The authors declare that assistive AI was used to generate software codes and experimental scripts. They state that the authors wrote and approved the manuscript and take responsibility for its content and conclusions.

Loading 2609.17822v1…