Uncertain graph management and analysis have attracted many research attentions. Among them, computing k-cores in uncertain graphs (aka, (k,)-cores) is an important problem and has emerged in many applications. Given an uncertain graph, the (k,)-cores can be derived by iteratively removing the vertex with an -degree of less than k and updating the -degrees of its neighbors. However, the results heavily depend on the two input parameters k and, and the settings for these parameters are unique to the specific graph structure and the user's subjective requirements. Additionally, computing and updating the -degree for each vertex is costly. To overcome these drawbacks, we have developed an index-based solution for computing (k,)-cores in this paper. The size of the index is well bounded by O(m), where m is the number of edges in the graph. Based on this index, queries can be answered in optimal time. We propose an algorithm for index construction with several different optimizations. We also propose a new algorithm for index construction in external memory, when the uncertain graph cannot be entirely loaded in memory. We conduct extensive experiments on eight real-world datasets to practically evaluate the performance of all the proposed algorithms.

Uncertainty in graph data occurs for a variety of reasons, such as noise and measurement errors. Recently, uncertain graph management and analysis have attracted many research attentions. Among them, computing k-cores in uncertain graphs (aka, (k, η)-cores) is an important problem and has emerged in many applications, for example, community detection, protein-protein interaction network analysis and influence maximization. Given an uncertain graph, the (k, η)-cores can be derived by iteratively removing the vertex with an η-degree of less than k and updating the η-degrees of its neighbors. However, the results heavily depend on the two input parameters k and η, and the settings for these parameters are unique to the specific graph structure and the user's subjective requirements. Additionally, computing and updating the η-degree for each vertex is the most costly component of the algorithm, and that cost is high. To overcome these drawbacks, we have developed an index-based solution for computing (k, η)-cores in this paper. The size of the index is well bounded by O(m), where m is the number of edges in the graph. Based on this index, queries for any k and η can be answered in optimal time. Further, the method is accompanied by several different optimizations to speed up construction of the index. We conduct extensive experiments on eight real-world datasets to practically evaluate the performance of all the proposed algorithms. The results demonstrate that this index-based approach is several orders of magnitude faster at processing queries than the traditional online approaches.?

Depth-first search (DFS) is a fundamental and important algorithm in graph analysis. It is the basis of many graph algorithms such as computing strongly connected components, testing planarity, and detecting biconnected components. The result of a DFS is normally shown as a DFS-Tree. Given the frequent updates in many real-world graphs (e.g., social networks and communication networks), we study the problem of DFS-Tree maintenance in dynamic directed graphs. In the literature, most works focus on the DFS-Tree maintenance problem in undirected graphs and directed acyclic graphs. However, their methods cannot easily be applied in the case of general directed graphs. Motivated by this, we propose a framework and corresponding algorithms for both edge insertion and deletion in general directed graphs. We further give several optimizations to speed up the algorithms. We conduct extensive experiments on 12 real-world datasets to show the efficiency of our proposed algorithms.