Cohesive Subgraph Detection on Large Graphs

University of Technology Sydney. Faculty of Engineering and Information Technology.Graphs have been widely used to model sophisticated relationships between different entities due to their strong representative properties. Social networks, traffic networks, and biological networks are among the applications that benefit from being expressed as graphs. The cohesive subgraph is an essential structure for understanding the organization of many real-world networks, and cohesive subgraph detection is a crucial problem in network analysis. There are many cohesive subgraph models, such as k-core, strongly connected component, and maximum density subgraph. Uncertain graph management and analysis have attracted much research attention. Among them, computing k-cores in uncertain graphs (aka, (k, eta)-cores) is an important problem and has emerged in many applications. However, the existing algorithms for computing (k, eta)-cores heavily depend on the two input parameters k and eta. In addition, computing and updating the eta-degree for each vertex is the costliest component in the algorithm, and the cost is high. To overcome these drawbacks, we propose an index-based solution for computing (k, eta)-cores. The index size is well-bounded by O(m), where m is the number of edges in the graph. Based on the index, queries for any k and eta can be answered in optimal time. We propose an algorithm for index construction with several different optimizations. We also discuss the (k, eta)-core computation when graphs cannot be entirely stored in memory. We adopt the semi-external setting, which allows O(n) memory usage, where n is the number of vertices in the graph. This assumption is reasonable in practice, and it has been widely adopted in massive graph analysis. We design an index-based solution for I/O efficient (k, eta)-core computation. Given the frequent updates in many real-world graphs, detecting strongly connected components (SCC) in dynamic graphs is a very complicated problem. In the thesis, we study the fully dynamic depth-first search (DFS) problem in directed graphs, which is a crucial basis of dynamic SCC detection. In the literature, most works focus on the dynamic DFS 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 several large real-world graphs to practically evaluate the performance of all proposed algorithms