Search

Statistical analysis of bipartite networks frequently requires randomly sampling from the set of all bipartite networks with the same degree sequence as an observed network. Trade algorithms offer an efficient way to generate samples of bipartite networks by incrementally 'trading' the positions of some of their edges. However, it is difficult to know how many such trades are required to ensure that the sample is random. I propose a stopping rule that focuses on the distance between sampled networks and the observed network, and stops performing trades when this distribution stabilizes. Analyses demonstrate that, for over 650 different degree sequences, using this stopping rule ensures a random sample with a high probability, and that it is practical for use in empirical applications. • Statistical analysis of bipartite networks requires randomly sampling. • It is difficult to determine whether a sample of bipartite networks is random. • The proposed stopping rule yields a random sample over 85% of the time. [ABSTRACT FROM AUTHOR]

Bipartite networks serve as highly suitable models to represent systems involving interactions between two distinct types of entities, such as online dating platforms, job search services, or e-commerce websites. These models can be leveraged to tackle a number of tasks, including link prediction among the most useful ones, especially to design recommendation systems. However, if this task has garnered much interest when conducted on unipartite (i.e. standard) networks, it is far from being the case for bipartite ones. In this study, we address this gap by performing an experimental comparison of 19 link prediction methods able to handle bipartite graphs. Some come directly from the literature, and some are adapted by us from techniques originally designed for unipartite networks. We also propose to repurpose recommendation systems based on graph convolutional networks (GCN) as a novel link prediction solution for bipartite networks. To conduct our experiments, we constitute a benchmark of 3 real-world bipartite network datasets with various topologies. Our results indicate that GCN-based personalized recommendation systems, which have received significant attention in recent years, can produce successful results for link prediction in bipartite networks. Furthermore, purely heuristic metrics that do not rely on any learning process, like the Structural Perturbation Method (SPM), can also achieve success. [ABSTRACT FROM AUTHOR]

The paper concentrates on the issue of distributed disturbance observer-based nonfragile bipartite consensus within nonlinear delayed multiagent systems, encompassing both leaderless and leader-following structures. The delays under consideration are nonuniform, manifesting in the state, the nonlinearity, and the communication processes. To suppress the external disturbances and the observer gain perturbations, distributed nonfragile disturbance observers pertaining to relative output and communication delays are developed to estimate the external disturbances for each agent. Employing the developed disturbance observer, distributed control protocols for nonfragile bipartite consensus are constructed incorporating states, estimated disturbances, and communication delays. These protocols can ensure bipartite consensus, compensate for external disturbances, and tolerate uncertainties in control gain. New augmented Lyapunov-Krasovskii functions are formulated by introducing the triple integral term and the augmented vector. The new bipartite consensus criteria for the studied multiagent systems are established with less conservatism by employing the techniques on second-order Bessel-Legendre integral inequality, reciprocally convex combination, and free weight matrix. Finally, numerical simulations and comparisons are performed for both leaderless and leader-following scenarios, thereby validating and enhancing the theoretical outcomes. • Multiagent systems with nonlinearity, disturbance and multiple delay, is considered. • Both cooperative and antagonistic relationships are all considered in consensus. • The perturbations in both observer and bipartite consensus protocol. • New Lyapunov-Krasovskii functions, and Bessel-Legendre inequality are employed. [ABSTRACT FROM AUTHOR]

The main problem addressed in this paper is the task-space bipartite formation tracking problem of uncertain heterogeneous Euler–Lagrange systems in predefined time. To solve this problem, an effective hierarchical predefined-time control algorithm is designed. This algorithm utilizes a non-singular sliding surface, allowing for the adjustment of the upper bound of the settling time as a flexible parameter. Key components of the proposed approach include an estimator for the leader's states and a controller tailored to the formation problem. To mitigate the effects of dynamic uncertainties in the system, the radial basis function neural network is integrated into the methodology. Finally, the effectiveness and validity of the proposed algorithm are demonstrated through numerical simulations, showcasing their practical applicability and efficacy. • Novel sliding mode control strategy tackles the bipartite formation problem. • The task-space controller considers the agents with different degrees-of-freedoms. • Neural network addresses the lumped uncertainties of the dynamic models. • Estimation and tracking errors converge to the origin in a predefined time. [ABSTRACT FROM AUTHOR]

The identification of events from social media platforms such as Twitter (now known as X) is a hot research problem. It has applications in diverse domains such as journalism, marketing, public safety, crisis management and disaster response. The process includes the identification, monitoring, and analysis of events or incidents while they are being discussed or reported on Twitter. When it comes to identifying events from tweets (i.e. feeds from Twitter), many of the currently available event detection methods mainly rely on keyword burstiness features or structural changes in the network. However, due to the intricate characteristics of tweets and the ever-changing nature of events, they frequently fail to recognise noteworthy occurrences before they become trending. Moreover, these methods face difficulties when it comes to capturing the evolving characteristics of events with limited or insufficient contextual information. In this paper, we propose a window-based tweet-processing method called EDTBERT for detecting events and tracking the evolution of events over time. Our proposed method utilizes the structural and semantic affinities that exist among words in tweets. The method starts by generating graph of tweets, where tweets are represented as nodes, and edges are the similarities between tweets. The method utilizes overlapping hashtags and named entities to capture the structural relationship between tweets. Additionally, a pre-trained sentence transformer model, specifically BERT, is employed to collect contextual knowledge and find semantically similar tweets. Next, the graph clustering technique is employed to identify optimized event clusters. Subsequently, our method generates chain of event clusters for each event to track the evolving variation of the event over time by utilising the "Maximum-Weight Bipartite Graph Matching" (MWBGM) algorithm. The effectiveness of our approach is assessed using standard Tweet Datasets. Our evaluation demonstrates that our approach outperforms the baseline approaches. [ABSTRACT FROM AUTHOR]

This work is dedicated to the leaderless/leader-following stochastic scaled consensus issue of second-order stochastic multi-agent systems (SMASs) in a noisy environment. Scaled consensus represents that the ratios among agents asymptotically tend to designated constants rather than the common convergence value. To lessen the influence of communication noise, some stochastic approximation protocols with time-varying gain are designed for our underlying system, where the time-varying gain remove the restriction of nonnegative value. Compared with the existing consensus results with communication noise, the major challenge is that the introduction of time-varying gain results in the inapplicability of Lyapunov-based technique. To cope with it, a state decomposition method is utilized, and a series of sufficient necessary conditions are set up for interacting agents with constant velocity and zero velocity if the topology includes a spanning tree. Furthermore, it is conducted that the consensus and bipartite consensus can be seen as two special cases of our work. Finally, the validity of our results is demonstrated by a simulation example. • The derived theoretical results are capable for leaderless and leader-following scaled consensus of second-order SMASs, despite the presence of communication noise. • A time-varying gain is utilized to reduce the negative impact of communication noise, and the time-varying gain removes the restriction of positive time-varying gain. • Moreover, we consider the scaled consensus models without or with a negative velocity feedback. We find that the negative velocity feedback does not affect the convergence of the velocity. [ABSTRACT FROM AUTHOR]

This article addresses the exponential bipartite synchronization (EBS) of multilayer signed networks with time-varying coupling (MSNs) under aperiodic intermittent-based adaptive dynamic event-triggered control (AAIDETC). Firstly, to increase the elasticity, a novel AAIDETC strategy is presented, whose superiority is that the control gains and the triggering parameters can vary with the evolution of the considered networks. Meanwhile, concerning the aperiodic intermittent control, a new definition of average control ratio (ACR) is put forward, which is more rigorous compared with the relevant results. Then, by the method of ACR, graph theory and Lyapunov approach, the simpler synchronization criterion is gained, which avoids the topology structure of MSNs. Moreover, the EBS issues of Chua's circuits and neural networks established on MSNs are studied, which are two practical applications of our theoretical results. Finally, corresponding numerical simulations are presented to verify the availability of the obtained results. • A new MSN model with time-varying coupling is proposed. • A novel AAIDETC is developed. • An improved definition of average control ratio is presented. [ABSTRACT FROM AUTHOR]

Copyright of Redes is the property of Redes-Revista Hispana para el Analisis de Redes Sociales 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.)

Let S = (G, σ) be a signed graph, where σ is the sign function on the edges of the underlying graph G. It is widely recognized that the adjacency spectrum alone cannot uniquely determine a signed graph. Therefore, it is of great interest to identify whether there exist any cospectral, non-isomorphic signed graphs within a specific class of signed graphs. In a significant contribution, Godsil et al. demonstrated that two components of G1 × G2, where both G1 and G2 are connected bipartite graphs, are cospectral if and only if at the minimum one of G1 and G2 is balanced. In this paper, we first generalize Godsil’s result for two connected signed bipartite graphs S1 and S2. Furthermore, we will define partitioned tensor product of two signed bipartite graphs, which will enable us to generate multiple pairs of cospectral non-isomorphic signed bipartite graphs. [ABSTRACT FROM AUTHOR]

In this paper, we undertake a comprehensive analysis of the Two-party public key exchange protocol proposed by Grigoriev & Shpilrain in 2019 which is intriguingly based on the homomorphism of tropical matrix algebras. The protocol was first hailed as a potential improvement in tropical cryptographic approaches. Subsequent cryptanalysis, however, has raised concerns regarding its vulnerability to attacks aiming at getting the secret parameters. The cryptanalytic efforts directed towards this key exchange protocol have not been in vain, as they have unequivocally declared its lack of robustness, ultimately classifying it as an insecure method for secure information exchange. Recognizing the critical importance of addressing such security weaknesses in modern cryptographic systems, our research focuses on uncovering novel and efficient approaches to circumvent the protocol’s security. As part of our contribution to the field, we propose an ingenious attack on this specific key exchange protocol. Remarkably, our attack is unique in that it does not necessitate the extraction of any private parameters. Rather, it capitalizes on leveraging the knowledge of public parameters and exploiting certain algebraic properties inherent to the protocol. This innovative strategy represents a significant departure from conventional attacks, which often rely on the extraction of private keys or exhaustive computations. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the relational architecture of the Intergovernmental Panel on Climate Change (IPCC) focussing on the individuals that, in the thirty years of its existence, have assured the connection between its different components. To study relational bridging within the IPCC, we created a unique database of all the individuals who have contributed to the organisation since its establishment and noted in which workstream they participated (i.e., function + Working Group + Assessment Report). From this database we extract the participants-workstreams affiliation network and use it to compute several metrics of bridgeness, which we discuss, validate, and compare. We use these metrics to investigate the general distribution and evolution of bridging in the IPCC, but also to identify individuals who more actively provided connections between its authors and government representatives (functional bridges), its Working Groups (thematic bridges) and its assessment cycles (temporal bridges). Focussing on the role of key bridge individuals and their trajectories within the organisation, we provide insights on the IPCC as a network organisation. • The paper is based on an original dataset of more than 8000 individuals who have contributed to the IPCC since 1988. • The paper investigates the individuals who have contributed to keeping together the different components of the IPCC. • The paper identifies temporal, thematic and functional bridge individuals and qualitatively analyses their career in the IPCC. [ABSTRACT FROM AUTHOR]

A double nested graph is a bipartite graph with the property that the neighborhood of vertices of each partite set form a chain with respect to set inclusion. Motivated by this structure, we generalize and define a new class of graphs and name it as k-nested graphs and study its properties. Characterization of a k-nested 2-self centered graph which is edge maximal is discussed and also we show that none of the k-nested 2-self centered graph is edge minimal. We extend the study and gave the bounds for Wiener index and some Szeged indices of k-nested graphs.We conclude this article by exploring some more degree based topological indices of k-nested graphs. [ABSTRACT FROM AUTHOR]

Analysis of a bipartite (two-mode) network is a significant research area to understand the formation of social communities, economic systems, drug side effect topology, etc. in complex information systems. Most of the previous works talk about a projection-based model or latent feature model, which predicts the link based on singular similarity. The projection-based models suffer from the loss of structural information in the projected network and the latent feature is hardly present. This work proposes a novel method for link prediction in the bipartite network based on an ensemble of composite similarities, overcoming the issues of modelbased and latent feature models. The proposed method analyzes the structure, neighborhood nodes as well as latent attributes between the nodes to predict the link in the network. To illustrate the proposed method, experiments are performed with five real-world data sets and compared with various state-of-art link prediction methods and it is inferred that this method outperforms with ~3% to ~9% higher using area under the precision-recall curve (AUC-PR) measure. This work holds great significance in the study of biological networks, e-commerce networks, complex web-based systems, networks of drug binding, enzyme protein, and other related networks in understanding the formation of such complex networks. Further, this study helps in link prediction and its usability for different purposes ranging from building intelligent systems to providing services in big data and web-based systems. [ABSTRACT FROM AUTHOR]

This prognostic study identifies subtypes of late-life depression and examines their depression trajectory by bipartite network clustering during psychosocial interventions. Key Points: Question: Are there subtypes of late-life depression with a distinct course of depression during psychosocial interventions? Findings: In this prognostic study of a combined sample of 535 older adults with depression, bipartite network clustering identified 3 subtypes of late-life depression: individuals with severe depression and a large social network; older, educated individuals with strong social support and frequent social interactions; and individuals with disability. Subtype 2 had the steepest decline of depression, while subtype 1 had the most persistent depression trajectory during psychosocial interventions. Meaning: Knowledge of an older adult's depression subtype at the outset of treatment may inform the selection of interventions and improve treatment planning. Importance: Approximately half of older adults with depression remain symptomatic at treatment end. Identifying discrete clinical profiles associated with treatment outcomes may guide development of personalized psychosocial interventions. Objective: To identify clinical subtypes of late-life depression and examine their depression trajectory during psychosocial interventions in older adults with depression. Design, Setting, and Participants: This prognostic study included older adults aged 60 years or older who had major depression and participated in 1 of 4 randomized clinical trials of psychosocial interventions for late-life depression. Participants were recruited from the community and outpatient services of Weill Cornell Medicine and the University of California, San Francisco, between March 2002 and April 2013. Data were analyzed from February 2019 to February 2023. Interventions: Participants received 8 to 14 sessions of (1) personalized intervention for patients with major depression and chronic obstructive pulmonary disease, (2) problem-solving therapy, (3) supportive therapy, or (4) active comparison conditions (treatment as usual or case management). Main Outcomes and Measures: The main outcome was the trajectory of depression severity, assessed using the Hamilton Depression Rating Scale (HAM-D). A data-driven, unsupervised, hierarchical clustering of HAM-D items at baseline was conducted to detect clusters of depressive symptoms. A bipartite network analysis was used to identify clinical subtypes at baseline, accounting for both between- and within-patient variability across domains of psychopathology, social support, cognitive impairment, and disability. The trajectories of depression severity in the identified subtypes were compared using mixed-effects models, and time to remission (HAM-D score ≤10) was compared using survival analysis. Results: The bipartite network analysis, which included 535 older adults with major depression (mean [SD] age, 72.7 [8.7] years; 70.7% female), identified 3 clinical subtypes: (1) individuals with severe depression and a large social network; (2) older, educated individuals experiencing strong social support and social interactions; and (3) individuals with disability. There was a significant difference in depression trajectories (F2,2976.9 = 9.4; P <.001) and remission rate (log-rank χ22 = 18.2; P <.001) across clinical subtypes. Subtype 2 had the steepest depression trajectory and highest likelihood of remission regardless of the intervention, while subtype 1 had the poorest depression trajectory. Conclusions and Relevance: In this prognostic study, bipartite network clustering identified 3 subtypes of late-life depression. Knowledge of patients' clinical characteristics may inform treatment selection. Identification of discrete subtypes of late-life depression may stimulate the development of novel, streamlined interventions targeting the clinical vulnerabilities of each subtype. [ABSTRACT FROM AUTHOR]

Robotic Process Automation has emerged in recent years as an important field by allowing faster and more secure processes through a reduction in the risks or errors but also an increase in the productivity rates of many industries. In this specific paper, the RPA problem aims at assigning financial transactions to software robots to minimize the total costs, induced by the licenses and utilization time. The problem is represented as a bipartite graph and the effective resistance of the graph, which is analog to an electrical circuit, is used to order the edges of a heuristic method to assign the transactions to robots. Preliminary results, based on real data from a bank, are compared to the optimal solution obtained by a linear integer programming model. They show that the heuristic method allows to obtain results quicker and that they are near the optimal solution. [ABSTRACT FROM AUTHOR]

A graph G is called irregular if the degrees of all its vertices are not the same. A graph is said to be Stepwise Irregular (SI) if the difference between the degrees of any two adjacent vertices is always 1. This paper deals with 2-Stepwise Irregular (2-SI) graphs in which the degrees of every pair of adjacent vertices differ by 2. Here, we discuss some properties of 2-SI graphs and generalize them for k-SI graphs for which the imbalance of every edge is k. Besides, we also compute bounds of irregularity for the Albertson index in any 2-SI graph. [ABSTRACT FROM AUTHOR]

We determine the colored patterns that appear in any 2-edge coloring of K n,n , with n large enough and with sufficient edges in each color. We prove the existence of a positive integer z2 such that any 2-edge coloring of K n,n with at least z 2 edges in each color contains at least one of these patterns. We give a general upper bound for z2 and prove its tightness for some cases. We define the concepts of bipartite r-tonality and bipartite omnitonality using the complete bipartite graph as a base graph. We provide a characterization for bipartite r-tonal graphs and prove that every tree is bipartite omnitonal. Finally, we define the bipartite balancing number and provide the exact bipartite balancing number for paths and stars. [ABSTRACT FROM AUTHOR]

A biclique of a graph G is a maximal complete bipartite induced subgraph of G with at least one edge. We define and study the time complexity of the problems of finding the minimum biclique transversal and maximum biclique independent set of a graph G, denoted by α b (G) and τ b (G) respectively. We prove that the Biclique-Transversal and Biclique-Independent-Set problems are NP-Complete for the classes of split graphs, planar graphs C 4 -free with ∆ = 4, and bipartite C 4 -free graphs with ∆ = 4. In addition, we provide polinomial time algorithms for block graphs and split gem-free graphs. Finally, we introduce the concept of biclique-perfectness. [ABSTRACT FROM AUTHOR]

Subgraph Problems are optimization problems on graphs where a solution is a subgraph that satisfies some property and optimizes some measure. Examples include shortest path, minimum cut, maximum matching, or vertex cover. In reality, however, one often deals with time-dependent data, i.e., the input graph may change over time and we need to adapt our solution accordingly. We are interested in guaranteeing optimal solutions after each graph change while retaining as much of the previous solution as possible. Even if the subgraph problem itself is polynomial-time computable, this multistage variant turns out to be NP-hard in most cases. We present an algorithmic framework that—for any subgraph problem of a certain type—guarantees an optimal solution for each point in time and provides an approximation guarantee for the similarity between subsequent solutions. We show that the class of applicable multistage subgraph problems is very rich and that proving membership to this class is mostly straightforward. As examples, we explicitly state these proofs and obtain corresponding approximation algorithms for the natural multistage versions of Shortest s-t- Path, Perfect Matching, Minimum s-t -Cut—and further classical problems on bipartite or planar graphs, namely Maximum Cut, Vertex Cover, and Independent Set. We also report that all these problems are already NP-hard on only two stages. [ABSTRACT FROM AUTHOR]

An orientation D of a graph G is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation D of a graph G is a k-orientation if the in-degree of each vertex in D is at most k. An orientation D of G is proper if any two adjacent vertices have different in-degrees in D. The proper orientation number of a graph G, denoted by → χ (G), is the minimum k such that G has a proper k-orientation. A weighted orientation of a graph G is a pair (D, w), where D is an orientation of G and w is an arc-weighting A(D) → N \ {0}. A semi-proper orientation of G is a weighted orientation (D, w) of G such that for every two adjacent vertices u and v in G, we have that S (d, w) (v) ≠ S (d,w) (u) , where S (d, w) (v) is the sum of the weights of the arcs in (D, w) with head v. For a positive integer k, a semi-proper k-orientation (D, w) of a graph G is a semi-proper orientation of G such that max vϵ V(G) S (d, w) (v) ≤ k. The semi-proper orientation number of a graph G, denoted by → χ s (G), is the least k such that G has a semi-proper k-orientation. In this work, we first prove that → χ s (G) ϵ {ω(G) - 1, ω(G)} for every split graph G, and that, given a split graph G, deciding whether →χ s (G) = ω(G) - 1 is an NP-complete problem. We also show that, for every k, there exists a (chordal) graph G and a split subgraph H of G such that →χ(G) ≤ k and →χ(H) = 2k - 2. In the sequel, we show that, for every n ≥ p(p + 1), →χ s (Pp n) = [3/ 2 p], where Pp n is the pth power of the path on n vertices. We investigate further unit interval graphs with no big clique: we show that →χ(G) ≤ 3 for any unit interval graph G with ω (G) = 3, and present a complete characterization of unit interval graphs with →χ(G) = ω (G) = 3. Then, we show that deciding whether →χ s (G) = ω (G) can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing →χ s (G) is FPT when parameterized by the minimum size of a vertex cover in G or by the treewidth of G. We also prove that not only computing →χ s (G) but also →χ(G), admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size 4 0(k2) and 0(2kk2), in chordal graphs and split graphs, respectively, for the problem of deciding whether →χ s (G) ≤ k parameterized by k. We also present exponential kernels for computing both →χ(G) and →χ s (G) parameterized by the value of the solution when G is a cograph. On the other hand, we show that computing →χ s (G) does not admit a polynomial kernel parameterized by the value of the solution when G is a chordal graph, unless NP ⊆ coNP/poly. [ABSTRACT FROM AUTHOR]

An identifying code of a closed-twin-free graph G is a set S of vertices of G such that any two vertices in G have a distinct intersection between their closed neighborhoods and S. It was conjectured in [F. Foucaud, R. Klasing, A. Kosowski, A. Raspaud. On the size of identifying codes in triangle-free graphs. Discrete Applied Mathematics, 2012] that there exists an absolute constant c such that for every connected graph G of order n and maximum degree ∆ , G admits an identifying code of size at most ∆-1/∆ n + c. We provide significant support for this conjecture by proving it for the class of all bipartite graphs that do not contain any pairs of open-twins of degree at least 2. In particular, this class of bipartite graphs contains all trees and more generally, all bipartite graphs without 4-cycles. Moreover, our proof allows us to precisely determine the constant c for the considered class, and the list of graphs needing c ≥ 0. For ∆ = 2 (the graph is a path or a cycle), it is long known that c = 3/2 suffices. For connected graphs in the considered graph class, for each ∆ ≥ 3, we show that c = 1 /∆ ≤ 1/3 suffices and that c is required to be positive only for a finite number of trees. In particular, for ∆ = 3, there are 12 trees with diameter at most 6 with a positive constant c and, for each ∆ ≥ 4, the only tree with positive constant c is the ∆-star. Our proof is based on induction and utilizes recent results from [F. Foucaud, T. Lehtilä. Revisiting and improving upper bounds for identifying codes. SIAM Journal on Discrete Mathematics, 2022]. [ABSTRACT FROM AUTHOR]

The long standing Zarankiewicz's conjecture states that the crossing number cr(K m,n) of the complete bipartite graph is Z(m, n):= [m/2][m-1/2][n/2][n-1/2]. Using flag algebras we show that cr(K n,n) ≥ 0.9118 • Z(n, n) + o(n4). We also show that the rectilinear crossing number cr-(K n ,n) of K n,n is at least 0.987 • Z (n,n) + o(n4). Finally, we show that if a drawing of K n ,n has no K 3,4 that has exactly two crossings, and these crossings share exactly one vertex, then it has at least Z (n,n) + o(n4) crossings. This is a local restriction inspired by Turán type problems that gives an asymptotically tight result. [ABSTRACT FROM AUTHOR]

A biclique is a maximal set of vertices in a graph that induces a complete bipartite graph. The biclique graph KB(G) of a graph G is the intersection graph of all bicliques in G. In this work, we introduce the concept of differentiating edges and non-edges between pairs of intersecting bicliques in a graph and the corresponding variants of the biclique graph: the edge differentiated (KB edif) and the non-edge differentiated (KB ndif) biclique graphs. Two bicliques are mutually included if they can be partitioned respectively into (X 1 , Y 1) and (X 2 , Y 2) such that X 1 c X 2 and Y 2 c Y 1. We show that all pairs of mutually included bicliques are non-edge differentiated, but they are not edge differentiated. We show that every pair of intersecting bicliques are differentiated by either edge or non-edge. Finally, we prove that graphs are free of edge differentiated bicliques if and only if they are (K 3 , C 5)-free and that graphs are free of non-edge differentiated bicliques if and only if they are (P 4 , paw)-free. [ABSTRACT FROM AUTHOR]

Finding a maximum-weight matching is a classical and well-studied problem in computer science, solvable in cubic time in general graphs. We introduce and consider in this work the "discovery" variant of the bipartite matching problem (or assignment problem) where edge weights are not provided as input but must be queried, requiring additional and costly computations. Hence, discovery algorithms are developed aiming to minimize the number of queried weights while providing guarantees on the computed solution. We show in this work the hardness of the underlying problem in general while providing several efficient algorithms that can make use of natural assumptions about the order in which the nodes are processed by the greedy algorithms. Our motivations for exploring this problem stem from finding practical solutions to maximum-weight matching in hypergraphs, a problem recently emerging in the formation of peer-to-peer energy sharing communities. [ABSTRACT FROM AUTHOR]

In this note we give a negative answer to a question proposed by Almendra-Hernández and Martínez-Sandoval. Let n ≤ m be positive integers and let X and Y be sets of sizes n and m in R n-1 such that X U Y is in generic position. There is a natural order on X x Y induced by the distances between the corresponding points. The question is if all possible orders on X x Y can be obtained in this way. We show that the answer is negative when n < m. The case n=m remains open. [ABSTRACT FROM AUTHOR]

In this paper, the bipartite synchronization of signed Lur'e network is studied under intermittent control, where the communication relationship of these adjacent nodes in the network can be either cooperative or competitive. Assuming that the network is structurally balanced, bipartite synchronization can be reached with some conditions and coordinate transform criterion. Then, Based on Lyapunov stability theory, some important norms are established. Ultimately, the simulation results can illustrate validness of theoretical analysis. • Based on the features of coordinate control, Lur'e networks is utilized to study synchronization problem. And synchronizing all nodes is the ultimate goal by adopting coordinate transform and nonlinear function. • Intermittent and pinning algorithm are used to achieve synchronization in signed Lur'e networks. Pinning control is a control strategy, which only needs to control finite nodes of the system [1]. Thus it is proposed to achieve bipartite leader-following synchronization in networks. • Finally, a numerical example is given to demonstrate the effectiveness and feasibility of the obtained results. [ABSTRACT FROM AUTHOR]

The bipartite containment control of nonlinear fractional multi-agent systems (FMASs) on fixed and switching signed directed networks is addressed in this article. Delayed control protocols are put forward to provide several simple algebraic criteria by means of using signed graph theory, fractional Razumikhin technique and common Lyapunov function approach. The presented method can well overcome the difficulty resulting from fractional calculus, time delay and switchings. Two numerical examples are presented for further clarifying the theoretical conclusions. • The signed directed networks with cooperative and antagonistic interactions are studied. • Fractional nonlinear multi-agent systems are considered. • Delayed control protocols are proposed to solve bipartite containment control under fixed and switching topologies. • Several simple criteria based on linear matrix inequalities are presented. [ABSTRACT FROM AUTHOR]

To alleviate the big data difficulties that have created a potential problem for many Internet users, it is necessary to filter, rank, and efficiently communicate the relevant information on the Web, where the diversity of possibilities is overwhelming. Recommender systems, which sift through enormous amounts of dynamically generated data to give consumers with personalised information and services, are able to overcome this problem. Bipartite graphs are currently generally used to store and understand this data due to its sparse nature. Data are mapped to a bipartite user-item interaction network where the graph topology captures detailed information about user-item associations, transforming a recommendation issue into a link prediction problem. Earlier, approaches for link prediction in bipartite graphs for various recommendation systems were developed, but the efficacy of the prediction methodology was not close to the standards required by real-time recommenders. So, the primary goal of this research is to offer an effective link prediction-based recommendation system that takes advantage of SVD++ along with K-nearest neighbors and reduces the system's error rate, leading to better outcomes. The proposed system is sorely tested on the MovieLens dataset and compared to some traditional recommendation methods. The results demonstrate that the suggested strategy exceeds all traditional approaches in terms of accuracy, and the actual suggestions are equally encouraging. [ABSTRACT FROM AUTHOR]

Plastic films are extensively utilized in agriculture, construction, and manufacturing, with their annual production reaching staggering figures. Addressing the global plastic pollution crisis is imperative. One promising approach is the augmentation of plastic films degradation through microbial agents. Consequently, we undertook composting experiments employing various plastics, including Polyethylene (PE), Poly lactic acid (PLA), and a treatment without plastic films addition (CK), mixed with kitchen waste. Employing bipartite association networks and difference significance analysis methods, we scrutinized the impact of different plastics on the microbial community within the compost piles. There were significant disparities in the microbial community composition among three composting piles. To pinpoint the key microorganisms responsible for PLA degradation, we conducted a comparative analysis of microbial species present on PLA compost piles and PLA film surfaces (PLAS), utilizing variance analysis, co-occurrence network analysis, and Spearman's correlation analysis. Our findings identified Bacillus as the pivotal microorganism involved in PLA degradation. Furthermore, employing function prediction by PICRUSt 2, we identified K00016 as the crucial gene facilitating PLA degradation by Bacillus. Subsequently, employing strain screening techniques, we isolated a highly effective PLA-degrading bacterium, Bacillus amyloliquefaciens strain ML274. The PLA films degradation rate of ML274 reached 3.18%. and other strains was lower than 3.0%. Thus, Bacillus emerges as the primary microorganism driving PLA degradation, emphasizing the significance of focusing on Bacillus genus microorganisms in the development of plastic-degrading bacterial agents for future endeavors. [Display omitted] • PE and PLA additions changed the microbial community of composting. • K00016 is a key gene for PLA degradation by Bacillus. • Bacillus amyloliquefaciens ML274 was selected with highest efficacy in degrading PLA. [ABSTRACT FROM AUTHOR]

In this paper we leverage a massive attack-focused terrorist database and we design a dynamic bipartite network analysis to examine the structural evolution of terrorists-targets relationships. We introduce two novel measures to jointly assess harmfulness and vulnerability of terrorist and target groups, both at local and global level. Statistical validation using null models provides evidence that the information contained in these measures is new and not included in other variables, thus emphasizing the usefulness of these topological indicators. Finally, a policy-support experiment designed as network dismantling-like drill is proposed to assess the effects of potential attack preventive strategies. • Bipartite network analysis to examine the evolution of terrorists-targets relationships. • Two measures are introduced to assess harmfulness and vulnerability of terrorist and target groups. • Null models provide statistical validation for the centrality measures. • Network dismantling-like exercise is proposed to assess potential attack preventive strategies. [ABSTRACT FROM AUTHOR]

This paper proposes a non-orthogonal multiple access (NOMA) based low-complexity relaying approach for multiuser cellular two-way relay channels (CTWRCs). In the proposed scheme, the relay detects the signal using successive interference cancellation (SIC) and re-generates the transmit signal with zero-forcing (ZF) transmit precoding. The achievable data rates of the NOMA-based multiuser two-way relaying (TWR) approach is analyzed. We further study the power allocation among different data streams to maximize the weighted sum-rate (WSR). We re-form the resultant non-convex problem into a standard monotonic program. Then, we design a polyblock outer approximation algorithm to solve the WSR problem. The proposed optimal power allocation algorithm converges fast and it is shown that the NOMA-TWR-OPA scheme outperforms a NOMA benchmark scheme and conventional TWR schemes. [ABSTRACT FROM AUTHOR]

The study of host-parasite interactions is key to understanding ecological interactions since parasites play a crucial role in the regulation of populations of host species. The families Nycteribiidae and Streblidae (Diptera: Hippoboscoidea) are ectoparasitic flies specific to bats, which have evolved adaptations to their host. The host-parasite interactions are formed by coevolutionary processes and illustrate the current and historical associations between the species involved. For this reason, the use of ecological networks in parasite-host interactions allows us to elucidate how the structure of their interactions respond to biotic and abiotic factors. In the present study, we evaluated changes in the fly-bat interaction networks in two contrasting landscapes in the Department of Arauca of the Colombian Orinoquia Region. The first landscape is composed of savannas and alluvial forests and the second with anthropogenic disturbances composed of cocoa crops, livestock areas and human settlements. We used mist nets to capture bats and collect their respective parasitic flies. Using this data, we built a bipartite interaction network for each landscape, and we calculated the main metrics of each network. 19.8% of the 524 bats captured presented ectoparasitic flies, with a total of 326 flies belonging to nine genera of Streblidae and one genus of Nycteribiidae. The diversity and prevalence of ectoparasitic flies of bats was higher for the disturbed landscape in contrast to savannas and forests. The networks of both landscapes were characterized by being highly specialized and modular. Nonetheless, the network obtained in the savannas and alluvial forests showed greater specialization, and the landscape with anthropogenic impact presented greater modularity. Our results confirm the high specialization and modularity that characterizes the ectoparasitic bat-fly antagonistic network. Also, we provided new observations suggesting that a degraded landscape may affect the bat hosts and favors overcrowding and, consequently, the exchange of ectoparasites between bat species, reducing the level of specialization and promoting the increased prevalence of bat ectoparasitic flies. [ABSTRACT FROM AUTHOR]

Many structural models in chemistry, biology, computer science, sociology, and operations research can be analyzed using graph theory. Some examples of these structure models are species movement between regions, molecular bonds, shortest spanning trees, development of computer algorithms. This paper introduces the edge decomposition of circulant graphs with 2 n vertices by different graph classes. These circulant graphs are denoted as C 2 n , n , where n is the degree of the graph C 2 n , n. We propose two algorithmic approaches for constructing edge decomposition of C 2 n , n. With aid of the proposed algorithmic approaches, we construct paths decompositions, trees decompositions, disjoint unions of cycles and trees decompositions, and complete bipartite graphs decompositions of C 2 n , n. In the end, a recursive construction of an edge decomposition, based on orthogonal edge decompositions, is proposed. This helps in using the mutually orthogonal decompositions of the circulant graphs C 2 n , n in several applications, such as the design of experiments and binary codes generation. [ABSTRACT FROM AUTHOR]

Habitat loss disrupts species interactions through local extinctions, potentially orphaning species that depend on interacting partners, via mutualisms or commensalisms, and increasing secondary extinction risk. Orphaned species may become functionally or secondarily extinct, increasing the severity of the current biodiversity crisis. While habitat destruction is a major cause of biodiversity loss, the number of secondary extinctions is largely unknown. We investigate the relationship between habitat loss, orphaned species, and bipartite network properties. Using a real seed dispersal network, we simulate habitat loss to estimate the rate at which species are orphaned. To be able to draw general conclusions, we also simulate habitat loss in synthetic networks to quantify how changes in network properties affect orphan rates across broader parameter space. Both real and synthetic network simulations show that even small amounts of habitat loss can cause up to 10% of species to be orphaned. More area loss, less connected networks, and a greater disparity in the species richness of the network's trophic levels generally result in more orphaned species. As habitat is lost to land‐use conversion and climate change, more orphaned species increase the loss of community‐level and ecosystem functions. However, the potential severity of repercussions ranges from minimal (no species orphaned) to catastrophic (up to 60% of species within a network orphaned). Severity of repercussions also depends on how much the interaction richness and intactness of the community affects the degree of redundancy within networks. Orphaned species could add substantially to the loss of ecosystem function and secondary extinction worldwide. [ABSTRACT FROM AUTHOR]

Many graph-based unsupervised dimensionality reduction techniques have raised concerns about their high accuracy. However, there is an urgent need to address the enormous time consumption problem in large-scale data scenarios. Therefore, we present a novel approach named Structure Preserved Fast Dimensionality Reduction (SPFDR). Firstly, the parameter-insensitive, sparse, and scalable bipartite graph is constructed to build the similarity matrix. Then, employing alternating iterative optimization, the linear dimensionality reduction matrix and the optimal similarity matrix preserved cluster structure are learned. The computational complexity of the conventional graph-based dimension reduction method costs O (n 2 d + d 3) , yet the proposed approach is O (n d m + n m 2) , wherein n , m , and d are the number of instances, anchors, and features, respectively. Eventually, experiments conducted with multiple open datasets will provide convincing evidence for how effective and efficient the proposed method is. • Introduces a fast dimensionality reduction method with anchors. • Continuously optimizes the bipartite graph, preserving manifold structure. • Integrates graph creation and projection learning with an efficient optimization. • Validated by extensive tests, demonstrating effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

We measured triadic closure in co-offending networks – i.e., the tendency of two individuals to co-offend if they share an accomplice – using a method that addresses the risk of overestimating clustering coefficients when using one-mode projections. We also assess the statistical significance of clustering coefficients using null models. The data relates to adult offenders (N = 274,689) connected to criminal investigations (N = 286,591) in Colombia. The observed coefficients range between 0.05 and 0.53 and are statistically significant, indicating that accomplices become sources of information about potential associates. They support the idea of preventing crime by targeting offenders' trustworthiness and disrupting information flows. • Clustering coefficients suggest that co-offending networks display triadic closure • Former accomplices become sources of information for new partners in crime • Assessing triadic closure in bipartite networks prevents overestimations • Null models assess the statistical significance of the clustering coefficients [ABSTRACT FROM AUTHOR]

Despite longstanding discussions and consequent improvements of gender representation in academia, the number of women working in academic research, their performance and their recognition still indicate the persistence of gender inequalities. Of the various mechanisms that may drive such inequality the one that relates the structure of research collaborative networks to the rewards that these networks facilitate is intriguing. If social networks play a role in academic performances and women are under-recognized compared to men, what are the mechanisms that relate networks to gender inequalities in academia? Do men and women obtain equal returns from similar network structure, or do women have to build different networks to obtain similar returns? This article contributes to the theoretical debate that aims to disentangle the mechanisms by which social networks may affect gendered success. We do so by looking at networks of collaborations to research projects in 10 years of public funding in Italy. We use a permutation t-test analysis to see if men and women, who are equally successful in getting funded for a high number of projects, build equal or unequal collaborative networks, and if these differences vary across disciplines with more or less tenured women. Our methodological contribution proposes an innovative way of measuring brokerage and constraint in one mode projections of bipartite networks, highly clustered and valued, and measures gender homophily by taking into account the higher or lower number of women available for collaborations in different disciplinary sectors. We find that men and women build similar collaborative networks; we also find that the more women are tenured in a discipline, the more they occupy higher ranks and lead research projects. When women's presence and high-rank roles increase, we see that men's collaborative networks are significantly more heterophilous, although women do not seem to significantly increase their collaborations with other women. We then regress the individual measures of network structure and composition against the average amount of money scholars receive per project and we interact each measure with gender, to observe if women obtain similar returns to men by building equal collaborative networks. Our results show that despite the similarities in network configurations in nearly all disciplines women still receive less funding than men. This suggests that an increased representation of women in academic fields is not enough to reduce inequalities. Our results are not directly generalizable to other international contexts, but the mechanisms that favor academic returns and exacerbate inequalities, and our methodological approach, are portable to other scientific and organizational contexts where collaborations are key to produce success. • We look at networks of collaborations to research projects in 10 years of academic funding in Italy. • We propose new brokerage and constraint measures for projections of bipartite networks. • Men and women build similar networks, and when women's numbers increase men work more with women. • Despite the similarities in network configurations women still receive less funding than men. • Gender inequalities seem to be related to the lack of women in leadership positions. [ABSTRACT FROM AUTHOR]

We examine the inclusion of specific nodal random effects for first- and second-mode nodes towards an ERGM for bipartite networks. The inclusion of such node-specific random effects in the ERGM accounts for unobserved heterogeneity in the bipartite network and ensures stable estimation results, especially for large-scale bipartite networks. Moreover, The predicted nodal random effects deliver reasonable interpretation to understand the network behavior. The estimation is carried out by an iterative estimation technique, iterating between pseudolikelihood estimation for the nodal random effects and maximum likelihood estimation for the network parameters. • Bipartite Network Analysis. • Inclusion of node specific heterogeneity in ERGM for bipartite networks for first- and second-mode nodes. • Scalable for the analysis of large bipartite networks. [ABSTRACT FROM AUTHOR]

The primary aim of the study aims to provide a solution for scheduling examinations for most of the universities and colleges across India which follow the Choice Based Credit System (CBCS) using a graph coloring algorithm. Nowadays, due to the flexibility of opting various subjects, and many students taking up different courses in their colleges and universities, it becomes difficult to schedule these examinations. Creating an examination schedule can be quite challenging and time-consuming for controlling the body of an examination. Our research work focuses on reducing the efforts for scheduling such examinations. With the knowledge of graph theory and graph traversing and coloring algorithms, our algorithm with the help of a few assumptions gives an efficient solution to the examination scheduling problem. A detailed correctness proof along with performance analysis has been done. The efficiency of our proposed algorithm is then compared to that of the coloring algorithm using backtracking. [ABSTRACT FROM AUTHOR]

In this work, for a given oriented graph D, we study its interval and hull numbers, denoted by ⃗in (D) and ⃗hn (D), respectively, in the oriented geodetic, ⃗P 3 and ⃗ P* 3 convexities. This last one, we believe to be formally defined and first studied in this paper, although its undirected version is well-known in the literature. Concerning bounds, for a strongly oriented graph D and the oriented geodetic convexity, we prove that ⃗hn g (D) ≤ m(D)-n(D) + 2 and that there is at least one such that ⃗hn g (D) = m(D) - n(D). We also determine exact values for the hull numbers in these three convexities for tournaments, which imply polynomial-time algorithms to compute them. These results allow us to deduce polynomial-time algorithms to compute ⃗hn P3 (D) when the underlying graph of D is split or cobipartite. Moreover, we provide a meta-theorem by proving that if deciding whether ⃗in g (D) ≤ k or ⃗hn g (D) ≤ k is NP-hard or W[i]-hard parameterized by k, for some i ϵ Z * + , then the same holds even if the underlying graph of D is bipartite. Next, we prove that deciding whether ⃗hn P3 (D) ≤ k or ⃗hn P3 * (D) ≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is bipartite; that deciding whether ⃗in P3 (D) ≤ k or whether ⃗in P3 *(D) ≤ k is NP-complete, and the same for ⃗hn P3 *(D) ≤ k even if D has no directed cycles and the underlying graph of D is a chordal bipartite graph; and that deciding whether ⃗in P3 (D) ≤ k or whether ⃗in P3 *(D) ≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is split. Finally, we also argue that the interval and hull numbers in the ⃗ P 3 and ⃗ P* 3 convexities can be computed in polynomial time for directed graphs with underlying graph of bounded tree-width by using Courcelle's theorem. [ABSTRACT FROM AUTHOR]

Cops and Robber is one of the most studied two-player pursuit-evasion games played on graphs, where multiple cops, controlled by one player, pursue a single robber. The cop number of a graph is the minimum number of cops that can ensure the capture of the robber. In directed graphs, two kinds of moves are defined for players: strong move, where a player can move both along and against the orientation of an arc to an adjacent vertex; and weak move, where a player can only move along the orientation of an arc to an out-neighbor. We study three variants of Cops and Robber on oriented graphs: strong cop model, where the cops can make strong moves while the robber can only make weak moves; normal cop model, where both cops and the robber can only make weak moves; and weak cop model, where the cops can make weak moves while the robber can make strong moves. We study the cop number of these models with respect to several variants of retracts on oriented graphs and establish that the strong and normal cop number of an oriented graph remains invariant in their strong and distributed retracts, respectively. Next, we go on to study all three variants with respect to the subdivisions of graphs and oriented graphs. Finally, we establish that all these variants remain computationally difficult even when restricted to the class of 2-degenerate bipartite graphs. [ABSTRACT FROM AUTHOR]

A biclique q-coloring is an assignment of q-colors to the vertices of a graph G, so that no biclique (maximal set of vertices that induces a complete bipartite subgraph of G with at least one edge) is monochromatic. Inspired by the coloring game, we introduce the biclique q-coloring game played on a graph G defined as follows. Two players, Alice and Bob, alternately color the vertices of a graph G using q colors. Alice's goal is to color the vertices of G so that no biclique is monochromatic, and Bob tries to prevent this. Both players play optimally and respect the following rule: if a biclique is fully colored, then there exist at least two vertices in the biclique with different colors. In this paper, we prove that the biclique q-coloring game is PSPACE-complete and study the game in powers of paths Pk n. [ABSTRACT FROM AUTHOR]

Social media has become a primary source of information for decision-makers, organizations, and scientists in today's fast-paced world. Indeed, because of the large volume of user-generated data available on social media, these online platforms are viewed as computable data sources that potentially mirror reality. It could be an authentic environment for the task of target customers identification for marketing. This paper presents a novel image-based personalized advertisement recommendation system named IPARS to identify target customers in social media using image processing and machine learning techniques for an online advertisement. Assume having a set of advertising images; The problem is identifying a group of social media users who are likely to be the potential target of those images. In IPARS, a given social network is first converted into a weighted bipartite graph where the nodes are the users and keywords. Then, another bipartite graph is formed by decomposing the advertising images into their objects, labels, concepts, and sentiments. We propose a couple of formulas to calculate the weight of edges for both graphs. An algorithm is proposed to search the social graph and identify and rank the best group of users. We have evaluated our proposed model on a set of images and users from the Flickr dataset and Twitter. The results showed that IPARS has a better performance compared with other algorithms. [ABSTRACT FROM AUTHOR]

In the field of ecommerce, most recommendation algorithms are based on user-item bipartite graph network (BGN). But this kind of recommendation algorithm is severely lacking in accuracy and diversity. In this paper, a novel ecommerce recommendation algorithm is proposed based on BGN link prediction. Firstly, all the user-item data were imported into distance formula to calculate the similarity between the attributes. Then, the BGN was projected into a single-mode network (SMN), making it more efficient to extract potential links from the BGN. On this basis, the potential links were predicted based on similarity. Through experiments on real ecommerce datasets, it was proved that our algorithm has a higher accuracy and coverage than typical recommendation algorithms. [ABSTRACT FROM AUTHOR]

The resilience of cyberphysical systems to denial-of-service (DoS) and integrity attacks is studied in this paper. The cyberphysical system is modeled as a linear structured system, and its resilience to an attack is interpreted in a graph theoretical framework. The structural resilience of the system is characterized in terms of unmatched vertices in maximum matchings of the bipartite graph and connected components of directed graph representations of the system under attack. We first present conditions for the system to be resilient to DoS attacks when an adversary may block access or turn off certain inputs to the system. We extend this analysis to characterize resilience of the system when an adversary might additionally have the ability to affect the implementation of state-feedback control strategies. This is termed an integrity attack. We establish conditions under which a system that is structurally resilient to a DoS attack will also be resilient to a certain class of integrity attacks. Finally, we formulate an extension to the case of switched linear systems, and derive conditions for such systems to be structurally resilient to a DoS attack. [ABSTRACT FROM AUTHOR]