Two market network models are investigated. One of them is based on the classical Pearson correlation as the measure of association between stocks returns, whereas the second one is based on the sign similarity measure of association between stocks returns. We study the uncertainty of identification procedures for the following market network characteristics: distribution of weights of edges, vertex degree distribution in the market graph, cliques and independent sets in the market graph, and the vertex degree distribution of the maximum spanning tree. We define the true network characteristics, the losses from the error of its identification by observations, and the uncertainty of identification procedures as the expected value of losses. We use elliptically contoured distribution as a model of multivariate stocks returns distribution. It is shown that identification statistical procedures based on the sign similarity are statistically robust in contrast to the procedures based on the classical Pearson correlation
In this paper, a user modeling task is examined by processing mobile device gallery of photos and videos. We propose a novel engine for preferences prediction based on scene recognition, object detection and facial analysis. At first, all faces in a gallery are clustered, and all private photos and videos with faces from large clusters are processed on the embedded system in offline mode. Other photos may be sent to the remote server to be analyzed by very deep sophisticated neural networks. The visual features of each photo are obtained from scene recognition and object detection models. These features are aggregated into a single descriptor in the neural attention unit. The proposed pipeline is implemented in mobile Android application. Experimental results for the Photo Event Collection, Web Image Dataset for Event Recognition and Amazon Fashion data demonstrate the possibility to efficiently process images without significant accuracy degradation.
In this paper we investigate the relation between the number of k-dominating sets and the number of independent sets in a tree. We call the k-interior of a tree T the forest that contains all the vertices of T of degree at least k. Heuberger and Wagner (2008) characterized for all n,d≥3 the n-vertex trees Td,n with maximum vertex degree d and the maximum number of independent sets. We show that for all n,k≥2, if a tree T has the maximum number of k-dominating sets among all n-vertex trees, then either it contains exactly 2⌊n−2k−1⌋ k-dominating sets or its k-interior is isomorphic to a forest aK1∪Tk,b for some integers a,b≥0. Moreover, we completely describe trees with the minimum possible number of k-dominating sets for every k≥2.
In this study we consider the shortest path problem, where the arc costs are subject to distributional uncertainty. Basically, the decision-maker attempts to minimize her worst-case expected loss over an ambiguity set (or a family) of candidate distributions that are consistent with the decision-maker's initial information. The ambiguity set is formed by all distributions that satisfy prescribed linear first-order moment constraints with respect to subsets of arcs and individual probability constraints with respect to particular arcs. Under some additional assumptions the resulting distributionally robust shortest path problem (DRSPP) admits equivalent robust and mixed-integer programming (MIP) reformulations. The robust reformulation is shown to be NP-hard, whereas the problem without the first-order moment constraints is proved to be polynomially solvable. We perform numerical experiments to illustrate the advantages of the considered approach; we also demonstrate that the MIP reformulation of DRSPP can be solved effectively using off-the-shelf solvers.
In this paper, we consider a class of orientation-preserving Morse–Smale diffeomorphisms defined on an orientable surface. The papers by Bezdenezhnykh and Grines showed that such diffeomorphisms have a finite number of heteroclinic orbits. In addition, the classification problem for such diffeomorphisms is reduced to the problem of distinguishing orientable graphs with substitutions describing the geometry of a heteroclinic intersection. However, such graphs generally do not admit polynomial discriminating algorithms. This article proposes a new approach to the classification of these cascades. For this, each diffeomorphism under consideration is associated with a graph that allows the construction of an effective algorithm for determining whether graphs are isomorphic. We also identified a class of admissible graphs, each isomorphism class of which can be realized by a diffeomorphism of a surface with an orientable heteroclinic. The results obtained are directly related to the realization problem of homotopy classes of homeomorphisms on closed orientable surfaces. In particular, they give an approach to constructing a representative in each homotopy class of homeomorphisms of algebraically finite type according to the Nielsen classification, which is an open problem today.
The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. The latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasichain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable.
The weighted vertex coloring problem for a given weighted graph is to minimize the number of colors so that for each vertex the number of the colors that are assigned to this vertex is equal to its weight and the assigned sets of vertices are disjoint for any adjacent vertices. For all but four hereditary classes that are defined by two connected 5-vertex induced prohibitions, the computational complexity is known of the weighted vertex coloring problem with unit weights. For four of the six pairwise intersections of these four classes, the solvability was proved earlier of the weighted vertex coloring problem in time polynomial in the sum of the vertex weights. Here we justify this fact for the remaining two intersections.
The article is considering the problem of increasing the performance and accuracy of video face identification. We examine the selection of the several best video frames using various techniques for assessing the quality of images. In contrast to traditional methods with estimation of image brightness/contrast, we propose to utilize the deep learning techniques that estimate the frame quality by using the lightweight convolutional neural network. In order to increase the effectiveness of the frame quality assessment step, we propose to distill knowledge of the cumbersome existing FaceQNet model for which there is no publicly available training dataset. The selected K-best frames are used to describe an input set of frames with a single average descriptor suitable for the nearest neighbor classifier. The proposed algorithm is compared with the traditional face feature extraction for each frame, as well as with the known clustering methods for a set of video frames.
The shareholder’s interest oriented from business operation relies on opportunism regulation of the manager under asymmetry. Effective motivation incentives should be exploited to facilitate the manager’s effort devotion enthusiasms. This paper establishes a theoretic model in which the shareholder offers equity-based incentive to a fairness-preferred manager to coordinate their interest conflicts and maximize her expected revenue. The manager exerts unverifiable levels of efforts toward both decision and coordination tasks making the most of his private information about fairness preference. Two interrelated performance measures on different hierarchical levels are considered for contracting purposes. In each situation, we derive the equilibrium effort choices and incentive coefficients of both participants, and investigate how these decisions are affected by fairness preference. Research findings suggest that the incorporation of firm equity dominates pure profit incentive in eliciting high effort levels toward two distinctive managerial tasks. Besides, the equity-based incentive weakens the perceived unfairness and facilitates the participants’ expected revenue. Comparative statics and numerical analysis are conducted to demonstrate our results and the effectiveness of the proposed equity-based incentive. Finally, we summarize the contributions of this paper and put forward directions for further study.
A novel image recognition algorithm based on sequential three-way decisions is introduced to speed up the inference in a convolutional neural network. In contrast to the majority of existing studies, our approach does not require a special procedure to train a neural network, and thus it can be used with arbitrary architectures including pre-trained convolutional nets. Each image is associated with a sequence of features extracted at different layers of the neural network. Features from earlier layers stand for coarse-grained image representation. Fine-grained representations include embeddings from one of later layers. Confidence scores of classifiers representing the input image at each granularity level are computed in order to populate a set of unlikely classes with low confidence scores. The thresholds for these scores are chosen by using the step-up multiple testing procedure. The categories from this set are not considered at the next levels with finer granularity. The algorithm selecting the granularity levels and thresholds for each level is trained on a small sample. An experimental study for several datasets and neural architectures demonstrated that the proposed approach reduces the running time by up to 40% with a controllable decrease in accuracy.
This paper is focused on the finetuning of acoustic models for speaker adaptation goals on a given gender. We pretrained the Transformer baseline model on Librispeech-960 and conducted experiments with finetuning on the gender-specific test subsets. The obtained word error rate (WER) relatively to the baseline is up to 5% and 3% lower on male and female subsets, respectively, if the layers in the encoder and decoder are not frozen, and the tuning is started from the last checkpoints. Moreover, we adapted our base model on the complete L2 Arctic dataset of accented speech and finetuned it for particular speakers and male and female genders separately. The models trained on the gender subsets obtained 1-2% lower WER when compared to the model tuned on the whole L2 Arctic dataset. Finally, it was experimentally confirmed that the concatenation of the pretrained voice embeddings (x-vector) and embeddings from a conventional encoder cannot significantly improve the speech recognition accuracy.
Purpose: Systems biology and network modeling represent, nowadays, the hallmark approaches for the development of predictive and targeted-treatment based precision medicine. The study of health and disease as properties of the human body system allows the understanding of the genotype-phenotype relationship through the definition of molecular interactions and dependencies. In this scenario, metabolism plays a central role as its interactions are well characterized and it is considered an important indicator of the genotype-phenotype associations. In metabolic systems biology, the genome-scale metabolic models are the primary scaffolds to integrate multi-omics data as well as cell-, tissue-, condition-specific information. Modeling the metabolism has both investigative and predictive values. Several methods have been proposed to model systems, which involve steady-state or kinetic approaches, and to extract knowledge through machine and deep learning.
Method: This review collects, analyzes, and compares the suitable data and computational approaches for the exploration of metabolic networks as tools for the development of precision medicine. To this extent, we organized it into three main sections: "Data and Databases", "Methods and Tools", and "Metabolic Networks for medicine". In the first one, we have collected the most used data and relative databases to build and annotate metabolic models. In the second section, we have reported the state-of-the-art methods and relative tools to reconstruct, simulate, and interpret metabolic systems. Finally, we have reported the most recent and innovative studies which exploited metabolic networks for the study of several pathological conditions, not only those directly related to the metabolism.
Conclusion: We think that this review can be a guide to researchers of different disciplines, from computer science to biology and medicine, in exploring the power, challenges and future promises of the metabolism as predictor and target of the so-called P4 medicine (predictive, preventive, personalized and participatory).
This book constitutes the proceedings of the 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021, held in Irkutsk, Russia, in July 2021.
The 29 full papers and 1 short paper presented in this volume were carefully reviewed and selected from 102 submissions. Additionally, 2 full invited papers are presented in the volume. The papers are grouped in the following topical sections: combinatorial optimization; mathematical programming; bilevel optimization; scheduling problems; game theory and optimal control; operational research and mathematical economics; data analysis.
We consider the maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance (denoted by (MSPITH)), which has wide applications in transportation network, networkwar and terrorist network. The problem (MSPITH) aims to maximize the length of the shortest path from the root of a tree to all its leaves by upgrading edge weights such that the upgrade cost under sum-Hamming distance is upper-bounded by a given value. We show that the problem (MSPITH) under weighted sum-Hamming distance is NP-hard. We consider two cases of the problem (MSPITH) under unit sum-Hamming distance based on the number K of critical edges. We propose a greedy algorithm within O(n + l log l) time when K = 1 and a dynamic programming algorithm within O(n(log n + K3)) time when K > 1, where n and l are the numbers of nodes and leaves in a tree, respectively. Furthermore, we consider a minimum cost shortest path interdiction problem by upgrading edges on trees under unit Hamming distance, denoted by (MCSPITUH) and propose a binary search algorithm within O(n4 log n) time, where a dynamic programming algorithm is executed in each iteration to solve its corresponding problem (MSPITH). Finally, we design numerical experiments to show the effectiveness of the algorithms.
Network interdiction problems by deleting critical edges have wide applicatio ns. However, in some practical applications, the goal of deleting edges is difficult to achieve. We consider the maximum shortest path interdiction problem by upgrading edges on trees (MSPIT) under unit/weighted l1l1 norm. We aim to maximize the the length of the shortest path from the root to all the leaves by increasing the weights of some edges such that the upgrade cost under unit/weighted l1l1 norm is upper-bounded by a given value. We construct their mathematical models and prove some properties. We propose a revised algorithm for the problem (MSPIT) under unit l1l1 norm with time complexity O(n), where n is the number of vertices in the tree. We put forward a primal dual algorithm in O(n2)O(n2) time to solve the problem (MSPIT) under weighted l1l1 norm, in which a minimum cost cut is found in each iteration. We also solve the problem to minimize the cost to upgrade edges such that the length of the shortest path is lower bounded by a value and present an O(n2)O(n2) algorithm. Finally, we perform some numerical experiments to compare the results obtained by these algorithms.
The present paper discusses the problem of distortions in speech signals transmitted over a communication channel to a biometric system during voice-based remote identification. A possible rectification approach involves a preliminary correction of the frequency spectrum of the received signal based on the pre-distortion principle. Taking into account a priori uncertainty, a new information indicator of speech signal distortions is proposed, along with a method for its measurement under conditions of small observation samples. An example of fast practical implementation of the method based on a parametric spectral analysis algorithm is considered. Results of an experimental test of the proposed approach are provided for three different communication channel instantiations. It is shown that the proposed method facilitates the transformation of an initially distorted speech signal into compliance with a registered voice template using an acceptable algorithmic information discrimination criterion. The described approach may be used in existing biometric systems and speaker identification technologies.
The ever-increasing importance of structured data in different applications, especially in the biomedical field, has driven the need for reducing its complexity through projections into a more manageable space. The latest methods for learning features on graphs focus mainly on the neighborhood of nodes and edges. Methods capable of providing a representation that looks beyond the single node neighborhood are kernel graphs. However, they produce handcrafted features unaccustomed with a generalized model. To reduce this gap, in this work we propose a neural embedding framework, based on probability distribution representations of graphs, named Netpro2vec. The goal is to look at basic node descriptions other than the degree, such as those induced by the Transition Matrix and Node Distance Distribution. Netpro2vec provides embeddings completely independent from the task and nature of the data. The framework is evaluated on synthetic and various real biomedical network datasets through a comprehensive experimental classification phase and is compared to well-known competitors.
The vertex 3-colourability problem is to verify whether it is possible to split the vertex set of a given graph into three subsets of pairwise nonadjacent vertices or not. This problem is known to be NP-complete for planar graphs of the maximum face length at most 4 (and, even, additionally, of the maximum vertex degree at most 5), and it can be solved in linear time for planar triangulations. Additionally, the vertex 3-colourability problem is NP-complete for planar graphs of the maximum vertex degree at most 4, but it can be solved in constant time for graphs of the maximum vertex degree at most 3. It would be interesting to investigate classes of planar graphs with simultaneously bounded length of faces and the maximum vertex degree and to find the threshold, for which the complexity of the vertex 3-colourability problem is changed from polynomial-time solvability to NP-completeness. In this paper, we prove NP-completeness of the vertex 3-colourability problem for planar graphs of the maximum vertex degree at most 4, whose faces are of length no more than 5.
It is a well known fact that any smooth manifold admits a Morse function, whereas the problem of existence of a Morse function for a topological manifold stated by Marston Morse in 1959 is still open. In the present paper we prove that a topological manifold admits a continuous Morse function if it admits a topological flow with a finite hyperbolic chain recurrent set. We construct this function as a Lyapunov function whose set of the critical points coincides with the chain recurrent set of the flow.