Given a directed graph$G$and two non-negative integers$k$and$l$, a D-core, or ($k$, l)-core, is the maximal subgraph$H\subseteq G$where each vertex in$H$has an in-degree and out-degree not smaller than$k$and$I$, respectively. D-cores have found extensive applications, such as social network analysis, fraud detection, and graph visualization. In these applications, graphs are highly dynamic and frequently updated with the insertions and deletions of vertices and edges, making it costly to recompute the D-cores from scratch to handle the updates. In the literature, the peeling-based algorithm has been proposed to handle D-core maintenance. However, the peeling-based method suffers from efficiency issues, e.g., it may degenerate into recomputing all the D-cores and is inefficient for batch updates due to sequential processing. To address these limitations, we introduce novel algorithms for incrementally maintaining D-cores in dynamic graphs. We begin by presenting the theoretical findings to identify the D-cores that should be updated. By leveraging these theoretical analysis results, we propose a local-search-based algorithm with optimizations to handle single-edge insertions and deletions. We further propose an H-index-based algorithm for scenarios involving batch updates. Several novel edge-grouping strategies are proposed to improve the efficiency of the H-index-based algorithm. Extensive empirical evaluations over both real-world and synthetic networks demonstrate that our proposed algorithms are up to 5 orders of magnitude faster than the peeling-based method.

Community search aims to retrieve dense subgraphs that contain the query vertices. While many effective community models and algorithms have been proposed in the literature, none of them address the unique challenges posed by streaming graphs, where edges are continuously generated over time. In this paper, we investigate the problem of truss-based community search over streaming directed graphs. To address this problem, we first present a peeling-based algorithm that iteratively removes edges that do not meet the support constraints. To improve the efficiency of the peeling-based algorithm, we propose three optimizations that leverage the time information of the streaming graph and the structural information of trusses. As the peeling-based algorithm may suffer from inefficiency when the input peeling graph is large, we further propose a novel order-based algorithm that preserves the community by maintaining the deletion order of edges in the peeling algorithm. Extensive experimental results on real-world datasets show that our proposed algorithms outperform the baseline by up to two orders of magnitude in terms of throughput.

(α, β)-core is an important cohesive subgraph model for bipartite graphs. Given a bipartite graph G, the problem of (α, β)-core decomposition is to compute non-empty (α, β)-cores for all possible values of α and β. The state-of-the-art (α, β)-core decomposition algorithm is a peeling-based algorithm, which iteratively deletes the vertex from high degree to low degree. However, as the peeling-based algorithm is designed for centralized environments, it cannot be applied to distributed environments, where graphs are partitioned and stored in different machines. Motivated by this, in this paper, we study the distributed (α, β)-core decomposition problem, aiming to develop new algorithms to support (α, β)-core decomposition in distributed environments. To this end, first, we analyze the local properties of (α, β)-core, and devise n-order Bi-indexes for the vertex, which are iteratively defined using the vertex neighbors’ (n − 1)-order Bi-indexes. Next, we propose an algorithm for (α, β)-core decomposition through iteratively calculating n-order Bi-indexes for every vertex. To further improve the efficiency of the algorithm, we propose two optimizations. Then, we extend our proposed algorithms to different distributed graph processing frameworks to make them run in distributed environments. Finally, extensive experimental results on both real and synthetic bipartite graphs demonstrate the efficiency of our proposed algorithms.

Given a directed graph G and integers k and l , a D-core is the maximal subgraph H ⊆ G such that for every vertex of H , its in-degree and out-degree are no smaller than k and l , respectively. For a directed graph G , the problem of D-core decomposition aims to compute the non-empty D-cores for all possible values of k and l. In the literature, several peeling-based algorithms have been proposed to handle D-core decomposition. However, the peeling-based algorithms that work in a sequential fashion and require global graph information during processing are mainly designed for centralized settings, which cannot handle large-scale graphs efficiently in distributed settings. Motivated by this, we study the distributed D-core decomposition problem in this paper. We start by defining a concept called anchored coreness , based on which we propose a new H-index-based algorithm for distributed D-core decomposition. Furthermore, we devise a novel concept, namely skyline coreness , and show that the D-core decomposition problem is equivalent to the computation of skyline corenesses for all vertices. We design an efficient D-index to compute the skyline corenesses distributedly. We implement the proposed algorithms under both vertex-centric and block-centric distributed graph processing frameworks. Moreover, we theoretically analyze the algorithm and message complexities. Extensive experiments on large real-world graphs with billions of edges demonstrate the efficiency of the proposed algorithms in terms of both the running time and communication overhead.