Core decomposition is a fundamental graph problem with large number of applications. Most existing approaches for core assume that the kept in memory machine. Nevertheless, many real-world graphs are big and may not reside memory. In literature, there only one work I/O efficient avoids loading whole However, this approach scalable to handle because it cannot bound size load most parts addition, can hardly updates. paper, we study following semi-external model, which allows node information...

We study the historical connectivity query in temporal graphs where edges continuously arrive. Given an arbitrary time window, and two vertices, problem aims to identify if vertices are connected by a path snapshot of window. The state-of-the-art method designs index based on two-hop cover, updating is costly when new In this paper, we propose framework design novel forest-based for queries. enables us answer queries searching forest. update modifying forest structure. Our techniques also...

Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as temporal graph. However, the information widely neglected by previous studies. Moreover, directly extending existing models may fail to find critical groups graphs, appear unilateral (i.e., one-layer) form. To fill gap, this paper, we propose novel model, called maximal λ -frequency group (MFG)....

Uncertainty in graph data occurs for a variety of reasons, such as noise and measurement errors. Recently, uncertain management analysis have attracted many research attentions. Among them, computing k-cores graphs (aka, (k, η)-cores) is an important problem has emerged applications, example, community detection, protein-protein interaction network influence maximization. Given graph, the η)-cores can be derived by iteratively removing vertex with η-degree less than k updating η-degrees its...

Core decomposition is a fundamental graph problem with large number of applications. Most existing approaches for core assume that the kept in memory machine. Nevertheless, many real-world graphs are too big to reside memory. In this paper, we study I/O efficient following semi-external model, which only allows node information be loaded We propose algorithm and an optimized decomposition. To handle dynamic updates, firstly show our can naturally extended edge deletion. Then, maintenance...

In social network analysis, structural cohesion (or vertex connectivity) is a fundamental metric in measuring the of groups. Given an undirected graph, k-vertex connected component (k-VCC) maximal subgraph whose at least k. A k-VCC has many outstanding properties, such as high cohesiveness, robustness, and overlapping. this paper, given graph G integer k, we study problem computing all k-VCCs G. The general idea for to recursively partition into overlapped subgraphs. We prove upper bound...

Computing top-k nearest neighbors (kNN) is a fundamental problem in road networks. Existing solutions either need complicated parameter configuration index construction or incur high costs when scanning an unbounded number of vertices query processing. In this paper, we propose novel parameter-free index-based solution for the kNN based on concept tree decomposition large Based our structure, efficient and progressive algorithm that returns each result bounded delay. We also optimize which...

Many real-world relationships between entities can be modeled as temporal graphs, where each edge is associated with a timestamp or time interval representing its occurrence. K -core fundamental model used to capture cohesive subgraphs in simple graph and have drawn much research attention over the last decade. Despite widespread research, none of existing works support efficient querying historical k -cores graphs. In this paper, given an integer window, we study problem computing all...

Hypergraphs provide a versatile framework for modeling complex relationships beyond pairwise interactions, finding applications in various domains. k -core decomposition is fundamental task hypergraph analysis that decomposes hypergraphs into cohesive substructures. Existing studies capture the cohesion based on vertex neighborhood size. However, such poses unique challenges, including efficiency of core value updates, redundant computation, and high memory consumption. We observe...

Minimum Spanning Tree (MST) is a fundamental structure in graph analytics and can be applied various applications. The problem of maintaining MSTs dynamic graphs significant, as many real-world are frequently updated. Existing studies on MST maintenance primarily focus theoretical analysis lack practical efficiency. In this paper, we propose novel algorithm to maintain graphs, which achieves high addition the tree structure, our main idea replacement edge for each edge. way, immediately...

Reachability is a fundamental problem in graph analysis. In applications such as social networks and collaboration networks, edges are always associated with timestamps. Most existing works on reachability queries temporal graphs assume that two vertices related if they connected by path non-decreasing timestamps (time-respecting) of edges. This assumption fails to capture the relationship between entities involved same group or activity no time-respecting connecting them. this paper, we...

Graph clustering is a fundamental problem widely experienced across many industries. The structural graph (SCAN) method obtains not only clusters but also hubs and outliers. However, the results closely depend on two sensitive parameters, ϵ μ, while optimal parameter setting depends different properties various user requirements. Moreover, all existing SCAN solutions need to scan at least whole graph, even if small number of vertices belong clusters. In this paper we propose an index-based...

Computing the maximum independent set (MIS) in a graph is fundamental NP-hard problem, which widely adopted many real-world applications. Extensive works have been done on computing an approximate MIS. While highly dynamic property of graphs calls for efficient MIS maintenance solutions, existing computation literature mainly focus single-machine scenario. The assumption that single machine can access whole makes them difficult to be straightforwardly applied large-scale distributed...

The shortest path distance and related concepts lay the foundations of many real-world applications in road network analysis. count has drawn much research attention academia, not only as a closeness metric accompanying shorted but also serving building block centrality computation. This paper aims to improve efficiency counting paths between two query vertices on large network. We propose novel index solution by organizing all tree structure several optimizations speed up construction....

Structural diversity of a vertex refers to the connections within its neighborhood and has been applied in various fields such as viral marketing user engagement. The paper studies querying structural for any query time windows streaming graphs. Existing are limited static graphs which fail capture vertices' diversities snapshots evolving over time. We design an elegant index structure significantly reduce size compared basic approach. propose optimized incremental algorithm update...