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.

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.

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 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.

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.

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.