Search

Partite, 3-uniform hypergraphs are 3-uniform hypergraphs in which each hyperedge contains exactly one point from each of the 3 disjoint vertex classes. We consider the degree sequence problem of partite, 3-uniform hypergraphs, that is, to decide if such a hypergraph with prescribed degree sequences exists. We prove that this decision problem is NP-complete in general, and give a polynomial running time algorithm for third almost-regular degree sequences, that is, when each degree in one of the vertex classes is k or k − 1 for some fixed k, and there is no restriction for the other two vertex classes. We also consider the sampling problem, that is, to uniformly sample partite, 3-uniform hypergraphs with prescribed degree sequences. We propose a Parallel Tempering method, where the hypothetical energy of the hypergraphs measures the deviation from the prescribed degree sequence. The method has been implemented and tested on synthetic and real data. It can also be applied for χ2 testing of contingency tables. We have shown that this hypergraph-based χ2 test is more sensitive than the standard χ2 test. The extra sensitivity is especially advantageous on small data sets, where the proposed Parallel Tempering method shows promising performance. [ABSTRACT FROM AUTHOR]

Introduction: At the pandemic's beginning, significant concern has risen about the prevalence of myocardial involvement after SARS‐CoV‐2 infection. We assessed the cardiovascular burden of SARS‐CoV‐2 in a large cohort of athletes and identified factors that might affect the disease course. We included 633 athletes in our study on whom we performed extensive cardiology examinations after recovering from SARS‐CoV‐2 infection. More than half of the athletes (n = 322) returned for a follow‐up examination median of 107 days after the commencement of their infection. Results: Troponin T positivity was as low as 1.4% of the athletes, where the subsequently performed examinations did not show definitive, ongoing myocardial injury. Altogether, 31% of the athletes' rapid training rebuild was hindered by persistent or reoccurring symptoms. Female athletes reported a higher prevalence of return to play (RTP) symptoms than their male counterparts (34% vs. 19%, p = 0.005). The development of long COVID symptoms was independently predicted by increasing age and acute symptoms' severity in a multiple regression model (AUC 0.75, CI 0.685–0.801). Athletes presenting with either or both cough and ferritin levels higher than >150 μg/L had a 4.1x (CI 1.78–9.6, p = 0.001) higher odds ratio of developing persistent symptoms. Conclusion: While SARS‐CoV‐2 rarely affects the myocardium in athletes, about one in three of them experience symptoms beyond the acute phase. Identifying those athletes with a predisposition to developing long‐standing symptoms may aid clinicians and trainers in finding the optimal return‐to‐play timing and training load rebuild pace. [ABSTRACT FROM AUTHOR]

Scholarly search engines, reference management tools, and academic social networks enable modern researchers to organize their scientific libraries. Moreover, they often provide recommendations for scientific publications that might be of interest to researchers. Because of the exponentially increasing volume of publications, effective citation recommendation is of great importance to researchers, as it reduces the time and effort spent on retrieving, understanding, and selecting research papers. In this context, we address the problem of citation recommendation, i.e., the task of recommending citations for a new paper. Current research investigates this task in different settings, including cases where rich user metadata is available (e.g., user profile, publications, citations). This work focus on a setting where the user provides only the abstract of a new paper as input. Our proposed approach is to expand the semantic features of the given abstract using knowledge graphs – and, combine them with other features (e.g., indegree, recency) to fit a learning to rank model. This model is used to generate the citation recommendations. By evaluating on real data, we show that the expanded semantic features lead to improving the quality of the recommendations measured by nDCG@10. [ABSTRACT FROM AUTHOR]

This paper introduces a generalized data base concept that unites relational and semi structured data models. As an important theoretical result we could find a quadratic decision algorithm for the implication problem of functional and join dependencies defined on the united data model. As practical contribution we presented a normal form for the new data model as a tool for data base design. With our novel representations of regular expressions, a more effective searching method could be developed. XML elements are described by XML schema languages such as a DTD or an XML Schema definition. The instances of these elements are semi-structured tuples. A semistructured tuple is an ordered list of (attribute: value) pairs. We may think of a semi-structured tuple as a sentence of a formal language, where the values are the terminal symbols and the attribute names are the non-terminal symbols. In the authors' former work (Szabó and Benczúr, 2015) they introduced the notion of the extended tuple as a sentence from a regular language generated by a grammar where the non-terminal symbols of the grammar are the attribute names of the tuple. Sets of extended tuples are the extended relations. The authors then introduced the dual language, which generates the tuple types allowed to occur in extended relations. They defined functional dependencies (regular FD - RFD) over extended relations. In this paper they rephrase the RFD concept by directly using regular expressions over attribute names to define extended tuples. By the help of a special vertex labeled graph associated to regular expressions the specification of substring selection for the projection operation can be defined. The normalization for regular schemas is more complex than it is in the relational model, because the schema of an extended relation can contain an infinite number of tuple types. However, the authors can define selection, projection and join operations on extended relations too, so a lossless-join decomposition can be performed. They extended their previous model to deal with XML schema indicators too, e.g., with numerical constraints. They added line and set constructors too, in order to extend their model with more general projection and selection operators. This model establishes a query language with table join functionality for collected XML element data. [ABSTRACT FROM AUTHOR]

In a previous result, we showed that the influence of social contacts spreads information about new artists through the Last.fm social network. We successfully decomposed influence from effects of trends, global popularity, and homophily or shared environment of friends. In this paper, we present our new experiments that use a mathematically sound formula for defining and measuring the influence in the network. We provide new baseline and influence models and evaluation measures, both batch and online, for real-time recommendations with very strong temporal aspects. Our experiments are carried over the 2-year 'scrobble' history of 70,000 Last.fm users. In our results, we formally define and distil the effect of social influence. In addition, we provide new models and evaluation measures for real-time recommendations with very strong temporal aspects. [ABSTRACT FROM AUTHOR]

We investigate the statistical properties of votes of customers for spots of France collected by the startup company Nomao. The frequencies of votes per spot and per customer are characterized by a power law distribution which remains stable on a time scale of a decade when the number of votes is varied by almost two orders of magnitude. Using the computer science methods we explore the spectrum and the eigenvalues of a matrix containing user ratings to geolocalized items. Eigenvalues nicely map to large towns and regions but show certain level of instability as we modify the interpretation of the underlying matrix. We evaluate imputation strategies that provide improved prediction performance by reaching geographically smooth eigenvectors. We point on possible links between distribution of votes and the phenomenon of self-organized criticality. [ABSTRACT FROM AUTHOR]

We investigate the statistical properties of votes of customers for spots of France collected by the startup company Nomao. The frequencies of votes per spot and per customer are characterized by a power law distribution which remains stable on a time scale of a decade when the number of votes is varied by almost two orders of magnitude. Using the computer science methods we explore the spectrum and the eigenvalues of a matrix containing user ratings to geolocalized items. Eigenvalues nicely map to large towns and regions but show certain level of instability as we modify the interpretation of the underlying matrix. We evaluate imputation strategies that provide improved prediction performance by reaching geographically smooth eigenvectors. We point on possible links between distribution of votes and the phenomenon of self-organized criticality. [ABSTRACT FROM AUTHOR]

We describe random sampling techniques for approximately solving problems that involve cuts and flows in graphs. We give a near-linear-time randomized combinatorial construction that transforms any graph on n vertices into an O(n log n)-edge graph on the same vertices whose cuts have approximately the same value as the original graph's. In this new graph, for example, we can run the Õ (m3/2)-time maximum flow algorithm of Goldberg and Rao to find an s-t minimum cut in Õ(n3/2) time. This corresponds to a (1 + ε)-times minimum s-t cut in the original graph. A related approach leads to a randomized divide-and-conquer algorithm producing an approximately maximum flow in Õ(mn) time. Our algorithm can also be used to improve the running time of sparsest cut approximation algorithms from Õ(m√n) to Õ (n²) and to accelerate several other recent cut and flow algorithms. Our algorithms are based on a general theorem analyzing the concentration of random graphs' cut values near their expectations. Our work draws only on elementary probability and graph theory. [ABSTRACT FROM AUTHOR]

Functional dependency (FD) is one of the most analyzed integrity constraints for any data model. In the relational data model, FDs are defined in a natural way: the values of an attribute set Y depend on the values of another attribute set X, that is, 'Y is a function of X'. FDs are well studied and are widely used in normalization theory. XML functional dependencies (XFD) can be defined in different ways and no universally best definition has been proposed. They are defined by very intricate concepts, and they are mostly based upon XML elements described by XML schema languages such as a DTD or an XML Schema definition. The instances of these elements are semi-structured tuples. A semi-structured tuple is an ordered list of (attribute: value) pairs. We may think of a tuple as a sentence of a formal language, where the values are the terminal symbols and the attribute names are the nonterminal symbols. In this way, the sequence of the attribute names is the left side of a production rule used to accept the next terminal symbol, that is, the next value of the tuple. So the list of values forms the sentence and the list of attributes forms the dual sentence. In this paper, we introduce the notion of the extended tuple as a sentence from a regular language generated by a grammar where the nonterminal symbols of the grammar are the attribute names of the tuple. Sets of extended tuples are the extended relations (relations are instances). We then introduce the dual language, which generates the tuple types allowed to occur in extended relations. We define functional dependencies over extended relations. The syntax of functional dependencies will be given on the graph of the finite state automaton accepting the regular language. Using this model, we can also handle extended relations generated by recursive regular expressions. The implication problem of our class of dependencies is decidable and finitely axiomatizable by a version of the Chase algorithm performed on the graph of the associated finite state automaton. [ABSTRACT FROM AUTHOR]

Hyper-graphs offer the opportunity to formulate logical statements about their components, for example, using Horn clauses. Several models of Information Systems can be represented using hyper-graphs as the workflows, i.e., the business processes. During the modeling of Information Systems, many constraints should be maintained during the development process. The models of Information Systems are complex objects, for this reason, the analysis of algorithms and graph structures that can support the consistency and integrity of models is an essential issue. A set of interdependencies between models and components of architecture can be formulated by functional dependencies and can be investigated via algorithmic methods. Information Systems can be perceived as overarching documents that includes data collections; documents to be processed; and representations of business processes, activities, and services. Whe selecting and working out an appropriate method encoding of artifacts in Information Systems, the complex structure can be represented using hyper-graphs. This representation enables the application of various model-checking, verification, and validation tools that are based on formal approaches. This paper describes the proposed representations in different situations using hyper-graphs, moreover, the formal, algorithmic-based model-checking methods that are coupled with the representations. The model-checking methods are realized by algorithms that are grounded in graph-theoretical approaches and tailored to the specificity of hyper-graphs. Finally, the possible applications in a real-life enterprise environment are outlined. [ABSTRACT FROM AUTHOR]

Copyright of Singidunum Journal of Applied Sciences is the property of Singidunum 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.)

In their seminal paper, Frank and Jordán [1995] show that a large class of optimization problems, including certain directed graph augmentation, fall into the class of covering supermodular functions over pairs of sets. They also give an algorithm for such problems, however, it relies on the ellipsoid method. Prior to our result, combinatorial algorithms existed only for the 0-1 valued problem. Our key result is a combinatorial algorithm for the general problem that includes directed vertex or S-T connectivity augmentation. The algorithm is based on Benczúr's previous algorithm for the 0-1 valued case [Benczúr 2003]. Our algorithm uses a primal-dual scheme for finding covers of partially ordered sets that satisfy natural abstract properties as in Frank and Jordán. For an initial (possibly greedy) cover, the algorithm searches for witnesses for the necessity of each element in the cover. If no two (weighted) witnesses have a common cover, the solution is optimal. As long as this is not the case, the witnesses are gradually exchanged for smaller ones. Each witness change defines an appropriate change in the solution; these changes are finally unwound in a shortest-path manner to obtain a solution of size one less. [ABSTRACT FROM AUTHOR]

The increasing trend of GPS-enabled smartphones has led to the tremendous usage of Location-Based Service applications. In the past few years, a significant amount of studies have been conducted to process All nearest neighbor (ANN) queries. An ANN query on a road network extracts and returns all the closest data objects for all query objects. Most of the existing studies on ANN queries are performed either in Euclidean space or static road networks. Moreover, combining the nearest neighbor query and join operation is an expensive procedure because it requires computing the distance between each pair of query objects and data objects. This study considers the problem of processing the ANN queries on a dynamic road network where the weight, i.e., the traveling distance and time varies due to various traffic conditions. To address this problem, a shared execution-based approach called standard clustered loop (SCL) is proposed that allows efficient processing of ANN queries on a dynamic road network. The key concept behind the shared execution technique is to exploit the coherence property of road networks by clustering objects that share common paths and processing the cluster as a single path. In an empirical study, the SCL method achieves significantly better performance than competitive methods and efficiently reduces the computational cost to process ANN queries in various problem settings. [ABSTRACT FROM AUTHOR]

To tackle the issues of semantic collision and inconsistencies between ontologies and the original data model while learning ontology from relational database (RDB), a semi-automatic semantic consistency checking method based on graph intermediate representation and model checking is presented. Initially, the W-Graph, as an intermediate model between databases and ontologies, was utilized to formalize the semantic correspondences between databases and ontologies, which were then transformed into the Kripke structure and eventually encoded with the SMV program. Meanwhile, description logics (DLs) were employed to formalize the semantic specifications of the learned ontologies, since the OWL DL showed good semantic compatibility and the DLs presented an excellent expressivity. Thereafter, the specifications were converted into a computer tree logic (CTL) formula to improve machine readability. Furthermore, the task of checking semantic consistency could be converted into a global model checking problem that could be solved automatically by the symbolic model checker. Moreover, an example is given to demonstrate the specific process of formalizing and checking the semantic consistency between learned ontologies and RDB, and a verification experiment was conducted to verify the feasibility of the presented method. The results showed that the presented method could correctly check and identify the different kinds of inconsistencies between learned ontologies and its original data model. [ABSTRACT FROM AUTHOR]

Abstract. The minimum number of edges of an undirected graph covering a symmetric, supermodular set-function is determined. As a special case, we derive an extension of a theorem of J. Bang-Jensen and B. Jackson on hypergraph connectivity augmentation. [ABSTRACT FROM AUTHOR]

Abstract. In the edge connectivity augmentation problem one wants to find an edge set of minimum total capacity that increases the edge connectivity of a given undirected graph by r. It is a known non-trivial property of the edge connectivity augmentation problem that there is a sequence of edge sets E[sub 1], E[sub 2] ....,such that Union[sub I less than or equal to tau] E[sub I] optmially increases the connectivity by r, for any integer r. The main result of the paper is that this sequence of edge sets can be divided into O(n) groups such that within one group, all E[sub I] are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs. [ABSTRACT FROM AUTHOR]