Search

© 2020, Springer Nature Switzerland AG. Furthest Neighbor search in high-dimensional space has been widely used in many applications such as recommendation systems. Because of the “curse of dimensionality” problem, c-approximate furthest neighbor (C-AFN) is a substitute as a trade-off between result accuracy and efficiency. However, most of the current techniques for external memory are only suitable for low-dimensional space. In this paper, we propose a novel algorithm called reverse incremental LSH based on Indyk’s LSH scheme to solve the problem with theoretical guarantee. Unlike the previous methods using hashing scheme, reverse incremental LSH (RI-LSH) is designed for external memory and can achieve a good performance on I/O cost. We provide rigorous theoretical analysis to prove that RI-LSH can return a-AFN result with a constant possibility. Our comprehensive experiment results show that, compared with other-AFN methods with theoretical guarantee, our algorithm can achieve better I/O efficiency.

Triangle listing is an important topic significant in many practical applications. Efficient algorithms exist for the task of triangle listing. Recent algorithms leverage an orientation framework, which can be thought of as mapping an undirected graph to a directed acylic graph, namely oriented graph, with respect to any global vertex order. In this paper, we propose an adaptive orientation technique that satisfies the orientation technique but refines it by traversing carefully based on the out-degree of the vertices in the oriented graph during the computation of triangles. Based on this adaptive orientation technique, we design a new algorithm, namely AOT, to enhance the edge-iterator listing paradigm. We also make improvements to the performance of AOT by exploiting the local order within the adjacent list of the vertices.

Aberrant lncRNA may contributes to development of cancer. It remains, however, a challenge to understand associations between lncRNA and cancer because of complex mechanisms involved in associations and insufficient sample sizes. With unprecedented wealth of lncRNA data, gene expression data and disease status data give us a new opportunity to design machine learning method to investigate underlying association mechanisms. In this paper, we propose a network-driven approach named NLDAM which for lncRNA-disease association mapping. NLDAM detects associations between lncRNA and genes, genes and disease. NLDAM constructs an association network, where nodes represent lncRNA, genes or disease status, and weighted edges represent significance of associations between nodes. NLDAM identifies significant paths from lncRNA to disease based on the weighted scores. The experimental results on synthetic datasets show the advantage of NLDAM in terms of lncRNA selection accuracy than traditional methylation sites search methods (including NTSDMHN and IDHI-MIRW) under false positive control. Furthermore, we applied NLDAM on ovarian cancer data from The Cancer Genome Atlas database and identified significant lncRNA-gene-disease path associations, among which we analyzed top 10 paths associated with oncogenes. We also provide hypothetical biological path associations to explain our findings.

In this chapter, we study edge connectivity-based graph decomposition; that is, each subgraph satisfies a certain edge connectivity requirement.

Due to the abundant runoff and sediment flux from the Yellow River, the Yellow River Delta (YRD) is one of the quickest continent-building areas worldwide. The YRD land area growth rate was controlled mainly by the amount of provided runoff and sediment. In this paper, the runoff and sediment load of Lijin hydro gauge station, located at the entrance of the YRD, are selected as the representatives, and the relationship between the supplements of the water/sediment and the land area is analyzed by correlation methods; besides, the variation trends of the incoming runoff and sediment load are illustrated based on the Mann–Kendal statistics test. The results indicate that, in the period of record, the annual land area is in perfect linear correlation with the accumulated annual runoff, as well with the accumulated annual sediment load; both the annual runoff and annual sediment load fluxes from Lijin station are in significantly decreasing trends. At last, considering the crisis the YRD faced, rational allocation of the water and sediment resources is put forward.

In this chapter, we discuss efficient techniques for computing the minimum degree-based graph decomposition (aka, core decomposition). Preliminaries are given in Section 3.1. A linear-time algorithm is presented in Section 3.2, while h-index-based local algorithms that can be naturally made parallel are presented in Section 3.3.

In this chapter, we present linear heap data structures that will be useful in the remainder of the book for designing algorithms to efficiently process large sparse graphs.

© Springer International Publishing AG, part of Springer Nature 2018. Topological sorting is a fundamental problem in graph analysis. Given the fact that real world graphs grow rapidly so that they cannot entirely reside in main memory, in this paper, we study external memory algorithms for the topological sorting problem. We propose a contraction-expansion paradigm and devise an external memory algorithm based on the paradigm for the topological sorting problem. Our new algorithm is efficient due to the introduction of the new paradigm and can be implemented easily by using the fundamental external memory primitives. We conduct extensive experiments on real and synthesis graphs and the results demonstrate the efficiency of our proposed algorithm.

Computing \(k\text {-}core\)s is a fundamental and important graph problem, which can be applied in many areas, such as community detection, network visualization, and network topology analysis. Due to the complex relationship between different entities, dual graph widely exists in the applications. A dual graph contains a physical graph and a conceptual graph, both of which have the same vertex set. Given that there exist no previous studies on the \(k\text {-}core\) in dual graphs, we formulate a k-connected core (\(k\text {-}CCO\)) model in dual graphs. A \(k\text {-}CCO\) is a \(k\text {-}core\) in the conceptual graph, and also connected in the physical graph. Given a dual graph and an integer k, we propose a polynomial time algorithm for computing all \(k\text {-}CCO\)s. We also propose three algorithms for computing all maximum-connected cores (\(MCCO\)), which are the existing \(k\text {-}CCO\)s such that a \((k+1)\)-\(CCO\) does not exist. We conduct extensive experiments on six real-world datasets and several synthetic datasets. The experimental results demonstrate the effectiveness and efficiency of our proposed algorithms.

Path skyline query is a fundamental problem in bicriteria network analysis and is widely applied in a variety of applications. Given a source s and a destination t in a bicriteria network G, path skyline query aims to identify all the skyline paths from s to t in G. In the literature, \(\mathsf {PSQ}\) is a fundamental algorithm for path skyline query and is also used as a building block for the afterwards proposed algorithms. In \(\mathsf {PSQ}\), a key operation is to record the skyline paths from s to v for each node v that is possible on the skyline paths from s to t. However, to obtain the skyline paths for v, \(\mathsf {PSQ}\) has to maintain other paths that are not skyline paths for v, which makes \(\mathsf {PSQ}\) inefficient. Motivated by this, in this paper, we propose a new algorithm \(\mathsf {PSQ^+}\) for the path skyline query. By adopting an ordered path exploring strategy, our algorithm can totally avoid the fruitless path maintenance problem in \(\mathsf {PSQ}\). We evaluate our proposed algorithm on real networks and the experimental results demonstrate the efficiency of our proposed algorithm. Besides, the experimental results also demonstrate the algorithm that uses \(\mathsf {PSQ}\) as a building block for the path skyline query can achieve a significant performance improvement after we substitute \(\mathsf {PSQ^+}\) for \(\mathsf {PSQ}\).

© Springer International Publishing AG, part of Springer Nature 2018. In this paper, we propose and study a novel cohesive subgraph model, named (k,s)-core, which requires each user to have at least k familiars or friends (not just acquaintances) in the subgraph. The model considers both user engagement and tie strength to discover strong communities. We compare the (k,s)-core model with k-core and k-truss theoretically and experimentally. We propose efficient algorithms to compute the (k,s)-core and decompose the graph by a particular sub-model k-fami. Extensive experiments show (1) our (k,s)-core and k-fami are effective cohesive subgraph models and (2) the (k,s)-core computation and k-fami decomposition are efficient on various real-life social networks.

Higher-order structures, also known as motifs or graphlets, have been recently used to successfully locate dense regions that cannot be detected otherwise by edge-centric methods [8, 89, 90].

Data privacy in location-based services involves two aspects. The location of a user is a kind of private data as many sensitive information can be inferred from it given some background knowledge. On the other hand, the POI database is a great asset to the LBS provider as its construction requires many resources and efforts. In this paper, we propose a method of protecting mutual privacy i.e., the location of the user issuing a query and the POI database of the LBS provider for location-based query processing. Our approach consists of two steps: data preparation and query processing. Data preparation is conducted by LBS itself and is totally an offline computation, while query processing involves some online computation and multiple rounds of communication between LBS and the user. We implement the query processing by two rounds of oblivious transfer extension OT-Extension on two small key sets, resulting an immediate response even on some big POI databases. We also theoretically prove the security and analyze the complexity of our approach. Compared with two state-of-the-art methods, our approach has several orders of magnitude improvement in response time, at the expense of little and acceptable communication cost.