Search

This paper proposes a parallel implementation of the Bron-Kerbosch algorithm, which finds all maximal cliques in large, complex graphs using CPU and thread-level parallelism and distributed memory with multiple cores. With the growing size and complexity of modern graphs, sequential algorithms can become impractical, making parallel computation a promising solution for reducing duration and enhancing scalability. Decomposing the graph into smaller components and distributing the workload across multiple threads using task parallelism is the proposed method. To optimise the algorithm’s efficacy across processes, load-balancing techniques are also investigated. The modified Bron-Kerbosch algorithm is implemented and evaluated on a variety of large graphs, exhibiting significant runtime and scalability enhancements over the sequential version. The conclusion of the paper discusses the prospective applications of the parallel Bron-Kerbosch algorithm in a variety of domains, including social network analysis, bio informatics, and network security. Overall, this research contributes to the expanding body of work on parallel computing and graph analysis by emphasising the advantages of CPU and thread-level parallelism for efficiently solving complex computational problems.

In the past few years, game randomizers have become increasingly popular. In general, a game randomizer takes some aspect of a game that is usually static and shuffles it somehow. In particular, in this paper we will discuss the type of randomizer that shuffles the locations of items in a game where certain key items are needed to traverse the game world and access some of these locations. Examples of these types of games include series such as The Legend of Zelda and Metroid. In order to accomplish this shuffling in such a way that the player is able to reach the end of the game, some novel algorithms in graph theory must be utilized, where the game world and its item locations are represented as a graph and each edge on the graph has some rule for which items are required to traverse it. In this paper, we define these algorithms formally and evaluate them with different metrics that can guide a developer’s decision about which algorithm works best for their game.

Formation flight holds significant potential for various applications involving aerial robot swarms. However, current methodologies lack the capability to autonomously execute large-scale formation flights in densely populated environments. To bridge the gap, a decentralized and asynchronous formation flight planner is proposed based on a graph-based formation metric and tight representations of kino-dynamically feasible trajectories for collision avoidance. The planner handles formation path planning along with dynamic obstacles and intervehicle collision avoidance using minimum volume convex hulls for agent trajectories. The employed formation metric is invariant to rotation, translation, and scaling, granting greater flexibility in formation coordination. A decoupled and distributed trajectory optimization framework is proposed to enhance the computational feasibility of large-scale formation flights. Moreover, to mitigate issues relating to communication delays between agents, asynchronous execution of a finite horizon navigation framework with usage of sparse trajectory control points for trajectory segments is employed. Simulations with multiple agents, static and dynamic obstacles support the robustness of the planner to formation flights in real world. The planner demonstrates goal/waypoints achievement and formation adherence capabilities that are assessed and compared using a popular quantifiable formation similarity metric. Furthermore, the paper also serves as a guideline to build upon trajectory planning frameworks for tight formation control in cluttered, dynamic environments.

Graph Attention Networks (GAT) is a type of neural network architecture designed to effectively model and process data represented as graphs. GATs leverage the concept of attention mechanisms to learn the importance of different nodes in a graph when performing tasks such as node classification or link prediction. By assigning attention weights to neighboring nodes, GATs can capture the relevance and influence of different graph elements in a localized manner. In this paper, we present Graph Oriented Attention Networks (GOAT) as a novel approach for attention calculation in graph-related tasks, where attention is specifically directed towards a particular destination node during each iteration. This approach aims to enhance the interpretability and control of attention within a graph neural network. By focusing attention on a specific destination node, the model can explicitly consider the influence of that particular node on the different graph nodes, providing insights into its role and importance within the graph structure. This approach is particularly valuable in scenarios where understanding the impact of individual nodes on specific targets is critical: in our case, to predict a heuristic for the $\text{A}^{\ast} $ search algorithm, we are focusing the attention on the destination node. Experimental results indicate that this new approach effectively improves both the performance and interpretability of graph-based models, facilitating a more fine-grained analysis of graph dynamics and the factors influencing specific nodes.

In this paper, an age of information (AoI) oriented data collection scheme is proposed for wireless sensor networks with energy-constrained unmanned aerial vehicles (UAVs). Different from traditional approaches that focus on one single UAV, we advocate the activation of multiple candidate UAVs to improve the AoI performances. However, coordinating multiple UAVs complicates the data collection strategies of each UAV, rendering AoI minimization a formidable challenge. To address the intractable formulated optimization problem, we propose a heuristic two-step algorithm based on greedy search for multiple UAVs. Specifically, we address the coordination of multiple UAVs through a novel algorithm grounded in graph theory and kernel K-means methods. Concurrently, we devise an energy-constrained trajectory planning algorithm to optimize data collection for each activated UAV. The numerical results validate the accuracy of the proposed algorithm, and demonstrate that both average AoI and energy consumption per UAV can be reduced when more energy-constrained UAVs are involved in the data collection process for wireless sensor networks.

Complex networks play a significant role in our daily lives. Due to the fact that complex networks, in reality, could suffer from manifold perturbations and network components could break down, it is, therefore, pivotal to investigate the robustness of complex networks in the face of perturbations. In the literature, enormous endeavors have been made to study network robustness. However, existing studies mainly deal with the interdependent networks, while little attention is paid to study the robustness of bipartite networks. Many networks, such as economical networks and biological networks, can be modeled as bipartite networks. It is therefore important to study the robustness of bipartite networks. Because the structures of bipartite networks differ from that of networks in common sense, existing robustness analysis methods cannot be applied to bipartite networks. With regard to this, this paper proposes a generic method based on the probabilistic theory to assess the robustness of bipartite networks under random node failures. The proposed method mathematically indicates that bipartite networks are robust to random perturbations. The experiments on random bipartite Erdös-Rényi and scale-free networks demonstrate that the theoretical results yielded by the proposed method coincide quite well with the simulation results. This paper also compares the proposed method against the well-studied method. The experiments indicate that the proposed method outperforms the comparison method.

With the rapid development of urban rail transit, huge subway systems have been built, which is the best choice for people due to the efficiency, safety, and punctuality. Therefore, the ability of subway systems to resist failures especially interruptions has attracted the attention of operators. In the paper, based on the graph theory, a resilience assessment method is proposed to quantitatively measure the performance and recovery rapidity within unifying metrics and models. We represent the subway network with an undirected graph where the subway stations are described using the nodes whereas tracks are demonstrated with the edges. The performance evaluation of a subway network is implemented based on the assessment of passenger flow and topological structure of the network, where weighted degrees and the weighted sum of the reasonable passageway to the other nodes are considered. The resilience of a subway network can be associated to the network performance loss triangle over the relevant timeline from the occurrence of a random or intentional disruption to full recovery. The Beijing Subway is taken as the example to perform the proposed approach which is verified through the numerical results in the paper. Following the resilience evaluation, a structure optimization model with a computational algorithm is proposed. Based on the genetic algorithm, we achieved the solution results of the simplified network of the Beijing Subway. Several interesting conclusions are drawn from the results.

Extensive studies regarding complete coverage problems have been conducted, but a few tackle scenarios where the mobile robot is equipped with reconfigurable modules. The reconfigurability of these robots creates opportunities to develop new navigation strategies with higher dexterity; however, it also simultaneously adds in constraints to the direction of movements. This paper aims to develop a valid navigation strategy that allows tetromino-based self-reconfigurable robots to perform complete coverage tasks. To this end, a novel graph theory-based model to simulate the workspace coverage and make use of dynamic programming technique for optimal path searching and adaptive robot morphology shifting algorithms is proposed. Moreover, the influence of algorithms starting variables on workspace coverage outcome is analyzed thoughtfully in this paper. The simulation results showed that the proposed method is capable of generating navigation paths throughout the workspace, which ensures complete workspace coverage while minimizing the total number of actions performed by the robot.

In the era of big data, reduced models capable of reducing big data graph to estimate personalized PageRank are limited. Personalized PageRank is a page rank calculation where random jumps are only allowed to a subset of start nodes. The resources of current process of calculation of personalized PageRank are highly prohibitive, thus in this paper we propose a novel fast accurate and less resource intensive algorithm to the personalized PageRank problem. FAST Personalized PageRank is utilized to find the target node set. Using the mentioned target set, the algorithm gives an estimation of the closeness of any pair of nodes in the graph. As the time taken by the estimation of personalized PageRank is directly proportional to the network size, in this paper a node reduction method is used to prune the graph. In this pruning model, most popular nodes also known as hubs are found using personalized page vector. To decrease the entropy and reduce the number of alternate paths to the target nodes, popular nodes are identified and flagged. The flagged nodes are, then, given a lower priority in the computation. This way the redundant path will being ignored in the computation process. After pruning the graph, estimation results achieve an improved time complexity. In our experiment, we compare our result with the benchmark FAST personalized PageRank approach. Our algorithm significantly reduces the computation time and outperforms the benchmark FAST personalized PageRank algorithm in highly dense graphs.

The world of system of systems engineering (SoSE), and consequently systems engineering, is currently being reformalized so as to provide greater functionality, integration, and extensibility into designed systems of systems (SoS). Graph theory and big data techniques are in position to play substantial roles in this reformalization, and hence, this paper fills a significant need by bringing together all known current applications of graph theory to SoSE in tutorial/summary form. In this paper, we explore the applications of graph theory and known graph algorithms for system design (and SoS design), optimization techniques, complexity measures, and novel graph algorithms for real-time deployment of SoS's and managing SoS design. The work is straightforward with several examples, and is meant to be a standalone document that can be used to quickly come up to speed regarding the applications of graph theory in SoSE.

Graph theory within power electronics, developed over a 50-year span, is continually evolving, necessitating ongoing research endeavors. Facing with the never-been-seen explosion of graph-structured data, the state-of-the-art deep learning technique-Graph Neural Networks (GNNs), becomes the leading trend in machine learning within just recent five years and demonstrated surprisingly broad and prominent benefits covering from new drug discovery to better IC design. However, its promising applications in Power Electronics are still rarely discussed and its full potential remains unexplored. Addressing this gap, this review paper is the first to outline GNNs’ general workflow in power electronics, laying the groundwork and examining current GNN methodologies within the field. To bridge the gap in the sparse GNN literature within this domain, we also provide extended discussions on leveraging insights from GNN-aided circuit design to enrich power electronics research. Our work includes in-depth GNN-based case studies that demonstrate promising applications from converters to system-level power electronics, showcasing GNNs’ unique benefits and untapped possibilities (e.g., accurate component design, voltage predictions on IEEE-13 bus and 118 bus systems). Additionally, we provide a comprehensive survey of GNNs’ latest and successful applications, emphasizing their impact on energy-centric sectors, such as transportation electrification, smart grids. Considering the interdisciplinary nature of power electronics in modern energy systems, our review highlights the potential of GNNs emerge as a promising tool to decode the intricate behavior and dynamics of power electronics systems, and we hope such synergies between advanced AI methodologies like GNNs with the ever-evolving graph theory can lead to more powerful tools, novel methodologies, and advancements in the power electronics community.

In this paper, we propose a load-balancing algorithm for small-cell integrated access and backhaul (IAB) networks operating in the millimeter wave (mmWave) band. With the help of mmWave communications, ultra-dense small cell deployment is a key technology for future networks, but it leads to high fiber installation costs. IAB has emerged as a cost-effective and flexible solution because it uses the multi-hop wireless backhaul to the core network via macro base stations (BSs). Multi-hop transmission and spectrum sharing between access and backhaul links cause an unbalanced load across BSs under IAB. To tackle the unbalanced load problem, we propose a graph-based load balancing algorithm for IAB by estimating and adapting to network load status. The weight of the graph is represented as the cost of the link between two BSs and is defined to reflect the cell load and link capacity. The proposed algorithm estimates the upcoming load and adjusts the network transmission schedule to balance the load inside the network. Through simulations, performance is evaluated in various environments. The simulation results show that the proposed algorithm not only distributes the load across small cells more evenly but also increases network throughput by 22.3% and 32.1% with 16.3% and 28.7% higher in UEs satisfaction when compared to MaxMinThroughput and Backpressure algorithms.

In this paper, we present a novel approach to estimating multiple time delays (TDs) in sensor arrays that is robust to outliers of TD measurements. These measurements are typically obtained from the peak of the cross correlation of two sensor signals but may contain outliers due to noise, significantly degrading the performance of downstream applications. To address this issue, we propose an approach to leverage only the best minimum-necessary TD measurements. First, we describe the general properties of TDs and show that the degree of freedom of TDs is the number of sensors minus one for a signal source, which indicates that the full set of TDs is redundant in this case. We then consider selecting nonredundant TDs from all measurements given the necessary and sufficient condition to reconstruct all TDs uniquely. We represent this condition by utilizing the graph theory, and then, formulate an optimization problem to select the optimal nonredundant TDs while satisfying the condition above. We reduce this problem to the problem of finding a minimum spanning tree and propose an efficient algorithm for TD estimation. Experimental evaluation shows that our method successfully eliminates outliers while ensuring that all TDs can be restored.

Weighted Petri nets are common tools for modeling and validating discrete event systems involving resource allocation, such as flexible manufacturing systems (FMSs). A subclass of weighted Petri nets called a system of sequential systems with shared resources (S4R) has the power for modeling complex FMSs where the execution of an operation may require multiple resource types and multiple units of some resource types. Deadlock resolution is a crucial issue for the operation of an FMS. A direct and efficient policy is developed in this paper for detecting deadlock markings by extracting a weighted resource flow graph (WRFG) from an S4R and recovering them by synthesizing a recovery-transition-based controller. This study contributes to the field with five folds: 1) with S4R, an efficient integrated policy is put forward for robust supervisor synthesis; 2) it enhances an algorithm for extracting the WRFG from an S4R to reveal the shared resource competitions by different processes; 3) to detect partial deadlock markings, a technique for finding weighted circular wait graphs (WCWGs) in WRFG is presented; 4) with WCWGs, an algorithm is designed for the design of recovery-transition-based controller such that the resulting controlled system becomes deadlock-free; and 5) it presents a comprehensive analysis to demonstrate the proposed method by using the Integrated Net Analyzer (INA). With the proposed policy, it is not necessary to generate a reachability graph, making the method efficient. Finally, the performance of the proposed policy is illustrated by some commonly used examples.

The security of in-vehicle networks has become an important issue as automobiles become more connected and automated. In this paper, we propose a graph-based intrusion detection and classification system, named G-IDCS, which aims to enhance the security of the in-vehicle controller area network (CAN) protocol. Existing intrusion detection systems (IDSs) using graph theory suffer from limitations, such as requiring a large number of CAN messages for detection and being unable to classify attack types despite analyzing numerous messages. Meanwhile, machine learning or deep learning-based systems have limited sensitivity to environmental changes such as attack type change due to model overfitting, and are unable to provide explanations for classification decisions. Using various graph features, our threshold-based intrusion detection method overcomes these limitations by integrating a threshold-based IDS and a machine learning-based attack type classifier. Our threshold-based intrusion detection method of G-IDCS reduces the number of CAN messages required for detection by more than 1/30 and improves the accuracy of combined attack detection by over 9% compared to an existing intrusion detection method that uses graph theory. Furthermore, unlike existing machine learning and deep learning-based intrusion detection systems, our threshold classifier is robust to changes in attack types and can provide explanations for the features used in attack detection. In addition, our machine learning-based attack type classifier outperforms existing techniques in all performance metrics and can serve as a digital forensic tool for investigating cyber attacks on in-vehicle networks. Using the classifier to identify attack types can facilitate the design of corresponding protection methods, thereby enhancing the security of in-vehicle networks.

Over the past few years, the number and volume of data sources in healthcare databases has grown exponentially. Analyzing these voluminous medical data is both opportunity and challenge for knowledge discovery in health informatics. In the last decade, social network analysis techniques and community detection algorithms are being used more and more in scientific fields, including healthcare and medicine. While community detection algorithms have been widely used for social network analysis, a comprehensive review of its applications for healthcare in a way to benefit both health practitioners and the health informatics community is still overwhelmingly missing. This paper contributes to fill in this gap and provide a comprehensive and up-to-date literature research. Especially, categorizations of existing community detection algorithms are presented and discussed. Moreover, most applications of social network analysis and community detection algorithms in healthcare are reviewed and categorized. Finally, publicly available healthcare datasets, key challenges, and knowledge gaps in the field are studied and reviewed.

Modern distribution grids are transforming due to the increasing amount of load and generation based on DC technologies, whose interconnection is facilitated by the upcoming AC-DC distribution networks. Their fault management is challenged by new issues related to the power transferred among AC and DC sub-networks. In light of this, the present paper proposes a novel Service Restoration (SR) algorithm, specifically tailored for AC-DC distribution grids, that optimizes the re-energization by establishing priorities of disconnected bus groups and computing, as candidate solutions, hierarchical combinations of normally open and normally closed switches. To overcome the limitations of existing approaches, a Multiple Criteria Decision Analysis (MCDA) is proposed to combine and objectively prioritize different SR goals (i.e., the use of telecontrolled switches, the minimization of power losses, and the applicability of the proposed solutions in a defined time horizon), and ultimately make the grid operator benefit from the possibility to flexibly tune different operational objectives. The proposed algorithm allows to effectively discriminating competing solutions, i.e., whence and how to re-energize disconnected buses, and complies with the time requirements for field implementation. The results prove the crucial role of DC sub-networks, associated to the control of power injection from AC-DC converters, in enhancing the SR by improving its targets and increasing the number of re-energized loads. Ultimately, the effect of MCDA comparison parameters on the SR outcomes is quantitatively investigated via global sensitivity analysis, whose adoption is recommended for supporting the grid operator in the algorithm implementation.

The aim of this study is the computerization of the argument Delphi method. The Delphi method is mainly designed for qualitative prediction within a group of experts, where the experts make predictions and a facilitator controls these predictions until the experts end up with a level of consensus. Argument Delphi, as opposed to the classical Delphi model, is built on the contradictions of the ideas of the experts. Argument Delphi mainly focuses on a discussion topic and asks experts to create new arguments and criticize other arguments from other experts. After a certain level of contradiction, the method yields an amount of contradictory, criticized arguments and builds a decision over these antitheses, as in the Hegelian approach. This is the first time the argument Delphi method has been modeled in a graph of arguments and the problem of qualitative decision has been transferred into a graph problem using Delphi method. This paper is also the first time that argument aggregation and evaluation methods have been proposed. Moreover, the computerized version of argument Delphi is applied to real-world problems using crowd involvement through Facebook. The problem is defined as the prediction of petroleum prices for the end of year and more than 100 contributors from all around the world argued and criticized each other. This paper also discusses the findings of this case study.

The smart grid connects components of power systems and communication networks in an interdependent two-way system that delivers electricity to consumers and collects data that enables it to react to usage levels and interference from threats, such as cyber-attacks. In this paper, we propose a novel cyber-attack failure propagation model in smart grids. Our realistic failure propagation model addresses the system’s heterogeneity by assigning different roles to its components. We define rules for and interdependencies of failure propagation and propose a new approach to studying cascading failures. In addition, our graph model identifies the most-vulnerable nodes. The model implements power flow analysis to guarantee that all transmission lines work below capacity and remove lines exceeding capacity. The model also considers that control packets could encounter different delays regarding the communication network structure and investigates the impact of communication delay on the failure of power components. Our results establish that by considering both power and communication characteristics and interdependencies, cascading failures can be modeled more accurately. We show that when we run the power flow analysis, there are a negligible number of failed nodes, which means that our model accurately identifies system failures.

The multipath challenge is a research line in continuous development because of its multiple benefits, however, these benefits are overshadowed by scalability, which goes down considerably when the paths are multiple and disjoint. The disjointness aggregates an extra value to the multiple paths, but it also implies more complex mathematical operations that increase the computational cost. In fact, diverse proposals exist that try to increase scalability by limiting the number of paths obtained to the minimum possible (two-disjoint paths), which is enough for backup applications but not for other purposes. This paper presents an algorithm that solves these drawbacks by discovering multiple disjoint paths among multiple nodes in an efficient way, while keeping bounded the computational cost and ensuring scalability. The proposed algorithm has been validated thoroughly by performing a theoretical analysis, bolstered afterwards by an exhaustive experimental evaluation. The collected results are promising, our algorithm reduces the time spent to obtain the disjoint paths regarding its competitors between one and three orders of magnitude, at the cost of a slight decrease in the number of paths discovered.

Community detection in network-type data provides a powerful tool in analyzing and understanding real-world systems. In fact, community detection approaches aim to reduce the network’s dimensionality and partition it into a set of disjoint clusters or communities. However, real networks are usually corrupted with noise or outliers which affect the detected community structure quality. In this paper, a new robust community detection algorithm that is capable of recovering a clean or a smoothed version of the corrupted graph and detecting the correct community structure is introduced. The proposed approach combines robust principal component analysis (RPCA) and symmetric nonnegative matrix factorization (SymNMF) in a single optimization problem. The proposed problem is solved under the framework of alternating direction methods of multipliers (ADMM). In particular, the corrupted adjacency matrix is decomposed into a low-rank and sparse components using RPCA and the community structure is detected by applying SymNMF to the extracted low-rank component. Extensive experiments that have been conducted on real and simulated binary and weighted networks show that the proposed approach significantly outperforms existing algorithms in detecting the correct community structure even in grossly corrupted networks.

In recent years, with regional integrated seabed resource exploitation continuing to expand, offshore oilfield power systems have gradually become networked, forming an offshore oilfield multi-platform interconnected power system. In this paper, a two-level optimization model for offshore oilfield multi-platform interconnected power system structure is developed. The lower-level model uses a minimum cut-load cost model that considers load priority to calculate the power outage losses of all N-1 fault conditions. The reliability assessment method helps to achieve a balance between economy and reliability. Additionally, an optimization model simplification method based on graph theory is proposed, and it uses the minimum cost maximum flow (MCMF) algorithm to optimize the power flow of the grid and narrows the problem's solution space. At the end of modeling, a parallel global taboo search algorithm is used to reduce the computational time and improve the probability of finding an optimal solution. Investigations of a real offshore oilfield multi-platform power system verify the accuracy of the model, the simplification method and the parallel global taboo search algorithm.

Power system benchmarks are transmission and distribution networks used to evaluate novel control algorithms and simulate grid evolution scenarios. These benchmarks range in size, system characteristics, and use cases. Although active working groups have created and published many benchmarks, these networks are not all representative of a given region and may not consider certain aspects such as increased penetration levels of distributed energy resources. To address these issues, synthetic benchmark networks and methodologies for generating them have been developed by various research groups. This paper provides a comprehensive survey of procedures commonly used to generate synthetic networks and a detailed account of the various metrics used to define and validate benchmarks. Existing models are categorized into different approaches, including expert design, anonymized clustering, statistical sampling, and heuristic algorithms. Deep graph generation based techniques are also presented and recommended for the network generation problem. A comparative summary is provided to highlight the different existing works in this area and reveal research gaps, along with a list of published datasets and their characteristics.

The leader-follower model is found efficient for robot swarm exploration tasks. When a swarm of mobile robots collaboratively explore an unknown environment with limited communication, such as communication delay or even message loss, it is necessary to adaptively re-group robots according to the dynamic communication conditions and task goals. In this paper, we propose to analyze the leader-follower topology in a graph fashion and employ Ratio Cut of the proposed graph for membership re-assignment. We take each robot as a node and consider both the communication delay and the goal, i.e., exploring towards unknown area, as the edge weight. Then we use the Laplacian matrix to bipartition the graph repeatedly to optimize group partition. Simulation results validate the effectiveness of the proposed method.

This paper proposes analytical approaches to extend the capacity of existing networks of electric vehicles (EVs) by placement of additional charging stations (CSs) as well as determining the sizes of existing and new CSs in order to handle future expansions of EVs. The EV flow at CSs is modeled by a graph where nodes are potential locations for CSs and edges are uncertain parameters representing the variable EV flow at CSs. The required extra CS locations are explored by transforming the CS placement problem into a controllability framework addressed by maximum matching principle (MMP). To find the sizes of each CS, the graph of CS network is partitioned featuring only one CS in each subgraph. The size of CS in each subgraph is then determined by transforming the problem into the problem of robust stability of a system with uncertain parameters where each parameter is associated with an edge of subgraph. The zero exclusion principle is then tested for the related Kharitonov rectangles and polygonal polynomials of closed loop system with selected feedback gain as CS capacity. The proposed analytical approach is tested on the existing Tesla CS Network of Sydney. The locations of extra required CSs as well as the sizes of existing and new CSs are determined to maintain the waiting times at all stations below the threshold level.

The manufacturing process of modern equipment becomes very complex due to features such as mass units, multiple machining, and complicated coupling-relationships, posing a big challenge for determining the manufacturing scheme. This paper addresses the challenge by proposing a graph theory-based optimization design for the complex manufacturing process. A detailed analysis of a serial of graph models built according to the manufacturing process features reveals that the Hamilton graph is suitable for modeling the manufacturing process system. Some model weight assignment functions are extracted for the quantitative study. Further the optimal scheme for an optimization design of the complex manufacturing process is solved using the full link graph feature algorithm - a search optimization algorithm. A manufacturing model matrix is constructed, and penalty number and divisor are formulated to simplify the matrix and improve the algorithm efficiency in the process of algorithm design. An example is provided to demonstrate feasibility and effectiveness of the proposed method.

As the system becomes more and more complex, we are usually in the state of indeterminacy. In the real world, the states of uncertainty and randomness are the two most common types of indeterminacy. An uncertain random graph is applied to describe a graph model with uncertainty and randomness simultaneously. This paper mainly focuses on the connectivity of two vertices in an uncertain random graph. Firstly, a local connectivity index is proposed to unveil the chance measure that two special vertices are connected in an uncertain random graph. Furthermore, a method for calculating the local connectivity index is formulated. In addition, some simplified forms of the method are developed, and an algorithm is designed to obtain the local connectivity index. Finally, the information relevant to the relationship between the local connectivity index and the connectivity index is discussed.

In many practical problems, randomness and uncertainty simultaneously appear in one complex system or network. When graph theory is applied to these problems, these complex systems or networks are usually represented by uncertain random graphs, in which some edges exist with degrees in probability measure, and some other edges exist with degrees in uncertain measure. In this paper, we focus on the connectivity of uncertain random graphs with respect to vertices. We propose the concepts of k-vertex-connectivity index and the connectivity of an uncertain random graph. The former is the chance measure that an uncertain random graph is k-vertex-connected, and the latter is an uncertain random variable, which characterizes the connectivity of the uncertain random graph with respect to vertices. We discuss some properties of these concepts. Methods and formulas are also presented for calculating the k-vertex-connectivity index, and the distribution and expected value of the connectivity of an uncertain random graph.

Optimal placement of flexible AC transmission systems (FACTS) devices and the cyber-security of associated data exchange are crucial for the controllability of wide area power networks. The placement of FACTS devices is studied in this paper from a novel graph theoretic perspective, which unlike the existing approaches, purely relies on topological characteristics of the underlying physical graphs of power networks. To this end, the maximum matching principle (MMP) is used to find the set of required FACTS devices for the grid controllability. In addition, the cyber-security of the most critical data related to the FACTS controllers is guaranteed by introducing the concept of moderated-k-security where k is a measure of data obscurity from the adversary perspective. The idea of moderated-k-symmetry is proposed to facilitate the arrangement of the published cyber graph based on a permutation of nodes within the symmetry group of the grid, called generator of automorphism. It is then verified that the published cyber-graph can significantly obscure the data exchange over the cyber graph for adversaries. Finally, a similarity is observed and demonstrated between the set of critical nodes attained from the symmetry analysis and the solution of the FACTS devices placement that further highlights the importance of symmetry for the analysis and design of complex power networks. Detailed simulations are applied to three power networks and analyzed to demonstrate the performance and eligibility of the proposed methods and results.

Privacy has become a major concern in data mining as it is utilized in many important applications. Distributed privacy-preserving data mining (DPPDM) is one of the techniques to address this concern, which focuses on protecting private information of members in distributed systems during data mining. As DPPDM is widely discussed in recent works, the semi-supervised manner of learning still draws less attention in this field. In this paper, a mixture-model-based semi-supervised DPPDM method is proposed. By introducing our method, a site in a distributed system is able to initiate a learning process using labeled data of its own and unlabeled data from all the sites. During the process, no individual data of any site is revealed to others, no information about data can be traced back to any specific site, and only the initiating site learns the result. We propose a parameter-masking privacy-preserving Expectation-Maximization (EM) algorithm and a mixture-model-based semi-supervised learning algorithm as the two main steps of our method. Experiments on both synthetic and real-world data demonstrate the effectiveness of the proposed method.

This paper proposes a formation control algorithm to create separated multiple formations for an undirected networked multi-agent system while preserving the network connectivity and avoiding collision among agents. Through the modified multi-consensus technique, the proposed algorithm can simultaneously divide a group of multiple agents into any arbitrary number of desired formations in a decentralized manner. Furthermore, the agents assigned to each formation group can be easily reallocated to other formation groups without network topological constraints as long as the entire network is initially connected; an operator can freely partition agents even if there is no spanning tree within each subgroup. Besides, the system can avoid collision without loosing the connectivity even during the transient period of formation by applying the existing potential function based on the network connectivity estimation. If the estimation is correct, the potential function not only guarantees the connectivity maintenance but also allows some extra edges to be broken if the network remains connected. Numerical simulations are performed to verify the feasibility and performance of the proposed multi-subgroup formation control.

Connectivity is one of the most important concepts in graph theory. When graph theory is applied to complex systems with indeterminate factors, uncertainty and randomness are two basic types of indeterminacy. Therefore, the model of uncertain random graph was proposed via chance theory, in which some edges exist with degrees in probability measure and others exist with degrees in uncertain measure. This paper discusses the connectivity of an uncertain random graph with respect to edges. Concepts of k-connectivity index and edge-connectivity of an uncertain random graph are proposed. Methods and algorithms for calculating the k-connectivity index and the distribution of edge-connectivity are also proposed. In addition, some properties of them are discussed.

Brain computer interface (BCI) has been widely studied to allow people to control external devices as an extension of capabilities or a replacement of lost functions. The decoding algorithm of brain signals is a crucial part in BCI, since its performance determines the efficiency of the interface. Decoding performance can be improved by generating optimal feature matrix. The objective of this paper is to propose and implement a decoding algorithm with optimized small dimension feature matrix on identifying motor intention of finger movement using electroencephalogram (EEG) signals. An experiment was designed and conducted, in which EEG was acquired from 10 healthy subjects during the left or the right index finger movement. Event-related desynchronization (ERD) topography was analyzed during motor tasks. A degree feature extraction algorithm was proposed based on the graph theory together with Support Vector Machine (SVM) to classify two kinds of index finger movement, which takes three factors into consideration: frequency bands, amplitude and range of ERD. The results showed that the algorithm can classify the finger movement effectively for 7 subjects based on a three-dimension optimized feature matrix, consisting of the maximum degree, average degree and clustering range. The proposed algorithm is not limited by the size of samples and can indicate the source area of the neural activities. Results also demonstrate that the proposed degree feature extraction algorithm can smooth signal noise and enlarge the feature differences between the contralateral and the ipsilateral hemispheres.

Rapid development of single cell RNA sequencing (scRNA-seq) technology has accelerated the exploration in biomedical researches. One of the focal interests in scRNA-seq data analysis is to classify cells into different types, which significantly assists in studying inter-cellular heterogeneity, such as cell types, cell states, and cell lineages, at the resolution of single cells. Although a number of tailored approaches have been developed for scRNA-seq data, their performance varies with different datasets and their clustering accuracy need to be improved. In this paper, we propose a novel ensemble clustering framework for scRNA-seq data called GRACE (GRAph-based Cluster Ensemble approach). First, we construct a highly reliable graph network for single cells by combining the clustering outcomes from five leading scRNA-seq data clustering methods. Then, we remeasure the relationships between cells by exploring the topology structure of network using random walk distance. Finally, we build a hierarchical cell-tree and obtain the clustering labels by cutting the tree structure into an appropriate number of sub-trees. Experimental results on twelve benchmark datasets show that GRACE has the higher clustering accuracy and is more robust among a variety of datasets than the state-of-the-art individual approaches. In addition, the graph structure of the network which is built upon the ensemble clusters is more reliable than the networks which are constructed according to the conventional similarity metrics.

A monotone fuzzy rule relabeling (MFRR) algorithm has been introduced previously for tackling the issue of a non-monotone fuzzy rule base in the Takagi-Sugeno-Kang (TSK) Fuzzy Inference System (FIS). In this paper, we further propose a new three-stage framework to develop a computationally efficient MFRR algorithm. The first stage determines the combinations of fuzzy rules to be relabeled by exploiting the prior information derived from a given non-monotone fuzzy rule base. This prior information includes the minimum number of fuzzy rules to be relabeled (denoted as $k$ ), as well as the states of fuzzy rules that must be, must not be, or may be relabeled. The second stage relabels the consequent parts of multiple sets of $k$ noisy fuzzy rules obtained from the first stage, such that a monotone fuzzy rule base is produced. The third stage selects the most suitable relabeled fuzzy rule base among the potential monotone fuzzy rule bases obtained from the second stage, either objectively or subjectively. We provide insights into MFRR and discuss its practical implementation. In addition, a network flow method is fused with the proposed MFRR framework, resulting in an efficient computation scheme. The MFRR framework is applied to Failure Mode and Effect Analysis (FMEA) problems related to a sewage treatment plant and a public hospital. It is also evaluated with real FMEA information from a semiconductor plant. The results are analyzed and discussed, which positively demonstrate the effectiveness of the proposed MFRR framework in formulating a monotone TSK-FIS model for undertaking FMEA problems.

Given a large graph, such as a social network or a knowledge graph, a fundamental query is how to find the distance from a source vertex to another vertex in the graph. As real graphs become very large and many distributed graph systems, such as Pregel, Pregel+, Giraph, and GraphX, are proposed, how to employ distributed graph systems to process single-source distance queries should attract more attention. In this paper, we propose a landmark-based framework to optimize the distance computation over distributed graph systems. We also use a measure called set betweenness to select the optimal set of landmarks for distance computation. Although we can prove that selecting the optimal set of landmarks is NP-hard, we propose a heuristic distributed algorithm that can guarantee the approximation ratio. Experiments on large real graphs confirm the superiority of our methods.

The quantitation of morphology information of X-ray angiography image has an important value in the diagnosis of coronary artery disease. This paper proposes an automatic morphology estimation method by using directed graph construction for X-ray angiography images. The quantitation of vascular tree morphology is achieved in three steps, including undirected graph construction, edge direction estimation, and directed graph construction. First, an undirected graph is constructed to represent the primary topology of the vessel tree. Vessel centerline is extracted and is then split and reassembled as edges of the undirected graph. Second, each edge is assigned with a direction by an iterative algorithm, where graph structure and geometrical parameters of vessels are used as constraints. Third, each edge is assigned to its parent based on a matching function, and the directed graph is finally constructed according to the parent-child relation between edges. As the output of the proposed method, the directed graph can provide the morphology information of the vessel tree, including the radius of each vessel segment, the blood flow direction, and the connectivity between vessel segments. The proposed method is validated with the simulated data and the real clinical coronary angiography data. An average edge parent accuracy of 97.44% and an average edge direction accuracy of 99.44% can be archived.

In this paper, a graph-theory-based approach for representing planar mechanisms is presented, the Santiago Portilla method (SPM). From the corresponding adjacency matrix, SPM generates an extended matrix containing the complete characterization of a planar mechanism, including all the information about both topology and geometry. This matrix representation can be used for the optimal design of mechanisms, allowing simultaneously the topological and dimensional synthesis by means of computational tools such as the metaheuristic algorithms. A case study corresponding to the design of a fixed-linear-trajectory tracker mechanism is included in order to test the efficiency of the proposed approach. It was carried out by addressing the design as an optimization problem and solving it with the differential evolution algorithm, representing the individuals in its population by the matrix form generated by the SPM. The results of the case study show that the SPM and its matrix representation constitute a useful and flexible tool for the solution of the real engineering problems involving the design of planar mechanisms.

Subgraph pattern matching is a basic building block for many applications. Where to commence the pattern matching task and how to proceed are fundamental issues in massive graphs. In this paper, we propose the most impact vertices in view of a query graph and diffusion walk on data graph. We present a novel impact vertices-aware diffusion walk algorithm, a distributed algorithm named DiffWalk, for subgraph pattern matching. Our algorithm employs the most impact vertices from a query graph to locate the initial search position and then proceeds to traverse a large-scale data graph by diffusion walk. We give theoretical analyses based on probability inference and spectral graph, which prove that graph pattern matching beginning at the most impact vertices could prevent comparison overhead by low-probability events first, also prove that diffusion walk could traverse graph efficiently. We have performed a range of experiments that demonstrate our algorithm efficiency both in running time and communication size.