Sparse matrices are often used to model the interactions among different objects and they are prevalent in many areas including e-commerce, social network, and biology. As one of the fundamental matrix operations, the sparse matrix chain multiplication (SMCM) aims to efficiently multiply a chain of sparse matrices, which has found various real-world applications in areas like network analysis, data mining, and machine learning. The efficiency of SMCM largely hinges on the order of multiplying the matrices, which further relies on the accurate estimation of the sparsity values of intermediate matrices. Existing matrix sparsity estimators often struggle with large sparse matrices, because they suffer from the accuracy issue in both theory and practice. To enable efficient SMCM, in this paper we introduce a novel row-wise sparsity estimator (RS-estimator), a straightforward yet effective estimator that leverages matrix structural properties to achieve efficient, accurate, and theoretically guaranteed sparsity estimation. Based on the RS-estimator, we propose a novel ordering algorithm for determining a good order of efficient SMCM. We further develop an efficient parallel SMCM algorithm by effectively utilizing multiple CPU threads. We have conducted experiments by multiplying various chains of large sparse matrices extracted from five real-world large graph datasets, and the results demonstrate the effectiveness and efficiency of our proposed methods. In particular, our SMCM algorithm is up to three orders of magnitude faster than the state-of-the-art algorithms.

Directed graphs are prevalent in social networks, web networks, and communication networks. A well-known concept of the directed graph is the D-core, or ( k, l )-core, which is the maximal subgraph in which each vertex has an in-degree not less than k and an out-degree not less than l. Computing the non-empty D-cores for all possible values of k and l , a.k.a. D-core decomposition, has found versatile applications spanning social network analysis, community search, and graph visualization. However, existing algorithms of D-core decomposition suffer from efficiency and scalability issues on large graphs, because serial peeling-based algorithms are limited by single-core utilization, while skyline coreness-based methods exhibit notably high time complexity. To tackle these issues, in this paper, we propose efficient parallel algorithms for D-core decomposition by leveraging the computational prowess of multicore CPUs. Specifically, we first propose a novel algorithm that computes the D-cores for each possible k value, by exploiting an implicit level-by-level vertex removal strategy, which not only diminishes dependencies between vertices but also maintains a time complexity akin to that of sequential algorithms. We further develop an advanced algorithm by introducing a novel concept of D-shell, which allows us to curtail redundant computations by reducing the necessary k values when computing corresponding D-cores, and deriving D-cores with larger k values from the D-cores currently computed based on D-shell. Extensive experiments on ten real-world large graphs show that our algorithms are highly efficient and scalable, and the advanced algorithm is up to two orders of magnitude faster than the state-of-the-art parallel decomposition algorithm with 32 threads.