Website Fingerprinting (WF) is an emerging traffic analysis technique that enables a passive adversary to infer which websites a user visits. However, most existing studies, whether in single-tab or multi-tab settings, rely on the unrealistic assumption that users only access website homepages, diverging significantly from real-world browsing behavior. Even recent works extending WF to subpages primarily focus on website-level identification, without distinguishing which specific subpages are visited, thereby limiting the attack's granularity and scope. In this paper, we propose HiFi-WF (Hierarchical Fine-grained Website Fingerprinting), a novel framework that breaks the homepage-only assumption and extends WF to multi-tab recognition and fine-grained subpage identification. We formulate the task as a hierarchical multi-label classification problem, jointly modeling the distinctions and correlations between homepages and subpages. To this end, HiFi-WF integrates a unified CNN-based extractor and layered encoder with a Feature Interaction Module based on multi-head cross-attention to capture inter-level dependencies. An Enhanced SubHead enforces hierarchical constraints to suppress invalid subpage predictions, while a cascaded channel–spatial attention mechanism refines discriminative features for precise hierarchical identification. Experimental results demonstrate that HiFi-WF achieves state-of-the-art performance at both hierarchical levels, attaining F1-scores of 92.1% (homepage) and 81.9% (subpage), thereby validating its effectiveness in advancing WF attacks toward realistic, fine-grained, and multi-tab browsing scenarios. Related codes and datasets can be found in https://github.com/wusongyang02-blip/HiFi-WF.

Bipartite graphs are commonly used to model relationships between two distinct entities in real-world applications, such as user-product interactions, user-movie ratings and collaborations between authors and publications. A butterfly (a 2×2 bi-clique) is a critical substructure in bipartite graphs, playing a significant role in tasks like community detection, fraud detection, and link prediction. As more real-world data is presented in a streaming format, efficiently counting butterflies in streaming bipartite graphs has become increasingly important. However, most existing algorithms typically assume that duplicate edges are absent, which is hard to hold in real-world graph streams, as a result, they tend to sample edges that appear multiple times, leading to inaccurate results. The only algorithm designed to handle duplicate edges is FABLE, but it suffers from significant limitations, including high variance, substantial time complexity, and memory inefficiency due to its reliance on a priority queue. To overcome these limitations, we introduce DEABCpro (Duplicate-Edge-Aware Butterfly Counting), an innovative method that uses bucket-based priority sampling to accurately estimate the number of butterflies, accounting for duplicate edges. Compared to existing methods, DEABCpro significantly reduces memory usage by storing only the essential sampled edge data while maintaining high accuracy. We provide rigorous proofs of the unbiasedness and variance bounds for DEABCpro, ensuring they achieve high accuracy. We compare DEABCpro with state-of-the-art algorithms on real-world streaming bipartite graphs. The results show that our DEABCpro outperforms existing methods in memory efficiency and accuracy, while also achieving significantly higher throughput.

Large Language Models (LLMs) have demonstrated remarkable capabilities in natural language processing tasks, yet their application to graph structure analysis, particularly in community search, remains underexplored. Community search, a fundamental task in graph analysis, aims to identify groups of nodes with dense interconnections, which is crucial for understanding the macroscopic structure of graphs. In this paper, we propose GraphCS, a comprehensive benchmark designed to evaluate the performance of LLMs in community search tasks. Our experiments reveal that while LLMs exhibit preliminary potential, they frequently fail to return meaningful results and suffer from output bias. To address these limitations, we introduce CS-Agent, a dual-agent collaborative framework to enhance LLM-based community search. CS-Agent leverages the complementary strengths of two LLMs acting as Solver and Validator. Through iterative feedback and refinement, CS-Agent dynamically refines initial results without fine-tuning or additional training. After the multi-round dialogue, Decider module selects the optimal community. Extensive experiments demonstrate that CS-Agent significantly improves the quality and stability of identified communities compared to baseline methods. To our knowledge, this is the first work to apply LLMs to community search, bridging the gap between LLMs and graph analysis while providing a robust and adaptive solution for real-world applications.

Uncertain butterflies are fundamental and popular graphlet motifs within uncertain bipartite networks, serving as a crucial metric in structural analysis. Despite extensive research have studied butterflies sufficiently on deterministic networks, few of works explore uncertain butterflies. In this paper, we introduce the Most Probable Maximum Weighted Butterfly (MPMB), which holds the highest probability of becoming a maximum weighted butterfly on an uncertain bipartite network. Proved that searching MPMBs is NP-Hard, we then proposed two samplingbased methods, namely Ordering Sampling (OS), and Ordering-Listing Sampling (OLS). The OS method is suitable for singletrial sampling, while the OLS method is optimized for multiple trials, which first finds candidate butterflies in rough before searching MPMBs. Our experimental results indicate that our basic method (OS) performs 1000× faster than the baseline and the optimized method (OLS) achieves another 180× speedup.

Structural graph clustering (SCAN) is one of the most popular graph clustering paradigms, and has attracted plenty of attention recently. Existing solutions assume that the input graphs is homogeneous, i.e., the vertices are of the same type. However, in many real applications, such as bibliographic networks and knowledge graphs, the input graphs is heterogeneous information networks which consist of multi-typed and interconnected objects, which makes SCAN cannot be applied to cluster. Therefore, in this paper, we study the SCAN problem over heterogeneous information networks. Based on the concept of meta-path, we propose two new structural graph clustering models first. Following these two new models, we design new algorithms to support the efficient clustering of a heterogeneous information network. We conduct extensive experiments on six real heterogeneous information networks, and the results demonstrate the effectiveness of our new models and the efficiency of our proposed clustering algorithms.

Bipartite graphs are widely used to model relationships among diverse entities in domains such as gene co-expression networks, collaboration networks, and customer-product interactions. A fundamental problem in analyzing bipartite graphs is the maximum balanced biclique (MBBC) search, which identifies the maximum fully connected subgraph with an equal number of vertices on both sides in the given bipartite graph. Despite its utility, the MBBC model suffers from practical limitations: its strict all-to-all connectivity and exact size-equality requirements make it impractical for noisy, incomplete real-world bipartite data. To overcome these limitations, we propose the maximum balanced k-biplex (MBKBP) model, which relaxes the stringent requirements of MBBC. In MBKBP, each vertex is allowed to miss up to k neighbors on the opposite side of the bipartite graph, and a user-defined parameter$\delta$ensures approximate balance between the two vertex sets. This flexibility enhances robustness to noise, accommodates incomplete data, and broadens the model's applicability. To compute the MBKBP in a given bipartite graph, a baseline approach involves enumerating all maximal balanced k-biplexes and identifying the largest one. However, as confirmed by our experiments, this approach is computationally inefficient. To address this challenge, we introduce the concept of$(z_{L},\ z_{R})$search space and propose a new framework to compute the MBKBP. By generating a series of smaller$(z_{L)}z_{R})$search spaces, our framework significantly reduces the number of maximal k-biplexes that need to be explored. Additionally, we leverage the$\delta$-balance property to refine the search spaces further and develop three categories of pruning rules to minimize computational overhead. Extensive experiments on real-world bipartite graphs demonstrate that our algorithm achieves up to three orders of magnitude speedup compared to baseline approache, showcasing its efficiency and practicality for bipartite graph analysis.

The$k$-truss is a popular cohesive subgraph model for graph analysis, which requires each edge in the subgraph to be contained in at least$k-2$triangles, each consists three pairwisely connected edges. In this paper, we study the$k$-truss breaking problem (TBP) that aims to find the smallest set of edges whose removal makes the graph free of$k$-truss. The problem has been formulated in the literature with applications in community deception, critical connection identification, etc. However, existing solutions cannot scale to large graphs. We observe that chosen edges in a high-quality solution usually have high triangle support, while most share triangles with a significant number of easy-breaking edges (i.e., low-support edges). Motivated by these, we propose the Easy-Breaking Heuristic (EBH) that prioritizes the candidate edges based on their impact on easy-breaking edges. We also design several optimizations to further enhance the performance of EBH. Additionally, we extend our framework to efficiently handle the$k$-truss minimization problem (TMP), which aims to identify a set of at most$b$edges whose removal minimizes the size of the remaining k-truss. Extensive experiments demonstrate that our proposed algorithm outperforms state-of-the-art approaches by up to three orders of magnitude in efficiency when solving TBP, while maintaining comparable effectiveness. Additionally, our proposed algorithm achieves up to four orders of magnitude improvement in efficiency for TMP, along with generally better effectiveness.

The rise of graph analytics platforms has led to the development of various benchmarks for evaluating and comparing platform performance. However, existing benchmarks often fall short of fully assessing performance due to limitations in core algorithm selection, data generation processes (and the corresponding synthetic datasets), as well as the neglect of API usability evaluation. To address these shortcomings, we propose a novel graph analytics benchmark. First, we select eight core algorithms by extensively reviewing both academic and industrial settings. Second, we design an efficient and flexible data generator and produce eight new synthetic datasets as the default datasets for our benchmark. Lastly, we introduce a multi-level large language model (LLM)-based framework for API usability evaluation-the first of its kind in graph analytics benchmarks. We conduct comprehensive experimental evaluations on existing platforms (GraphX, PowerGraph, Flash, Grape, Pregel+, Ligra, and G-thinker). The experimental results demonstrate the superiority of our proposed benchmark.

Triangle counting in hypergraph streams-including both hyper-vertex and hyper-edge triangles-is a fundamental problem in hypergraph analytics, with broad applications. However, existing methods face two key limitations: (i) an incomplete classification of hyper-vertex triangle structures, typically considering only inner or outer triangles; and (ii) inflexible sampling schemes that predefine the number of sampled hyperedges, which is impractical under strict memory constraints due to highly variable hyperedge sizes. To address these challenges, we first introduce a complete classification of hyper-vertex triangles, including inner, hybrid, and outer triangles. Based on this, we develop HTCount, a reservoir-based algorithm that dynamically adjusts the sample size based on the available memory M. To further improve memory utilization and reduce estimation error, we develop HTCount-P, a partition-based variant that adaptively partitions unused memory into independent sample subsets. We provide theoretical analysis of the unbiasedness and variance bounds of the proposed algorithms. Case studies demonstrate the expressiveness of our triangle structures in revealing meaningful interaction patterns. Extensive experiments on real-world hypergraphs show that both our algorithms achieve highly accurate triangle count estimates under strict memory constraints, with relative errors that are 1 to 2 orders of magnitude lower than those of existing methods and consistently high throughput.

Graphs have been widely used to represent the relationships of entities in real-world applications [1], [2]. k-truss model is a typical cohesive subgraph model and has received considerable attention due to its unique cohesive properties on degree and bounded diameter [3], [4].

In many real-world scenarios, relationships between two different entities can be naturally represented as bipartite graphs, such as author-paper, user-item, and people-location. Cohesive subgraph search, which aims to find densely connected subgraphs, is a popular research topic on bipartite graphs. While various cohesive subgraph models are proposed on bipartite graphs, none of them consider the temporal dimension, which expresses dynamic changes occurring in cohesive subgraphs over time. In this paper, we propose the first cohesive subgraph model$(\alpha,\ \beta,\ \mathcal{T})$-core on temporal bipartite graphs. Given degree constraints$\alpha$and$\beta$, as well as a time window$\mathcal{T}=[t_{s},t_{e}],(\alpha,\beta,\ \mathcal{T})$-core guarantees that each vertex in the upper or lower layer has at least$\alpha$or$\beta$neighbors, respectively, within the snapshot over the time window$\mathcal{T}$. An intuitive solution to compute the$(\alpha,\ \beta,\ \mathcal{T})$-core is to iteratively remove the vertices that do not satisfy the degree constraints in the snapshot, which suffers from inefficiency and is impractical on large temporal bipartite graphs. Therefore, we turn to index-based methods to enhance query performance. To support efficient arbitrary$(\alpha,\ \beta,\ \mathcal{T})$-core queries, we propose a vertex-partitioning historical index called VH-Index and a time-partitioning historical index called TH-Index. Note that these two indexes need to store$(\alpha,\ \beta,\ \mathcal{T})$-core for each possible combination of$\alpha, \beta$, and$a\mathcal{T}$and incur large construction costs. Therefore, we further propose a temporal intersection index called TH*-Index to strike a balance between the efficiency of query processing and the space cost of the index. We develop both sequential and parallel algorithms for efficiently constructing the temporal-intersection index. Extensive experiments are conducted on 10 real-world temporal bipartite graphs to validate the effectiveness of the$(\alpha,\ \beta,\ \mathcal{T})$-core model and the efficiency of our proposed algorithms.

With the great amount of available data, especially collected from the ubiquitous Internet of Things (IoT), the issue of privacy leakage has been an increasing concern recently. To preserve the privacy of IoT datasets, traditional methods usually calibrate random noises on the data values to achieve differential privacy (DP) [1]. However, the amount of calibrating noises should be carefully designed and a heedless value will definitely degrade the availability of datasets.

Hop-constrained s-t simple path (HC-s-t path) enu-meration is a fundamental problem in graph analysis. Existing solutions for this problem focus on optimizing the processing performance of a single query. However, in practice, it is more often that multiple H C-s-t path queries are issued simultaneously and processed as a batch. Therefore, we study the problem of batch H C-s-t path query processing in this paper and aim to compute the results of all queries concurrently and efficiently as a batch. To achieve this goal, we first propose the concept of H C-s path query which can precisely characterize the common computation among different queries. We then devise a two-phase H C-s path query detection algorithm to identify the common H C-5 path queries for the given H C-s-t path queries. Based on the detected HC-s path queries, we further devise an efficient HC-s-t path enumeration algorithm in which the common computation represented by H C-s path queries are effectively shared. We conduct extensive experiments on real-world graphs and the experimental results demonstrate that our proposed algorithm is efficient and scalable regarding processing multiple HC-s-t path queries in large graphs at billion-scale.

Top- k Nearest Neighbors ( k NN) problem on road network has numerous applications on location-based services. As direct search using the Dijkstra's algorithm results in a large search space, a plethora of complex-index-based approaches have been proposed to speedup the query processing. However, even with the current state-of-the-art approach, long query processing delays persist, along with significant space overhead and prohibitively long indexing time. In this paper, we depart from the complex index designs prevalent in existing literature and propose a simple index named KNN-Index. With KNN-Index, we can answer a k NN query optimally and progressively with small and size-bounded index. To improve the index construction performance, we propose a bidirectional construction algorithm which can effectively share the common computation during the construction. Theoretical analysis and experimental results on real road networks demonstrate the superiority of KNN-Index over the state-of-the-art approach in query processing performance, index size, and index construction efficiency.

Computing the reachability between two vertices in a graph is a fundamental problem in graph data analysis. Most of the existing works assume that the edges in the graph have no labels, but in many real application scenarios, edges naturally come with edge-labels, and label constraints may be placed on the edges appearing on a valid path between two query vertices. Therefore, we study the label-constrained reachability (LCR) queries in this paper, where we are given a source vertex s , a target vertex t , a label set Δ, and the goal is to check whether there exists any path from s to t such that all the labels of edges on the path belong to Δ. A plethora of methods have been proposed in the literature to support the LCR queries. All these methods take the assumption that the graph is resident in the main memory of a machine. Nevertheless, the graphs in many real application scenarios are generally big and may not reside in memory. In these cases, existing methods suffer from serious scalability problem, i.e., result in huge I/O costs. Motivated by this, in this paper, we study the I/O efficient LCR query problem and aim to efficiently answer the LCR queries when the graph cannot fit in the main memory. To achieve this goal, we propose a reduction-based indexing approach. We introduce two elegant graph reduction operators which aims to reduce the size of the graph loaded in memory while preserving the LCR information among the remaining vertices. With these two operators, we devise an index named LCR-Index and propose algorithms to adaptively construct the index based on the available memory. Equipped with LCR-Index, we can answer a LCR query by only scanning the LCR-Index sequentially. Experiments demonstrate our query processing algorithm can handle graphs with billions of edges.

Shortest path query on road networks is a fundamental problem to support many location-based services and wide variant applications. Contraction Hierarchies(CH) is widely adopted to accelerate the shortest path query by leveraging shortcuts among vertices. However, the state-of-the-art CH construction method named$\mathsf{VCHCons}$suffers from inefficiencies due to their strong reliance on pre-determined vertex order. This leads to the generation of a large number of invalid shortcuts and the limit of parallel processing capability. Motivated by it, in this paper, an innovative CH construction algorithm called$\mathsf{ECHCons}$is devised following an edge-centric paradigm, which addresses the issue of invalid shortcut production by introducing a novel edge-ordering strategy. Furthermore, it optimizes shortcut calculation within a dynamically constructed optimal subgraph, which is significantly smaller than the original network, thus shrinking the traversal space during index construction. To further enhance efficiency and overcome the limitations in parallelism inherent to$\mathsf{VCHCons}$, our approach leverages batch contraction of edges and introduces a well-defined lower bound technique to unlock more efficient parallel computation resources. Our approach provides both theoretical guarantee and practical advancement in CH construction. Extensive and comprehensive experiments are conducted on real road networks. The experimental results demonstrate the effectiveness and efficiency of our proposed approach.

Biclique percolation community (BPC) search is a fundamental problem in bipartite graph analysis and have many applications. Existing online approach has to enumerate all the maximal bicliques and compute the results based on these bicliques. Considering the large number of maximal bicliques in real graphs and the high frequency of BPC search requests issued in real applications, existing approach is cost prohibitive to obtain the result. Motivated by this, we devise an index-based (BPC-Index) approach to address the problem. Based on the index, we can obtain the result in near-optimal time with well-bounded index space. We further devise an efficient index construction algorithm. Moreover, we also extend our indexing method to address the personalized BPC search problem, which is one of the most common variants of BPC search. We conduct extensive experiments on 10 real bipartite graphs, and the experimental results demonstrate the effectiveness of the BPC model, and the efficiency of our BPC search algorithms and index construction algorithms. Remarkably, our approach can achieve up to 8 orders of magnitude speedup compared to the existing online approach.

Shortest path counting computes the number of shortest paths between two vertices on a graph, which can be used in the applications such as social network search and POI (Point of Interest) recommendation. The state-of-the-art approach leverages index to speed up the query processing. However, this approach incurs not only significant space overheads but also prohibitive indexing time, which makes it inapplicable to handle such queries on large graphs. Motivated by this, in this paper, we aim to propose a new solution to scale up the shortest path counting. To achieve this goal, we first propose a novel size-tunable indexing framework, which allows users to tune the index space consumption based on their requirements for query processing efficiency and available memory. Based on the size-tunable indexing framework, we devise a new parallel paradigm to accelerate index construction. We conduct experiments on 15 real graphs and the experimental results demonstrate that our new approach significantly outperforms the state-of-the-art approach regarding the index space cost and index construction cost, and is able to handle billion-scale graphs that the state-of-the-art approach cannot process with less than 5 milliseconds query processing time on all test cases.

A frequency bursting pattern (FBP) in temporal graphs represents some interaction behavior that accumulates its frequency at the fastest rate. Mining FBPs is essential to early warning of emergencies. However, existing studies on frequency-based pattern mining in graphs do not consider the temporal information and bursting features of a subgraph pattern. As a result, they may not provide effective and efficient mining algorithms for FBP discovery. In this paper, we study the problem of discovering top-k FBPs in temporal graphs. We present a novel model, referred to as maximal (m, θ)-bursting pattern, to describe FBPs in a temporal graph, which is a subgraph with a size larger than m that accumulates its frequency at the fastest rate during a time interval of length no less than θ. A naive solution for top-k FBPs discovery is to use the best-first search algorithm, where the burstiness threshold changes as more patterns are mined. However, this method will result in huge search space since we need to check every possible time interval for a candidate pattern in the temporal graph. To tackle this problem, we devise an online top-k framework in which k candidate results are maintained from the initial timestamp to the end in the temporal graph. Under the new framework, we further conceive two optimization strategies by exploiting incremental subgraph matching and Evolutionary Game Theory to boost the performance. Extensive experiment results on five real temporal graphs show that our algorithm has higher efficiency, effectiveness and scalability.

Hop-constrained s-t simple path (k-st path) enumeration is a fundamental problem in graph databases and plays an important role in many real-world applications. Given a dynamic graph G, a source-target pair s-t, and a hop constraint k, we aim to efficiently compute k-st paths: list all simple paths within length k from s to t, and then continuously maintain the results against edge updates. Although the k-st path enumeration has been well studied in static setting, the existing works on static graphs cannot be applied or adapted to handle dynamic graphs efficiently. To address the challenges on dynamic computation, we propose a partial path-based index structure and an efficient enumeration algorithm based on the index. We also propose several well-designed techniques to efficiently maintain the index and locate the affected results with graph updates. Comprehensive experiments verify that our proposed CPEupdatealgorithm outperforms the state-of-the-art methods by up to 4 orders of magnitude on dynamic graphs. The experiment results also show that the time cost of our initialization step CPEstartup(including index construction) is similar to the state-of-the-art static method.

Abstract In the real world, road networks with weight and label on edges can be applied in several application domains. The shortest path query with label restrictions has been receiving increasing attention recently. To efficiently answer such kind of queries, a novel index, namely Contraction Hierarchies with Label Restrictions (CHLR), is proposed in the literature. However, existing studies mainly focus on the static road networks and do not support the CHLR maintenance when the road networks are dynamically changed. Motivated by this, in this paper, we investigate the CHLR maintenance problem in dynamic road networks. We first devise a baseline approach to update CHLR by recomputing the potential affected shortcuts. However, many shortcuts recomputed in baseline do not change in fact, which leads to unnecessary overhead of the baseline. To overcome the drawbacks of baseline, we further propose a novel CHLR maintenance algorithm which can only travel little shortcuts through an update propagate chain with accuracy guarantee. Moreover, an optimization strategy is presented to further improve the efficiency of index maintenance. Considering the frequency of edge changes, we also propose a batch index maintenance algorithm to handle batch edge changes which can process a large number of edge changes at once. Furthermore, a parallel method is proposed to further accelerate calculations. Extensive and comprehensive experiments are conducted on real road networks. The experimental results demonstrate the efficiency and effectiveness of our proposed algorithms.

$k$-truss model is a typical cohesive subgraph model and has been received considerable attention recently. However, the$k$-truss model only considers the direct common neighbors of an edge, which restricts its ability to reveal fine-grained structure information of the graph. Motivated by this, in this paper, we propose a new model named$(k, \tau)$-truss that considers the higher-order neighborhood ($\tau$hop) information of an edge. Based on the$(k, \tau)$-truss model, we study the higher-order truss decomposition problem which computes the$(k, \tau)$-trusses for all possible$k$values regarding a given$\tau$. Higher-order truss decomposition can be used in the applications such as community detection and search, hierarchical structure analysis, and graph visualization. To address this problem, we first propose a bottom-up decomposition paradigm in the increasing order of$k$values to compute the corresponding$(k, \tau)$-truss. Based on the bottom-up decomposition paradigm, we further devise three optimization strategies to reduce the unnecessary computation. We evaluate our proposed algorithms on real datasets and synthetic datasets, the experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms.

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. However, in real world, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks. Following the balanced clique model, we study themaximalbalancedcliqueenumeration problem (${\mathsf {MBCE}}$) which computes all the maximal balanced cliques in a given signed network. Moreover, in some applications, users prefer a unique and representative balanced clique with maximum size rather than all balanced cliques. Thus, we also study themaximumbalancedcliquesearch problem (${\mathsf {MBCS}}$) which computes the balanced clique with maximum size. We show that${\mathsf {MBCE}}$problem and${\mathsf {MBCS}}$problem are both NP-Hard. For the${\mathsf {MBCE}}$problem, a straightforward solution is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. For the${\mathsf {MBCS}}$problem, we first propose a baseline solution. To overcome the huge search space problem of the baseline solution, we propose a new search framework based on search space partition. To further improve the efficiency of the new framework, we propose multiple optimization strategies regarding to redundant search branches and invalid candidates. We conduct extensive experiments on large real datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms for${\mathsf {MBCE}}$problem and${\mathsf {MBCS}}$problem.

With the great amount of available data, especially collecting from the ubiquitous Internet of Things (IoT), the issue of privacy leakage arises increasingly concerns recently. To preserve the privacy of IoT datasets, traditional methods usually calibrate random noises on the data values to achieve differential privacy (DP). However, the amount of the calibrating noises should be carefully designed and a heedless value will definitely degrade the availability of datasets. Thus, in this work, we propose a stochastic perturbation method to sanitize the dataset, where the perturbation is obtained from the rest samples in the same dataset. In addition, we derive the expression of the utility level based on its unique framework and prove that the proposed algorithm can achieve the$\epsilon$-DP. To show the effectiveness of the proposed algorithm, we conduct extensive experiments on real-life datasets by various functions, such as query answers and machine learning tasks. By comparing with the state-of-the-art methods, our proposed algorithm can achieve a better performance under the same privacy level.

Structural clustering (SCAN) is one of the most popular graph clustering paradigms. However, SCAN assumes that the input graph is undirected and can not cluster the directed graphs. To address this problem, in this paper, we propose a new structural clustering model based on SCAN to cluster directed graphs. Following the new model, we propose an index-based approach to support the efficient clustering of a given graph. Moreover, we also devise efficient index maintenance algorithms to handle the case that the input graph is dynamically updated. We conduct extensive experiments on nine real directed graphs, one of which contains more than 2 billion edges. The results demonstrate the effectiveness and efficiency of our proposed methods.

The shortest-path query, which returns the shortest path between two vertices, is a basic operation on complex networks and has numerous applications. To handle shortest-path queries, one option is to use traversal-based methods (e.g., breadth-first search); another option is to use extension-based methods, i.e., extending existing methods that use indexes to handle shortest-distance queries to support shortest-path queries. These two types of methods make different trade-offs in query time and space cost, but comprehensive studies of their performance on real-world graphs are lacking. Moreover, extension-based methods usually use extra attributes to extend the indexes, resulting in high space costs. To address these issues, we thoroughly compare the two types of methods mentioned above. We also propose a new extension-based approach, Monotonic Landmark Labeling (MLL), to reduce the required space cost while still guaranteeing query time. We compare the performance of different methods on ten large real-world graphs with up to 5.5 billion edges. The experimental results reveal the characteristics of various methods, allowing practitioners to select the appropriate method for a specific application.

Hop-constrained s-t simple path (HC-s-t path) enumeration is a fundamental problem in graph analysis and has received considerable attention recently. Straightforward distributed solutions are inefficient and suffer from poor scalabiltiy when addressing this problem in billion-scale graphs due to the disability of pruning fruitless exploration or huge memory consumption. Motivated by this, in this paper, we aim to devise an efficient and scalable distributed algorithm to enumerate the HC-s-t paths in billion-scale graphs. We first propose a new hybrid search paradigm tailored for HC-s-t path enumeration. Based on the new search paradigm, we devise a distributed enumeration algorithm following the divide-and-conquer strategy. The algorithm can not only prune fruitless exploration, but also well bound the memory consumption with high parallelism. We also devise an effective workload balance mechanism that is automatically triggered by the idle machines to handle skewed workloads. Moreover, we explore the bidirectional search strategy to further improve enumeration efficiency. The experiment results demonstrate the efficiency of our proposed algorithm.

Computing the shortest path between two vertices is a fundamental problem in road networks. Most of the existing works assume that the edges in the road networks have no labels, but in many real applications, the edges have labels and label constraints may be placed on the edges appearing on a valid shortest path. Hence, we study the label-constrained shortest path queries in this paper. In order to process such queries efficiently, we adopt an index-based approach and propose a novel index structure, LSD-Index, based on tree decomposition. With LSD-Index, we design an efficient query processing algorithm with good performance guarantees. Moreover, we also propose an algorithm to construct LSD-Index and further improve the efficiency of index construction by exploiting the parallel computing techniques. We conduct extensive performance studies using large real road networks including the whole USA road network. Compared with the state-of-the-art approach, the experimental results demonstrate that our algorithm not only achieves up to 2 orders of magnitude speedup in query processing time but also consumes much less index space. Meanwhile, the indexing time is also competitive, especially that for the parallel index construction algorithm.

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. In real world, however, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks, and study the maximal balanced clique enumeration problem which computes all the maximal balanced cliques in a given signed network. We show that the maximal balanced clique enumeration problem is NP-Hard. A straightforward solution for the maximal balanced clique enumeration problem is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. We conduct extensive experiments on large real and synthetic datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms.

Computing the shortest path between two vertices is a fundamental problem in road networks that is applied in a wide variety of applications. To support efficient shortest path query processing, a plethora of index-based methods have been proposed in the literature, but few of them can support dynamic road networks commonly encountered in practice, as their corresponding index structures cannot be efficiently maintained when the input road network is dynamically updated. Motivated by this, we study the shortest path index maintenance problem on dynamic road networks in this paper. We adopt Contraction Hierarchies (CH) as our underlying shortest path computation method because of its outstanding overall performance in pre-processing time, space cost, and query processing time and aim to design efficient algorithms to maintain the index structure, shortcut index , of CH when the input road network is dynamically updated. To achieve this goal, we propose a shortcut-centric paradigm focusing on exploring a small number of shortcuts to maintain the shortcut index. Following this paradigm, we design an auxiliary data structure named SS-Graph and propose a shortcut weight propagation mechanism based on the SS-Graph. With them, we devise efficient algorithms to maintain the shortcut index in the streaming update and batch update scenarios with non-trivial theoretical guarantees. We experimentally evaluate our algorithms on real road networks and the results demonstrate that our approach achieves 2--3 orders of magnitude speedup compared to the state-of-the-art algorithm for the streaming update.

Community search is important in graph analysis and can be used in many real applications. In the literature, various community models have been proposed. However, most of them cannot well identify the overlaps between communities which is an essential feature of real graphs. To address this issue, k-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the k-clique percolation community model and study the densest clique percolation community search problem which aims to find the k-clique percolation community with the maximum k value that contains a given set of query nodes. We adopt an index based approach to solve this problem. Based on the observation that a k-clique percolation community is a union of maximal cliques, we devise a novel compact index, DCPC-Index, to preserve the maximal cliques and their connectivity information of the input graph. With DCPC-Index, we can answer the densest clique percolation community query efficiently. Besides, we also propose an index construction algorithm based on the definition of DCPC-Index and further improve the algorithm in terms of efficiency and memory consumption. We conduct extensive performance studies on real graphs and the experimental results demonstrate the efficiency of our index-based query processing algorithm and index construction algorithm.

The problem of computing (α, β)-core in a bipartite graph for given α and β is a fundamental problem in bipartite graph analysis and can be used in many applications such as online group recommendation, fraudsters detection, etc. Existing solution to computing (α, β)-core needs to traverse the entire bipartite graph once. Considering the real bipartite graph can be very large and the requests to compute (α, β)-core can be issued frequently in real applications, the existing solution is too expensive to compute the (α, β)-core. In this paper, we present an efficient algorithm based on a novel index such that the algorithm runs in linear time regarding the result size (thus, the algorithm is optimal since it needs at least linear time to output the result). We prove that the index only requires O(m) space where m is the number of edges in the bipartite graph. Moreover, we devise an efficient algorithm with time complexity O(δ·m) for index construction where δ is bounded by √m and is much smaller than √m in practice. We also discuss efficient algorithms to maintain the index when the bipartite graph is dynamically updated and parallel implementation of the index construction algorithm. The experimental results on real and synthetic graphs (more than 1 billion edges) demonstrate that our algorithms achieve up to 5 orders of magnitude speedup for computing (α, β)-core and up to 3 orders of magnitude speedup for index construction, respectively, compared with existing techniques.

Community search is important in graph analysis and can be used in many real applications. In the literature, various community models have been proposed. However, most of them cannot well identify the overlaps between communities which is an essential feature of real graphs. To address this issue, the k-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the k-clique percolation community model and study the densest clique percolation community search problem which aims to find the k-clique percolation community with the maximum k value that contains a given set of query nodes. We adopt an index-based approach to solve this problem. Based on the observation that a k-clique percolation community is a union of maximal cliques, we devise a novel compact index, DCPC-Index, to preserve the maximal cliques and their connectivity information of the input graph. With DCPC-Index, we can answerthe densest clique percolation community query efficiently. Besides, we also propose an index construction algorithm based on the definition of DCPC-Index and further improve the algorithm in terms of efficiency and memory consumption. We conduct extensive performance studies on real graphs and the experimental results demonstrate the efficiency of our index-based query processing algorithm and index construction algorithm.

Graph coloring is a fundamental graph problem that is widely applied in a variety of applications. The aim of graph coloring is to minimize the number of colors used to color the vertices in a graph such that no two incident vertices have the same color. Existing solutions for graph coloring mainly focus on computing a good coloring for a static graph. However, since many real-world graphs are highly dynamic, in this paper, we aim to incrementally maintain the graph coloring when the graph is dynamically updated. We target on two goals: high effectiveness and high efficiency. To achieve high effectiveness, we maintain the graph coloring in a way such that the coloring result is consistent with one of the best static graph coloring algorithms for large graphs. To achieve high efficiency, we investigate efficient incremental algorithms to update the graph coloring by exploring a small number of vertices. We design a color-propagation based algorithm which only explores the vertices within the 2-hop neighbors of the update-related and color-changed vertices. We then propose a novel color index to maintain some summary color information and, thus, bound the explored vertices within the neighbors of these vertices. Moreover, we derive some effective pruning rules to further reduce the number of propagated vertices. The experimental results demonstrate the high effectiveness and efficiency of our approach.

The problem of computing k -edge connected components ( k -ECCs) of a graph G for a specific k is a fundamental graph problem and has been investigated recently. In this paper, we study the problemof ECC decomposition, which computes the k -ECCs of a graph G for all k values. ECC decomposition can be widely applied in a variety of applications such as graph-topology analysis, community detection, Steiner component search, and graph visualization. A straightforward solution for ECC decomposition is to apply the existing k -ECC computation algorithm to compute the k -ECCs for all k values. However, this solution is not applicable to large graphs for two challenging reasons. First, all existing k -ECC computation algorithms are highly memory intensive due to the complex data structures used in the algorithms. Second, the number of possible k values can be very large, resulting in a high computational cost when each k value is independently considered. In this paper, we address the above challenges, and study I/O efficient ECC decomposition via graph reduction. We introduce two elegant graph reduction operators which aim to reduce the size of the graph loaded in memory while preserving the connectivity information of a certain set of edges to be computed for a specific k . We also propose three novel I/O efficient algorithms, Bottom-Up, Top-Down, and Hybrid, that explore the k values in different orders to reduce the redundant computations between different k values. We analyze the I/O and memory costs for all proposed algorithms. In our experiments, we evaluate our algorithms using seven real large datasets with various graph properties, one of which contains 1.95 billion edges. The experimental results show that our proposed algorithms are scalable and efficient.

Maximal clique enumeration is a fundamental problem in graph theory and has been extensively studied. However, maximal clique enumeration is time-consuming in large graphs and always returns enormous cliques with large overlaps. Motivated by this, in this paper, we study the diversified top-k clique search problem which is to find top-k maximal cliques that can cover most number of nodes in the graph. Diversified top-k clique search can be widely used in a lot of applications including community search, motif discovery, and anomaly detection in large graphs. A naive solution for diversified top-k clique search is to keep all maximal cliques in memory and then find k of them that cover most nodes in the graph by using the approximate greedy max k-cover algorithm. However, such a solution is impractical when the graph is large. In this paper, instead of keeping all maximal cliques in memory, we devise an algorithm to maintain k candidates in the process of maximal clique enumeration. Our algorithm has limited memory footprint and can achieve a guaranteed approximation ratio. We also introduce a novel light-weight PNP-Index, based on which we design an optimal maximal clique maintenance algorithm. We further explore three optimization strategies to avoid enumerating all maximal cliques and thus largely reduce the computational cost. We conduct extensive performance studies on six real graphs one of which contains 0.3 billion edges, and the results demonstrate the high efficiency and effectiveness of our approach.