$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 the m aximal b alanced c lique e numeration problem (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 the m aximum b alanced c lique s earch problem (MBCS) which computes the balanced clique with maximum size. We show that MBCE problem and MBCS problem are both NP-Hard. For the 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 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 MBCE problem and MBCS problem.

Bipartite graphs are widely used to capture the relationships between two types of entities. In bipartite graph analysis, finding the maximum balanced biclique (MBB) is an important problem with numerous applications. A biclique is balanced if its two disjoint vertex sets are of equal size. However, in real-world scenarios, each vertex is associated with a weight to denote its properties, such as influence, i.e., weighted bipartite graph. For weighted bipartite graphs, the previous studies for MBB are no longer applicable due to the ignorance of weight. To fill the gap, in this paper, we propose a reasonable definition of “balance” by restricting the weight difference between two sides of a biclique within $k$ . Given a weighted bipartite graph $G$ and a constraint $k$ , we aim to find the maximum $k$ -balanced biclique (Max $k$ BB) with the maximum weight. To address the problem, we first propose an approach based on biclique enumeration on single side of $G$ following the Branch-and-Bound framework. To improve the performance, we further devise three optimization strategies to prune invalid search branches. Moreover, we utilize graph reduction strategy to reduce the redundant search space. Extensive experiments are conducted on 12 real bipartite datasets to demonstrate the efficiency, effectiveness and scalability of our proposed algorithms. The experimental results show that our algorithms can address MBB detection problem efficiently, and the case study demonstrates the effectiveness of our model compared with MBB model.

The act of website fingerprinting, which involves monitoring traffic features to infer private user information, has attracted much attention in the research community recently. While previous studies primarily focused on classifying fingerprint information using clean traffic data, it remains a challenging task to apply fingerprinting to noisy traffic data or evade defensive measures. This work aims to address the challenges associated with website fingerprinting attacks and defense strategies in the presence of noise. Specifically, we introduce two novel attack methods: filter-assisted attack and augmentation-assisted attack. The first attack method leverages packet size distribution to effectively filter out noise, while the second one trains a classification model by incorporating artificial noise. Compared with the traditional website fingerprinting attacks, these proposed attack methods demonstrate superior resilience to noise and exceptional evasion capabilities against defensive measures (e.g., random packet defense, Walkie-Talkie, WTF-PAD, etc.). In parallel, we propose a list-assisted defense strategy that strikes a balance between defense performance and network overhead. This defense mechanism offers effective protection against website fingerprinting attacks while minimizing the impact on network performance. In our experiments, we employ a comprehensive dataset encompassing TCP/IP traffic with packet size information collected from three prominent web browsers, as well as Tor cell traffic without packet size information obtained from a Tor browser. We thoroughly evaluate our proposed methods in both closed-world and open-world scenarios. Our experimental results shed valuable insights into the influence of noise and the efficacy of different attack and defense approaches on website fingerprinting.

Graph as one of the most fundamental and representative data structures has found a wide spectrum of emerging application domains such as social media, financial transactions, biology science, and road networks. Recently, with the proliferation of graph applications, graph processing has attracted much attention in both industry and academia. Among them, most existing works focus on the static graphs in which the vertices and edges are immutable. However, in the real world, graphs are constantly and dynamically changing, bringing tricky challenges to process such dynamic graphs. This paper surveys the recent advances in dynamic graph processing, including centrality, graph coloring, cohesive subgraph, path traversal, and graph separation. We summarize the computational complexity models for dynamic algorithm analysis, theoretically compare the efficiency of algorithms among different research topics. Moreover, we also explore the research opportunities for the future.