Search

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G, two vertices s, t ∈ V(G), and an integer k, adds (randomly) to G a number of arcs such that for every minimal st-cut Z in G of size at most k, with probability 2−poly(k) the set Z becomes a minimumst-cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set whose parameterized complexity status was repeatedly posed as open problems: Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], a number of weighted variants of classic directed cut problems, such as Weightedst-Cut or Weighted Directed Feedback Vertex Set. By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H, if the ListH-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

The main results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By dense we mean that \(|E(G)|\ge \alpha \, |V(G)|^2\) for some fixed \(\alpha \gt 0\). While a constant-factor approximation is trivial for this class of graphs, approximations with factor arbitrarily close to 1 need a sophisticated algorithm and complicated mathematical justification. More precisely, we provide an algorithm that for a given (dense) graph G of order n and given \(\varepsilon \gt 0\) , returns an integer g such that G has an embedding in a surface of genus g, and this is ɛ-close to a minimum genus embedding in the sense that the minimum genus \(\mathsf {g}(G)\) of G satisfies: \(\mathsf {g}(G)\le g\le (1+\varepsilon)\mathsf {g}(G)\). The running time of the algorithm is \(O(f(\varepsilon)\,n^2)\) , where \(f(\cdot)\) is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) whose genus is g. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time \(O(f_1(\varepsilon)\,n^2)\). Our algorithms are based on the analysis of minimum genus embeddings of quasirandom graphs. We use a general notion of quasirandom graphs [25]. We start with a regular partition obtained via an algorithmic version of the Szemerédi Regularity Lemma (due to Frieze and Kannan [17] and to Fox, Lovász, and Zhao [14, 15]). We then partition the input graph into a bounded number of quasirandom subgraphs, which are preselected in such a way that they admit embeddings using as many triangles and quadrangles as faces as possible. Here we provide an ɛ-approximation \(\nu (G)\) for the maximum number of edge-disjoint triangles in G. The value \(\nu (G)\) can be computed by solving a linear program whose size is bounded by certain value \(f_2(\varepsilon)\) depending only on ɛ. After solving the linear program, the genus can be approximated (see Corollary 1.7). The proof of this result is long and will be of independent interest in topological graph theory. [ABSTRACT FROM AUTHOR]

The Graph Minors Structure Theorem of Robertson and Seymour asserts that, for every graph H, every H-minor-free graph can be obtained by clique-sums of "almost embeddable" graphs. Here a graph is "almost embeddable" if it can be obtained from a graph of bounded Euler-genus by pasting graphs of bounded pathwidth in an "orderly fashion" into a bounded number of faces, called the vortices, and then adding a bounded number of additional vertices, called apices, with arbitrary neighborhoods. Our main result is a full classification of all graphs H for which the use of vortices in the theorem above can be avoided. To this end, we identify a (parametric) graph \(\mathscr{S}_{t}\) and prove that all \(\mathscr{S}_{t}\) -minor-free graphs can be obtained by clique-sums of graphs embeddable in a surface of bounded Euler-genus after deleting a bounded number of vertices. We show that this result is tight in the sense that the appearance of vortices cannot be avoided for H-minor-free graphs, whenever H is not a minor of \(\mathscr{S}_{t}\) for some \(t\in \mathbb {N}\). Using our new structure theorem, we design an algorithm that, given an \(\mathscr{S}_{t}\) -minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every \(\mathscr{S}_{t}\) as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes. [ABSTRACT FROM AUTHOR]

To address the challenge of performance portability and facilitate the implementation of electronic structure solvers, we developed the basic matrix library (BML) and Parallel, Rapid O(N), and Graph-based Recursive Electronic Structure Solver (PROGRESS) library. The BML implements linear algebra operations necessary for electronic structure kernels using a unified user interface for various matrix formats (dense and sparse) and architectures (CPUs and GPUs). Focusing on density functional theory and tight-binding models, PROGRESS implements several solvers for computing the single-particle density matrix and relies on BML. In this paper, we describe the general strategies used for these implementations on various computer architectures, using OpenMP target functionalities on GPUs, in conjunction with third-party libraries to handle performance critical numerical kernels. We demonstrate the portability of this approach and its performance in benchmark problems. [ABSTRACT FROM AUTHOR]

In a graph G = (V , E) , a non-empty set A of k distinct vertices, is called a k - attack on G. The vertices in the set A are considered to be under attack. A set D ⊆ V can defend or counter the attack A on G if there exists a one-to-one function f : A ⟼ D , such that either f (u) = u or there is an edge between u , and its image f (u) , in G. A set D is called a k - defensive dominating set if it defends against any k -attack on G. Given a graph G = (V , E) , the minimum k -defensive domination problem requires us to compute a minimum cardinality k -defensive dominating set of G. When k is not fixed, it is co-NP-hard to decide if D ⊆ V is a k -defensive dominating set. However, when k is fixed, the decision version of the problem is NP-complete for general graphs. On the positive side, the problem can be solved in linear time when restricted to paths, cycles, co-chain, and threshold graphs for any k. This paper mainly focuses on the problem when k > 0 is fixed. We prove that the decision version of the problem remains NP-complete for bipartite graphs; this answers a question asked by Ekim et al. (Discrete Math. 343 (2) (2020)). We establish a lower and upper bound on the approximation ratio for the problem. Further, we show that the minimum k -defensive domination problem is APX-complete for bounded degree graphs. On the positive side, we show that the problem is efficiently solvable for complete bipartite graphs for any k > 0. Towards the end, we study a relationship between the defensive domination number and another well-studied domination parameter. [ABSTRACT FROM AUTHOR]

In this short note, we consider a graph process recently introduced by Frieze, Krivelevich and Michaeli. In their model, the edges of the complete graph Kn ${K}_{n}$ are ordered uniformly at random and are then revealed consecutively to a player called Builder. At every round, Builder must decide if they accept the edge proposed at this round or not. We prove that, for every d≥2 $d\ge 2$, Builder can construct a spanning d $d$‐connected graph after (1+o(1))nlog n/2 $(1+o(1))n\mathrm{log}\unicode{x0200A}n/2$ rounds by accepting (1+o(1))dn/2 $(1+o(1))dn/2$ edges with probability converging to 1 as n→∞ $n\to \infty $. This settles a conjecture of Frieze, Krivelevich and Michaeli. [ABSTRACT FROM AUTHOR]

Bicycling is among the most environmentally sustainable and economically affordable travel modes available. The popularity of bicycling activities strongly depends on the availability of well-connected bicycle networks. Existing methodologies to measure network connectivity are often purely academic, complex, subjective, or locally specific. This study aims to develop and test a reliable methodology for evaluating bicycle network connectivity. The study proposed two weighted shortest-path graph algorithms: the low-stress bike network connectivity (LSBNC), and designated bicycle network connectivity (BNC) algorithms. The weights of the algorithms were the function of slope, level of traffic stress, and link length. We tested the algorithms on the California cities of San Francisco, Davis, Sacramento, and Hayward, along with San Francisco Bay Area counties, and found that algorithms can produce meaningful quantitative connectivity scores. The results indicate that Davis's BNC and LSBNC scores are 0.36 and 0.40, whereas for San Francisco, these scores are 0.07 and 0.47, respectively. The remaining Bay Area county's networks are better connected through a low-stress bike network compared with a designated bicycle network. Finally, we fitted the connectivity scores with the designated bike network or low-stress bike network intersection density and found that the BNC score can be calculated with goodness of fit (R2) of 0.90 and LSBNC can be calculated with R2 of 0.38. The developed methodology will help planners, engineers, and policymakers with the ability to efficiently evaluate bicycle network connectivity. Practical Applications: In general, agencies must understand their network connectivity level before deciding the budget allocation for any infrastructure improvement. This study proposed two novel shortest path–based algorithms that can measure the designated bike or low-stress bike network connectivity for biking. The algorithm used the level of traffic stress, slope, and segment length to calculate the connectivity score. The practitioner can apply our proposed algorithm to obtain the connectivity score at a node or census tract level as well as for the entire network. The connectivity score will range from zero to one, where zero means the network is not connected at all, and one means the network is 100% connected. The obtained connectivity score through our algorithm will help the agency to identify the appropriate portion of the network where improvement is required. [ABSTRACT FROM AUTHOR]

The Vertex Graph Coloring problem (VGC ) is a well-known difficult combinatorial optimization problem. It is one of Karp's 21 NP-complete problems. It consists in assigning a color to each vertex of a graph in such a way that any two neighboring vertices do not share the same color, and the number of the used colors is minimized. VGC is used to solve a variety of real-world problems such as time tabling and scheduling, radio frequency assignment, and computer register allocation. To deal with this problem on large graphs, the emerging large graph processing frameworks are an excellent promising candidate. Giraph is one of the most popular large graph processing frameworks both in industry and academia. In this work, two novel graph coloring algorithms are introduced. These algorithms designed to reap the benefit of the simple parallelization model offered by any vertex-centric frameworks, such as Giraph. The algorithms are based on well-known sequential heuristic techniques namely Largest-First (LF) and Saturation Largest-First (SLF). We have compared the performances of the proposed algorithms to previous Giraph based graph coloring algorithms, with regard to their solution quality and executing time, using benchmark graphs from the SNAP library. The obtained experimental results have revealed that the proposed algorithms are much more efficient than the existing Giraph algorithms. [ABSTRACT FROM AUTHOR]

Conventional database systems function as static data repositories, storing vast amounts of facts and offering efficient query processing capabilities. The sheer volume of data these systems store has a direct impact on their scalability, both in terms of storage space and query processing time. Deductive database systems, on the other hand, require far less storage space since they derive new knowledge by applying inference rules. The challenge is how to efficiently obtain the required derivations, compared to having them in explicit form. In this study, we concentrate on a set of predefined inference rules for subsumption and disjointness relations, including their negations. We use compact data structures to store the facts and provide algorithms to support each type of relation, minimizing even further the storage space requirements. Our experimental findings demonstrate the feasibility of this approach, which not only saves space but is often faster than a baseline that uses well‐known graph traversal algorithms implemented on top of a traditional adjacency list representation to derive the relations. [ABSTRACT FROM AUTHOR]

Directly generating material structures with optimal properties is a long-standing goal in material design. Traditional generative models often struggle to efficiently explore the global chemical space, limiting their utility to localized space. Here, we present a framework named Material Generation with Efficient Global Chemical Space Search (MAGECS) that addresses this challenge by integrating the bird swarm algorithm and supervised graph neural networks, enabling effective navigation of generative models in the immense chemical space towards materials with target properties. Applied to the design of alloy electrocatalysts for CO2 reduction (CO2RR), MAGECS generates over 250,000 structures, achieving a 2.5-fold increase in high-activity structures (35%) compared to random generation. Five predicted alloys— CuAl, AlPd, Sn2Pd5, Sn9Pd7, and CuAlSe2 are synthesized and characterized, with two showing around 90% Faraday efficiency for CO2RR. This work highlights the potential of MAGECS to revolutionize functional material development, paving the way for fully automated, artificial intelligence-driven material design. Designing materials with optimal properties is a longstanding challenge, as current methods struggle to explore the vast chemical space effectively. Here, the authors combine generative model with optimization methods to design novel and highly active alloy electrocatalysts for CO2 electroreduction. [ABSTRACT FROM AUTHOR]

Astrocytes form extensive networks with diverse calcium activity, yet the organization and connectivity of these networks across brain regions remain largely unknown. To address this, we developed AstroNet, a data-driven algorithm that uses two-photon calcium imaging to map temporal correlations in astrocyte activation. By organizing individual astrocyte activation events chronologically, our method reconstructs functional networks and extracts local astrocyte correlations. We create a graph of the astrocyte network by tallying direct co-activations between pairs of cells along these activation pathways. Applied to the CA1 hippocampus and motor cortex, AstroNet reveals notable differences: astrocytes in the hippocampus display stronger connectivity, while cortical astrocytes form sparser networks. In both regions, smaller, tightly connected sub-networks are embedded within a larger, loosely connected structure. This method not only identifies astrocyte activation paths and connectivity but also reveals distinct, region-specific network patterns, providing new insights into the functional organization of astrocytic networks in the brain. AstroNet, a novel data-driven algorithm, maps astrocytic network connectivity through calcium imaging, revealing distinct connectivity patterns in the hippocampus and motor cortex, and providing insights into astrocyte network organization across brain regions. [ABSTRACT FROM AUTHOR]

Geomagnetically Induced Current (GIC) refers to the electromagnetic response of the Earth and its conductive modern infrastructures to space weather and would pose a significant threat to high-voltage power grids designed for the alternative current operation. To assess the impact of space weather on the power grid, one needs to calculate the GIC on a national or continental scale. In this study, we developed a smart and parallelized GIC modelling algorithm, Graph GIC. This algorithm deploys a graph representing a power grid in a single-line diagram, in which substations/transformers act as nodes and transmission lines as edges. With these denotations, a power grid and its electric parameters are mathematically represented with an adjacency matrix and an admittance matrix. We used sparse matrix and parallelisation techniques to expedite the intensive computation in cases of large-scale power grids. The Graph GIC was validated with a benchmark grid, applied to the GIC calculation of the 500 kV power grid of Guangdong, China, and conducted preliminary analysis on the grid's susceptibility to geomagnetic storms. The Graph GIC algorithm has the advantage of an intuitive and highly scalable graph representation of a power grid at any scale. It achieves high-accuracy calculation and a speedup of about 18 times after parallelisation. This algorithm could be applied to assess the impact of space weather on a power grid up to continental scales and could be incorporated into global space weather modelling frameworks. [ABSTRACT FROM AUTHOR]

Given a graph G , Min-Max-Acy-Matching is the problem of finding a maximal matching M in G of minimum cardinality such that the set of M -saturated vertices induces an acyclic subgraph in G. The decision version of Min-Max-Acy-Matching is known to be NP -complete. In this paper, we strengthen this result by proving that the decision version of Min-Max-Acy-Matching is NP -complete even for dually chordal graphs. Also, we give the first positive algorithmic result for Min-Max-Acy-Matching by proposing a linear-time algorithm for computing a minimum cardinality maximal acyclic matching in proper interval graphs, a subclass of dually chordal graphs. [ABSTRACT FROM AUTHOR]

In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a (2 / 3) -approximation for the Maximum Independent Set problem on interval graphs. We show that this is tight, even on unit interval graphs of maximum degree 3. We show that on chordal graphs, the greedy algorithm is a (1 / 2) -approximation and that this is again tight. These results contrast with the known (tight) approximation ratio of 3 Δ + 2 of the greedy algorithm for general graphs of maximum degree Δ. [ABSTRACT FROM AUTHOR]

The Maximum Independent Set problem is well-studied in graph theory and related areas. An independent set of a graph is a subset of non-adjacent vertices of the graph. A maximum independent set is an independent set of maximum size. This paper studies the Maximum Independent Set problem in some classes of geometric intersection graphs in a distributed setting. More precisely, we study the Maximum Independent Set problem on two geometric intersection graphs, interval and axis-parallel segment intersection graphs, and present deterministic distributed algorithms in a model that is similar but a little weaker than the local communication model. We compute the maximum independent set on interval graphs in O (k) rounds and O (n) messages, where k is the size of the maximum independent set and n is the number of nodes in the graph. We provide a matching lower bound of Ω (k) on the number of rounds, whereas Ω (n) is a trivial lower bound on message complexity. Thus, our algorithm is both time and message-optimal. We also study the Maximum Independent Set problem in interval count l graphs, a special case of the interval graphs where the intervals have exactly l different lengths. We propose an 1 2 -approximation algorithm that runs in O (l) round. For axis-parallel segment intersection graphs, we design an 1 2 -approximation algorithm that obtains a solution in O (D) rounds. The results in this paper extend the results of Molla et al. [J. Parallel Distrib. Comput. 2019]. [ABSTRACT FROM AUTHOR]

Accurate 6D object pose estimation is critical for autonomous docking. To address the inefficiencies and inaccuracies associated with maximal cliques-based pose estimation methods, we propose a fast 6D pose estimation algorithm that integrates feature space and space compatibility constraints. The algorithm reduces the graph size by employing Laplacian filtering to resample high-frequency signal nodes. Then, the truncated Chamfer distance derived from fusion features and spatial compatibility constraints is used to evaluate the accuracy of candidate pose alignment between source and reference point clouds, and the optimal pose transformation matrix is selected for 6D pose estimation. Finally, a point-to-plane ICP algorithm is applied to refine the 6D pose estimation for autonomous docking. Experimental results demonstrate that the proposed algorithm achieves recall rates of 94.5%, 62.2%, and 99.1% on the 3DMatch, 3DLoMatch, and KITTI datasets, respectively. On the autonomous docking dataset, the algorithm yields rotation and localization errors of 0.96° and 5.82 cm, respectively, outperforming existing methods and validating the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

The Newton-Krylov method with the explicit Jacobian matrix is an efficient numerical method for solving the nuclear reactor nonlinear multiphysics coupling system. Compared with the Jacobian-free Newton-Krylov (JFNK) method, it has a better preconditioner matrix (the Jacobian matrix itself) and can achieve a more stable and faster convergence. How to compute the Jacobian matrix efficiently is a key issue for this method. The graph coloring algorithm is an essential technique and has been used to reduce the Jacobian computational burden by exploiting its sparsity. The fewer the coloring numbers in the Jacobian, the less the Jacobian computational cost will be. Besides, when computing the Jacobian in a distributed memory parallel environment, the parallel graph coloring algorithms are required because the Jacobian is distributed among processors. Currently, a popular parallel graph coloring algorithm has been used to color the Jacobian. However, this parallel graph coloring algorithm shows poor scalability in parallel. The coloring numbers will increase with the processors, resulting in poor Jacobian computational efficiency. In this paper, a more efficient parallel graph coloring method is proposed that aims to reduce the coloring numbers and improve Jacobian computation efficiency in parallel. The main feature of the new method is that the coloring numbers decrease with the increasing number of processors. A neutronics/thermal-hydraulic coupling problem arising from the simplified high-temperature gas coolant model is utilized to assess the performance of the newly proposed method. The results show that (1) the parallel coloring number is reduced significantly, (2) the Jacobian computed by the new method is completely correct and excellent parallel scalability is achieved, and (3) the parallel coloring Newton-Krylov method with explicit Jacobian is more efficient and more stable than the parallel JFNK due to a better preconditioner. [ABSTRACT FROM AUTHOR]

In graph-based SLAM systems, loop-closure edges with large noise may severely impede the optimizer from rapidly converging to the optimal solution, leading to a noticeable decrease in localization accuracy and map consistency. Therefore, the objective of this paper was to investigate robust methods for handling loop-closure edges, which was crucial for optimization algorithms in the presence of large noise. Toward this aim, this paper introduced a new concept of K-means clustering to classify the residual values of loop-closure edges, thereby established a new residual threshold model. This model adaptively adjusted the weights of loop-closure edges during optimization to reduce their impact on the optimization process. Subsequently, the formulation of the residual weighted enhancement for recursive least squares pose graph optimization algorithm (RW-RLSPGO) was based on the iterative reweighted least squares principle. Finally, it conducted Monte Carlo experiments on both simulated and real pose graph optimization (PGO) datasets. The experimental results demonstrate a significant improvement in both accuracy and robustness with the RW-RLSPGO algorithm, validating its effectiveness in high-noise environments. [ABSTRACT FROM AUTHOR]

The article provides a comprehensive survey on the use of Graph Neural Networks (GNNs) in recommender systems (RSs), highlighting their role in enhancing recommendations through advanced learning techniques. Topics discussed include GNN-based recommender models, challenges in data quality and computational efficiency, and future research directions such as explainability, scalability, and dynamic graph handling.

Consider a graph G = (V , E) and a function f : V → { 0 , 1 , 2 }. A vertex u with f (u) = 0 is defined as undefended by f if it lacks adjacency to any vertex with a positive f -value. The function f is said to be a weak Roman dominating function (WRD function) if, for every vertex u with f (u) = 0 , there exists a neighbor v of u with f (v) > 0 and a new function f ′ : V → { 0 , 1 , 2 } defined in the following way: f ′ (u) = 1 , f ′ (v) = f (v) − 1 , and f ′ (w) = f (w) , for all vertices w in V ∖ { u , v } ; so that no vertices are undefended by f ′. The total weight of f is equal to ∑ v ∈ V f (v) , and is denoted as w (f). The Weak Roman domination number denoted by γ r (G) , represents m i n { w (f) | f is a WRD function of G }. For a given graph G , the problem of finding a WRD function of weight γ r (G) is defined as the Minimum Weak Roman domination problem. The problem is already known to be NP-hard for bipartite and chordal graphs. In this paper, we further study the algorithmic complexity of the problem. We prove the NP-hardness of the problem for star convex bipartite graphs and comb convex bipartite graphs, which are subclasses of bipartite graphs. In addition, we show that for the bounded degree star convex bipartite graphs, the problem is efficiently solvable. We also prove the NP-hardness of the problem for split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm to solve the problem for P 4 -sparse graphs. Further, we have presented some approximation results. [ABSTRACT FROM AUTHOR]

The study examines different graph-based methods of detecting anomalous activities on digital markets, proposing the most efficient way to increase market actors' protection and reduce information asymmetry. Anomalies are defined below as both bots and fraudulent users (who can be both bots and real people). Methods are compared against each other, and state-of-the-art results from the literature and a new algorithm is proposed. The goal is to find an efficient method suitable for threat detection, both in terms of predictive performance and computational efficiency. It should scale well and remain robust on the advancements of the newest technologies. The article utilized three publicly accessible graph-based datasets: one describing the Twitter social network (TwiBot-20) and two describing Bitcoin cryptocurrency markets (Bitcoin OTC and Bitcoin Alpha). In the former, an anomaly is defined as a bot, as opposed to a human user, whereas in the latter, an anomaly is a user who conducted a fraudulent transaction, which may (but does not have to) imply being a bot. The study proves that graph-based data is a better-performing predictor than text data. It compares different graph algorithms to extract feature sets for anomaly detection models. It states that methods based on nodes' statistics result in better model performance than state-of-the-art graph embeddings. They also yield a significant improvement in computational efficiency. This often means reducing the time by hours or enabling modeling on significantly larger graphs (usually not feasible in the case of embeddings). On that basis, the article proposes its own graph-based statistics algorithm. Furthermore, using embeddings requires two engineering choices: the type of embedding and its dimension. The research examines whether there are types of graph embeddings and dimensions that perform significantly better than others. The solution turned out to be dataset-specific and needed to be tailored on a case-by-case basis, adding even more engineering overhead to using embeddings (building a leaderboard of grid of embedding instances, where each of them takes hours to be generated). This, again, speaks in favor of the proposed algorithm based on nodes' statistics. The research proposes its own efficient algorithm, which makes this engineering overhead redundant. [ABSTRACT FROM AUTHOR]

In many scientific domains, there is a growing interest in the shortest path problem. Traffic routes that can be precisely defined become arbitrary due to the damage that natural catastrophes inflict on roads and bridges. The truth membership, indeterminacy membership, and falsity membership of the component elements make up a neutrosophic set. Their axis of symmetry is indeterminacy membership, and it has a symmetric form. The neutrosophic number is a better way to express the edge distance in uncertain circumstances. With an edge distance stated using Fermatean neutrosophic numbers (FrNN), the study aims to solve the shortest path problem of the Fermatean neutrosophic graph. Additionally, the edge distance will be resolved based on the score and precise functions derived from the FrNN. In order to solve the shortest path problem and determine the shortest distance, the application of a circle-breaking algorithm is suggested. [ABSTRACT FROM AUTHOR]

Multi-view clustering considers the diversity of different views and fuses these views to produce a more accurate and robust partition than single-view clustering. It is a key problem of multi-view clustering research to allocate each view reasonably based on its contribution value. In this paper, we propose a weighted multi-view clustering model via sparse graph learning to cope with allocation of different views. The proposed idea is to assign different view weights instead of equal view weights to learn a high-quality shared similarity matrix for multi-view clustering. In our new proposed method, it can consider the clustering capacity heterogeneity of different views in fusion by assigning a weight for each view so that each view special feature are fully excavated, and improve the performance of multi-view clustering. Moreover, our proposed method can directly obtained cluster indicators by imposing low rank constraints without any post-processing operations. In addition, our model is proposed based on sparse graph, so that the outliers and noise in each view data are well handled and the robustness of the algorithm is effectively guaranteed. Finally, numerous experimental results are conducted on different sizes benchmark datasets, and show that the performance of our algorithm is quite satisfactory. The code of our proposed method is publicly available at https://github.com/zhoujie05/A-weighted-multi-view-clustering-via-sparse-graph-learning. [ABSTRACT FROM AUTHOR]

The deployment of increasingly diverse services on edge devices is becoming increasingly prevalent. Efficiently deploying functionally heterogeneous services to resource heterogeneous edge nodes while achieving superior user experience is a challenge that every edge system must address. In this paper, we propose a container-node graph (CN-Graph)-based container optimal matching deployment algorithm, edge Kuhn-Munkres algorithm (EKM) based on container-node graph, designed for heterogeneous environment to optimize system performance. Initially, containers are categorized by functional labels, followed by construction of a CN-Graph model based on the relationship between containers and nodes. Finally, the container deployment problem is transformed into a weighted bipartite graph optimal matching problem. In comparison with the mainstream container deployment algorithms, Swarm, Kubernetes, and the recently emerged ECSched-dp algorithm, the EKM algorithm demonstrates the ability to effectively enhance the average runtime performance of containers to 3.74 times, 4.10 times, and 2.39 times, respectively. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V , we say A dominates B if every vertex of B is adjacent to at least one vertex of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a transitive partition of size k if V i dominates V j for all 1 ≤ i < j ≤ k. In this article, we study a variation of transitive partition, namely 2- transitive partition. For two disjoint subsets A and B of V , we say A 2- dominates B if every vertex of B is adjacent to at least two vertices of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a 2- transitive partition of size k if V i 2 -dominates V j for all 1 ≤ i < j ≤ k. The Maximum 2- Transitivity Problem is to find a 2 -transitive partition of a given graph with the maximum number of parts. We show that the decision version of this problem is NP-complete for chordal and bipartite graphs. On the positive side, we design three linear-time algorithms for solving Maximum 2- Transitivity Problem in trees, split, and bipartite chain graphs. [ABSTRACT FROM AUTHOR]

At the current stage, 3D graph convolutional algorithms face the following issues: (1) The problem of determining the neighborhood in graph convolution. (2) The issue of fusing features at different depths in deep graph convolutional algorithms. (3) The challenge of feature fusion and recognition in multi-path deep graph convolutional algorithms. Based on these, the paper "Multi-Path Deep Segmentation Network Based on 3D Graph Convolutional Algorithm and Its Application in Point Cloud Segmentation" is proposed. Inspired by visual computing theory, the neighborhood for 3D graph convolution is determined based on the receptive field theory, and a 3D graph convolutional algorithm based on visual selectivity is proposed; A single-link deep feature extraction algorithm for 3D graph convolution based on visual selectivity is proposed, it achieve the fusion of features at different depths learned by the graph convolutional algorithm by a pyramid learning method; A multi-link feature extraction algorithm for 3D graph convolution based on visual selectivity is proposed, and achieve multi-link feature fusion and segmentation to utilize the RPN calculation method. compared with algorithms such as PointNet, PointNet++, KPConv deform, 3D GCN, and My Algorithm, The segmentation performance and geometric invariance of the proposed algorithm are validated on the ShapeNetPart dataset and the custom Mortise_and_Tenon_DB dataset, and Experiments demonstrate that the proposed algorithm is correct and feasible, offers superior 3D point cloud segmentation performance, and exhibits strong geometric invariance. [ABSTRACT FROM AUTHOR]

Graph properties’ computation is widely used in science. Some algorithms for specific graphs help us compute properties like girth, clique number, and independent number. Nevertheless, processing time would be increased by the growth of the number of graph vertices. This paper suggests machine learning methods for computing a given graph’s girth, maximum clique number, and maximum independent set number. We leveraged random graph generation methods to collect many graph instances. Next, we present 14 features used for the training and testing while classifying or predicting those properties. The experimental results on the collected dataset offer accuracies of 90.51%, 91.61%, and 99.99% for binary classification and correlation coefficients of 0.9703, 0.8757, and 0.992 for value prediction for maximum clique number, girth, and maximum independent set number, respectively. [ABSTRACT FROM AUTHOR]

Fire is a dangerous disaster that causes human, ecological, and financial ramifications. Forest fires have increased significantly in recent years due to natural and artificial climatic factors. Therefore, accurate and early prediction of fires is essential. While significant advancements have been made in traditional and Deep Learning (DL) methods for fire detection, challenges remain in accurately pinpointing and recognizing fire regions, especially in diverse and large environments, to prevent damage effectively. To address these challenges, this paper introduces a novel Federated Learning (FL)-based method called Indoor-Outdoor FireNet (IOFireNet) for detecting and localizing fire regions. The proposed method incorporates a Bilateral Filter (BF) to effectively preprocess fire images to reduce noise artifacts and enhance detection clarity. It employs Super Pixel-based Adaptive Clustering (SPAC) to precisely segment fire and non-fire regions. A global IOFireNet model is developed to aggregate parameters from local models, improving detection accuracy across varied environments, while MobileNet is used for efficient data processing, enabling predictions on fire spread, severity, and affected areas to support early warnings. The proposed FL-based IOFireNet attains an accuracy rate of 98.65% for fire detection and 97.14% of mean IoU for segmentation. The proposed SPAC model reaches a mean IoU of 4.06%, which is 2.45% better than the graph cut algorithm and CRF model. The proposed model achieves an accuracy of 0.23%, 4.20%, 3.29%, and 10.02%, better than VGG-19, ResNet-50, Inception, and Dense Net, respectively. [ABSTRACT FROM AUTHOR]

In the current era of mobile edge networks, a significant challenge lies in overcoming the limitations posed by limited edge storage and computational resources. To address these issues, accurate network traffic prediction has emerged as a promising solution. However, due to the intricate spatial and temporal dependencies inherent in mobile edge network traffic, the prediction task remains highly challenging. Recent spatio-temporal neural network algorithms based on graph convolution have shown promising results, but they often rely on pre-defined graph structures or learned parameters. This approach neglects the dynamic nature of short-term relationships, leading to limitations in prediction accuracy. To address these limitations, we introduce Ada-ASTGCN, an innovative attention-based adaptive spatio-temporal graph convolutional network. Ada-ASTGCN dynamically derives an optimal graph structure, considering both the long-term stability and short-term bursty evolution. This allows for more precise spatio-temporal network traffic prediction. In addition, we employ an alternative training approach during optimization, replacing the traditional end-to-end training method. This alternative training approach better guides the learning direction of the model, leading to improved prediction performance. To validate the effectiveness of Ada-ASTGCN, we conducted extensive traffic prediction experiments on real-world datasets. The results demonstrate the superior performance of Ada-ASTGCN compared to existing methods, highlighting its ability to accurately predict network traffic in mobile edge networks. [ABSTRACT FROM AUTHOR]

It is currently an unsolved problem to determine whether, for every 2-list assignment L of a ▵ -free planar graph G, there exists an independent set A L such that G [ V G \ A L ] is L-colorable. However, in this paper, we take a slightly different approach to the above problem. We prove the N P -completeness of the decision problem of determining an independent set A such that G [ V G \ A ] is 2-choosable for ▵ -free, 4-colorable graphs of diameter 3. Building upon this notion, we examine the computational complexity of two optimization problems: minimum near-3-choosability and minimum 2-choosable-edge-deletion. In the former problem, the goal is to find an independent set A of minimum size in a given graph G, such that the induced subgraph G [ V G \ A ] is 2-choosable. We establish that this problem is N P -hard to approximate within a factor of | V G | 1 - ϵ for any ϵ > 0 , for planar bipartite graphs of arbitrary large girth. On the other hand, the problem of minimum 2-choosable-edge-deletion involves determining an edge set F ⊆ E G of minimum cardinality such that the spanning subgraph G [ E G \ F ] is 2-choosable. We prove that this problem can be approximated within a factor of O (log | V G |) . [ABSTRACT FROM AUTHOR]

Graph‐based spectrum sensing in noisy environments has major implications for civilian and military signal processing applications. However, existing algorithms suffer from high computational complexity and performance deterioration at low signal‐to‐noise ratios (SNRs). Therefore, a spectrum‐sensing algorithm based on graph feature fusion using a quadratic form derived from self‐loop weights and the graph Laplacian matrix is proposed in this study. The sum of the first and second block maxima of the power spectrum of the observed signal is selected as the input to the graph converter. Self‐loop weights are combined with the Laplacian matrix to construct the graph quadratic form, which serves as the test statistic for decision‐making. By applying majorisation and the extreme value theory, it is demonstrated that the proposed algorithm outperforms existing methods. The simulation results confirm the robust spectrum‐sensing performance across various signal modulation types and pulse shapes. Thus, compared to existing algorithms, except block range‐ and energy‐detection‐based methods, the proposed algorithm demonstrates the best spectrum‐sensing performance under low SNRs and channel‐fading conditions, while achieving the lowest computational complexity. The proposed approach enables more efficient and accurate spectrum sensing, fostering advancements in communication technologies and defence applications. [ABSTRACT FROM AUTHOR]

Knowledge Graphs (KGs) are widely used in many fields of application, and especially play an essential role in recommendation systems. KGs often need to be complete, missing relationships between users and items, data sparsity, weak associations, and difficulties in knowledge inference, resulting in low credibility of recommendation results. Therefore, we propose a novel Knowledge Graph (KG) recommendation algorithms. Due to the availability of interaction data across numerous events, KGs also exhibit dynamics over time. By taking into account the temporal variable, it is possible to organise well-structured external information to connect users and items, thereby expanding user preferences to a certain extent. The proposed algorithm employs GCNs to encode the heterogeneous graph, which includes user-item interactions and the KG. It addresses the challenge of high-dimensional data by using the inner product of users and items. The algorithm uncovers potential alignment relationships and learns the embedding of user-item and relationships by applying convolutional processing to the graph data's features and performing data fusion, the new algorithm uncovers potential alignment relationships, and learns embedding of user-item and relationships. The experimental results on the Mean Reciprocal Rank (MRR) and Hits@k demonstrate that the proposed algorithm outperforms state-of-the-art algorithms in terms of the credibility and accuracy of recommendation results. [ABSTRACT FROM AUTHOR]

Knowledge graphs, powerful tools that explicitly transfer knowledge to machines, have significantly advanced new knowledge inferences. Discovering unknown relationships between diseases and genes/proteins in biomedical knowledge graphs can lead to the identification of disease development mechanisms and new treatment targets. Generating high‐quality representations of biomedical entities is essential for successfully predicting disease‐gene/protein associations. We developed a computational model that predicts disease‐gene/protein associations using the Precision Medicine Knowledge Graph, a biomedical knowledge graph. Embeddings of biomedical entities were generated using two different methods—a large language model (LLM) and the knowledge graph embedding (KGE) algorithm. The LLM utilizes information obtained from massive amounts of text data, whereas the KGE algorithm relies on graph structures. We developed a disease‐gene/protein association prediction model, "Cross‐Modal Embedding Integrator (CMEI)," by integrating embeddings from different modalities using a multi‐head attention mechanism. The area under the receiver operating characteristic curve of CMEI was 0.9662 (± 0.0002) in predicting disease‐gene/protein associations. In conclusion, we developed a computational model that effectively predicts disease‐gene/protein associations. CMEI may contribute to the identification of disease development mechanisms and new treatment targets. [ABSTRACT FROM AUTHOR]

The unsupervised attribute graph embedding technique aims to learn low-dimensional node embedding using neighborhood topology and attribute information under unlabeled data. Current unsupervised models are mostly based on graph self-encoders, but full-batch training limits the scalability of the model and ignores attribute integrity when reconstructing the topology. In order to solve the above problems while considering the unsupervised learning of the model and full use of node information, this paper proposes a graph neural network architecture based on a graph self-encoder to capture the nonlinearity of the attribute graph data, and an attribute graph embedding algorithm that explicitly models the influence of neighborhood information using a multi-level attention mechanism. Specifically, the proposed algorithm fuses topology information and attribute information using a lightweight sampling strategy, constructs an unbiased graph self-encoder on the sampled graph, implements topology aggregation and attribute aggregation, respectively, models the correlation between topology embedding and attribute embedding, and considers multi-level loss terms. [ABSTRACT FROM AUTHOR]

Practical algorithms for computing canonical forms of multi-digraphs do not exist in the literature. This paper proposes two practical approaches for finding canonical forms, from the perspective of nD symbolic computation. Initially, the approaches turn the problem of finding canonical forms of multi-digraphs into computing canonical forms of indexed monomials in computer algebra. Then, the first approach utilizes the double coset representative method in computational group theory for canonicalization of indexed monomials and shows that finding the canonical forms of a class of multi-digraphs in practice has polynomial complexity of approximately O ((k + p) 2) or O (k 2.1) by the computer algebra system (CAS) tool Tensor-canonicalizer. The second approach verifies the equivalence of canonicalization of indexed monomials and finding canonical forms of (simple) colored tripartite graphs. It is found that the proposed algorithm takes approximately O ((k + 2 p) 4.803) time for a class of multi-digraphs in practical implementation, combined with one of the best known graph isomorphism tools Traces, where k and p are the vertex number and edge number of a multi-digraph, respectively. [ABSTRACT FROM AUTHOR]