Unboundedness and efficiency in graph computation

Ph.D.Due to the ubiquity of graphs, graph analytics has attracted much attention from both research and industry communities. Among many important topics in graph analytics, dense subgraph discovery is a prominent topic in analyzing social networks, web networks and the like. Due to their polynomial-time computability and their ability to capture dense regions in a graph, two dense subgaph formulations, namely k-core and k-truss, have been widely employed. Though the problem of computing these two notions in static graphs has been thoroughly studied in the literature, the state-of-the-art solutions for maintaining them under graph updates are far from satisfactory. For this reason, in this thesis, we study both core maintenance and truss maintenance in evolving graphs and accordingly devise efficient incremental algorithms. An incremental algorithm is desired to be bounded; that is, its cost is of O(f(||CHANGED||c)) for some polynomial function f and some positive integer c, where CHANGED comprises the changes to both the graph and the result and ||CHANGED||c is the size of the c-hop neighborhood of CHANGED. An incremental problem is bounded if it has a bounded incremental algorithm and is unbounded otherwise. We study the (un)boundedness of both core maintenance and truss maintenance and show that the algorithms proposed are near bounded. This is one of few efforts to study the (un)boundedness of incremental graph problems.Shortest path related problems are another important topic in graph analytics. In this thesis, we in addition study the problem of efficiently counting shortest paths between two given vertices. To this end, we propose a framework based on the notion of exact shortest path covering to construct a 2-hop labeling L(·) such that for any two vertices s and t, the number of shortest paths between them can be easily calculated based on L(s) and L(t).Our extensive performance studies validate the efficiency of all our algorithms.图数据是一种被广泛应用的数据类型，因此基于图的数据分析一直都是学术界和工业界的研究热点。计算出一张给定的图中的紧密子图是图分析中一个非常重要的问题。k-core和k-truss作为两种被经常使用的紧密子图，在提供高质量保证的同时，也具有多项式可算的优点。如何在静态图中快速地计算这两种紧密子图已经是一个被研究得比较透彻的问题，但如何在图持续被改动的情况下高效地维护一张图的k-core和k-truss却是一个仍然需要更深入的研究的问题：当改动较大的情况下，已知的算法都不能做到比重头计算快。因此，在这篇学位论文中，我们系统研究了core和truss的维护问题，并相应地提出了实际可行的高效增量算法。我们说一个增量算法是有界的，如果它的复杂度可以用O(f(IICHANGEDIIc))表示。这里，CHANGED表示图自身的改动（新增的点、边和被删的点、边）和图的改动所造成的结果的改动；IICHANGEDIIc表示以CHANGED为中心、半径为c的邻域；f表示一个多项式。一个增量问题（动态问题）是有界的，如果它有一个有界的增量算法；否则，这个问题就是无界的。我们研究了core和truss的维护的有（无）界性并证明了我们提出的算法是实际应用中是接近有界的。最短路相关的问题是图分析中的另一个热点。在这篇论文中，我们研究了如何快速地计算出两个点之间的最短路的数量。我们提出了一个基于精确最短路覆盖的框架，进而能构造出一个标签函数L(·)，使得：给定两个点s和t，通过检查L(s)和L(t)，我们能很快地计算出两点间最短路的数量。我们大量的实验结果证实我们提出的算法的确是高效可靠的。Zhang, Yikai.Thesis Ph.D. Chinese University of Hong Kong 2019.Includes bibliographical references (leaves 104-113).Abstracts also in Chinese.Title from PDF title page (viewed on 23, December, 2020)