Efficient set representation and membership testing are important in high-speed network measurement. Fast insertions, space efficiency, fast query, and low false positive rate are the core requirements of traffic measurement, but existing solutions, such as hash tables and Bloom filters(BFs), cannot satisfy these requirements simultaneously. The state-of-the-art cuckoo filter and its variants(CFs) rely on the random eviction relocation strategy to resolve hash collisions, improving space utilization while reducing false positives and maintaining high query efficiency. However, CFs suffer a critical challenge in practical applications: insertion could trigger multiple evictions when all candidate buckets for an element are saturated, leading to insertion performance degradation, especially when space utilization exceeds 0.8. To solve the above problem, we propose a novel relocation strategy based on a random graph model, called the local minimum strategy. Our core idea is to use the implicit meaning of the number of evictions in each bucket as an indication to minimize the relocation of elements. We theoretically and experimentally prove that the eviction threshold for each bucket is$O(\log m)$, where$m$is the number of buckets. The threshold establishes the bounds for the probability of a successful insertion. The experimental results show that, the local minimum strategy significantly reduces the number of relocations by 67 %, as well as increasing the insertion throughput by more than 10 %.

As mobile device usage and data traffic increase, the demand for faster data processing becomes crucial. Mobile edge computing (MEC) meets this need by placing servers at the network’s edge for real-time computing. However, fixed terrestrial MEC servers struggle with scalability, limiting their effectiveness. Integrating unmanned aerial vehicles (UAV) with MEC technology offers a promising solution, enhancing communication efficiency and service quality. This paper proposes a joint communication and computation offloading model for coordinated multi-point (CoMP) UAV-assisted MEC networks utilizing hexagonal cell partitioning. Within each cell, a cluster of UAVs, each equipped with its own MEC server and connected to a central server via a reliable backhaul, collaborates to serve terrestrial user equipment. To analyze this system, we develop a unified analytical framework integrating stochastic geometry and queuing theory. Furthermore, we define the success probability of edge computing (SPEC) metric to quantitatively evaluate communication reliability and computational efficiency. Finally, we explore the effects of critical parameters on network performance. Simulation results closely match the theoretical predictions, confirming our proposed model’s validity and our analysis’s accuracy. Notably, our proposed model demonstrates an improvement in SPEC of approximately 57.24% over non-CoMP model and 24.97% over the user-centric CoMP model.

Graphlets are small, connected, and non-isomorphic induced subgraphs that describe the topological structure of a graph. Counting graphlets is a fundamental task in graph mining and social network analysis. It has numerous applications in many fields, including dense subgraph discovery, anomaly detection, etc. Most existing work assumes a static graph. However, graphs are dynamic in the real world, which can be described as graph streams. Counting graphlets in graph streams is a challenge due to the streaming nature of the input. While there have been several studies on counting graphlets in graph streams, these works are limited to simple graphlets like triangles and butterflies. In this paper, we propose SGES algorithm to estimate more complex graphlets in graph streams. In SGES, we first propose an unbiased sampling strategy to maintain fixed-size sampled edges, which in turn allows us to unbiasedly estimate the number of subgraphs and then count graphlets based on the combinational relationship between the number of subgraphs and the number of graphlets. Extensive experiments over large real-world graph streams prove that our algorithm can obtain accurate estimation values of graphlet counts with high throughput.

Service Function Chaining (SFC) dynamically links multiple Virtual Network Functions (VNFs) to provide flexible and scalable network services for network entities and users. Implementing SFCs at the network edge provides instant VNF service yet is confined by the limited edge resources. Existing strategies suggest either to deploy new VNFs for diverse service provision or to deploy more installed VNFs for reliable service provision. However, these one-sided optimizations fail to realize comprehensive improvements in the network service quality. To this end, the motivation of this paper is to consider a more comprehensive SFC deployment plan to provide more efficient network services. In this paper, we propose DeepSFC, an online SFC deployment scheme at network edge. Our DeepSFC considers the impact of resource allocations and deployment locations on the average latency of overall service requests. It realizes an elegant trade-off between the diversity and the availability of SFCs by adopting the Deep Reinforcement Learning (DRL) method. To be specific, we first determine the type and number of VNFs that need to be deployed. Thereafter, we optimize the deployment locations of these chosen VNFs in the service chain, considering the impact of dynamic bandwidth in the real network. For more general scenarios wherein users’ service requirements change or the deployed server crashes, we further relocate the VNF deployment with the joint consideration of performance degradation and migration cost. Evaluation results show that DeepSFC outperforms its competitors in various experimental settings and responds the requests with lower average latency.

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.

To enable secure and effective downlink multiple-input multiple-output (MIMO) transmission, it has recently been proposed to integrate space-time block code (STBC) with spatial modulation (SM) and artificial noise (AN). However, this technique suffers from high detection complexity at the receiver side. In this contribution, therefore, we present an AN-assisted transmission scheme for the quasi-orthogonal space–time block coded receive spatial modulation (QOSTBC-RSM) system while developing two low-complexity detection algorithms. Our simulation results demonstrate that the proposed scheme and the corresponding detection methods are capable of guaranteeing safe transmission and achieving near-optimal bit error rate (BER) performance while significantly reducing computational overhead.

Abstract With the rapid development of information technologies, multi-source heterogeneous data has become an open problem, and the data is usually modeled as graphs since the graph structure is able to encode complex relationships among entities. However, in practical applications, such as network security analysis and public opinion analysis over social networks, the structure and the content of graph data are constantly evolving. Therefore, the ability to continuously monitor and detect interesting patterns on massive and dynamic graphs in real-time is crucial for many applications. Recently, a large group of excellent research works has also emerged. Nevertheless, these studies focus on different updates of graphs and apply different subgraph matching algorithms; thus, it is desirable to review these works comprehensively and give a thorough overview. In this paper, we systematically investigate the existing continuous subgraph matching techniques from the aspects of key techniques, representative algorithms, and performance evaluation. Furthermore, the typical applications and challenges of continuous subgraph matching over dynamic graphs, as well as the future development trends, are summarized and prospected.

Sketches are widely deployed to represent network flows to support complex flow analysis. Typical sketches usually employ hash functions to map elements into a hash table or bit array. Such sketches still suffer from potential weaknesses upon throughput, flexibility, and functionality. To this end, we propose Ark filter, a novel sketch that stores the element information with either of two candidate buckets indexed by the quotient or remainder between the fingerprint and filter length. In this way, no further hash calculations are required for future queries or reallocations. We further extend the Ark filter to enable capacity elasticity and more functionalities (such as frequency estimation and top-$k$query). Comprehensive experiments demonstrate that, compared with Cuckoo filter, Ark filter has$2.08\times$,$1.34\times$, and$1.68\times$throughput of deletion, insertion, and hybrid query, respectively; compared with Quotient filter, Ark filter has$4.55\times$,$1.74\times$, and$22.12\times$throughput of deletion, insertion, and hybrid query, respectively; compared with Bloom filter, Ark filter has$2.55\times$and$2.11\times$throughput of insertion and hybrid query, respectively.

RDF stream processing (RSP) has become a vibrant area of research in the Semantic Web community, which guarantees interoperability and opens up important applications. There have been efforts to extend RDF data and SPARQL query for representing streaming information and continuous querying functionalities. However, existing solutions will incur significant low throughput due to the recomputation of the results from scratch as the window slides. In this paper, we propose a novel graph-based framework, referred as IncTreeRDF, towards continuous SPARQL query evaluation over RDF data streams. Under the framework, the RDF data streams are modeled as streaming graphs; the SPARQL queries are translated into graph patterns and evaluated via continuous sub-graph pattern-matching over streaming RDF graphs. IncTreeRDF employs a query-centric auxiliary data structure called TStore to store some intermediate results, which supports fast incremental maintenance. Based on TStore, we can not only avoid re-computing matches of the query but also prune invalid updates. Besides, we define matching-free update, in which subgraph matching calculation can be avoided under this scenario. Extensive experimental results show that IncTreeRDF significantly outperforms existing competitors.

We consider cyber security as one of the most significant technical challenges in current times. One of the main tasks is to detect anomalous patterns in the network streams as soon as they appear. In order to solve the above problem, previous propositions use statistical or machine learning-based methods to detect anomalous patterns in the network streams. However, these solutions incur significant low efficiency and precision due to the frequent recomputation of the results from scratch and unreasonable assumptions. In graph theory, dense subgraphs can be used to model the anomalous patterns if we abstract the network streams as a dynamic graph. This motivates us to explore dense subgraph discovery under the scenario where the network is updating. In this paper, we propose a graph-based framework, referred to as SAD, towards continuous dense subgraph discovery over network streams. In specific, we design an auxiliary data structure that is a concise representation of intermediate results, and its execution model allows a fast incremental maintenance strategy. In this way, we can detect anomalous patterns in the network streams in near real-time. Experiments demonstrate that SAD can not only get a higher accuracy of 90.2% but also faster than $11.4\times$ times compared to the state-of-the-art anomaly detection algorithms.

The advanced persistent threat (APT) is a stealthy cyber attack perpetrated by a group that gains unauthorized access to a computer network and remains undiscovered to steal specific data and resources. Fast detection and defense of APT attacks are critical tasks in cyber security. Previous works use simple feature extraction and classification methods to distinguish APT information flow from the normal one. However, APT attacks are latent, with very little flow and mixed in many normal information flows. Moreover, APT attacks can adjust their behavior according to the environment, making it challenging to be discovered and extract features. Meanwhile, dynamic information flow tracking (DIFT) is a tool for tracking information flow, which can also adjust the marking strategy according to the environment and is often used to track and detect APT information flow. On the other hand, game theory is a mathematical model that expresses the game of two or more parties. Therefore, this motivates us to model a game theory to solve the above challenge. In this paper, to solve the above obstacles, we propose an intelligent game theory framework named DPS, which models the strategic interaction between APTs and DIFT and aims to get a high reward for DIFT. Our proposed DPS framework utilizes deep reinforcement learning to find the Nash equilibrium. The game model is a nonzero-sum, average reward stochastic game. Specifically, we design a subgraph pruning strategy and deep Q-network to guide the player in exploring new strategies in the information flow graph. Finally, we implement our framework to compute an optimal defender strategy to defend cyber security. Based on 2 real-world datasets, the experiment results demonstrate that the DPS framework can delay APT intrusions under equilibrium in 3 epochs and get a better reward than the Uniform policy.

Abstract Nowadays, the scale of various graphs soars rapidly, which imposes a serious challenge to develop processing and analytic algorithms. Among them, graph pattern matching is the one of the most primitive tasks that find a wide spectrum of applications, the performance of which is yet often affected by the size and dynamicity of graphs. In order to handle large dynamic graphs, incremental pattern matching is proposed to avoid re-computing matches of patterns over the entire data graph, hence reducing the matching time and improving the overall execution performance. Due to the complexity of the problem, little work has been reported so far to solve the problem, and most of them only solve the graph pattern matching problem under the scenario of the data graph varying alone. In this article, we are devoted to a more complicated but very practical graph pattern matching problem, continuous matching of evolving patterns over dynamic graph data, and the investigation presents a novel algorithm for continuously pattern matching along with changes of both pattern graph and data graph. Specifically, we propose a concise representation of partial matching solutions, which can help to avoid re-computing matches of the pattern and speed up subsequent matching process. In order to enable the updates of data graph and pattern graph, we propose an incremental maintenance strategy, to efficiently maintain the intermediate results. Moreover, we conceive an effective model for estimating step-wise cost of pattern evaluation to drive the matching process. Extensive experiments verify the superiority of .

\emphSeasonal periodicity is a frequent phenomenon for social interactions in temporal networks. A key property of this behavior is that it exhibits periodicity for multiple particular periods in temporal networks. Mining such seasonal-periodic patterns is significant since it can indicate interesting relationships between the individuals involved in the interactions. Unfortunately, most previous studies for periodic pattern mining ignore the seasonal feature. This motivates us to explore mining seasonal-periodic subgraphs, and the investigation presents a novel model, called maximal σ-periodic $ømega$-seasonal k-subgraph. It represents a subgraph with size larger than k and that appears at least σ times periodically in at least $ømega$ particular periods on the temporal graph. Since seasonal-periodic patterns do not satisfy the anti-monotonic property, we propose a weak version of support measure with an anti-monotonic property to reduce the search space efficiently. Then, we present an effective mining algorithm to seek all maximal σ-periodic $ømega$-seasonal k-subgraphs. Experimental results on real-life datasets show the effectiveness and efficiency of our approach.

An evolving pattern graph is defined by an initial pattern graph and a graph update stream consisting of edge insertions and deletions. Identifying and monitoring evolving graph patterns in the data graph is important in various application domains such as Cyberthreats surveillance. This motivates us to explore matching patterns with evolvement, and the investigation presents a novel algorithm \incepg for continuously matching of evolving patterns. Specially, we propose a concise representation \Index of partial matching solutions, and its execution model allows fast incremental maintenance. We also conceive an effective model for estimating step-wise cost of pattern evaluation to drive the matching process. Extensive experiments verify the superiority of \incepg.