Distributed k-Core Decomposition

1 Introduction

• K-core decomposition recursively removes nodes of degree below k; nodes in the k-core but not the (k + 1)-core have coreness k, and larger coreness indicates a more central position.Cores are concentric: nodes in a 3-core also belong to the 2-core and 1-core.Source: §1 · p. 1
• Applications include characterizing social networks, visualizing complex graphs, studying proteins, and identifying epidemiological spreaders.Source: §1 · p. 1
• Distributed k-core computation addresses live systems that may inspect themselves and graphs too large for one host or inherently distributed across hosts.The introduction gives P2P overlays as a live-system example and cites a 2010 Facebook graph with 500 million users and more than 65 billion connections.Source: §1 · pp. 1–2
• The proposed distributed algorithm adapts from one host per node to multiple nodes per host and completes in O(N) rounds, with an upper bound of N − K + 1.K is the number of nodes with minimal degree; the paper reports that realistic graphs require surprisingly few rounds.Source: §1 · p. 2

2 Notation and system model

• A k-core is the maximum induced subgraph in which every node has at least k neighbors within that subgraph.Source: §2 · p. 2
• A node has coreness k when it belongs to the k-core but not the (k + 1)-core.Source: §2 · p. 2
• Each graph node is assigned to exactly one host responsible for computing its coreness, and each host’s assigned node set is V(x).When the graph itself is the distributed system, each node is also a host and the node and host neighbor sets coincide.Source: §2 · p. 2
• Hosts can query neighbors of themselves or their assigned nodes, but cannot obtain neighbor information for other hosts’ nodes; communication is reliable and hosts do not crash during computation.Source: §2 · p. 2

3 Algorithm

• A node has coreness k exactly when it has k neighbors with coreness at least k, but not k + 1 neighbors with coreness at least k + 1.Source: §3 · p. 3

Proof

• The proof rules out a (k + 1)-core containing the node by merging the cores of k + 1 qualifying neighbors with that node, which would contradict coreness k.Source: Proof · p. 3

3 Algorithm

• Each node communicates its coreness estimate to neighbors, recomputes its own estimate from theirs, and sends an update when its estimate changes, continuing until convergence.Source: Proof · p. 3

3.1 One host, one node

• Each node initializes its core estimate to its degree and neighbor estimates to +∞, then computes the largest i with at least i neighbor estimates ≥ i and only decreases its estimate.Changed estimates are sent every δ time units to avoid flooding with updates that are quickly superseded.Source: §3.1 · pp. 3–4

3.1.1 Example

• In the sample graph, estimates propagate from nodes 1 and 6 through nodes 2 and 5; the algorithm converges after the third round, with core 2 for nodes 2–5 and core 1 for nodes 1 and 6.Source: §3.1.1 · p. 4

3.1.2 Optimization

• Sending an update only when the new core estimate is below the recipient’s known estimate reduced exchanged messages by approximately 50% in the reported experiment.Source: §3.1.2 · p. 5

3.2 One host, multiple nodes

• Hosts initialize their nodes’ estimates to their degrees, emulate cascading updates internally until quiescent, and then send the resulting estimates to neighboring hosts.New external estimates trigger further local updates until none remain.Source: §3.2 · pp. 5–6

3.2.1 Communication policy

• Broadcast communication sends a batch of updates to all, while point-to-point communication sends each host only the updates relevant to it.Source: §3.2.1 · p. 6

3.2.2 Node-hosts assignment policy

• The assignment policy maps each node identifier u to host u mod |H|.This policy assumes integer node identifiers in [0 … n−1] and host identifiers in [0 … |H|−1].Source: §3.2.2 · p. 6

• A centralized server can terminate the protocol once every host reports that it generated no new estimate during a round.This approach is particularly suited to the one-node, multiple-host scenario.Source: §3.3 · p. 6
• Epidemic aggregation protocols can compute the last round with a new estimate in O(log |H|) rounds, after which hosts can detect termination.The protocol stops when that last-update value has not changed for a while.Source: §3.3 · p. 7
• A fixed round count is an option when approximate decomposition suffices, since most real-world graphs finish in a few tens of rounds and estimate error becomes extremely low after very few rounds.Source: §3.3 · p. 7

4.1 Safety and liveness

• The algorithm is safe and live: each node’s estimate never falls below its coreness and eventually equals it.The proofs focus on the one-to-one scenario, with the results stated to extend easily to one-to-many.Source: §4 · p. 7, §4.1 · p. 8

4.2 Time complexity

• The execution time is at most N − K + 1 rounds, where K is the number of nodes with minimal degree.The general size-only bound is N rounds.Source: §4.2 · pp. 9–10
• Real-world graphs with millions of nodes converge in fewer than 100 rounds, while a constructed graph family takes exactly N − 1 rounds for N ≥ 5.The N = 12 example has diameter 3, despite its linearly increasing convergence time.Source: §4.2 · p. 10, Figure 3 · p. 11
• A linear chain of size N takes ⌈N/2⌉ rounds, and the paper notes that small diameter does not generally ensure shorter execution time.Source: §4.2 · p. 10

4.3 Message complexity

• The distributed k-core computation has message complexity O(∆·M), where ∆ is the graph’s maximum degree and M is its number of edges.Source: §4.3 · p. 11

5.1 One-to-one version

• Most one-to-one runs complete in a few tens of rounds, while web-Berkstan and RoadNet-TX require a few hundreds.The paper reports averages over 50 experiments.Source: §5.1 · p. 11, §5 · p. 11
• Average and maximum messages per node are generally comparable to average and maximum node degree, leaving high-degree nodes more overloaded.Table 1 reports execution time and message counts alongside graph characteristics.Source: §5.1 · pp. 11–12, Table 1 · p. 12
• In web-Berkstan, the 55-core finishes before round 225, but the 1-core continues beyond round 300; its delay may be associated with the graph’s high diameter.More than half of the 55-core remains incorrect at round 25.Source: §5.1 · p. 12
• The maximum error across experimental datasets is at most 1 by cycle 22.Figure 4 plots average error and maximum error over time.Source: §5.1 · p. 12, Figure 4 · p. 13
• When exact coreness is unnecessary, the algorithm can stop after a predefined number of rounds with both average and maximum errors described as extremely low.The paper gives optimizing gossip protocols as an example use.Source: §5.1 · p. 13

5.2 One-to-many version

• With a broadcast medium, the one-to-many protocol sends fewer than 3 estimates per node on average, while its completion time is equivalent to the one-to-one version.Without broadcast, overhead increases with the number of hosts and tends toward one-to-one levels.Source: §5.2 · p. 13

• The paper presents, to the authors’ knowledge, the first distributed algorithms for k-core decomposition of online and/or large graphs.Source: §6 · p. 13
• Experiments show that the algorithms efficiently converge in few rounds on realistic graphs, despite large bounds that are tight for specific worst cases.Source: §6 · pp. 13–14
• The authors are considering implementing the algorithms in frameworks such as Hadoop and Pregel, whose efficiency, scalability, and fault-tolerance features the solutions could inherit.Source: §6 · p. 14