The explosive growth of multimodal web data demands communication that transmits meaning rather than raw bits. Existing semantic-communication systems often fail under noise, missing modalities, and distribution shifts because they optimize surface features instead of modality-invariant knowledge. We present Grasp, a knowledge-centric framework for cross-modal communication. Grasp segments streams into semantic blocks and builds a graph over them; a lightweight Graph Neural Networks (GNN) produces schedulable, importance-weighted representations. At its core is knowledge purification : we minimize a conditional mutual information upper bound to perform a three-way disentanglement—strongly related, weakly related, and task-irrelevant components—so that only essential semantics are transmitted while non-essential factors are suppressed. To maintain synchrony, we introduce one-to-two temporal contrastive learning to achieve triple alignment of video, audio, and text despite sampling asynchrony. For efficient transmission, Grasp uses a cross-modal shared vector-quantization codebook—a discrete knowledge codebook —updated by multimodal attention. At the receiver, a soft-recovery mechanism leverages this shared knowledge to robustly reconstruct semantics under low signal-to-noise ratio (SNR) or missing modalities, yielding graceful degradation. Across web tasks—including cross-modal retrieval and missing-modality inference—Grasp improves knowledge consistency, semantic fidelity, and downstream performance over strong baselines while maintaining low latency. These results show that communication structured around purified knowledge is key to building robust, semantic-aware systems for the modern web.

Cyclic fault diagnosis is crucial for ensuring system reliability, as it facilitates the early detection and resolution of recurring failures, minimizing downtime and maintenance costs. Existing methods often face challenges with high computational complexity and scalability, limiting their real-time applicability in complex networks like Bijective Connection (BC) networks, where rapid fault isolation is essential. In this paper, we explore the cyclic diagnosability ofg-BC networks under two classical system-level fault diagnosis models: the P/M/C model and the MM* model. Cyclic diagnosability, which focuses on maintaining connectivity with cycles in the residual subgraph after failures, is a more robust measure than traditional diagnosability. We prove that for anyg-BC networkg-Xnthat satisfies Definition 3, the cyclic diagnosability is given byct(g-Xn) = 5n− 8 −gforg= 1,n≥ 12 and 2 ≤g≤ 5,n≥ 11 under both models, thereby determining the maximum number of faults that can be accurately identified while preserving at least two cyclic components. To support practical diagnosis under these models, we propose two fast and scalable algorithms with low time complexity: TDPMC (Threshold-Based Fault Diagnosis under the P/M/C Model forg-BC Networks) and FBDMM (Suspicion-Score-Based MM* Fault Diagnosis with Dynamic Threshold forg-BC Networks). Both methods exploit the topological features of BC networks to efficiently identify cyclic faults. The time complexities of TDPMC and FBDMM areO(nN) andO(n2N), respectively. Experimental results on an 11-dimensional and 12-dimensionalg-BC networks validate the theoretical findings, demonstrating significant improvements in accuracy, recall, and fault detection reliability.

With the rapid development of cloud computing, big data, and artificial intelligence, data center networks have become the core of modern computing infrastructure. As an important type of data center network, determining theh-component diagnosability ofk-dimensional DCell networksDCellk,nwith n-port switch has become a critical issue for enhancing network’s diagnostic capabilities and assessing network’s vulnerability. However, there is currently scarce research on the h-component diagnosability ofDCellk,nbased on the mutual testing model. In this paper, we innovatively propose theh-component diagnosability and diagnostic algorithm of DCell networks based on the mutual testing model. We first theoretically prove and determine that the h-component diagnosability of DCellk,n is ctPMC h (DCellk,n) = (h− 1)n + hk− (2h− 2) for 2 ≤h≤ 3 andk≥ (h− 2)n+ (4 −h),n≥h+ 1. It implies that the data center networkDCellk,ncan identify (h− 1)n+hk− (2h− 2) faulty nodes when the count of remaining components is at leasth(2 ≤ h ≤ 3). Furthermore, we also propose a novel and broadly applicableh-componentt-diagnosable algorithm ICFD-P based on iterative testing, combinatorial properties and linearly many fault analysis to diagnose all faulty nodes inDCellk,n, effective as a general framework in interconnection networks. We apply the algorithm ICFD-P to simulated data and real data to diagnose faulty nodes. The simulation experiments highlight the effectiveness and robustness of the designed ICFD-P strategy within and even beyond the allowed range of diagnosability inDCellk,n, combined with its enhanced fault diagnosis capability and theoretical foundation for reliability and security, make it a valuable tool for maintaining the stability and security of such networks.

Data center DCell networks are particularly well-suited for large, reliability-critical data centers due to their scalability, fault tolerance, and efficient bandwidth utilization. The reliability and diagnosis of DCell networks are of paramount importance in ensuring smooth operation and continuous availability of data center services. Traditional fault diagnosis models, which focus on global fault detection, are more suited to simpler networks. In contrast, complex DCell networks require fault diagnosis under specific conditions to accommodate dynamic changes and constraints. This paper studies the cyclic diagnosability of DCell networks under different system-level diagnostic models, which is a novel fault diagnosis strategy. Cyclic diagnosability, denoted as$ct_{c}(G)$, represents the maximum size of a set of fault vertices$D$in a network$G$, so that the self-diagnosis system can identify all vertices in$D$under the condition that at least two connected components of$G-D$contain a cycle. We show that for$k$-dimensional DCell with$n$-port switches$DCell_{k,n}$, when$k \geq 2$,$3 \leq n \leq 5$, or$k \geq \frac {n}{2} + 1$,$n \geq 6$, the cyclic diagnosability is$4k+2n-5$under the PMC and MM* models based on the indistinguishability of the constructed set and the linear multiple fault analysis technology. Additionally, we propose two practical cyclic fault diagnosis algorithms with low time complexity: PMC-Based Cyclic Fault Diagnosis (PMCCFD) and MM*-Based Cyclic Fault Diagnosis (MMCFD) for the PMC and MM* models to improve fault detection and recovery in large-scale DCell networks. We also implement the PMCCFD and MMCFD algorithms on both synthetic and real data. Furthermore, we verify the availability/efficiency of algorithms PMCCFD and MMCFD in terms of accuracy rate, recall, false negative rate, negative predictive value, and F1Score.

As the core infrastructures in the information systems, the data center networks carry a large number of tasks of data processing and storage. In a data center network, intermittent faults are often difficult to be found and dealt with in time because of their hiddenness and uncertainty. Once these faults accumulate to a certain extent, they can cause serious network outages and even lead to the collapse of the entire data center. In order to discover and resolve these potential problems in a timely manner, it is crucial to apply intermittent fault diagnosis, thus ensures the continuous and stable operation of the data center. In this paper, we propose the intermittent fault diagnosabilitytPMCI(Cn) for ann-dimensional data center network CSDC under the Preparata/Metze/Chien model (PMC model) by establishing the fault tolerance of the network. Additionally, under the PMC model, we propose a probabilistic multiple intermittent fault diagnosis algorithm (PMIFDPMC) with time complexityO(nN) by preferentially generating weighted multiple test networks (GWMTN) whereNis the scale of CSDC. Moreover, we apply the algorithm PMIFDPMC to a 7-dimensional CSDC and a real-world dataset of the Internet of Things. Across different scenarios of intermittent fault nodes, we calculate the Accuracy, Recall, FNR, G-mean, and F1-score using various testing iterations. The experimental results demonstrate that, as the number of testing iterations of algorithm PMIFDPMC increases, the quantity of intermittent fault nodes that are correctly diagnosed also increases. This highlights the favorable performance and effectiveness of algorithm PMIFDPMC on the real-world dataset of the Internet of Things.

Federated learning is vulnerable to model poisoning attacks in which malicious participants compromise the global model by altering the model updates. Current defense strategies are divided into three types: aggregation-based methods, validation dataset-based methods, and update distance-based methods. However, these techniques often neglect the challenges posed by device heterogeneity and asynchronous communication. Even upon identifying malicious clients, the global model may already be significantly damaged, requiring effective recovery strategies to reduce the attacker's impact. Current recovery methods, which are based on historical update records, are limited in environments with device heterogeneity and asynchronous communication. To address these problems, we introduce FedHAN, a reliable federated learning algorithm designed for asynchronous communication and device heterogeneity. FedHAN customizes sparse models, uses historical client updates to impute missing parameters in sparse updates, dynamically assigns adaptive weights, and combines update deviation detection with update prediction-based model recovery. Theoretical analysis indicates that FedHAN achieves favorable convergence despite unbounded staleness and effectively discriminates between benign and malicious clients. Experiments reveal that FedHAN, compared to leading methods, increases the accuracy of the model by 7.86%, improves the detection accuracy of poisoning attacks by 12%, and enhances the recovery accuracy by 7.26%. As evidenced by these results, FedHAN exhibits enhanced reliability and robustness in intricate and dynamic federated learning scenarios.

Federated learning, as a distributed learning framework, aims to develop a global model while preserving client privacy. However, heterogeneity of client data leads to fairness issues and reduced performance. Techniques like parameter decoupling and prototype learning appear promising, yet challenges such as forgetting historical data and limited generalization persist. These methods also lack local insights, with locally trained features prone to overfitting, which affects generalization in global parameter aggregation. To address these challenges, we propose FedCPD, a personalized federated learning framework. FedCPD maintains historical information, reduces information loss, and increases personalization through hierarchical feature distillation and cross-layer feature fusion. Moreover, we utilize representation techniques like prototype contrastive learning and prototype alignment to capture diverse client data features, thus improving model generalization and fairness. Experiments show FedCPD outperforms state-of-the-art models, enhancing generalization by up to 10.40% and personalization by up to 4.90%, highlighting its effectiveness and superiority.

Model inversion and adversarial attacks in semantic communication pose risks, such as content leaks, alterations, and prediction inaccuracies, which threaten security and reliability. This paper introduces, from an attacker's viewpoint, a novel framework called RepObE (Representation Learning-Enhanced Obfuscation Encryption Modular Semantic Task Framework) to secure semantic communication. This framework employs dynamic encryption during semantic extraction and feature transmission to hinder attackers from reconstructing data through eavesdropping, thus strengthening system privacy. To combat image communication task challenges, we propose a prototype adversarial collaborative alignment training approach enhanced by representation learning. This method extracts and encodes semantic features while using dynamic perturbation and robust optimization to improve system resilience against adversarial threats. The approach ensures reliable semantic communication in complex environments, maintaining performance while countering attacks using feature obfuscation, adversarial training, and representation learning. Experimental results demonstrate that our method surpasses existing techniques by more than 2% in resisting model inversion attacks on classification tasks. Visually, our method excels with minimal decipherable images for attackers. It also shows a 3% to 5% improvement in countering adversarial attacks on classification tasks.

Rapid iterations and updates in both software and hardware, along with significant advancements in communication technology, have given rise to the concepts of symbiotic Internet of Things (IoT) and ubiquitous interconnectivity, providing strong evidence for the flourishing development of the Internet of Things. However, the limited resources and computing capabilities, along with the heterogeneity of deployment environments, make symbiotic IoT devices more susceptible to security threats and operational issues. Intermittent failures are especially prevalent in the symbiotic IoT, leading to more significant risks for devices. In this paper, we present an IFDGAT-LSTM (Intermittent Fault Diagnosis Based on Long Short-Term Memory and Graph Attention Network) framework for diagnosing intermittent failures in wireless sensing devices within the symbiotic IoT. The framework is based on a graph neural network and takes into account not only the time series characteristics of symbiotic IoT devices but also their deployment topology. By incorporating both aspects, we achieve more accurate diagnostics of intermittent failures in the symbiotic IoT, thus enhancing its reliability. Firstly, we propose the concept of a quasi-dynamic graph based on the variations in the topology within the symbiotic IoT. Subsequently, we introduce an intermittent failure diagnosis framework that combines a graph neural network to identify intermittent failure nodes within the quasi-dynamic graph. Finally, we performed experiments on the WADI symbiotic IoT dataset to evaluate the performance of our model in diagnosing intermittent failure nodes. We used the precision, recall, and F1 score metrics for assessment. The experimental outcomes show that our proposed model, IFDGAT-LSTM, achieves an Precision of 99.58% in diagnosing intermittent failure nodes. This highlights the strong performance and efficacy of the IFDGAT-LSTM model.

The rapid proliferation of Internet of Things (IoT) systems has introduced complex networks of interconnected devices, computational resources, and web-based communication infrastructure. Privacy protection in IoT data routing is critical to enabling secure deployment of large language models (LLMs) for processing distributed sensor data, user queries, and device-generated content. However, IoT environments inherently involve heterogeneous devices, dynamic network topologies, and resource-constrained nodes, complicating the design of privacy-preserving routing mechanisms that simultaneously ensure reliability across diverse communication layers. To address these challenges, we propose an innovative FtPR (Fault-tolerant Privacy Routing) model based on secure multiparty computing mechanism, which enables secure and efficient data fusion and transmission in IoT networks. FtPR establishes a novel connection between IoT device clusters and data center network architecture AQDNn routers, leveraging the hierarchical architecture of AQDNn to construct completely independent spanning trees (CIST). By exploiting the non-overlapping paths between nodes in distinct CISTs, FtPR achieves fault-tolerant routing while maintaining privacy guarantees. Building on this framework, we introduce a secure multiparty computing mechanism to perturb link weights in the AQDNn. This ensures that link weights across different CISTs adhere to constrained ranges, preventing adversarial inference of routing paths. Each node operates with localized knowledge of its connected link weights, eliminating the need for global network visibility. Consequently, even if malicious actors compromise one or multiple nodes, they cannot reconstruct end-to-end communication paths, thereby preserving route anonymity. Experimental results demonstrate that FtPR improves IoT network performance and security, reducing misclassification rates and marginal release score compared to state-of-the-art methods.

The explosion of cameras embedded in IoT devices—from mobile phones to autonomous vehicles—has positioned video analytics as a transformative AI tool across healthcare, smart cities, and beyond. Yet, the substantial computing and bandwidth demands of these applications outstrip what IoT devices alone can handle, particularly when low latency is required. Computing Power Networking (CPN) is an emerging solution that unifies cloud, edge, and device resources, enabling seamless, efficient task distribution for real-time analytics. While recent advances in cloud-edge frameworks show promise, current approaches often neglect the economic incentives that drive resource availability. To address this, we present a novel, privacy-enabled dual-layer Stackelberg game model that establishes a dynamic pricing strategy for video analytics in CPN. Our model introduces a two-stage negotiation: IoT devices contract with edge servers for computational and bandwidth resources, while edge servers may offload tasks to the cloud for enhanced service. Using game theory, we derive optimal pricing and offloading strategies under both complete and incomplete information, proving a Nash equilibrium. Comprehensive simulations validate our approach, showing improvements in resource efficiency, reduced latency, and incentivized resource-sharing across all CPN tiers. Specifically, our hybrid offloading strategy significantly reduces latency compared to edge-only and cloud-only computation models. For varying IoT device quantities, the average latency reduction across all scenarios is approximately 30.5%. This work provides an economically sustainable, privacy-conscious solution to the computational challenges of video analytics in an interconnected, resource-sharing ecosystem.

Vehicular edge computing (VEC) tackles the escalating computational demands of intelligent transportation systems by offloading tasks to nearby roadside units (RSUs) for processing. However, in the dynamic vehicular network environment, where vehicles are constantly moving, effective VEC demands a sophisticated approach to managing computing, caching, and communication resources. This involves coordinating resource allocation and data caching across multiple vehicles and RSUs while making complex decisions about task placement. In this paper, we present VECO, a Vehicular Edge Caching and Offloading framework powered by digital twins (DTs). VECO leverages DTs for real-time monitoring of network conditions and resource states, enabling predictive analysis and intelligent decision-making. The framework incorporates a Dynamic Task Caching and Computation Offloading (DT2C) mechanism to optimize data caching and adapt task offloading based on task characteristics and dynamic resource availability. Specifically, we develop a utility-based caching algorithm for RSUs and a novel task offloading strategy using a Proximal Policy Optimization-based deep reinforcement learning algorithm. Extensive experiments demonstrate that VECO, augmented by the DT2C mechanism, significantly outperforms baseline approaches, achieving faster learning convergence and a 21% reduction in total costs, including system latency and energy consumption.

Autonomous Transportation Systems (ATS) make the transportation system transition from “passive transportation” to “autonomous service”. The wireless nature of communication in ATS presents significant cybersecurity challenges. Conventional intelligent vehicular intrusion detection methods may not suffice in situations where vehicular data is produced at an unprecedented scale and diverse cybersecurity threats are launched. Therefore, there is a demand for the creation of advanced intelligent vehicular intrusion detection systems that can effectively manage potential cyberattacks within ATS. Toward this end, this paper proposes QnGSA (hypercube driven graph self-attention intelligent vehicular intrusion detection model) in ATS, a novel intrusion detection model that helps to protect both the vehicles and the data they transmit, preventing disruptions to services, theft of sensitive information, and potential harm to passengers or cargo. QnGSA not only proposes a construction method of association graph by introducing hypercube and semi-supervised K-means++ clustering algorithm (QnSSKM). But also, QnGSA self-extracts the graph structural information of hypercube, and uses the graph self-attention mechanism to aggregate node features and obtain more accurate representation. Furthermore, this paper uses Graph Attention Network classifier to correlate the learned node representation with the fault category, and uses Softmax function to map the node representation to the probability distribution of different categories. The category with the highest probability is selected as the prediction label of the node, so as to realize the intelligent vehicular intrusion detection. Experiments results show that our proposed QnGSA method achieves the best results compared with state-of-the-art methods in terms of accuracy, macro precision/recall/F1.

Mobile Opportunistic Networks (MONs) often experience frequent interruptions in end-to-end connections, which increases the likelihood of message loss during delivery and makes users more susceptible to various cyber attacks. However, most currently proposed anonymous routing protocols are primarily designed for networks with stable connections, making it challenging to protect user identities in MONs. To address these challenges, we propose FLAG-POR (Forward Legal Anonymous Group Pairing-Onion Routing), a novel anonymous routing protocol specifically tailored to enhance message delivery anonymity and security in MONs. Specifically, we abstract the mobile opportunistic network as a contact graph. By introducing the concept of “groups” into the pairing-onion routing protocol, which encrypts messages and relay nodes layer by layer, we develop a novel group-based pairing-onion routing protocol. This protocol ensures message confidentiality and relay node anonymity, while also improving message forwarding rates, as any node within a group can potentially act as a relay. To ensure message authenticity, we employ the efficient SM2 signing algorithm to generate signatures for the message source. Furthermore, by incorporating parameters such as the public key validity period and master key validity period into the group pairing-onion routing protocol, we achieve forward security in message delivery. We conduct a thorough theoretical analysis of the protocol’s security and performance. The experimental results demonstrate that our FLAG-POR protocol outperforms baseline anonymous protocols in terms of delivery success rate, traceability rate, path anonymity, and node anonymity. Additionally, the FLAG-POR scheme effectively resists three potential threats to the routing system: collusion attack threat, node identification threat, and path identification threat, in any situation.

Fault diagnosability can reflect the actual self diagnosing capability of a multiprocessor system better. However, people usually focus on the overall information and neglect the important local information. In order to reflect the locality of a system at a node better, this paper proposes a novel fault diagnosis strategy, called x-block local fault diagnosability (x-BLFD), where the x-block condition requires more than x connected fault-free nodes. Then, we characterize some important properties about the x-BLFD of multiprocessors interconnected networks under the Preparata/Metze/Chien model (P/M/C), and further propose the x-BLFD in an$f(x)$-extended block network with the minimum$(x+1)$-subnetwork degree at some node. We also establish an approximate algorithm to calculate the x-BLFD of a large-scale diagnosable network at some node, and analyze the experimental performance of large-scale networks. Furthermore, we apply our proposed conclusion to obtain the x-BLFD of 16 well-known networks at some node directly under P/M/C, including dual cubes, hierarchical cubic networks, DQcubes, twisted hypercubes, Bicube networks, crossed cubes, folded hypercubes, k-ary n-cubes, balanced hypercubes, BC graphs,$(n,k)$-star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, split-star networks, data center networks, and$(n,k)$-arrangement graphs. Finally, we compare the x-BLFD with the diagnosability, conditional diagnosability, pessimistic diagnosability, and$t/k$-diagnosability by a large number of detailed numerical analysis. It can be seen that the x-BLFD is greater than all the other types of fault diagnosabilities.

As the multiprocessor systems are becoming large-scale, fault-diagnosis is crucial to ensure the reliability of multiprocessor systems. In order to improve the self-diagnosis capability of a multiprocessor system, a pessimistic fault diagnosis scheme such as$t/s$-diagnosis allows some fault-free processors to be mistakenly identified as faulty. All faulty processors in a$t/s$-diagnosable multiprocessor system ($t\leq s$) should be identified into a set with size up to$s$, when the total amount of faulty processors in the system does not exceed$t$. This article focuses on the$t/s$-diagnosis for the$n$-dimensional bijective connection network$X_{n}$. An adaptive$t/s$-diagnosis algorithm APDMM*$t/s$of complexity$O(M(log_{2}\,M)^{2})$under the comparison model is proposed, where$M$is the total amount of nodes in$X_{n}$. Then, the correctness of algorithm APDMM*$t/s$is proved by the fault-tolerant properties of the network itself. Moreover, we calculate the$t/s$-diagnosability of$X_{n}$by theoretical method in mathematics, which is$-\frac{1}{2}y^{2}+(n-\frac{1}{2})y+1$for$2 \leq y \leq n$under comparison model, where$s=-\frac{1}{2}y^{2}+(n-\frac{1}{2})y+y-1$. Furthermore, we apply algorithm APDMM*$t/s$on the hypercube and the real-world network WSN-DS to verify our main results, and analyze the experimental outcomes in terms of true positive rate, false positive rate, accuracy and precision. The experimental results reveal the advantage and high performance of our algorithm APDMM*$t/s$. Besides, we compare the$t/s$-diagnosability of$X_{n}$with traditional accurate diagnosability, and it turns out that as$n$gets larger, the$t/s$-diagnosability of$X_{n}$is significantly better than traditional accurate diagnosability.

The rise of software-defined networking (SDN) has greatly enhanced the flexibility and programmability of networks, but it has also brought new security challenges while achieving more efficient multipath, more flexible load balancing, and more secure authentication. To address this problem, we propose an innovative solution: the load-balanced heterogeneous multipath authenticated routing selection (LBHMARS) framework. This framework implements load balancing of multipath routing, as well as authentication and location of compromised switches in SDN networks, while ensuring the security of traffic entering the system. LBHMARS establishes a secure and efficient routing mechanism in SDN using the IPv6 protocol. We combine strong encryption and signature schemes with a novel path load balancing algorithm to ensure traffic balance and data integrity among multiple network paths. Finally, we introduce a mechanism to locate and isolate malicious switches, further enhancing network security. Compared with existing solutions, our extensive simulations show that LBHMARS has superior performance in mitigating attacks and maintaining high network throughput. In addition, LBHMARS also performs well in terms of latency and low packet loss.

The Augmented Intelligence of Things (AIoT) is an emerging technology that combines augmented intelligence with the Internet of Things (IoT) to facilitate advanced decision-making processes. In this paper, we focus on the detection of vehicle trajectory anomalies in a vehicle-road collaboration system by AIoT, aiming to improve the traffic safety and road operation efficiency. We transmit collaboration data collected by sensors to an IoT server, which enables the effective data analysis for vehicle trajectory information. We propose a self-supervised learning augmented intelligence algorithm to achieve precise and efficient detection of trajectory anomalies. First, we models the traffic road network as a topology graph. Subsequently, we sample the relevant subgraph contexts for each target node through a random walk algorithm. And the subgraphs with higher intimacy scores are selected as the contextual background to be input along with the target node. After that, the anomaly score of each target node is computed through the generative learning module and the contrastive learning module. To evaluate the effectiveness of our anomaly detection approach, we initially conduct pre-training of the model using four widely utilized graph machine learning datasets. The experimental results reveal that our approach surpasses previous methods in the accuracy of identifying graph anomaly nodes. In addition, we carry out our approach on two real traffic datasets with high accuracies of 86.47% and 85.2%, respectively. This result demonstrates the effectiveness of our proposed approach in detecting trajectory anomalies in real traffic scenarios.

Ensuring the stability and security of unmanned aerial vehicle (UAV) communication, especially during long-distance missions, is essential for safeguarding against potential attacks. Large-scale UAV communication faces challenges including eavesdropping threat, data tampering, replay threat and man-in-the-middle threat. We propose a security information transmission solution based on reinforcement learning and location confusion algorithm (RLPC-SIT) to achieve a secure data transmission between UAVs. First, we leverage the principles of reinforcement learning to identify the most stable transmission routes. Secondly, we employ location confusion techniques to blur each location of the transmitting UAV with respect to other UAVs. Furthermore, we utilize the concept of message authentication to encrypt the transmitted data, thus making it inaccessible to malicious nodes and preventing forgery. The results of our theoretical analysis and simulation-based experiments indicate that our approach outperforms other security schemes.

With the rapid growth of the number of processors in a multiprocessor system, faulty processors occur in it with a probability that rises quickly. The probability of a subsystem with an appropriate size being fault-free in a definite time interval is a significant and practical measure of the reliability for a multiprocessor system, which characterizes the functionality of a multiprocessor system well. Motivated by the study of subgraph reliability, as well as the attractive structure and fault tolerance properties of$(n, k)$-arrangement graph$A_{n, k}$, we focus on the subgraph reliability for$A_{n, k}$under the probabilistic fault model in this article. First, we investigate intersections of no more than four subgraphs in$A_{n, k}$, and classify all the intersecting modes. Second, we focus on the probability$P(q, A_{n, k}^{n-1, k-1})$with which at least one$(n-1, k-1)$-subarrangement graph is fault-free in$A_{n, k}$, when given a uniform probability$q$with which a single vertex is fault-free, and we establish the$P(q, A_{n, k}^{n-1, k-1})$by adopting the principle of inclusion–exclusion under the probabilistic fault model. Finally, we study the probabilistic fault model involving a nonuniform probability with which a single vertex is fault-free, and we prove that the$P(q, A_{n, k}^{n-1, k-1})$under both models is very close to the asymptotic value by both theoretical arguments and experimental results.

Endogenous security has the ability to discover, eliminate, and solve internal security problems and hidden dangers within the network, and is a superior technology to ensure future network security. The$t/k$-diagnosis strategy, as a strong and adaptive self-diagnosis strategy, is an important part for ensuring endogenous security. Moreover, the folded hypercube ($FQ_{n}$) as a data transmission network (e.g., optical network) topology offers new potential for the construction of large-scale, high data throughput, and low-latency systems, such as computing network, human-cyber-physical systems, and smart grid. However, there are few studies on endogenous security based on$FQ_{n}$networks. Therefore, this article designs an adaptive system-level fault self-diagnosis strategy, namely Fast t/k-Diagnosis Under Maeng-Malek Model (Ftk-DIAG-MM*) to diagnosis the faulty vertices in$FQ_{n}$network under the Maeng-Malek model (MM* mod). Then, we provide a proof of the algorithm correctness theoretically by the fault tolerance of$FQ_{n}$network. It is derived by theoretical derivation that the$t/k$-diagnosability inherent to the$FQ_{n}$network is$(n+1)\break(k+1)-k(k+3)/2$. The simulation experiments demonstrate that the designed Ftk-DIAG-MM* strategy can correctly diagnose all vertices within the range allowed by the diagnosability, and still has a great performance when it exceeds the range allowed by the diagnosability. It greatly enhances the fault diagnosis capability of$FQ_{n}$network in the circumstance of misdiagnosing a few vertices, which provides an important theoretical basis for the reliability and endogenous security of$FQ_{n}$networks.

The growing demand for high-performance computing and the acceleration of information processing have brought multiprocessor systems into the era of E-class computing. The reliability of interconnection networks built on multiprocessor systems is facing severe challenges with the rapid growth of the networks' scale. For example, a large-scale processor failure may disconnect the entire network and result in the appearance of many different components. Rapid fault diagnosis has great advantages in industry, especially in real-time systems, which means that rapid diagnosis of fault processors is particularly important. However, the fault diagnosis capability in a network is closely related to the amount of components that the network can tolerate in its application. The diagnosis method of faulty processors, which cause many components is called component diagnosis. In particular,$ct_{g}(G)$refers to the maximum number of faulty processors meeting the$g$-component condition that can be diagnosed in network$G$under certain system-level diagnostic model. In this article, based on the indistinguishability of the constructed set and linear multiple faults analysis technology, we propose the 2, 3-component diagnosabilities of star graph network$S_{n}$under P-M-C-M. Moreover, we propose a novel$g$-component$t$-diagnosable algorithm FCFDSn innovatively to diagnose all faulty processors, and we implement the algorithm FCFDSn on both synthetic data and real data. Furthermore, we verify the availability/efficiency of algorithm FCFDSn in terms of true positive rate, true negative rate, and accuracy rate.

Abstract Reliability of a multiprocessor system becomes an important issue for parallel computing. Component diagnosability and component connectivity of a graph play crucial roles in assessing the vulnerability of an interconnection network, which are two significant indicators for the reliability and fault tolerance of a multiprocessor system. Until now, only a little knowledge of results have been known on $r$-component diagnosability and $r$-component connectivity. In this paper, we first propose the $r$-component diagnosability of $n$-dimensional alternating group graph $AG_{n}$ under PMC model. And then we promote our research on $AG_{n}$ by a fairly good construction for general $r$-component connectivity of $AG_{n}$, where $6\leq r\leq n-1$. The theoretical analysis and simulation show that the general $r$-component connectivity of $AG_{n}$ is larger than those of $Q_{n}$, $D_n$ and $FQ_{n}$.

The fault diagnosability of a network indicates the self-diagnosis ability of the network, thus it is an important measure of robustness of the network. As a neoteric feature for measuring fault diagnosability, the r -component diagnosability ct r (G) of a network G imposes the restriction that the number of components is at least r in the remaining network of G by deleting faulty set X , which enhances the diagnosability of G . In this article, we establish the r -component diagnosability for n -dimensional hierarchical cubic network HCN n , and we show that, under both PMC model and MM* model, the r -component diagnosability of HCN n is rn -½( r -1) r +1 for n ≥ 2 and 1≤ r≤ n-1 . Moreover, we introduce the concepts of 0-PMC subgraph and 0-MM* subgraph of HCN n . Then, we make use of 0-PMC subgraph and 0-MM* subgraph of HCN n to design two algorithms under PMC model and MM* model, respectively, which are practical and efficient for component fault diagnosis of HCN n . Besides, we compare the r -component diagnosability of HCN n with the extra conditional diagnosability, diagnosability, good-neighbor diagnosability, pessimistic diagnosability, and conditional diagnosability, and we verify that the r -component diagnosability of HCN n is higher than the other types of diagnosability.

With the rapid increase of the number of processors in multiprocessor systems and the fast expansion of interconnection networks, the reliability of interconnection network is facing severe challenges, where the fast recognition of fault processors is crucial. In practice, most of the processor failures are intermittent faults. In this article, we first determine the intermittent fault diagnosability$t_{I}^{PMC}(S_{n}^{2})$of$n$-dimensional split-star network$S_{n}^{2}$under the PMC model. In addition, we propose a fast intermittent fault probabilistic diagnosis algorithm FIFPDPMC to identify the nodes with intermittent fault in the$n$-dimensional split-star network$S_{n}^{2}$under the PMC model, and we calculated the time complexity of the algorithm FIFPDPMC. Then we implement the algorithm FIFPDPMC in the IoT-based wireless sensor network (IoTWSN) and a randomly generated network (RGN) under different number of nodes with intermittent fault, and we evaluate the performance and efficiency of the algorithm FIFPDPMC in terms of accuracy, precision, recall (TPR), F1, G-mean, FPR, TNR and FNR. Experimental results show that, as the number of stages of executing the algorithm FIFPDPMC increases, the number of nodes with intermittent fault being diagnosed by the algorithm FIFPDPMC increases, which implies that the algorithm FIFPDPMC has good performance and efficiency in both IoTWSN and RGN.

In order to evaluate the reliability of a multiprocessor system, the fault diagnosability was introduced and utilized as a significant indicator. In the study of fault diagnosability, researchers usually concentrate on the diagnosability of the global system but ignore its local information. However, the local information also plays a crucial role in the reliability of a multiprocessor system. Thus, an innovative concept of fault diagnosability, called$y$-fault-free-block local fault diagnosability, is put forward to study the fault diagnosability of a multiprocessor system at local vertex, where the$y$-fault-free-block condition requires more than$y$connected vertices. In this article, we characterize several important properties about the$y$-fault-free-block local fault diagnosability of a multiprocessor interconnection network under the MM* model and propose its$y$-fault-free-block local fault diagnosability at local vertex. Furthermore, we apply our results to some well-known networks, and we obtain their$y$-fault-free-block local fault diagnosabilities at local vertex directly under the MM* model, including bijective connection graph, star graph, and$(n,k)$-star graph. Finally, we compare the$y$-fault-free-block local fault diagnosability of a graph at local vertex with other types of diagnosability, including the diagnosability, conditional diagnosability, good-neighbor diagnosability, and pessimistic diagnosability. It can be seen that the$y$-fault-free-block local fault diagnosability at vertex is larger than all the other types of diagnosability.

Intermittent faults are common in daily life and industrial manufacture, which have been drawing much attention from both academia and industry. In practice, intermittent faults will pose a great threat to system performance and equipment safety. Because of the randomness and unpredictability of intermittent faults, it is a great challenge to diagnose them. The fault diagnosis strategy under system-level diagnostic model plays a very important role in measuring the endogenous network security without prior knowledge, which can significantly enhance the self-diagnosing capability of network. However, as the networks become large-scale and complicated, the fault diagnosis using full syndromes from a system-level diagnostic model seems to reach its bottleneck. In this article, we first determine that the intermittent fault diagnosability of a general$r$-regular network$G$under comparison model is$(t^{\text{Intermittent}}(G))^{M}=r-2$. This results can be directly applied to 18 well-known networks. Then, we propose a reliable neural network enabled intermittent fault diagnosis algorithm RNNIFDCom to solve the problem of fault identification with partial syndromes for a general$r$-regular network$G$under comparison model. Finally, we implement our proposed algorithm RNNIFDCom in different networks and analyze its performance under different number of faulty nodes in terms of true positive rate, true negative rate, false positive rate, and false negative rate. The experimental results verify the theoretical results and show the advantage of our proposed algorithm RNNIFDCom.

Abstract As the size of a multiprocessor system grows, the probability that faults occur in this system increases. One measure of the reliability of a multiprocessor system is the probability that a fault-free subsystem of a certain size still exists with the presence of individual faults. In this paper, we use the probabilistic fault model to establish the subgraph reliability for $AG_n$, the $n$-dimensional alternating group graph. More precisely, we first analyze the probability $R_n^{n-1}(p)$ that at least one subgraph with dimension $n-1$ is fault-free in $AG_n$, when given a uniform probability of a single vertex being fault-free. Since subgraphs of $AG_n$ intersect in rather complicated manners, we resort to the principle of inclusion–exclusion by considering intersections of up to five subgraphs and obtain an upper bound of the probability. Then we consider the probabilistic fault model when the probability of a single vertex being fault-free is nonuniform, and we show that the upper bound under these two models is very close to the lower bound obtained in a previous result, and it is better than the upper bound deduced from that of the arrangement graph, which means that the upper bound we obtained is very tight.

A human contact network (HCN) consists of individuals moving around and interacting with each other. In HCN, it is essential to detect malicious users who break the data delivery through terminating the data delivery or tampering with the data. Since malicious users will pay more but gain less when breaking the data delivery of opportunistic contacts, we focus on the non-opportunistic contacts that occur more frequently and stably. It is observed that people contact with each other more frequently if they have more social features in common. In this paper, we build up topology structure for HCN based on social features, and propose a graph theoretical comparison detection model to perform malicious users detection. Then we present an adaptive detection scheme based on Hamiltonian cycle decomposition. Also, we define comparison-0-string and comparison-1-string to improve the detection efficiency. Moreover, we perform scenario simulations on real data to realize the detected process of malicious users. Experiments show that, when the number of malicious users is bounded by the dimension of HCN, our scheme has a detection rate of 100% with both false positive rate and false negative rate being 0%, and the running cost is also very low when compared to baseline approaches. When the number of malicious users exceeds the bound, the detection rate of our scheme decreases slowly, while the false positive rate and false negative rate increase slowly, but they are still better than the baseline approaches.

Cyberspace is not a “vacuum space”, and it is normal that there are inevitable viruses and worms in cyberspace. Cyberspace security threats stem from the problem of endogenous security, which is caused by the incompleteness of theoretical system and technology of the information field itself. Thus it is impossible and unnecessary for us to build an “aseptic” cyberspace. On the contrast, we must focus on improving the “self-immunity” of network. Literally, endogenous security is an endogenous effect from its own structural factors rather than external ones. The$t/k$-diagnosis strategy plays a very important role in measuring endogenous network security without prior knowledge, which can significantly enhance the self-diagnosing capability of network. As far as we know, few research involves$t/k$-diagnosis algorithm and$t/k$-diagnosability of interconnection networks under MM* model. In this article, we propose a fast$f(r,k+1)/k$-diagnosis algorithm of complexity$O(Nr^2)$, say$G$MIS$k$DIAGMM*, for a general$r$-regular network$G$under MM* model by designing a 0-comparison subgraph$M_0(G)$, where$N$is the size of$G$. We determine that the$t/k$-diagnosability$(t(G)/k)^M$of$G$under MM* model is$f(r,k+1)$by$G$MIS$k$DIAGMM* algorithm. Moreover, we establish the$(t(G)/k)^M$of some interconnection networks under MM* model, including BC networks,$(n,l)$-star graph networks, and data center network DCells. Finally, we compare$(t(G)/k)^M$with diagnosability, conditional diagnosability, pessimistic diagnosability, extra diagnosability, and good-neighbor diagnosability under MM* model. It can be seen that$(t(G)/k)^M$is greater than other fault diagnosabilities in most cases.

Fault diagnosability is utilized as a significant measure that reflects the reliability of a multiprocessor system. However, people frequently pay close attention to the entire systems diagnosability while ignoring the systems important local information. The m-fault-free-neighbor local fault diagnosability (for short, m-FFNLFD) is a novel indicator, which describes the diagnosability of a system at a local node with m fault-free neighbors. In this paper, we propose the m-FFNLFD of general networks at local node under the Preparata Metze Chien model. Moreover, we also characterize some important properties of m-FFNLFD of a multiprocessor system under the comparison model. Furthermore, we apply our proposed conclusions to directly obtain the m-FFNLFD of 11 well-known networks under PMC-M and MM*-M, including hypercubes, locally twisted cubes, k-ary n-cubes, crossed cubes, twisted hypercubes, exchanged hypercubes, star graphs, (n, k)-star graphs, (n, k)-arrangement graphs, data center network DCells and BCDCs. Finally, we compare the m-FFNLFD with both diagnosability and conditional diagnosability, and it is shown that the m-FFNLFD is greater than all the other fault diagnosabilities.

Thet/kt/k-diagnosabilityandhh-extra connectivityare regarded as two important indicators to improve the network reliability. The t/k-diagnosis strategy can significantly improve the self-diagnosing capability of a network at the expense of no more thankfault-free nodes being mistakenly diagnosed as faulty. Theh-extra connectivity can tremendously improve the real fault tolerability of a network by insuring that each remaining component has no fewer than h+1 nodes. However, there is few result on the inherent relationship between these two indicators. In this article, we investigate the reason that caused the serious flawed results in (Liu, 2020), and we propose a diagnosis algorithm to establish the t/k-diagnosability for a large-scale connected networkGunder the PMC model by considering its h-extra connectivity. Let κh(G) be the h-extra connectivity of G. Then, we can deduce that G is κh(G)/h-diagnosable under the PMC model with some basic conditions. All κh(G)faulty nodes can be correctly diagnosed in the large-scale connected network G and at most h fault-free nodes would be misdiagnosed as faulty. The complete fault tolerant method adopts combinatorial properties and linearly many fault analysis to conquer the core of our proofs. We will apply the newly found relationship to directly obtain the κh(G)/h-diagnosability of a series of well known networks, including hypercubes, folded hypercubes, balanced hypercubes, dual-cubes, BC graphs, star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, alternating group graphs, split-star networks, k-ary n-cubes and (n,k)-star graphs.

For interconnection network losing processors, it is considerable to calculate the number of vertices in the maximal component in the surviving network. Moreover, the component connectivity is a significant indicator for reliability of a network in the presence of failing processors. In this article, we first prove that when a set$M$of at most$3n-7$processors is deleted from an$n$-star graph, the surviving graph has a large component of size greater or equal to$n!-|M|-3$. We then prove that when a set$M$of at most$4n-9$processors is deleted from an$n$-star graph, the surviving graph has a large component of size greater or equal to$n!-|M|-5$. Finally, we also calculate the$r$-component connectivity of the$n$-star graph for$2\leq r\leq 5$.

The attackers in a network may have a tendency of targeting on a group of clustered nodes, and they hope to avoid the existence of significant large communication groups in the remaining network, such as botnet attack, DDoS attack, and Local Area Network Denial attack. Current various kinds of connectivity do not well reflect the fault tolerance of a network under these attacks. This observation inspires a new measure for network reliability to resist the block attack by taking into account of the dispersity of the remaining nodes. Let$G$be a network,$C\subset V(G)$and$G[C]$be aconnected subgraph. Then$C$is called an$h$h-faulty-blockof$G$if$G-C$is disconnected, and every component of$G-C$has at least$h+1$nodes. The minimum cardinality over all$h$-faulty-blocks of$G$is called$h$h-faulty-block connectivityof$G$, denoted by${FB}\kappa _h(G)$. In this article, we determine${FB}\kappa _h(Q_n)$for$n$-dimensional hypercube$Q_n$($n\geq 4$), a classic interconnection network. We establish that${FB}\kappa _h(Q_n)=(h+2)n-3h-1$for$0\leq h\leq 1$, and${FB}\kappa _h(Q_n)=(h+2)n-4h+1$for$2\leq h\leq n-2$, respectively. Larger$h$-faulty-block connectivity implies that an attacker will have to stage an attack to a bigger block of connected nodes, so that each remaining components will not be too small, which will in turn limit the size of large components. In other words, there will not be great disparity in sizes between any two remaining components, and hence there will less likely be a significantly large remaining communication group. The larger the$h$-faulty-block, the more difficult for an attacker to achieve that goal. As a consequence, the resistance of the network against the attacker will increase. Our experiments also show that as$h$increases, the$h$-faulty-block gets larger, and the size disparity between any two remaining components decreases. In turn, as expected, the size of the largest remaining communication group becomes smaller.

A network's diagnosability is the maximum number of faulty vertices that the network can discriminate solely by performing mutual tests among vertices. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. The h-extra fault diagnosability is an important and widely accepted diagnostic strategy as a new measure of diagnosability, which guarantees that the scale of every component is at least h+1 in the remaining system. Moreover, it increases the allowed faulty vertices, hence enhancing the diagnosability of the network. There have been lots of state-of-the-art literatures concerning the h-extra fault diagnosability. Although there are some methods to theoretically prove the extra fault diagnosability of some other well-known networks under MM* model, these methods have some serious flaws when there exists a 4-cycle in these networks. In this article, we investigate the reason that caused the flawed results in some references, and we derive a different, broadly applicable, and complete fault tolerant method to establish the extra fault diagnosability in an n-dimensional alternating group graph AGnunder MM* model. The complete fault tolerant method adopts combinatorial properties and linearly many fault analysis to conquer the core of our proofs. Moreover, we compare the extra fault diagnosability of AGnwith various types of fault diagnosability, including the diagnosability, strong diagnosability, conditional diagnosability, t/k-diagnosability, and pessimistic diagnosability. It can be seen that the extra fault diagnosability is greater than all the other types of fault diagnosability.

For interconnection network losing processors, usually, when the surviving network has a large connected component, it can be used as a functional subsystem without leading to severe performance degradation. Consequently, it is crucial to characterize the interprocessor communication ability and efficiency of the surviving structure. In this article, we prove that when a subset$D$of at most$6n-17$processors is deleted from an$n$-dimensional alternating group graph$\text{AG}_n$, there exists a largest component with cardinality greater or equal to$|V(\text{AG}_n)|-|D|-3$for$n\geq 6$in the remaining network, and the union of small components is, first, an empty graph; or, second, a 3-cycle, or an edge, or a 2-path, or a singleton; or, third, an edge and a singleton, or two singletons. Then, we prove that when a subset$D$of at most$8n-25$processors is deleted from$\text{AG}_n$, there exists a largest component with cardinality greater or equal to$|V(\text{AG}_n)|-|D|-5$for$n\geq 6$in the remaining network, and the union of small components is, first, an empty graph; or, second, a 5-cycle, or a 4-path, or a 4-claw, or a 4-cycle, or a 3-path, or a 3-claw, or a 3-cycle, or a 2-path, or an edge, or a singleton; or, third, a 4-cycle and a singleton, or a 3-path and a singleton, or a 3-claw and a singleton, or a 2-path and a singleton, two edges, an edge and a singleton, or two singletons; or, fourth, two edges and a singleton, or a 2-path and two singletons, or an edge and two singletons, or three singletons.

Abstract The connectivity of a graph is a classic measure for fault tolerance of the network. Restricted connectivity measure is a crucial subject for a multiprocessor system’s ability to tolerate fault processors, and improves the connectivity measurement accuracy. Furthermore, if a network possesses a restricted connectivity property, it is more reliable with a lower vertex failure rate compared with other networks. The $\left (n,k\right )$-dimensional enhanced hypercube, denoted by $Q_{n,k}$, a variant of hypercube, which is a well-known interconnection network. In this paper, we analyze the fault tolerant properties for $\left (n,k\right )$-enhanced hypercube, and establish the $1$-restricted connectivity of $Q_{n,k} (n\ge k+1)$ and $\{2,3\}$-restricted connectivity of $(n,k)$-enhanced hypercube $Q_{n,k} (n=k+1)$. Furthermore, we propose the tight upper bound of $\{2,3\}$-restricted connectivity of $Q_{n,k} (n> k+1)$. Moreover, we show many figures to better illustrate the process of the proofs.

This paper addresses the issues of selfishness, limited network resources, and their adverse effects on real-time dissemination of Emergency Warning Messages (EWMs) in modern Autonomous Moving Platforms (AMPs) such as Vehicular Social Networks (VSNs). For this purpose, we propose a social intelligence based identification mechanism to differentiate between a selfish and a cooperative node in the network. Therefore, we devise a crowdsensing based mechanism to calculate a tie-strength value based on several social metrics. Moreover, we design a recursive evolutionary algorithm for each node’s reputation calculation and update. Given that, then we estimate each node’s state-transition probability to select a super-spreader for rapid dissemination. In order to ensure a seamless and reliable dissemination process, we incorporate 5G network structure instead of conventional short range communication which is used in most vehicular networks at present. Finally, we design a real-time dissemination algorithm for EWMs and evaluate its performance in terms of network parameters such as delivery-ratio, delay, hop-count, and message-overhead for varying values of vehicular density, speed, and selfish nodes’ density based on realistic vehicular mobility traces. In addition, we present a comparative analysis of the performance of the proposed scheme with state-of-the-art dissemination schemes in VSNs.

Summary The problem of influence maximization (IM) has become an important research topic due to the rapid growth of mobile social networks. It attempts to identify a set of nodes, referred to as influencers, contributing to the spread of maximum information. In this article, we present the construction of social relation graph based on mobile communication data. And we propose a new centrality measure—activity degree to characterize the activity of nodes. By combining the local attributes of nodes and the behavioral characteristics of nodes to measure node activity degree, which can be used to evaluate the influence of users in mobile social networks, we introduce Susceptible‐Infected‐Susceptible model to simulate the dynamic spreading of information. We take advantage of the two indicators the degree centrality and the betweenness centrality to get a better ranking results. In comparison with spanning graph and initial graph, the results of comparison demonstrate that our algorithm has advantages in the scope of influence propagation.

A network’s diagnosability is the maximum number of faulty vertices that the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network’s robustness. The g-good-neighbor conditional diagnosability is the maximum cardinality of g-good-neighbor conditional fault-set that the system is guaranteed to identify. The g-good-neighbor conditional diagnosability of EH(s,t) under the PMC model has been proposed by Liu et al. [Liu, X., Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol., 35, 390–393]. However, the method by Liu et al. [Liu, X., Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol., 35, 390–393] is too complicated to follow, and it is not complete. We will propose a complete method to establish the g-good-neighbor conditional diagnosability of EH(s,t) under the PMC model by optimizing the structure of the proof in [Liu, X., Yuan, J. and Ma, X. (2014) The g-good-neighbor conditional diagnosability of the exchange hypercube under the PMC model. J. Taiyuan Univ. Sci. Technol., 35, 390–393] and adding the missing case. Also we add a ratio in a table to represent the probability that a faulty set with size s contains all neighbors of any vertex, which is very low. Moreover, we mainly establish the g-good-neighbor conditional diagnosability for exchanged hypercube EH(s,t) under the comparison model.

The h-extra node-connectivity of a graph G is the size of a minimal node-set, whose removal will disconnect G, but each remaining component has no fewer h + 1 nodes. Based on h-extra node-connectivity, the h-extra conditional fault-diagnosability of networks has been proposed for a better, more realistic measure of networks' fault-tolerability. It is the maximal x such that G is h-extra conditionally x-fault-diagnosable. This paper will establish a relationship between the h-extra node-connectivity and h-extra conditional fault-diagnosability for a regular graph G, under the classic PMC diagnostic model. We will apply the newly found relationship to a variety of well-known regular networks, to directly obtain their h-extra conditional fault-diagnosability. The significance of the paper's work is that it relates the notions of h-extra node-connectivity and h-extra conditional fault-diagnosability, so that a regular network's h-extra conditional fault-diagnosability may be known once its h-extra node-connectivity is known.

A network's diagnosability is the maximum number of faulty vertices the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. Several conditional diagnosability have been proposed in the past to increase the allowed faulty vertices, and hence enhancing the diagnosability of the network. The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has at least g fault-free neighbors (i.e., good neighbors). In this paper, we establish the g-good-neighbor conditional diagnosability for the (n; k)-arrangement graph network An;k. We will show that, under both the PMC model and the comparison model, the An;k's g-good-neighbor conditional diagnosability is [(g + 1)k - g](n - k), which can be several times higher than the An;k's original diagnosability.

The g-restricted connectivity (g-RC) is the minimum vertex-set size of a network, whose deletion disconnects the network such that each remaining vertex has at least g neighbors in its respective component. The g-RC is a deterministic indicator of tolerability of a network with failing processors. The g-good-neighbor fault diagnosability (g-GNFD) is the largest set size of correctly identified faulty vertices in a network such that any good vertex has no fewer g good neighbors. This paper establishes the relationship between g-RC and g-GNFD of general regular networks, first under the PMC model and second under the MM* model. Moreover, this paper directly gives the g-GNFD of some well-known special networks by their g-RC and our proposed relationship.

Various services such as location-based service (LBS) allow mass collection of spatio-temporal data because the ubiquity of cheap embedded sensors on smart phones. Therefore, the individual privacy-preserving is receiving increasing attention during the data publication. However, the inherent inaccuracy of data acquisition equipments, sampling error and low sampling rate may lead to uncertainty. In this paper, we propose a privacy-preserving approach for trajectory publication with considering the uncertainty in trajectory. The correlation between two trajectories are computed according to the temporal overlap similarity, the trajectory direction similarity and the distance between trajectories with uncertainty. Then a greedy algorithm is proposed to achieve k-anonymity based on graph partition. The analysis and experiment evaluations based on the GeoLife trajectory data set show that significant privacy and QoS benefits can be achieved.

The$t/k$-diagnosis strategy can significantly enhance the system’s self-diagnosing capability at the expense of no more than$k$fault-free processors (vertices) being mistakenly diagnosed as faulty under the PMC model. It is a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis on multiprocessor systems. It can detect up to$t$faulty processors (vertices) which might include at most$k$misdiagnosed processors (vertices), where$k$is typically a small number. In the case$k\ge 1$, to our knowledge, there is no known$t/k$-diagnosis algorithm for general regular networks. In this paper, we first propose a general$t/k$-diagnosis ($k\ge 1$) algorithm for some$m$-regular networks. These$m$-regular networks satisfying some conditions could establish the$t/k$-diagnosis algorithm, say$t/k$-$G$-$DIAG$, to determine the$t/k$-diagnosability. The complexity of this algorithm is only$O(N\log N)$(when$N\ge 2^m$) or$O(Nm)$(when$N< 2^m$) where$N$is the number of vertices in the network. Second, we present a complete proof that the network$G$is actually$t/k$-diagnosable. Finally, we establish the$t/k$-diagnosability ($1\le k\le 3$) of some regular networks, including an$n$-dimensionalalternating group graph, an$n$-dimensionalSplit-Star Network, a$l^n$-hypermeshand an$(n,l)$-star graph, which are well-known interconnection networks proposed for multiprocessor systems.

Connectivity is a classic measure for fault tolerance of a network in the case of vertices failures. Extra connectivity and restricted connectivity are two important indicators of the robustness of a multi-processor system in presence of failing processors. An interconnection network's diagnosability is an important measure of its self-diagnostic capability. The conditional diagnosability is widely accepted as a new measure of diagnosability by assuming that any fault-set cannot contain all neighbors of any node in a multiprocessor system. In this paper, we analyze the combinatorial properties and fault tolerance ability for the Split-Star Network, denoted by Sn2, a well-known interconnection network proposed for multiprocessor systems, establish the g-extra connectivity, where 1 ≤ g ≤ 3. We also determine the h-restricted connectivity (h = 1; 2), and prove that the conditional diagnosability of Sn2(n ≥ 4) is 6n - 16 under the comparison model, which is about three times of the Sn2's traditional diagnosability. As a product, the strong diagnosability of Sn2is also obtained.

As the cardinality of multiprocessor systems grows, the probability of arising malfunctioning or failing processors in the system is bound to increase. It is then of both practical and theoretical importance to know the reliability of the system as a whole. One metric for a system's overall reliability is the measurement of the collective effect of its subsystems becoming faulty. However, a challenge of this approach is that the subsystems often interact with each other in a complex manner, making the analysis difficult. Wu and Latifi (Int. Sci., vol. 178, pp. 2337-2348, Oct. 2008) proposed two schemes to evaluate the system reliability of the Star graph network under a probabilistic fault model. The first scheme computes the combinatorial probability of subgraphs to obtain an upper-bound on the reliability by considering the intersection of no more than three subgraphs. The second scheme computes an approximate combinatorial probability by completely neglecting the intersection among subgraphs. Recently, Lin et al. have applied this approach to investigate the reliability of the multiprocessor system based on the arrangement graph (IEEE Trans. Rel., vol. 62, no. 2, pp. 807-818, Jun. 2015). In this paper, we extend the above approach by computing both upper- and lower-bounds and considering the difference of the two, to establish the reliability of the (n, k) -Star graph, another extensively studied interconnection network for multiprocessor systems. More specifically, we compute a lower-bound and an upper-bound on the reliability by taking into account the intersection of no more than four or three subgraphs, respectively. The empirical study shows that the upper- and lower-bounds are both very close to the approximate results. Especially, the lower the single-node reliability goes, the closer the approximate reliability is to both lower- and upper-bounds.

Extra connectivity is an important indicator of the robustness of a multiprocessor system in presence of failing processors. The g-extra conditional diagnosability and the t/m-diagnosability are two important diagnostic strategies at system-level that can significantly enhance the system's self-diagnosing capability. The g-extra conditional diagnosability is defined under the assumption that every component of the system removing a set of faulty vertices has more than g vertices. The t/m-diagnosis strategy can detect up to t faulty processors which might include at most m misdiagnosed processors, where m is typically a small integer number. In this paper, we analyze the combinatorial properties and fault tolerant ability for an (n, k)-arrangement graph, denoted by An,k, a well-known interconnection network proposed for multiprocessor systems. We first establish that the An,k's one-extra connectivity is (2k - 1) (n - k) - 1 (k ≥ 3, n ≥ k + 2), two-extra connectivity is (3k - 2)(n - k) - 3 (k ≥ 4, n ≥ k + 2), and three-extra connectivity is (4k - 4)(n - k) - 4 ( k ≥ 4, n ≥ k + 2 or k ≥ 3, n ≥ k + 3), respectively. And then, we address the g-extra conditional diagnosability of An,kunder the PMC model for 1 ≤ g ≤ 3. Finally, we determine that the (n, k)-arrangement graph An,kis [(2k - 1)(n - k) - 1]/1-diagnosable (k ≥ 4, n ≥ k + 2), [(3k - 2)(n - k) - 3]/2-diagnosable (k ≥ 4, n ≥ k + 2), and [(4k - 4)(n - k) - 4]/3-diagnosable (k ≥ 4, n ≥ k + 3) under the PMC model, respectively.

The${{t/k}}$-diagnosis is a diagnostic strategy at system level that can significantly enhance the system’s self-diagnosing capability. It can detect up to${{t}}$faulty processors (or nodes, units) which might include at most${{k}}$misdiagnosed processors, where${ {k}}$is typically a small number. Somani and Peleg (, 1996) claimed that an$n$-dimensional Star Graph (denoted${{S_n}}$), a well-studied interconnection model for multiprocessor systems, is${{((k + 1)n - 3k - 2)/k}}$-diagnosable. Recently, Chen and Liu (, 2012) found counterexamples for the diagnosability obtained in, without further pursuing the cause of the flawed result. In this paper, we provide a new, complete proof that an${\mbi {n}}$-dimensional Star Graph is actually${{((k + 1)n - 3k - 1)/k}}$-diagnosable, where${{1 \leq k \leq 3}}$, and investigate the reason that caused the flawed result in. Based on our newly obtained fault-tolerance properties, we will also outline an${ {O(N \log N)}}$diagnostic algorithm (${ {N = n!}}$is the number of nodes in${{S_n}}$) to locate all (up to${ {(k + 1)n - 3k - 1}}$) faulty processors, among which at most${ {k\, (1 \leq k \leq 3)}}$fault-free processors might be wrongly diagnosed as faulty.

Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3, and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AGn, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AGn's traditional diagnosability. As a byproduct, the strong diagnosability of AGnis also obtained.

As the size of a multiprocessor computer system grows, the probability of having faulty (i.e., malfunctioning or failing) processors in the system increases. It is then important to quantify how the faults collectively affect the entire system. The reliability of subsystems in a system, defined as the probability that a fault-free subsystem of a certain size still exists when the system has faults, is a measure for the faults' effect on the whole system. It can be used as an indicator of system health. In this paper, we will present two schemes to calculate the reliability of an$(n-1,k-1)$-subgraph in the$(n,k)$-Arrangement Graph$A_{n,k}$, an extensively studied interconnection network proposed for multiprocessor computers. The first scheme will use a probability fault model and the Principle of Inclusion-Exclusion to establish an upper-bound of the reliability, by taking into account the intersection of not more than three subgraphs. The second scheme uses basically the same idea, but completely neglects the intersection among subgraphs to calculate an approximate reliability. The results of the two schemes are compared, and are shown to be in good agreement, especially as the single-node reliability$p$goes low.