Journal of Innovations in Computer Science and Engineering (JICSE)

Abstract The concept of six degrees of separation stands as a significant phenomenon, positing that any two independent entities worldwide can connect through a chain of no more than six acquaintances. This article delves into the study of this phenomenon across various network models, aiming to quantify the rates of information propagation, idea dissemination, disease transmission, and predictive trends in society and economics. We extend the examination beyond the conventional notion of "six degrees of separation" by investigating the factors impacting degrees of separation and Milgram's condition in complex networks. Our objective is to elucidate that the actual degree of separation within a network is intricately tied to its structure and various parameters. Instead of being a universal rule, this concept can be construed as a condition that networks must satisfy. We explore Milgram's condition in diverse network models, encompassing random, small-world, and scale-free networks, while scrutinizing the impact of the frequency and length of cycles on degrees of separation. We introduce a novel criterion, termed multiplicity within the network and assess its relationship with the Hamming distance. We evaluate the effectiveness of Milgram's condition and degrees of separation in the context of these two parameters. Our findings underscore the close association between Milgram's condition and degrees of separation with the specific network model and its structure.

Abstract The de Bruijn graph, initially proposed as a topological architecture for interconnection networks, offers unique attributes. These graphs are regular, Eulerian, and Hamiltonian, boasting a small diameter close to optimal connectivity. Their low average distance, small diameter, and high connectivity contribute to remarkable fault tolerance against both node and edge failures. Comprehensively, these graphs serve as pivotal components in word-representing networks, finding applications in various scientific and engineering domains, particularly in genome assembly. They play a significant role in bioinformatics, information theory, coding, communication networks, and multiprocessors. Additionally, de Bruijn graphs are utilized in peer-to-peer (P2P) networks and distributed hash tables (DHT), demonstrating their versatility. Moreover, de Bruijn graphs can serve as a robust infrastructure for modeling online/offline user behavior. In this article, we delve into the different types of de Bruijn graphs and their unique properties from a graph theory perspective. Our focus is on evaluating the reliability of these graphs concerning resilience, fragility, and vulnerability to random failures and targeted attacks on both nodes and edges.

Abstract Moore and Shannon introduced a probabilistic model in which network nodes are assumed to be completely reliable, and communication links or edges can fail with a given probability, such as p. The main problem is determining the probability that the network will remain connected under these conditions, meaning establishing a route between the source and destination terminals. If all links are operational with the same probability of p, the reliability of the entire network is described as a function of p, leading to the reliability polynomial of the network. Moore and Shannon proposed their reliability analysis on specific networks known as hammock networks. Such networks can be well adapted to array-based circuits such as FinFET, VSFET, MOSFET, NEMS, and CNFETs. In this article, focusing on hammock networks, we utilize their combination to design and implement MOS-based transistors, i.e., nMOS and pMOS, and implement basic logical gates based on such networks. To determine the reliability polynomial coefficients, various methods have been presented, most of which exhibit computational complexity due to the recursive property. In practice, for circuits with large orders and sizes, the exact calculation of reliability polynomial coefficients falls into the NP-hard complexity class. In this study, while reviewing the existing problems, efficient methods have been employed to determine the polynomial coefficients of reliability. To ensure fair and accurate comparisons and evaluations, simulation results are utilized to extract performance and reliability measures for all circuits. The reliability of the investigated networks is then compared and analyzed.

Abstract Over the past few years, the study of complex networks as an interdisciplinary subject has yielded numerous insights. Communication links within these networks have been found to play a crucial role in shaping the implementation of dynamic processes. Recursive graphs are a class of complex networks whose internal structure is governed by recurrent relations. Among these, line graphs are especially important because they represent the communication links within the network as nodes. Studying the heterogeneity, or irregularity, of different graph models is a fundamental research issue in complex and social network analysis. In this article, we investigate the mapping between graph robustness and heterogeneity metrics and their equivalent metrics in line graphs. Specifically, we analyze the distribution of eigenvalues and important indices of heterogeneity in recursive and line graphs. We also examine the changes in heterogeneity of recursive line graphs with the introduction of a set of important heterogeneity indices. Our approach is broadly applicable to a wide range of indicators and complex networks beyond those discussed in this study.