Search

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]

The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximalmatching either take polylogarithmic time which is considered inefficient, or require a strictly superlinear space of n1+Ω(1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [15]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition.We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an O(log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved O(log log Δ) round algorithm for 1 + ε approximate matching. All these results can also be implemented in the congested clique model in the same number of rounds. [ABSTRACT FROM AUTHOR]

The restoration lemma by Afek et al. [3] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is tiebreaking-sensitive: if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two selected shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible. We settle this question affirmatively with the first general construction of restorable tiebreaking schemes. We then show applications to various problems in fault-tolerant network design. These include a faster algorithm for subset replacement paths, more efficient fault-tolerant (exact) distance labeling schemes, faulttolerant subset distance preservers and +4 additive spanners with improved sparsity, and fast distributed algorithms that construct these objects. For example, an almost immediate corollary of our restorable tiebreaking scheme is the first nontrivial distributed construction of sparse fault-tolerant distance preservers resilient to three faults. [ABSTRACT FROM AUTHOR]

Contemporary graph learning algorithms are not well-suited for large molecules since they do not consider the hierarchical interactions among the atoms, which are essential to determining the molecular properties of macromolecules. In this work, we propose Multiresolution Graph Transformers (MGT), the first graph transformer architecture that can learn to represent large molecules at multiple scales. MGT can learn to produce representations for the atoms and group them into meaningful functional groups or repeating units. We also introduce Wavelet Positional Encoding (WavePE), a new positional encoding method that can guarantee localization in both spectral and spatial domains. Our proposed model achieves competitive results on three macromolecule datasets consisting of polymers, peptides, and protein-ligand complexes, along with one drug-like molecule dataset. Significantly, our model outperforms other state-of-the-art methods and achieves chemical accuracy in estimating molecular properties (e.g., highest occupied molecular orbital, lowest unoccupied molecular orbital, and their gap) calculated by Density Functional Theory in the polymers dataset. Furthermore, the visualizations, including clustering results on macromolecules and low-dimensional spaces of their representations, demonstrate the capability of our methodology in learning to represent long-range and hierarchical structures. Our PyTorch implementation is publicly available at https://github.com/HySonLab/Multires-Graph-Transformer. [ABSTRACT FROM AUTHOR]

Background: The utilization of long reads for single nucleotide polymorphism (SNP) phasing has become popular, providing substantial support for research on human diseases and genetic studies in animals and plants. However, due to the complexity of the linkage relationships between SNP loci and sequencing errors in the reads, the recent methods still cannot yield satisfactory results. Results: In this study, we present a graph-based algorithm, GCphase, which utilizes the minimum cut algorithm to perform phasing. First, based on alignment between long reads and the reference genome, GCphase filters out ambiguous SNP sites and useless read information. Second, GCphase constructs a graph in which a vertex represents alleles of an SNP locus and each edge represents the presence of read support; moreover, GCphase adopts a graph minimum-cut algorithm to phase the SNPs. Next, GCpahse uses two error correction steps to refine the phasing results obtained from the previous step, effectively reducing the error rate. Finally, GCphase obtains the phase block. GCphase was compared to three other methods, WhatsHap, HapCUT2, and LongPhase, on the Nanopore and PacBio long-read datasets. The code is available from https://github.com/baimawjy/GCphase. Conclusions: Experimental results show that GCphase under different sequencing depths of different data has the least number of switch errors and the highest accuracy compared with other methods. [ABSTRACT FROM AUTHOR]

The hypothalamus in the mammalian brain is responsible for regulating functions associated with survival and reproduction representing a complex set of highly interconnected, yet anatomically and functionally distinct, sub-regions. It remains unclear what factors drive the spatial organization of sub-regions within the hypothalamus. One potential factor may be structural connectivity of the network that promotes efficient function with well-connected sub-regions placed closer together geometrically, i.e., the strongest axonal signal transferred through the shortest geometrical distance. To empirically test for such efficiency, we use hypothalamic data derived from the Allen Mouse Brain Connectivity Atlas, which provides a structural connectivity map of mouse brain regions derived from a series of viral tracing experiments. Using both cost function minimization and comparison with a weighted, sphere-packing ensemble, we demonstrate that the sum of the distances between hypothalamic sub-regions are not close to the minimum possible distance, consistent with prior whole brain studies. However, if such distances are weighted by the inverse of the magnitude of the connectivity, their sum is among the lowest possible values. Specifically, the hypothalamus appears within the top 94th percentile of neural efficiencies of randomly packed configurations and within one standard deviation of the median efficiency when packings are optimized for maximal neural efficiency. Our results, therefore, indicate that a combination of geometrical and topological constraints help govern the structure of the hypothalamus. [ABSTRACT FROM AUTHOR]

Modifying network results is the most intuitive way to inject domain knowledge into network detection algorithms to improve their performance. While advances in computation scalability have made detecting large‐scale networks possible, the human ability to modify such networks has not scaled accordingly, resulting in a huge ‘interaction gap’. Most existing works only support navigating and modifying edges one by one in a graph visualization, which causes a significant interaction burden when faced with large‐scale networks. In this work, we propose a novel graph pattern mining algorithm based on the minimum description length (MDL) principle to partition and summarize multi‐feature and isomorphic sub‐graph matches. The mined sub‐graph patterns can be utilized as mediums for modifying large‐scale networks. Combining two traditional approaches, we introduce a new coarse‐middle‐fine graph modification paradigm (i.e. query graph‐based modification →$\rightarrow$ sub‐graph pattern‐based modification →$\rightarrow$ raw edge‐based modification). We further present a graph modification system that supports the graph modification paradigm for improving the scalability of modifying detected large‐scale networks. We evaluate the performance of our graph pattern mining algorithm through an experimental study, demonstrate the usefulness of our system through a case study, and illustrate the efficiency of our graph modification paradigm through a user study. [ABSTRACT FROM AUTHOR]

Several concepts that model processes of spreading (of information, disease, objects, etc.) in graphs or networks have been studied. In many contexts, we assume that some vertices of a graph G are contaminated initially, before the process starts. By the q -forcing rule, a contaminated vertex having at most q uncontaminated neighbors enforces all the neighbors to become contaminated, while by the p -percolation rule, an uncontaminated vertex becomes contaminated if at least p of its neighbors are contaminated. If given a set S of initially contaminated vertices all vertices eventually become contaminated when continuously applying the q -forcing rule (respectively the p -percolation rule), S is called a q -forcing set (respectively, a p -percolating set) in G. In this paper, we consider sets S that are at the same time q -forcing sets and p -percolating sets, and call them (p , q) -spreading sets. Given positive integers p and q , the minimum cardinality of a (p , q) -spreading set in G is a (p , q) -spreading number, σ (p , q) (G) , of G. While q -forcing sets have been studied in a dozen of papers, the decision version of the corresponding graph invariant has not been considered earlier, and we fill the gap by proving its NP-completeness. This, in turn, enables us to prove the NP-completeness of the decision version of the (p , q) -spreading number in graphs for an arbitrary choice of p and q. Again, for every p ∈ N and q ∈ N ∪ { ∞ } , we find a linear-time algorithm for determining the (p , q) -spreading number of a tree, where in the case p ≥ 2 we apply Riedl's algorithm from [Largest and smallest minimal percolating sets in trees, Electron. J. Combin. 19 (2012) Paper 64] on p -percolation in trees. In addition, we present a lower and an upper bound on the (p , q) -spreading number of a tree and characterize extremal families of trees. In the case of square grids, we combine some results of Bollobás from [The Art of Mathematics: Coffee Time in Memphis. Cambridge Univ. Press, New York, 2006], and the AIM Minimum Rank-Special Graphs Work Group from [Zero forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 2008 1628–1648], and new results on (2 , 1) -spreading and (4 , q) -spreading to obtain σ (p , q) (P m □ P n) for all (p , q) ∈ (N ∖ { 3 }) × (N ∪ { ∞ }) and all m , n ∈ N. [ABSTRACT FROM AUTHOR]

Reconstructing 2D curves from sample points has long been a critical challenge in computer graphics, finding essential applications in vector graphics. The design and editing of curves on surfaces has only recently begun to receive attention, primarily relying on human assistance, and where not, limited by very strict sampling conditions. In this work, we formally improve on the state‐of‐the‐art requirements and introduce an innovative algorithm capable of reconstructing closed curves directly on surfaces from a given sparse set of sample points. We extend and adapt a state‐of‐the‐art planar curve reconstruction method to the realm of surfaces while dealing with the challenges arising from working on non‐Euclidean domains. We demonstrate the robustness of our method by reconstructing multiple curves on various surface meshes. We explore novel potential applications of our approach, allowing for automated reconstruction of curves on Riemannian manifolds. [ABSTRACT FROM AUTHOR]

Background: Resting‐state functional magnetic resonance imaging (rs‐fMRI) technology and the complex network theory can be used to elucidate the underlying mechanisms of brain diseases. The successful application of functional brain hypernetworks provides new perspectives for the diagnosis and evaluation of clinical brain diseases; however, many studies have not assessed the attribute information of hyperedges and could not retain the high‐order topology of hypergraphs. In addition, the study of multi‐scale and multi‐layered organizational properties of the human brain can provide richer and more accurate data features for classification models of depression. Purpose: This work aims to establish a more accurate classification framework for the diagnosis of major depressive disorder (MDD) using the high‐order line graph algorithm. And accuracy, sensitivity, specificity, precision, F1 score are used to validate its classification performance. Methods: Based on rs‐fMRI data from 38 MDD subjects and 28 controls, we constructed a human brain hypernetwork and introduced a line graph model, followed by the construction of a high‐order line graph model. The topological properties under each order line graph were calculated to measure the classification performance of the model. Finally, intergroup features that showed significant differences under each order line graph model were fused, and a support vector machine classifier was constructed using multi‐kernel learning. The Kolmogorov–Smirnov nonparametric permutation test was used as the feature selection method and the classification performance was measured with the leave‐one‐out cross‐validation method. Results: The high‐order line graph achieved a better classification performance compared with other traditional hypernetworks (accuracy = 92.42%, sensitivity = 92.86%, specificity = 92.11%, precision = 89.66%, F1 = 91.23%). Furthermore, the brain regions found in the present study have been previously shown to be associated with the pathology of depression. Conclusions: This work validated the classification model based on the high‐order line graph, which can better express the topological features of the hypernetwork by comprehensively considering the hyperedge information under different connection strengths, thereby significantly improving the classification accuracy of MDD. Therefore, this method has potential for use in the clinical diagnosis of MDD. [ABSTRACT FROM AUTHOR]

Automatic International Classification of Disease (ICD) coding, a system for assigning proper codes to a given clinical text, has received increasing attention. Previous studies have focused on formulating the ICD coding task as a multi-label prediction approach, exploring the relationship between clinical texts and ICD codes, parent codes and child codes, and siblings. However, the large search space of ICD codes makes it difficult to localize target labels. Moreover, there exists a great unbalanced distribution of ICD codes at different levels. In this work, we propose LabGraph, which transfers ICD coding into a graph generation problem. Specifically, we present adversarial domain adaptation training algorithms, graph reinforcement algorithms, and adversarial perturbation regularization. Then, we present a discriminator for label graphs that calculates the reward for each ICD code in the generator label graph. LabGraph surpasses existing state-of-the-art approaches on core assessment measures such as micro-F1, micro-AUC, and P@K, leading to the formation of a new state-of-the-art study. [ABSTRACT FROM AUTHOR]

To deal with the problem of complex changes of topology in UAVs (Unmanned Aerial Vehicles) network and the increasing need of data transmission, the combination of self-organizing and SDN (Software Defined Network) is a usefull paradigm. However, the control node's position in SDN will influence the transmission of command between controller and relay nodes, thus determining the quality of communication. In this context, we present a network construction, named SDN-FANET (Flying Ad-Hoc Network). We formulate the problem as a classical network center location model. To solve this problem, we propose a particle swarm algorithm based on the graph theory. Simulation results show the algorithm performs better in terms of accuracy and stability, compared with several benchmarks. Particularly, with the initial particle position optimized, the proposed algorithm converges faster. [ABSTRACT FROM AUTHOR]

A phylogenetic graph search relies on a large number of highly parameterized search procedures (e.g. branch‐swapping, perturbation, simulated annealing, genetic algorithm). These procedures vary in effectiveness over datasets and at alternative points in analytical pipelines. The multi‐armed bandit problem is applied to phylogenetic graph searching to more effectively utilize these procedures. Thompson sampling is applied to a collection of search and optimization "bandits" to favour productive search strategies over those that are less successful. This adaptive random sampling strategy is shown to be more effective in producing heuristically optimal phylogenetic graphs and more time efficient than existing uniform probability randomized search strategies. The strategy acts as a form of unsupervised machine learning that can be applied to a diversity of phylogenetic datasets without prior knowledge of their properties. [ABSTRACT FROM AUTHOR]

Given an n -vertex graph G with a fixed linear ordering of V (G) and two integers k , b , the problem FIXED-ORDER BOOK DRAWING with few crossings per edge asks whether or not G admits a k -page book drawing where the maximum number of crossings per edge can be upper bounded by the number b. This problem was posed as an open question by Bhore et al. (J. Graph Algorithms Appl. 2020). In this paper, we study this problem from the viewpoint of parameterized complexity, in particular, we develop fixed-parameter tractable algorithms for it. More specifically, we show that this problem parameterized by both the bound number b of crossings per edge and the vertex cover number τ of the input graph admits an algorithm with running time in (b + 2) (τ 3) ⋅ n , and this problem parameterized by both the bound number b of crossings per edge and the pathwidth κ of the vertex ordering admits an algorithm with running time in (b + 2) (κ 2) ⋅ n. Our results provide a specific answer to Bhore et al.'s question. [ABSTRACT FROM AUTHOR]

To address the limitations in capturing complex semantic features between entities and the incomplete acquisition of entity and relationship information by existing patent knowledge graph reasoning algorithms, we propose a reasoning method that integrates semantic and structural features for patent knowledge graphs, denoted as SS-DSA. Initially, to facilitate the model representation of patent information, a directed graph representation model based on the patent knowledge graph is designed. Subsequently, structural information within the knowledge graph is mined using inductive learning, which is combined with the learning of graph structural features. Finally, an attention mechanism is employed to integrate the scoring results, enhancing the accuracy of reasoning outcomes such as patent classification, latent inter-entity relationships, and new knowledge inference. Experimental results demonstrate that the improved algorithm achieves an up to approximately 30% increase in the MRR index compared to the ComplEx model in the public Dataset 1; in Dataset 2, the MRR and Hits@n indexes, respectively, saw maximal improvements of nearly 30% and 112% when compared with MLMLM and ComplEx models; in Dataset 3, the MRR and Hits@n indexes realized maximal enhancements of nearly 200% and 40% in comparison with the MLMLM model. This effectively proves the efficacy of the refined model in the reasoning process. Compared to recently widely applied reasoning algorithms, it offers a superior capability in addressing complex structures within the datasets and accomplishing the completion of existing patent knowledge graphs. [ABSTRACT FROM AUTHOR]

Structural graph clustering is a data analysis technique that groups nodes within a graph based on their connectivity and structural similarity. The Structural graph clustering SCAN algorithm, a density-based clustering method, effectively identifies core points and their neighbors within areas of high density to form well-defined clusters. However, the clustering quality of SCAN heavily depends on the input parameters, ϵ and μ , making the clustering results highly sensitive to parameter selection. Different parameter settings can lead to significant differences in clustering results, potentially compromising the accuracy of the clusters. To address this issue, a novel structural graph clustering algorithm based on the adaptive selection of density peaks is proposed in this paper. Unlike traditional methods, our algorithm does not rely on external parameters and eliminates the need for manual selection of density peaks or cluster centers by users. Density peaks are adaptively identified using the generalized extreme value distribution, with consideration of the structural similarities and interdependencies among nodes, and clusters are expanded by incorporating neighboring nodes, enhancing the robustness of the clustering process. Additionally, a distance-based structural similarity method is proposed to re-cluster noise nodes to the correct clusters. Extensive experiments on real and synthetic graph datasets validate the effectiveness of our algorithm. The experiment results show that the ADPSCAN has a superior performance compared with several state-of-the-art (SOTA) graph clustering methods. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Data-intensive applications executing on NVM-based storage systems experience serious bottlenecks when moving data between DRAM and NVM. We advocate for the use of the long-existing but recently neglected on-chip DMA to expedite data movement with three contributions. First, we explore new latency-oriented optimization directions, driven by a comprehensive DMA study, to design a high-performance DMA module, which significantly lowers the I/O size threshold to observe benefits. Second, we propose a new data movement engine, Fastmove, that coordinates the use of the DMA along with the CPU with DDIO-aware strategies, judicious scheduling, and load splitting such that the DMA's limitations are compensated, and the overall gains are maximized. Finally, with a general kernel-based design, simple APIs, and DAX file system integration, Fastmove allows applications to transparently exploit the DMA and its new features without code change. We run three data-intensive applications MySQL, GraphWalker, and Filebench atop NOVA, ext4-DAX, and XFS-DAX, with standard benchmarks like TPC-C, and popular graph algorithms like PageRank. Across single- and multi-socket settings, compared to the conventional CPU-only NVM accesses, Fastmove introduces to TPC-C with MySQL 1.13–2.16× speedups of peak throughput, reduces the average latency by 17.7–60.8%, and saves 37.1–68.9% CPU usage spent in data movement. It also shortens the execution time of graph algorithms with GraphWalker by 39.7–53.4%, and introduces 1.01–1.48× throughput speedups for Filebench. [ABSTRACT FROM AUTHOR]

Graphs that are used to model real-world entities with vertices and relationships among entities with edges, have proven to be a powerful tool for describing real-world problems in applications. In most real-world scenarios, entities and their relationships are subject to constant changes. Graphs that record such changes are called dynamic graphs. In recent years, the widespread application scenarios of dynamic graphs have stimulated extensive research on dynamic graph processing systems that continuously ingest graph updates and produce up-to-date graph analytics results. As the scale of dynamic graphs becomes larger, higher performance requirements are demanded to dynamic graph processing systems. With the massive parallel processing power and high memory bandwidth, GPUs become mainstream vehicles to accelerate dynamic graph processing tasks. GPU-based dynamic graph processing systems mainly address two challenges: maintaining the graph data when updates occur (i.e., graph updating) and producing analytics results in time (i.e., graph computing). In this paper, we survey GPU-based dynamic graph processing systems and review their methods on addressing both graph updating and graph computing. To comprehensively discuss existing dynamic graph processing systems on GPUs, we first introduce the terminologies of dynamic graph processing and then develop a taxonomy to describe the methods employed for graph updating and graph computing. In addition, we discuss the challenges and future research directions of dynamic graph processing on GPUs. [ABSTRACT FROM AUTHOR]

Summary: The breadth‐first search procedure is an algorithm that traverses the vertices of a graph, determining the distance from each vertex to the initial vertex. The distance is infinite for a non‐reachable vertex from the starting vertex. Despite having an efficient serial version, this important algorithm is irregular, making its effective parallel implementation a daunting task. This paper shows the results of an OpenMP‐based implementation of the breadth‐first search procedure using the bag data structure. Furthermore, the code relied on the C++ programming language. This paper reimplements an existing proposal coded using the Cilk++ programming language. The experiments relied on 32 strongly connected graphs and 31 disconnected graphs in executions performed on two machines. The first machine contained 28 cores and two threads per core. The second machine comprised 48 processing cores, with hyperthreading disabled. Regarding the serial version, the parallel implementation yielded a speedup of up to 20× when using 28 processing cores and up to 25× when using 56 threads in tests performed on a machine with the first generation of Intel® Xeon® Scalable processors. Furthermore, the new parallel implementation yielded speedups of up to 45× when using 48 cores in experiments performed on a machine with the second generation of Intel® Xeon® Scalable processors. [ABSTRACT FROM AUTHOR]

Drug repurposing aims to find new therapeutic applications for existing drugs in the pharmaceutical market, leading to significant savings in time and cost. The use of artificial intelligence and knowledge graphs to propose repurposing candidates facilitates the process, as large amounts of data can be processed. However, it is important to pay attention to the explainability needed to validate the predictions. We propose a general architecture to understand several explainable methods for graph completion based on knowledge graphs and design our own architecture for drug repurposing. We present XG4Repo (eXplainable Graphs for Repurposing), a framework that takes advantage of the connectivity of any biomedical knowledge graph to link compounds to the diseases they can treat. Our method allows methapaths of different types and lengths, which are automatically generated and optimised based on data. XG4Repo focuses on providing meaningful explanations to the predictions, which are based on paths from compounds to diseases. These paths include nodes such as genes, pathways, side effects, or anatomies, so they provide information about the targets and other characteristics of the biomedical mechanism that link compounds and diseases. Paths make predictions interpretable for experts who can validate them and use them in further research on drug repurposing. We also describe three use cases where we analyse new uses for Epirubicin, Paclitaxel, and Predinisone and present the paths that support the predictions. [ABSTRACT FROM AUTHOR]

This research paper introduces an optimization methodology for the strategic electric sources' placement at multiple positions in a DC islanded microgrid characterized by a mesh network, aiming to minimize line losses while considering minimal cable weight. The DC microgrid studied in this paper is composed of PV panels, batteries, a diesel generator, and 20 residential loads. Employing Dijkstra's algorithm, a graph algorithm used in Google Maps, the study identifies the shortest path (resistance) between potential source nodes and various variable loads within a predefined electric distribution mesh network topology. This study focuses on active power considerations and offers valuable insights into the placement optimization of multiple sources' positions in DC microgrid mesh networks. A key contribution of this paper lies in the ranking of source node positions based on minimal to maximal line losses, taking into consideration optimal cable weights, while using MATPOWER to validate sources' ranking based on Dijkstra's hypothesis. The research further includes a techno-economic study to assess the viability of sources' placement at multiple positions within the mesh network, comparing it with the optimal placement scenario involving a single position for all sources. This methodology serves as a valuable resource for system designers and operators aiming to minimize line losses and optimize energy distribution in DC microgrids in a mesh topology. [ABSTRACT FROM AUTHOR]

Background: The growing abundance of in vitro omics data, coupled with the necessity to reduce animal testing in the safety assessment of chemical compounds and even eliminate it in the evaluation of cosmetics, highlights the need for adequate computational methodologies. Data from omics technologies allow the exploration of a wide range of biological processes, therefore providing a better understanding of mechanisms of action (MoA) related to chemical exposure in biological systems. However, the analysis of these large datasets remains difficult due to the complexity of modulations spanning multiple biological processes. Results: To address this, we propose a strategy to reduce information overload by computing, based on transcriptomics data, a comprehensive metabolic sub-network reflecting the metabolic impact of a chemical. The proposed strategy integrates transcriptomic data to a genome scale metabolic network through enumeration of condition-specific metabolic models hence translating transcriptomics data into reaction activity probabilities. Based on these results, a graph algorithm is applied to retrieve user readable sub-networks reflecting the possible metabolic MoA (mMoA) of chemicals. This strategy has been implemented as a three-step workflow. The first step consists in building cell condition-specific models reflecting the metabolic impact of each exposure condition while taking into account the diversity of possible optimal solutions with a partial enumeration algorithm. In a second step, we address the challenge of analyzing thousands of enumerated condition-specific networks by computing differentially activated reactions (DARs) between the two sets of enumerated possible condition-specific models. Finally, in the third step, DARs are grouped into clusters of functionally interconnected metabolic reactions, representing possible mMoA, using the distance-based clustering and subnetwork extraction method. The first part of the workflow was exemplified on eight molecules selected for their known human hepatotoxic outcomes associated with specific MoAs well described in the literature and for which we retrieved primary human hepatocytes transcriptomic data in Open TG-GATEs. Then, we further applied this strategy to more precisely model and visualize associated mMoA for two of these eight molecules (amiodarone and valproic acid). The approach proved to go beyond gene-based analysis by identifying mMoA when few genes are significantly differentially expressed (2 differentially expressed genes (DEGs) for amiodarone), bringing additional information from the network topology, or when very large number of genes were differentially expressed (5709 DEGs for valproic acid). In both cases, the results of our strategy well fitted evidence from the literature regarding known MoA. Beyond these confirmations, the workflow highlighted potential other unexplored mMoA. Conclusion: The proposed strategy allows toxicology experts to decipher which part of cellular metabolism is expected to be affected by the exposition to a given chemical. The approach originality resides in the combination of different metabolic modelling approaches (constraint based and graph modelling). The application to two model molecules shows the strong potential of the approach for interpretation and visual mining of complex omics in vitro data. The presented strategy is freely available as a python module (https://pypi.org/project/manamodeller/) and jupyter notebooks (https://github.com/LouisonF/MANA). [ABSTRACT FROM AUTHOR]

AbstractLocation prediction based on social media information is highly valuable in human mobility research and has multiple real-life applications. However, existing research methods often ignore social influences, largely ignoring implicit information regarding interactions between users and geographical locations. Additionally, they generally employ single modeling structures, which restricts the effective integration of complex spatiotemporal characteristics and factors influencing user mobility. In this context, we propose a novel network with physical and social awareness that expresses both physical and social influences of user mobility from a global perspective based on a heterogeneous graph constructed using users and spatial locations as nodes and relationships between them as edges. This graph enables the model to leverage information from connected nodes and edges to infer missing or unobserved data. The model predicts future locations of users by effectively integrating the temporal and spatial features of user trajectory series. The proposed model is validated using three social media datasets. The experimental results demonstrate that the proposed method outperforms the state-of-the-art baseline models. This indicates the importance of considering complex interactions between users and locations, as well as the various influences of physical and social spaces. [ABSTRACT FROM AUTHOR]

We introduce time‐varying extremum graph (tveg), a topological structure to support visualization and analysis of a time‐varying scalar field. The extremum graph is a sub‐structure of the Morse–Smale complex. It captures the adjacency relationship between cells in the Morse decomposition of a scalar field. We define the tveg as a time‐varying extension of the extremum graph and demonstrate how it captures salient feature tracks within a dynamic scalar field. We formulate the construction of the tveg as an optimization problem and describe an algorithm for computing the graph. We also demonstrate the capabilities of tveg towards identification and exploration of topological events such as deletion, generation, split and merge within a dynamic scalar field via comprehensive case studies including a viscous fingers and a 3D von Kármán vortex street dataset. [ABSTRACT FROM AUTHOR]

Motivation The increasing availability of complete genomes demands for models to study genomic variability within entire populations. Pangenome graphs capture the full genomic similarity and diversity between multiple genomes. In order to understand them, we need to see them. For visualization, we need a human-readable graph layout: a graph embedding in low (e.g. two) dimensional depictions. Due to a pangenome graph's potential excessive size, this is a significant challenge. Results In response, we introduce a novel graph layout algorithm: the Path-Guided Stochastic Gradient Descent (PG-SGD). PG-SGD uses the genomes, represented in the pangenome graph as paths, as an embedded positional system to sample genomic distances between pairs of nodes. This avoids the quadratic cost seen in previous versions of graph drawing by SGD. We show that our implementation efficiently computes the low-dimensional layouts of gigabase-scale pangenome graphs, unveiling their biological features. Availability and implementation We integrated PG-SGD in ODGI which is released as free software under the MIT open source license. Source code is available at https://github.com/pangenome/odgi. [ABSTRACT FROM AUTHOR]

We introduce a new inductive bias for learning in dynamic event-based human systems. This is intended to partially address the issue of deep learning in chaotic systems. Instead of fitting the data to polynomial expansions that are expressive enough to approximate the generative functions or of inducing a universal approximator to learn the patterns and inductive bias, we only assume that the relationship between the input features and output classes changes over time, and embed this assumption through a form of dynamic contrastive learning in pre-training, where pre-training labels contain information about the class labels and time periods. We do this by extending and integrating two separate forms of contrastive learning. We note that this approach is not equivalent to inserting an extra feature into the input data that contains time period, because the input data cannot contain the label. We illustrate the approach on a recently designed learning algorithm for event-based graph time-series classification, and demonstrate its value on real-world data. [ABSTRACT FROM AUTHOR]

Graph representation learning aims to map nodes or edges within a graph using low-dimensional vectors, while preserving as much topological information as possible. During past decades, numerous algorithms for graph representation learning have emerged. Among them, proximity matrix representation methods have been shown to exhibit excellent performance in experiments and scale to large graphs with millions of nodes. However, with the rapid development of the Internet, information interactions are happening at the scale of billions every moment. Most methods for similarity matrix factorization still focus on static graphs, leading to incomplete similarity descriptions and low embedding quality. To enhance the embedding quality of temporal graph learning, we propose a temporal graph representation learning model based on the matrix factorization of Time-constrained Personalize PageRank (TPPR) matrices. TPPR, an extension of personalized PageRank (PPR) that incorporates temporal information, better captures node similarities in temporal graphs. Based on this, we use Single Value Decomposition or Nonnegative Matrix Factorization to decompose TPPR matrices to obtain embedding vectors for each node. Through experiments on tasks such as link prediction, node classification, and node clustering across multiple temporal graphs, as well as a comparison with various experimental methods, we find that graph representation learning algorithms based on TPPR matrix factorization achieve overall outstanding scores on multiple temporal datasets, highlighting their effectiveness. [ABSTRACT FROM AUTHOR]

Motion planning for autonomous vehicles relies heavily on perception and prediction results to find a safe, collision-free local trajectory that adheres to traffic rules. However, vehicle perception is frequently limited by occlusion, and the generation of safe local trajectories with restricted perception poses a significant challenge in the field of motion planning. This paper introduces a collision avoidance trajectory planning algorithm that considers potential collision risks, within a hierarchical framework of sampling and optimization. The primary objective of this work is to generate trajectories that are safer and align better with human driver behavior while considering potential collision risks in occluded regions. Specifically, in occlusion scenarios, the state space is discretized, and a dynamic programming algorithm is used for a sampling-based search to obtain initial trajectories. Additionally, the concept of a driving risk field is introduced to describe potential collision risk elements within the human-vehicle-road environment. By drawing inspiration from graph search algorithms, potential collision risk areas are accurately described, and a cost function is proposed for evaluating potential risks in occluded regions. Drivers typically exhibit conservative and cautious driving behavior when navigating through occluded regions. The proposed algorithm not only prioritizes driving safety but also considers driving efficiency, thereby reducing the vehicle’s conservativeness when passing through occlusions. The research results demonstrate that the ego vehicle can actively avoid blind spots and tends to move away from occluded regions, aligning more closely with human driver behavior. [ABSTRACT FROM AUTHOR]

In GNSS/IMU integrated navigation systems, factors like satellite occlusion and non-line-of-sight can degrade satellite positioning accuracy, thereby impacting overall navigation system results. To tackle this challenge and leverage historical pseudorange information effectively, this paper proposes a graph optimization-based GNSS/IMU model with virtual constraints. These virtual constraints in the graph model are derived from the satellite's position from the previous time step, the rate of change of pseudoranges, and ephemeris data. This virtual constraint serves as an alternative solution for individual satellites in cases of signal anomalies, thereby ensuring the integrity and continuity of the graph optimization model. Additionally, this paper conducts an analysis of the graph optimization model based on these virtual constraints, comparing it with traditional graph models of GNSS/IMU and SLAM. The marginalization of the graph model involving virtual constraints is analyzed next. The experiment was conducted on a set of real-world data, and the results of the proposed method were compared with tightly coupled Kalman filtering and the original graph optimization method. In instantaneous performance testing, the method maintains an RMSE error within 5% compared with real pseudorange measurement, while in a continuous performance testing scenario with no available GNSS signal, the method shows approximately a 30% improvement in horizontal RMSE accuracy over the traditional graph optimization method during a 10-second period. This demonstrates the method's potential for practical applications. [ABSTRACT FROM AUTHOR]

With the rapid development of cloud computing paradigm and mobile devices, the number of cloud services and user interest data are growing explosively. It becomes harder for users to find suitable cloud services within satisfying response time. Thus a suitable cloud service automatic recommendation system is needed to solve the above problem. In this work, we propose KG2Rec, a novel recommendation method based on Knowledge Graph to provide users with appropriate recommendations to meet their real-time needs. The property-specific knowledge graph model is designed to model user–item and item–item bipartite relations. Based on the property-specific knowledge graph model, property-specific user–item relation features can be mined from it. Then the user–item relation features will be integrated into an improved collaborative filtering algorithm based on the local sensitive hash technique for Top-N item recommendation. Finally, we evaluate the proposed method in terms of Top-N recommendation on the MovieLens dataset, and prove it outperforms numbers of state-of-the-art recommendation systems. In addition, we prove it has well performance in term of long tail recommendation and big data processing. [ABSTRACT FROM AUTHOR]

Cognitive satellite networks can enhance spectrum efficiency by enabling satellite networks to dynamically share idle spectrum with terrestrial networks. However, when taking into consideration the inter-cell or internet interferences in various application circumstances, dynamic spectrum optimization in cognitive satellite networks remains challenging due to the diversified QoS demands of secondary terrestrial users. To address this issue, this paper proposes an efficient spectrum allocation algorithm which is based on graph coloring technique and combined with analytic hierarchy process so as to meet the requirements of dynamic spectrum allocation to secondary terrestrial users with diversified QoS demands and yet without causing severe inference to primary satellite users. In this paper, we combine graph coloring algorithm and analytic hierarchy process so as to assign the heterogeneous spectrum bands to secondary users in an orderly manner. The method of graph coloring is applied to control obvious interference caused by the secondary users. We also provide numerical results to evaluate the impacts of different parameter settings on the performances of the proposed solution. [ABSTRACT FROM AUTHOR]

This paper proposes a Robust Spatial-Temporal Graph Neural Network (RSTGNN), which overcomes the limitations faced by graph-based models against dynamic graph perturbations using robust spatial-temporal self-attentions to learn dynamic graph embeddings. In the RSTGNN model training, a selective spatial self-attention technique is employed to aggregate neighboring information based on projected node similarity, which reduces attention weights of edges with less similarity, enabling better information aggregation and preventing the model from ignoring spatial-temporal information. The temporal self-attention layer in the RSTGNN model intensifies temporal patterns using time-span-limited temporal attention weights. Additionally, the model uses a spatial-temporal loss function that penalizes nodes and edges most likely perturbed to alleviate the influence of dynamic graph perturbation. Specifically, the spatial loss focuses on attention weights associated with high-degree and potentially-attacked nodes, while the temporal loss targets attention weights of high centrality-varied nodes to prevent nodes from experiencing excessive centrality changes. To verify the effectiveness of our approach, we evaluate RSTGNN compared with other graph-based models under different node-based or edge-based perturbation rates. Results demonstrate that RSTGNN maintains high effectiveness in dynamic node classification and link prediction for five real dynamic graph datasets. [ABSTRACT FROM AUTHOR]

Accurate news representation is of crucial importance in personalized news recommendation. Most of existing news recommendation model lack comprehensiveness because they do not consider the higher-order structure between user–news interactions, relevance between user clicks on news. In this paper, we propose graph neural news recommendation based on multi-view representation learning which encodes high-order connections into the representation of news through information propagation along the graph. For news representations, we learn click news and candidate news content information embedding from various news attributes. And then combine obtained structure-based representations with representations from news content. Besides, we adopt a candidate-aware attention network to weight clicked news based on their relevance with candidate news to learn candidate-aware user interest representation for better matching with candidate news. The performance of the model has been improved in common evaluation metric. Extensive experiments on benchmark datasets show that our approach can effectively improve performance in news recommendation. [ABSTRACT FROM AUTHOR]

Advanced control strategies for delivering heat to users in a district heating network have the potential to improve performance and reduce wasted energy. To enable the design of such controllers, this paper proposes an automated plant modeling framework that captures the relevant system dynamics, while being adaptable to any network configuration. Starting from the network topology and system parameters, the developed algorithm generates a state-space model of the system, relying on a graph-based technique to facilitate the combination of component models into a full network model. The accuracy of the approach is validated against experimental data collected from a laboratory-scale district heating network. The verification shows an acceptable average normalized root-mean-square error of 0.39 in the mass flow rates delivered to the buildings, and 0.15 in the network return temperature. Furthermore, the ability of the proposed modeling technique to rapidly generate models characterizing different network configurations is demonstrated through its application to topology optimization. The optimal design, obtained via a branch and bound algorithm, reduces network heat losses by 15% as compared to the conventional length-minimized topology. [ABSTRACT FROM AUTHOR]

Many studies now indicate that brain disorders are associated with functional connectivity between brain regions, but the impact of interactions among functional connections on diseases remains to be explored. Moreover, existing models for analyzing the temporal and spatial attributes of fMRI data exhibit limitations in their efficacy. Currently, there is an absence of a comprehensive model capable of simultaneously capturing disease-related interactions within functional connectivity, fully leveraging the temporal and spatial characteristics of fMRI, and achieving superior diagnostic accuracy. To address these gaps, we propose a model to classify brain disorders that employs a novel algorithm and multimodal graph convolutional networks to process the temporal and spatial features of fMRI data separately, along with the demographic information. In the proposed model, a deep feature selection algorithm is employed to discover disease-related biomarkers and evaluate their impact on brain disorders. Remarkably, this approach has led to a classification accuracy of 80.66%, which surpasses the performance of graph neural networks by approximately 10%. Notably, our investigations have uncovered novel biomarkers linked to autism, with our findings corroborated by relevant literature. These achievements underscore the model's potential in revealing critical insights pertinent to autism, thereby facilitating groundbreaking experimental research in the field. [ABSTRACT FROM AUTHOR]

In today's society, communication among people has become more frequent and extensive due to the rapid development of science, technology, and the Internet. This vast communication occurs in real life and virtual online worlds. However, with the overwhelming amount of information available, people often struggle with finding and accessing the information they need, leading to frustration. To address this challenge, we conducted a study to extract valuable information and insights from users' social relationships. While existing models can help us understand and analyze users' social relationships to some extent, there are still significant challenges in extracting valuable insights. Therefore, we conducted in-depth research to improve the GraphRec model and created a new social recommendation model called the CWYGNN model. The CWYGNN model is unique because it can identify deeper connections in users' social interactions through in-depth learning of the social sequences between users. This is important for understanding users' behavioral patterns, predicting their needs, and providing personalized services. To validate the effectiveness of the CWYGNN model, we conducted experiments and comparisons on several public datasets. The experimental results show that the CWYGNN model outperforms similar approaches in processing user social relationships and extracting valuable insights. This result provides a new way of thinking and methodology to help us better understand and serve users and ultimately enhance their overall experience. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Jilin University (Science Edition) / Jilin Daxue Xuebao (Lixue Ban) is the property of Zhongguo Xue shu qi Kan (Guang Pan Ban) Dian zi Za zhi She and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Personalized learning resource recommendations may help resolve the difficulties of online education that include learning mazes and information overload. However, existing personalized learning resource recommendation algorithms have shortcomings such as low accuracy and low efficiency. This study proposes a deep recommendation system algorithm based on a knowledge graph (D-KGR) that includes four data processing units. These units are the recommendation unit (RS unit), the knowledge graph feature representation unit (KGE unit), the cross compression unit (CC unit), and the feature extraction unit (FE unit). This model integrates technologies including the knowledge graph, deep learning, neural network, and data mining. It introduces cross compression in the feature learning process of the knowledge graph and predicts user attributes. Multimodal technology is used to optimize the process of project attribute processing; text type attributes, multivalued type attributes, and other type attributes are processed separately to reconstruct the knowledge graph. A convolutional neural network algorithm is introduced in the reconstruction process to optimize the data feature qualities. Experimental analysis was conducted from two aspects of algorithm efficiency and accuracy, and the particle swarm optimization, neural network, and knowledge graph algorithms were compared. Several tests showed that the deep recommendation system algorithm had obvious advantages when the number of learning resources and users exceeded 1,000. It has the ability to integrate systems such as the particle swarm optimization iterative classification, neural network intelligent simulation, and low resource consumption. It can quickly process massive amounts of information data, reduce algorithm complexity and requires less time and had lower costs. Our algorithm also has better efficiency and accuracy. [ABSTRACT FROM AUTHOR]

Function layout, also known as function reordering or function placement, is one of the most effective profile-guided compiler optimizations. By reordering functions in a binary, compilers can improve the performance of large-scale applications or reduce the compressed size of mobile applications. Although the technique has been extensively studied in the context of large-scale binaries, no study has thoroughly investigated function layout algorithms on mobile applications. In this article, we develop the first principled solution for optimizing function layouts in the mobile space. To this end, we identify two key optimization goals: reducing the compressed code size and improving the cold start-up time of a mobile application. Then, we propose a formal model for the layout problem, whose objective closely matches our goals, and a novel algorithm for optimizing the layout. The method is inspired by the classic balanced graph partitioning problem. We have carefully engineered and implemented the algorithm in an open-source compiler, Low-level Virtual Machine (LLVM). An extensive evaluation of the new method on large commercial mobile applications demonstrates improvements in start-up time and compressed size compared to the state-of-the-art approach.1 [ABSTRACT FROM AUTHOR]

Internet-of-Vehicles (IoV) plays an important part in Intelligent Transportation Systems and is widely regarded as one of the most strategic applications in smart city development. Smart spectrum resource management has received much attention from the research community as it is believed to be a promising approach for solving the spectrum resource challenge of IoV and Intelligent Transportation Systems. In this article, we propose a dynamic spectrum optimization technique based on a deep learning method for user mobility prediction. For this purpose, based on the Exploration and Preferential Return (EPR) model which can be used to investigate the movement trend and aggregation behavior of the target, we adopt the D-Exploration and Preferential Return (D-EPR) model as a deep learning technique to train a Long-Short Term Memory (LSTM) recurrent neural network (RNN) in order to predict the future locations of IoV nodes. With the predicted user's mobility, a graph theoretic algorithm is then applied to achieve spectrum reuse and optimization. Besides, our proposed deep-learning-based user mobility prediction is able to identify the user position. This paper then compares the performances of mobility prediction by traditional methods and our proposal. The outcomes of spectrum efficiency and network capacity are also provided to show the effectiveness of the proposed solution. Numerical results are provided to evaluate the prediction accuracy and network utility of our proposal with various memory histories, user distribution mechanisms and node dwell time. [ABSTRACT FROM AUTHOR]

This paper presents a comprehensive survey of knowledge graphs in education. It covers the patterns and prospects of research in this area. A total of 48 relevant publications between 2011 and 2023 were collected from the Web of Science, Scopus, and ProQuest for review. The findings reveal a sharp increase in recent years in the body of research into educational knowledge graphs which was mainly conducted from institutions in China. Most of the relevant research work adopted a quantitative method, such as performance evaluation, user surveys, and controlled experiments, to assess the effectiveness of knowledge graph approaches. The findings also suggest that knowledge graph approaches were primarily researched and implemented in higher education institutions, with a focus on computer science, mathematics, and engineering. The most frequently addressed objectives included enhancing knowledge representation and providing personal learning recommendations, and the most common applications were concept instruction and educational recommendations. Diverse data resources, such as course materials, student learning behaviours, and online encyclopaedia, were processed to implement knowledge graph approaches in different scenarios. Relevant technical means employed for the implementation of knowledge graphs dealt with the purposes of building knowledge ontology, achieving recommendations, and creating knowledge graphs. Various pedagogies such as personalised learning and collaborative learning are supported by the knowledge graph approaches. The findings also identified key limitations in the relevant work, including insufficient information for knowledge graph construction, difficulty in extending applications across subject areas, the restricted scale and scope of data resources, and the lack of comprehensive user feedback and evaluation processes. [ABSTRACT FROM AUTHOR]

In response to asynchronous and delayed sensors within multi-sensor integrated navigation systems, the computational complexity of joint optimization navigation solutions persistently rises. This paper introduces an adaptive fast integrated navigation algorithm for INS/GPS/VO based on factor graph. The factor graph model for INS/GPS/VO is developed subsequent to individual modeling of the Inertial Navigation System (INS), Global Positioning System (GPS), and Visual Odometer (VO) using the factor graph model approach. Additionally, an Adaptive Fast Incremental Smoothing (AFIS) factor graph optimization algorithm is proposed. The simulation results demonstrate that the factor-graph-based integrated navigation algorithm consistently yields high-precision navigation outcomes even amidst dynamic changes in sensor validity and the presence of asynchronous and delayed sensor measurements. Notably, the AFIS factor graph optimization algorithm significantly enhances real-time performance compared to traditional Incremental Smoothing (IF) algorithms, while maintaining comparable real-time accuracy. [ABSTRACT FROM AUTHOR]

We propose a technique (IPEAC) that extends the Ant Colony Optimization (ACO) for shortest path finding. In a grid-based environment, when the ACO converges, the optimal path needs to be identified among other emerging paths. Our proposed approach utilizes an image processing algorithm named Connected Component Analysis (CCA). In our implementation, the result of the ACO is an image that models the system elements of source, destination, obstacles, background and agents. This image is fed into CCA which applies a sequence of operators to find the optimal path and calculates its coordinates so that it can be traversed. IPEAC was tested against Dijkstra and A* algorithms. Our experimental work showed that IPEAC is effective and produced an accuracy of 97.8% compared to the A* and 91.8% compared to Dijkstra, however the A* was superior in terms of time efficiency and IPEAC was 60% more efficient that Dijkstra. [ABSTRACT FROM AUTHOR]

Given a large set U where each item a∈ U has weight w(a), we want to estimate the total weight \(W=\sum _{a∈ U} w(a)\) to within factor of 1± ɛ with some constant probability > 1/2. Since n=|U| is large, we want to do this without looking at the entire set U. In the traditional setting in which we are allowed to sample elements from U uniformly, sampling Ω (n) items is necessary to provide any non-trivial guarantee on the estimate. Therefore, we investigate this problem in different settings: in the proportional setting we can sample items with probabilities proportional to their weights, and in the hybrid setting we can sample both proportionally and uniformly. These settings have applications, for example, in sublinear-time algorithms and distribution testing. Sum estimation in the proportional and hybrid setting has been considered before by Motwani, Panigrahy, and Xu [ICALP, 2007]. In their article, they give both upper and lower bounds in terms of n. Their bounds are near-matching in terms of n, but not in terms of ɛ. In this article, we improve both their upper and lower bounds. Our bounds are matching up to constant factors in both settings, in terms of both n and ɛ. No lower bounds with dependency on ɛ were known previously. In the proportional setting, we improve their \(\tilde{O}(\sqrt {n}/ɛ ^{7/2})\) algorithm to \(O(\sqrt {n}/ɛ)\). In the hybrid setting, we improve \(\tilde{O}(\sqrt [3]{n}/ ɛ ^{9/2})\) to \(O(\sqrt [3]{n}/ɛ ^{4/3})\). Our algorithms are also significantly simpler and do not have large constant factors. We then investigate the previously unexplored scenario in which n is not known to the algorithm. In this case, we obtain a \(O(\sqrt {n}/ɛ + \log n / ɛ ^2)\) algorithm for the proportional setting, and a \(O(\sqrt {n}/ɛ)\) algorithm for the hybrid setting. This means that in the proportional setting, we may remove the need for advice without greatly increasing the complexity of the problem, while there is a major difference in the hybrid setting. We prove that this difference in the hybrid setting is necessary, by showing a matching lower bound. Our algorithms have applications in the area of sublinear-time graph algorithms. Consider a large graph G=(V, E) and the task of (1 ± ɛ)-approximating |E|. We consider the (standard) settings where we can sample uniformly from E or from both E and V. This relates to sum estimation as follows: we set U = V and the weights to be equal to the degrees. Uniform sampling then corresponds to sampling vertices uniformly. Proportional sampling can be simulated by taking a random edge and picking one of its endpoints at random. If we can only sample uniformly from E, then our results immediately give a \(O(\sqrt {|V|} / ɛ)\) algorithm. When we may sample both from E and V, our results imply an algorithm with complexity \(O(\sqrt [3]{|V|}/ɛ ^{4/3})\). Surprisingly, one of our subroutines provides an (1 ± ɛ)-approximation of |E| using \(\tilde{O}(d/ɛ ^2)\) expected samples, where d is the average degree, under the mild assumption that at least a constant fraction of vertices are non-isolated. This subroutine works in the setting where we can sample uniformly from both V and E. We find this remarkable since it is O(1/ɛ2) for sparse graphs. [ABSTRACT FROM AUTHOR]

Given a bipartite graph G, the Bicluster Editing problem asks for the minimum number of edges to insert or delete in G so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter k, which is the number of allowed modified edges. We first show that one can obtain a kernel with 4.5k vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time O ∗ (2. 581 k) . Our algorithm has the advantage of being conceptually simple and should be easy to implement. [ABSTRACT FROM AUTHOR]