Search

Benefit from avoiding the utilization of labeled samples, which are usually insufficient in the real world, unsupervised learning has been regarded as a speedy and powerful strategy on clustering tasks. However, clustering directly from primal data sets leads to high computational cost, which limits its application on large-scale and high-dimensional problems. Recently, anchor-based theories are proposed to partly mitigate this problem and field naturally sparse affinity matrix, while it is still a challenge to get excellent performance along with high efficiency. To dispose of this issue, we first presented a fast semisupervised framework (FSSF) combined with a balanced $K$ -means-based hierarchical $K$ -means (BKHK) method and the bipartite graph theory. Thereafter, we proposed a fast self-supervised clustering method involved in this crucial semisupervised framework, in which all labels are inferred from a constructed bipartite graph with exactly $k$ connected components. The proposed method remarkably accelerates the general semisupervised learning through the anchor and consists of four significant parts: 1) obtaining the anchor set as interim through BKHK algorithm; 2) constructing the bipartite graph; 3) solving the self-supervised problem to construct a typical probability model with FSSF; and 4) selecting the most representative points regarding anchors from BKHK as an interim and conducting label propagation. The experimental results on toy examples and benchmark data sets have demonstrated that the proposed method outperforms other approaches. [ABSTRACT FROM AUTHOR]

This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared. [ABSTRACT FROM AUTHOR]

Biochemical mechanisms with mass action kinetics are often modeled by systems of polynomial differential equations (DE). Determining directly if the DE system has multiple equilibria (multistationarity) is difficult for realistic systems, since they are large, nonlinear and contain many unknown parameters. Mass action biochemical mechanisms can be represented by a directed bipartite graph with species and reaction nodes. Graph-theoretic methods can then be used to assess the potential of a given biochemical mechanism for multistationarity by identifying structures in the bipartite graph referred to as critical fragments. In this article we present a graph-theoretic method for conservative biochemical mechanisms characterized by bounded species concentrations, which makes the use of degree theory arguments possible. We illustrate the results with an example of a mitogen-activated protein kinases (MAPK) network. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we consider certain generalizations of the well-known Fibonacci and Lucas numbers, the generalized Fibonacci and Lucas p-numbers. We give relationships between the generalized Fibonacci p-numbers, F p (n), and their sums, , and the 1-factors of a class of bipartite graphs. Further we determine certain matrices whose permanents generate the Lucas p-numbers and their sums. [Copyright &y& Elsevier]

Presents information on graphs and crossing numbers. Definition of a graph and a complete graph; Crossing number of a planar graph; Discussion of the toroidal crossing numbers for complete bipartite graphs.

This paper studies the bipartite synchronization in a network of nonlinear systems with collaborative and antagonistic interactions. Under the assumption that the signed graph is structurally balanced and the considered domain does not contain the origin, we use contraction theory to obtain some sufficient conditions such that the network admits a bipartite synchronization solution. These conditions are described by coupling matrices and the contractivity of lower-dimensional dynamic systems. In particular, if the nonlinear system satisfies a one-sided Lipschitz condition and the coupling matrices are identical, we also obtain some sufficient conditions about the second smallest eigenvalue of signed graph for the bipartite synchronization. Some numerical examples are presented to illustrate the effectiveness of the obtained results. [ABSTRACT FROM AUTHOR]

We present a linear-time subspace clustering approach that combines sparse representations and bipartite graph modeling. The signals are modeled as drawn from a union of low-dimensional subspaces, and each signal is represented by a sparse combination of basis elements, termed atoms, which form the columns of a dictionary matrix. The sparse representation coefficients are arranged in a sparse affinity matrix, which defines a bipartite graph of two disjoint sets: 1) atoms and 2) signals. Subspace clustering is obtained by applying low-complexity spectral bipartite graph clustering that exploits the small number of atoms for complexity reduction. The complexity of the proposed approach is linear in the number of signals, thus it can rapidly cluster very large data collections. Performance evaluation of face clustering and temporal video segmentation demonstrates comparable clustering accuracies to state-of-the-art at a significantly lower computational load. [ABSTRACT FROM PUBLISHER]

In this article, the bipartite consensus of first-order multiagent systems with a connected structurally balanced signed graph is studied. To reduce the communications among agents, a distributed event-triggered control law is proposed, where the event-triggering condition of each agent only uses its own state and the sampled states of its neighbours, and no knowledge of the global network topology is required. By relating to the nonexistence of some finite-time convergence, a novel analysis is given to show that there is no Zeno behavior in the proposed event-triggered multiagent system. Then, from the Lyapunov stability theory and the algebraic graph theory, it is proved that all agents can reach agreement with an identical magnitude but opposite signs. Finally, a numerical example is given to illustrate the efficiency and feasibility of the proposed results. [ABSTRACT FROM AUTHOR]

Highlights: [•] Bipartite flocking model for multi-agent systems using signed graph theory. [•] Bipartite flocking control with and without a virtual leader. [•] Both fixed and switching velocity topologies are considered. [Copyright &y& Elsevier]

We calculate and investigate the relativistic correlation function for bipartite systems of spin-1/2 particles in vector states and spin-1 particles in tensor states. We show that the relativistic correlation function, which depends on particle momenta, may have local extrema. Furthermore, the momentum dependence of the correlation functions for two choices of the relativistic spin operator may be significantly different. [ABSTRACT FROM AUTHOR]

We study the concurrence of arbitrary dimensional bipartite quantum systems. An explicit analytical lower bound of concurrence is obtained which detects entanglement for some quantum states better than some well-known separability criteria and improves the lower bounds, such as from the positive partial transposition, realignment criteria, and Breuer's entanglement witness. [ABSTRACT FROM AUTHOR]

Abstract: Many multi-class classification algorithms in statistics and machine learning typically combine several binary classifiers in order to construct an overall classifier. In the popular pairwise ensemble, one classifier is built for each pair of classes, resulting in pairwise bipartite rankings. In contrast, ordinal regression algorithms consider a single ranking function for several ordered classes. It is known in the literature that pairwise ensembles can be useful for ordinal regression. However, can single ranking models make a contribution to multi-class classification? The answer to this question should be affirmative, as supported by theoretical results presented in this article. We conduct a formal analysis of the consistency of pairwise bipartite rankings by uncovering the conditions under which they can be equivalently expressed in terms of a single ranking. Similar to the utility representability of pairwise preference relations, it turns out that transitivity plays a crucial role in the characterization of the ranking representability of pairwise bipartite rankings. To this end, we introduce the new concepts of strict ranking representability, a restrictive condition that can be verified easily, and AUC ranking representability, a practically more useful condition that is more difficult to verify. However, the link between pairwise bipartite rankings and dice games allows us to formulate necessary transitivity conditions for AUC ranking representability. A sufficient condition on the other hand is obtained by introducing a new type of transitivity that can be verified by solving an integer quadratic program. [ABSTRACT FROM AUTHOR]

Abstract: In this work we present a dynamical model that successfully describes the organization of mutualistic ecological systems. The main characteristic of these systems is the nested structure of the bipartite adjacency matrix describing their interactions. We introduce a nestedness coefficient, as an alternative to the Atmar and Patterson temperature, commonly used to measure the nestedness degree of the network. This coefficient has the advantage of being based on the robustness of the ecological system and it is not only describing the ordering of the bipartite matrix but it is also able to tell the difference, if any, between the degree of organization of each guild. [Copyright &y& Elsevier]

Abstract: The hypercube is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. Let f denote the number of faulty vertices in an n-cube. This study demonstrates that when f ⩽ n −2, the n-cube contains a fault-free path with length at least 2 n −2f −1 (or 2 n −2f −2) between two arbitrary vertices of odd (or even) distance. Since an n-cube is a bipartite graph with two partite sets of equal size, the path is longest in the worst-case. Furthermore, since the connectivity of an n-cube is n, the n-cube cannot tolerate n −1 faulty vertices. Hence, our result is optimal. [Copyright &y& Elsevier]

The article describes a mathematical solution to a combinatorial optimization problem that arises in higher education. Topics discussed include how the classic Assignment Problem for bipartite graphs can be used in combinatorial optimization problem, how Integer Linear Programming leads to more flexibility, and how Integer Linear Programming allows the optimization to be fine-tuned to handle more challenging data sets.

Community detection in complex networks is a topic of high interest in many scientific fields. A bipartite network is a special type of complex network whose nodes are decomposed into two disjoint sets such that no two nodes within the same set are adjacent. Many relationships in real-world systems can be represented by a bipartite network, such as predator-prey relationships, plant-pollinator interactions, and drug-target interactions. While community detection in unipartite networks has been extensively studied in the past decade, identification of modules or communities in bipartite networks is still in its early stage. Several quantitative functions have been developed for evaluating the quality of bipartite network divisions, however, these functions were designed based on null model comparisons and thus are subject to certain resolution limits. In this paper, we propose a new quantitative function called bipartite partition density for community detection in bipartite networks, and use some network examples to demonstrate that this quantitative function is superior to the widely used Barber’s bipartite modularity and other functions. Based on the bipartite partition density, the bipartite network community detection problem is formulated into an integer nonlinear programming model in which a bipartite network can be partitioned into reasonable overlapping communities by maximizing the quantitative function. We further develop a heuristic adapted label propagation algorithm (BiLPA) to optimize the bipartite partition density in large-scale bipartite networks. BiLPA is efficient and does not require any prior knowledge about the number of communities in the networks. We conduct extensive experiments on simulated and real-world networks and demonstrate that BiLPA can successfully identify the community structures of bipartite networks. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies the testing bipartiteness of simple undirected graphs based on generalized rough sets. A new binary relation induced from a simple undirected graph is first defined. The concept of quasi-outer definable sets is then introduced, and some of its important properties are investigated. Finally, based on the quasi-outer definable set, a new algorithm is designed for testing bipartiteness of a simple undirected graph. Experiments show that the proposed algorithm is more efficient than the traditional one when the graph is represented by an adjacency matrix. [Copyright &y& Elsevier]

Entanglement of formation for arbitrary mixed states in a (2 ⊗ 2)-dimensional Hubert space is well known. For higher-dimensional mixed states analytical expressions for quantifying entanglement exist for a particular family of states. In this work, we calculate analytically the entanglement of formation for a family of bipartite (2 ⊗ d)-dimensional mixed states which can be obtained from tripartite 2 ⊗ 2 ⊗ d pure states following the entanglement relations obtained by Koashi and Winter [Phys. Rev. A 69, 022309 (2004)]. [ABSTRACT FROM AUTHOR]

Abstract: A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1⩽ w ⩽ k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ n is f-edge fault-tolerant spanning laceable if n(⩾3) is odd and f ⩽ n −1, and f-edge fault-tolerant spanning connected if n (⩾2) is even and f ⩽ n −2. [Copyright &y& Elsevier]

Abstract This paper investigates the issue of finite/fixed-time bipartite consensus (FFTBC) of multi-agent systems with signed graphs. A new unified framework of finite-time and fixed-time bipartite consensus is built via some discontinuous control protocols based on the theory of differential inclusion and set-valued Lie derivative. Under the structurally balanced or unbalanced signed graphs, the goal of FFTBC is reached by a common discontinuous controller with different control gains, which fills the gap in studying FFTBC issues with discontinuous protocols. Some numerical examples with comparisons are given to demonstrate the effectiveness of our designs. [ABSTRACT FROM AUTHOR]

The n -dimensional hypercube Q n is a graph with 2 n vertices, each labeled with a distinct binary string of length n . The vertices are connected by an edge if and only if their labels differ in one bit. The hypercube is bipartite, the set of nodes is the union of two sets: nodes of parity 0 (the number of ones in their labels is even) and nodes of parity 1 (the number of ones is odd). We consider Hamiltonian paths in hypercubes with faulty edges and prove the following: (1) If Q n has one vertex u of degree 1, then u can be connected by a Hamiltonian path with every vertex v that is of a parity different than u and that is not connected with u by a healthy edge. (2) If Q n with n ≥ 4 has two vertices u and v of degree 1, then they can be connected by a Hamiltonian path if the distance between u and v is odd and greater than 1 or if u and v are connected by the faulty edge. (3) If Q n contains a cycle ( u, v, w, x ) in which all edges going away from the cycle from u and w are faulty, then u or w can be connected by a Hamiltonian path with any vertex outside the cycle that is of different parity than u and w . Moreover, in all three cases, the thesis remains true even if Q n has n − 3 additional faulty edges. Furthermore, in all three cases, no other Hamiltonian paths are possible. [ABSTRACT FROM AUTHOR]

Abstract A crucial task in the process of constructing Internet testbeds is to substantially reduce the number of nodes in the interdomain Internet topology, while maintaining its essential properties. In this paper, we first decompose the Internet topology into seven bipartite graphs, a matching graph and a core graph using two normalized Laplacian spectral features, namely, the weighted spectral distribution and the multiplicity of the eigenvalue 1. Then, we accomplish a marked reduction in size of the topology by sampling and merging these graphs. The proposed approach was tested on realistic Internet graphs that were explored from 2000 to 2016 and a large-scale simulated graph. The experimental results confirm that our approach can effectively reduce the number of nodes in these graphs by more than 96%, while maintaining their essential properties. [ABSTRACT FROM AUTHOR]

The area of mathematical psychology concerning knowledge spaces is complemented by the theoretical notion of a "curriculum space," which is developed as a mathematical model for curriculum design in order to illuminate the interplay between learners and the curricula in which they enroll. The analysis is carried out in terms of concepts from graph theory and order theory, yielding a precise language in which to communicate aspects of curricular influences on student-achievement. Emphasis is placed on the structure of tasks that are addressed in a curriculum, the structure of prerequisite-course assignments within the curriculum, and the compatibility between these structures. Among the main results, conditions are given under which the tasks in a curriculum induce a partially ordered set, curricula that admit "compatible" prerequisite-structures are completely characterized, and a greedy algorithm is presented for categorizing courses into "curriculum maps" that respect the compatibility condition. • Knowledge space theory is complemented by the notion of a curriculum space. • Bipartite graphs model learners and tasks in a curriculum. • Greedy algorithm for compatible curriculum maps. • Prerequisite structure given by a partially ordered set of tasks in a curriculum. • Students who remain underprepared after completing prerequisite courses. [ABSTRACT FROM AUTHOR]

Reversible one-dimensional cellular automata are studied from the perspective of Welch Sets. This paper presents an algorithm to generate random Welch sets that define a reversible cellular automaton. Then, properties of Welch sets are used in order to establish two bipartite graphs describing the evolution rule of reversible cellular automata. The first graph gives an alternative representation for the dynamics of these systems as block mappings and shifts. The second graph offers a compact representation for the evolution rule of reversible cellular automata. Both graphs and their matrix representations are illustrated by the generation of random reversible cellular automata with 6 and 18 states. [ABSTRACT FROM AUTHOR]

Vertex Bisection Minimization problem (VBMP) consists of partitioning a vertex set into two sets B and B′ where | B | = | V | / 2 such that vertex width, VW , is minimized which is defined as the number of vertices in B which are adjacent to at least one vertex in B′ . It is an NP-complete problem in general. VBMP has applications in fault tolerance and is related to the complexity of sending messages to processors in interconnection networks via vertex disjoint paths. In this paper, a memetic algorithm has been designed for this problem (MAVBMP) in which four construction heuristics have been proposed to generate the initial population. These heuristics are analyzed statistically and accordingly used in proportion to generate the initial population for MAVBMP. A new crossover type search operator has been proposed for recombination and a local improvement operator has also been developed. Extensive experiments have been conducted on several classes of graphs such as complete bipartite graphs, 2-dimensional ordinary meshes, 2-dimensional toroidal meshes, 3-dimensional toroidal meshes, complete split graph, join of hypercubes and Harwell-boeing graphs which are a subset of public domain Matrix Market library. Trends observed in the experimental results for some of the classes of graphs have led to conjectures for vertex width. [ABSTRACT FROM AUTHOR]

This paper is concerned with the secure bipartite consensus of second-order multi-agent systems under denial-of-service (DoS) attacks. The communication network is an antagonistic network, in which there is cooperative or competitive relationship between neighboring agents. Meanwhile, information cannot be transmitted when the system is attacked. A novel event-triggered control algorithm based on sampled data is proposed to save limited resources and exclude the Zeno behavior. By applying the convergence of monotone sequences, graph theory as well as the discrete-time Lyapunov function method, some sufficient conditions on threshold parameters, frequency and duration of DoS attacks, and sampling period are derived to ensure the bipartite consensus under DoS attacks. Finally, the correctness and advantages of theoretical results are demonstrated by a numerical simulation. [ABSTRACT FROM AUTHOR]

The study and analysis of social graphs impacts on a wide range of applications, such as community decision making support and recommender systems. With the boom of online social networks, such analyses are benefiting from a massive collection and publication of social graphs at large scale. Unfortunately, individuals’ privacy right might be inadvertently violated when publishing this type of data. In this article, we introduce ( k , ℓ)-anonymity; a novel privacy measure aimed at evaluating the resistance of social graphs to active attacks. ( k , ℓ)-anonymity is based on a new problem in Graph Theory, the k-metric antidimension defined as follows. Let G = ( V , E ) be a simple connected graph and S = { w 1 , … , w t } ⊆ V an ordered subset of vertices. The metric representation of a vertex u ∈ V with respect to S is the t -vector r ( u | S ) = ( d G ( u , w 1 ) , … , d G ( u , w t ) ) , where d G ( u, v ) represents the length of a shortest u − v path in G . We call S a k -antiresolving set if k is the largest positive integer such that for every vertex v ∈ V − S there exist other k − 1 different vertices v 1 , … , v k − 1 ∈ V − S with r ( v | S ) = r ( v 1 | S ) = ⋯ = r ( v k − 1 | S ) . The k -metric antidimension of G is the minimum cardinality among all the k -antiresolving sets for G . We address the k -metric antidimension problem by proposing a true-biased algorithm with success rate above 80% when considering random graphs of size at most 100. The proposed algorithm is used to determine the privacy guarantees offered by two real-life social graphs with respect to ( k , ℓ)-anonymity. We also investigate theoretical properties of the k -metric antidimension of graphs. In particular, we focus on paths, cycles, complete bipartite graphs and trees. [ABSTRACT FROM AUTHOR]

We present several efficient implementations of the simulated annealing algorithm for Ising spin glasses on sparse graphs. In particular, we provide a generic code for any choice of couplings, an optimised code for bipartite graphs, and highly optimised implementations using multi-spin coding for graphs with small maximum degree and discrete couplings with a finite range. The latter codes achieve up to 50 spin flips per nanosecond on modern Intel CPUs. We also compare the performance of the codes to that of the special purpose D-Wave devices built for solving such Ising spin glass problems. Program summary Program title: SimAn v1.0 Catalogue identifier: AEVZ_v1_0 Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AEVZ_v1_0.html Program obtainable from: CPC Program Library, Queen’s University, Belfast, N. Ireland Licensing provisions: GNU General Public License, version 3 No. of lines in distributed program, including test data, etc.: 14999 No. of bytes in distributed program, including test data, etc.: 26594 Distribution format: tar.gz Programming language: C++, OpenMP for parallelization. Computer: Any PC. Operating system: Linux/OS X/UNIX. Has the code been vectorised or parallelized?: Parallelized using OpenMP. RAM: Variable, from a few megabytes. Classification: 4.13, 6.5, 23. Nature of problem: Ising spin glass ground states on sparse graphs. Solution method: Simulated annealing. Running time: From milliseconds to seconds. [ABSTRACT FROM AUTHOR]

Spectral clustering, one of the most popular clustering methods, has attracted considerable attention in many fields owing to its excellent empirical properties. However, previously developed solutions to spectral clustering problems consist of two successive steps: (1) performing spectral embedding and eigendecomposition to obtain relaxed partition matrix; (2) performing k -means or spectral rotation to obtain the final binary indicator matrix. However, these two steps may miss a co-optimal solution, leading to unreasonable results. Furthermore, the implementation of eigendecomposition is significantly time-consuming and requires a computational complexity of 0 (n 3). To address these issues, in this study, we propose a new framework for jointly performing spectral embedding and improving spectral rotation using an anchor-based acceleration strategy. In addition, we replace the spectral rotation term with a more mathematically rigorous form. To effectively solve the proposed model, we iteratively use the generalized power iteration method and the improved version of the coordinate descent method to solve our unified framework directly. Extensive experimental results on real benchmark datasets validate the effectiveness of the proposed algorithm compared with other state-of-the-art spectral-based methods. The proposed algorithm achieves the best performance on six-eighths of small-scale datasets, five-sixths of large-scale datasets, and three-fourths of high-dimensional datasets, while maintaining superior implementation efficiency. [ABSTRACT FROM AUTHOR]

This article presents a new optimization-based approach to determine the class of stabilizing control structures with the necessary set of feedback links for interconnected systems. The proposed approach relies on a graph-theoretic interpretation and its equivalence in terms of binary linear programs (BLPs). To carry out the primary goal, first, the stabilizability of a linear time-invariant (LTI) system under the decentralized control structure is presented in terms of a BLP. Next, two graph-based criteria are proposed to characterize stabilizing control structures with the required feedback links. Finally, all possible stabilizing control structures with the necessary feedback links are derived via solving a set of BLPs. In addition to the analysis of stabilizing control structures, the proposed graph-theoretic approach offers a versatile set of tools to find the simplest control structures capable of assigning the closed-loop spectrum in a totally arbitrary desired region. Simulation results illustrate the assessment of stabilizing control structures, the required additional feedback links, and the elegant generalization of the proposed approach to regional pole-placement. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we introduce the concept of the k-path-(bi)panconnectivity of (bipartite) graphs. It is a generalization of the (bi)panconnectivity and of the paired many-to-many k-disjoint path cover. The 2-path-bipanconnectivity with only one exception of the n-cube Q n (n ⩾4) is proved. Precisely, the following result is obtained: In an n-cube with n ⩾4 given any four vertices u 1, v 1, u 2, v 2 such that two of them are in one partite set and the another two are in the another partite set. Let s = t =5 if C = u 1 u 2 v 1 v 2 is a cycle of length 4, and s = d(u 1, v 1)+1 and t = d(u 2, v 2)+1 otherwise, where d(u, v) denotes the distance between two vertices u and v. And let i and j be any two integers such that both i − s ⩾0 and j − t ⩾0 are even with i + j ⩽2 n . Then there exist two vertex-disjoint (u 1, v 1)-path P and (u 2, v 2)-path R with ∣V(P)∣= i and ∣V(R)∣= j. As consequences, many properties of hypercubes, such as bipanconnectivity, bipanpositionable bipanconnectivity [18], bipancycle-connectivity [12], two internally disjoint paths with two given lengths, and the 2-disjoint path cover with a path of a given length [21], follow from our result. [Copyright &y& Elsevier]

Abstract: The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the standard assignment problem, any node in one partition can be matched with any node in the other partition without any restriction. In this paper, variations of the standard assignment problem are defined with matching constraints by introducing structures in the partitions of the bipartite graph, and by defining constraints on these structures. According to the first constraint, the matching between the two partitions should respect the hierarchical-ordering constraints defined by forest and level graph structures produced by using the nodes of the two partitions respectively. In order to define the second constraint, the nodes of the partitions of the bipartite graph are distributed into mutually exclusive sets. The set-restriction constraint enforces the rule that in one of the partitions all the elements of each set should be matched with the elements of a set in the other partition. Even with one of these constraints the assignment problem becomes an NP-hard problem. Therefore, the extended assignment problem with both the hierarchical-ordering and set-restriction constraints becomes an NP-hard multi-objective optimization problem with three conflicting objectives; namely, minimizing the numbers of hierarchical-ordering and set-restriction violations, and maximizing the summation of the weights of the edges of the matching. Genetic algorithms are proven to be very successful for NP-hard multi-objective optimization problems. In this paper, we also propose genetic algorithm solutions for different versions of the assignment problem with multiple objectives based on hierarchical and set constraints, and we empirically show the performance of these solutions. [Copyright &y& Elsevier]

Abstract: Let G(V, E) be a connected undirected graph with n vertices and m edges, where each vertex v is associated with a cost C(v) and each edge e =(u, v) is associated with two weights, W(u → v) and W(v → u). The issue of assigning an orientation to each edge so that G becomes a directed graph is resolved in this paper. Determining a scheme to assign orientations of all edges such that is minimized is the objective. This issue is called the edge-orientation problem (the EOP). Two variants of the EOP, the Out-Degree-EOP and the Vertex-Weighted EOP, are first proposed and then efficient algorithms for solving them on general graphs are designed. Ascertaining that the EOP is NP-hard on bipartite graphs and chordal graphs is the second result. Finally, an O(n log n)-time algorithm for the EOP on trees is designed. In general, the algorithmic results in this paper facilitate the implementation of the weighted fair queuing (WFQ) on real networks. The objective of the WFQ is to assign an effective weight for each flow to enhance link utilization. Our findings consequently can be easily extended to other classes of graphs, such as cactus graphs, block graphs, and interval graphs. [Copyright &y& Elsevier]

We present an approach to improving the precision of an initial document ranking wherein we utilize cluster information within a graph-based framework. The main idea is to perform re-ranking based on centrality within bipartite graphs of documents (on one side) and clusters (on the other side), oil the premise that these are mutually reinforcing entities. Links between entities are created via consideration of language models induced from them. We find that our cluster-document graphs give rise to much better retrieval performance than previously proposed document-only graphs do. For example, authority-based re-ranking of documents via a HITS-style cluster-based approach outperforms a previously-proposed PageRank-inspired algorithm applied to solely-document graphs. Moreover, we also show that computing authority scores for clusters constitutes an effective method for identifying clusters containing a large percentage of relevant documents [ABSTRACT FROM AUTHOR]

This work deals with the analysis and protocol design problems of finite-time consensus for multi-agent systems on signed and directed networks. A new distributed protocol with two reciprocal fractional power feedbacks of local consensus error has been proposed to remove the influence of initial states on the consensus time. By introducing a well-structured Lyapunov function, the technical difficulty arising from the asymmetrical Laplacian matrices of directed graphs is circumvented. Furthermore, it is shown that the feasibility of this proposed protocol can be extended to directed graphs with a spanning tree by mathematical induction method. The upper bounds of the finite-time periods are given under the circumstances of directed networks with a spanning tree apart from the strongly-connected ones. This new protocol is then extended to the application of finite-time bipartite formation control of multi-agent systems. Simulations and experiments of bipartite formation of multiple nano-quadcopters are implemented to prove the validity and practicability of this new protocol. In the experiment, a novel fuzzy logic is also introduced to realize the group collision avoidance of all nano-quadcopters. [ABSTRACT FROM AUTHOR]

This article aims to analyze the leader-following consensus for multi-agent systems (MASs) in the presence of cooperative and competitive interactions. The primary aim of this article is to design a hybrid-triggered control protocol that ensures the bipartite leader-following consensus of MASs under controller gain variations. By using a Bernoulli random variable, time-triggered and event-triggered controllers are combined to form a hybrid-triggered controller. A structurally balanced graph is deployed to illustrate the cooperative and competitive interaction between neighboring agents. By employing Lyapunov stability theory and utilizing the properties of algebraic graph theory, the sufficient requirements for assuring the bipartite leader-following consensus will be established by means of linear matrix inequalities (LMIs). The derived conditions assure the bipartite consensus of the multi-agent system with same magnitude and opposite sign. Furthermore, the controller gain value can be computed by solving the LMIs. Numerical examples will be delivered to verify the viability of the derived theoretical results. • The bipartite consensus for MASs with gain variations is addressed in this paper. • A structurally balanced graph is employed to show the communication among agents. • A hybrid-triggered control is developed by event- and time-triggered schemes. • Sufficient conditions for bipartite consensus are derived using the Lyapunov method. [ABSTRACT FROM AUTHOR]

We study how quantum walks can be used to find structural anomalies in graphs via several examples. Two of our examples are based on star graphs, graphs with a single central vertex to which the other vertices, which we call external vertices, are connected by edges. In the basic star graph, these are the only edges. If we now connect a subset of the external vertices to form a complete subgraph, a quantum walk can be used to find these vertices with a quantum speedup. Thus, under some circumstances, a quantum walk can be used to locate where the connectivity of a network changes. We also look at the case of two stars connected at one of their external vertices. A quantum walk can find the vertex shared by both graphs, again with a quantum speedup. This provides an example of using a quantum walk in order to find where two networks are connected. Finally, we use a quantum walk on a complete bipartite graph to find an extra edge that destroys the bipartite nature of the graph. [ABSTRACT FROM AUTHOR]

Abstract: Searching and mining biomedical literature databases are common ways of generating scientific hypotheses by biomedical researchers. Clustering can assist researchers to form hypotheses by seeking valuable information from grouped documents effectively. Although a large number of clustering algorithms are available, this paper attempts to answer the question as to which algorithm is best suited to accurately cluster biomedical documents. Non-negative matrix factorization (NMF) has been widely applied to clustering general text documents. However, the clustering results are sensitive to the initial values of the parameters of NMF. In order to overcome this drawback, we present the ensemble NMF for clustering biomedical documents in this paper. The performance of ensemble NMF was evaluated on numerous datasets generated from the TREC Genomics track dataset. With respect to most datasets, the experimental results have demonstrated that the ensemble NMF significantly outperforms classical clustering algorithms of bisecting K-means, and hierarchical clustering. We compared four different methods for constructing an ensemble NMF. For clustering biomedical documents, this research is the first to compare ensemble NMF with typical classical clustering algorithms, and validates ensemble NMF constructed from different graph-based ensemble algorithms. This is also the first work on ensemble NMF with Hybrid Bipartite Graph Formulation for clustering biomedical documents. [Copyright &y& Elsevier]

Abstract: Stocks with similar financial ratio values across years have similar price movements. We investigate this hypothesis by clustering groups of stocks that exhibit homogeneous financial ratio values across years, and then study their price movements. We propose using cross-graph quasi-biclique (CGQB) subgraphs to cluster stocks, as they can define the three dimensional (3D) subspaces of financial ratios that the stocks are homogeneous in across the years, and they can also handle missing values that are rampant in the stock data. Furthermore, investors can easily analyze these 3D subspaces to explore the relations between the stocks and financial ratios. We develop a novel algorithm, CGQBminer, which mines the complete set of CGQB subgraphs from the stock data. Through experimental analysis, we show that the hypothesis is valid. Furthermore, we demonstrate that having an investment strategy which uses groups of stocks mined by CGQB subgraphs have higher returns than one that does not. We also conducted an extensive performance analysis on CGQBminer, and show that it is efficient across different 3D datasets and parameter settings. [Copyright &y& Elsevier]

Abstract-This paper is concerned with the study of observability in a structural framework. It turns out that the system is structurally observable if and only if the system is output connected and contains no contraction. We focus our attention on the observability preservation under sensor failure. We consider linear observable systems and we wonder if a given system remains observable in case of sensor failure. More precisely, we will characterize among the sensors those which are critical, i.e., which failure leads to observability loss, those which are useless for observability purpose and the set of those which are useful without being critical. Using a graph approach we classify the sensors with respect to their importance for output connection preservation, contraction avoidance and then observability preservation under sensor failure. [ABSTRACT FROM AUTHOR]

Provides an overview of the technical articles and features presented in this issue. [ABSTRACT FROM AUTHOR]