Source-linked AI summary
Core-periphery identification in massive networks
Eric Yanchenko
TL;DR
Massive networks create a need for scalable core-periphery detection because adjacency-matrix methods impose storage and memory demands. The paper develops an edge-list-based divide-and-conquer algorithm and reports strong synthetic and real-world performance, including a network with almost 14 million edges processed without loading the entire network into memory.
Problem
Adjacency-matrix core-periphery methods have limited scalability because they require O(n^2) storage and loading the full matrix into memory.
Method
The paper combines edge-list optimization with repeated random edge sub-sampling, core-periphery labeling on sub-graphs, and averaging to obtain node coreness.
Results
Almost 14 million edges were analyzed on a real-world network without loading the entire edge list into memory, while the proposed algorithm outperformed a similar adjacency-matrix method on synthetic networks.
Takeaways & Limitations
The edge-list divide-and-conquer approach supports core-periphery analysis of massive networks with more efficient memory use than adjacency-matrix representations.
Takeaways & Limitations
Scaling to larger networks depends on available computing cores and edge-list query speed, while fast sub-sampling is necessary for gigabyte-scale edge lists.
Abstract
from arXiv · showhide
Modern networks can be huge with millions or even billions of nodes and edges. Thus, algorithms must be capable of scaling to such large networks in order to be practically useful. In this work, we are interested in developing an algorithm to identify core-periphery structure in massive networks. Core-periphery structure is a meso-scale feature where nodes are grouped into a densely connected core or sparsely connected periphery. To identify such structures in large networks, we propose a divide-and-conquer algorithm. The key feature of our algorithm is leveraging the edge list representation of the network, instead of the adjacency matrix, as it tends to be faster and makes a more efficient use of memory. We apply the proposed algorithm to synthetic and real-world data, notably demonstrating its performance on a real-world network with almost 14 million edges without loading the entire network into memory.
1 Introduction
The paper addresses scalable core-periphery detection in massive networks, where conventional adjacency-matrix methods face storage and memory constraints. It proposes an edge-list-based divide-and-conquer strategy to analyze large networks in smaller pieces.
- Massive networks require scalable algorithms for identifying meso-scale structures such as communities and core-periphery structure.
- Core-periphery structure groups nodes into a densely connected core and a more sparsely connected periphery.
- Sub-sampling analyzes networks in smaller pieces before combining results, but network dependence and topology create additional challenges.
- Existing core-periphery methods have limited scalability because adjacency matrices require O(n^2) storage and must be loaded entirely into memory.
- The proposed method uses edge lists and divide-and-conquer sampling to identify core-periphery structure in massive networks.
2 Methodology
The methodology optimizes a core-periphery objective with greedy label switching and adapts it to edge lists for scalable divide-and-conquer analysis. Edge lists reduce storage and can improve speed for sparse networks, although repeated objective evaluation remains costly.
- Core-periphery optimization: The objective maximizes the Borgatti–Everett core-periphery metric over 2^n possible label assignments, making heuristic optimization necessary.For n = 100, exhaustive search is already impractical.
- Edge-list evaluation: O(n^2) adjacency-matrix evaluation is replaced by O(m) edge-list evaluation for the objective function.The edge-list procedure loops through edges and checks whether either incident node belongs to the core.
- Core-periphery optimization: The method represents networks as edge lists and uses a greedy algorithm to optimize core-periphery labels by accepting objective-improving node swaps.The objective is evaluated for proposed labels, and each swap is retained only when it increases the metric.
- Edge-list evaluation: For sparse networks, edge lists use O(m) storage instead of O(n^2), and the edge-list approach is faster when m = o(n).When m = O(n), speeds are approximately equivalent, but the edge list still uses less space in typical real-world networks.
- Divide-and-conquer: The divide-and-conquer algorithm samples q m edges repeatedly, optimizes labels on each subgraph, and aggregates the resulting core proportions.The approach addresses the base algorithm’s O(nm) cost and its requirement to load the entire network into memory.
3 Experiments
Experiments compare edge-list and adjacency-matrix approaches on synthetic and real-world networks, evaluating runtime, AUC, objective values, and memory use. The divide-and-conquer edge-list method is generally fast and accurate, including on a network with almost 14 million edges.
- Synthetic data: For sparse networks with average density p̄ ≤ 0.006, the edge-list greedy approach is faster than the adjacency-matrix algorithm.Runtime increases with density for both algorithms, but the edge-list method increases more slowly.
- Synthetic data: Both divide-and-conquer algorithms outperform the base greedy algorithm in speed and accuracy on synthetic networks.The divide-and-conquer methods have comparable AUC, while their accuracy exceeds that of the greedy algorithm.
- Synthetic data: For n ≥ 2000, the edge-list divide-and-conquer algorithm is the fastest while retaining AUC comparable to the adjacency-matrix divide-and-conquer method.Both divide-and-conquer methods achieve larger AUC than the greedy algorithm as network size varies.
- Real-world networks: On four real-world networks, Algorithm 3 produces significantly larger objective values than degree ranking, often by at least one order of magnitude.On Twitch, Algorithm 3 achieves an objective value more than 20 times greater than degree ranking.
- Real-world networks: The Google edge list occupies about 0.15 GB, yet the proposed method samples directly from the file without loading the entire edge list into memory.This demonstrates a proof of concept on a personal desktop for a graph with almost 14 million edges.
4 Conclusion
The paper presents an edge-list divide-and-conquer algorithm for core-periphery identification that improves computational speed and memory efficiency. It performs well on synthetic and real-world networks, including one with almost 14 million edges, while larger-scale use depends on hardware and edge-list querying speed.
- The proposed divide-and-conquer algorithm identifies core-periphery structure using an edge-list representation.This representation supports computational speedups and more efficient memory use than an adjacency matrix.
- The algorithm performed well on both synthetic and real-world networks.
- Almost 14 million edges were processed without loading the entire network into memory.
- Scaling to even larger networks is limited by the number of available computing cores and the speed of edge-list queries.Gigabyte-scale edge lists require fast sub-sampling to maintain scalability.
Appendix
The appendix specifies adjacency-matrix procedures for evaluating and greedily optimizing the core-periphery objective function. These routines maintain objective-related quantities while iteratively updating node labels.
- The objective-function evaluation takes an adjacency matrix and core-periphery labels as input, returning the objective value and the number of core-core and core-periphery edges.
- The evaluation procedure initializes summary quantities and accumulates adjacency-matrix entries across node pairs.
- The objective calculation combines observed edge structure with the expected core-periphery edge proportion and overall edge density.
- The objective-function update takes the current labels and a node index, then returns updated labels, the objective value, and the relevant edge count.
- The greedy algorithm randomly orders nodes and retains updates when the new objective value exceeds the current value.