Search

We study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity as well as the full spectrum distribution. For an integer d ∈ 3 , 7 , we find families of random semi-regular graphs that have higher algebraic connectivity than random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when d ≥ 8 . More generally, we study random semi-regular graphs whose average degree is d, not necessarily an integer. This provides a natural generalization of a d-regular graph in the case of a non-integer d . We characterize their algebraic connectivity in terms of a root of a certain sixth-degree polynomial. Finally, we construct a small-world-type network of an average degree of 2.5 with relatively high algebraic connectivity. We also propose some related open problems and conjectures. [ABSTRACT FROM AUTHOR]

Underwriters play a pivotal role in the IPO process. Information entropy, a tool for measuring the uncertainty and complexity of information, has been widely applied to various issues in complex networks. Information entropy can quantify the uncertainty and complexity of nodes in the network, providing a unique analytical perspective and methodological support for this study. This paper employs a bipartite network analysis method to construct the relationship network between underwriters and accounting firms, using the centrality of underwriters in the network as a measure of their influence to explore the impact of underwriters' influence on the distribution of interests and audit outcomes. The findings indicate that a more pronounced influence of underwriters significantly increases the ratio of underwriting fees to audit fees. Higher influence often accompanies an increase in abnormal underwriting fees. Further research reveals that companies underwritten by more influential underwriters experience a decline in audit quality. Finally, the study reveals that a well-structured audit committee governance and the rationalization of market sentiments can mitigate the negative impacts of underwriters' influence. The innovation of this paper is that it enriches the content related to underwriters by constructing the relationship network between underwriters and accounting firms for the first time using a bipartite network through the lens of information entropy. This conclusion provides new directions for thinking about the motives and possibilities behind financial institutions' cooperation, offering insights for market regulation and policy formulation. [ABSTRACT FROM AUTHOR]

We construct an infinite family of bounded-degree bipartite unique neighbour expander graphs with arbitrarily unbalanced sides. Although weaker than the lossless expanders constructed by Capalbo et al., our construction is simpler and may be closer to being implementable in practice, due to the smaller constants. We construct these graphs by composing bipartite Ramanujan graphs with a fixed-size gadget in a way that generalises the construction of unique neighbour expanders by Alon and Capalbo. For the analysis of our construction, we prove a strong upper bound on average degrees in small induced subgraphs of bipartite Ramanujan graphs. Our bound generalises Kahale's average degree bound to bipartite Ramanujan graphs, and may be of independent interest. Surprisingly, our bound strongly relies on the exact Ramanujan-ness of the graph and is not known to hold for nearly-Ramanujan graphs. [ABSTRACT FROM AUTHOR]

We consider a point process (PP) generated by superimposing an independent Poisson point process (PPP) on each line of a 2D Poisson line process (PLP). Termed PLP-PPP, this PP is suitable for modeling networks formed on an irregular collection of lines, such as vehicles on a network of roads and sensors deployed along trails in a forest. Inspired by vehicular networks in which vehicles connect with their nearest wireless base stations (BSs), we consider a random bipartite associator graph in which each point of the PLP-PPP is associated with the nearest point of an independent PPP through an edge. This graph is equivalent to the partitioning of PLP-PPP by a Poisson Voronoi tessellation (PVT) formed by an independent PPP. We first characterize the exact distribution of the number of points of PLP-PPP falling inside the ball centered at an arbitrary location in R 2 as well as the typical point of PLP-PPP. Using these distributions, we derive cumulative distribution functions (CDFs) and probability density functions (PDFs) of kth contact distance (CD) and the nearest neighbor distance (NND) of PLP-PPP. As intermediate results, we present the empirical distribution of the perimeter and approximate distribution of the length of the typical chord of the zero-cell of this PVT. Using these results, we present two close approximations of the distribution of node degree of the random bipartite associator graph. In a vehicular network setting, this result characterizes the number of vehicles connected to each BS, which models its load. Since each BS has to distribute its limited resources across all the vehicles connected to it, a good statistical understanding of load is important for an efficient system design. Several applications of these new results to different wireless network settings are also discussed. [ABSTRACT FROM AUTHOR]

We consider a random geometric hypergraph model based on an underlying bipartite graph. Nodes and hyperedges are sampled uniformly in a domain, and a node is assigned to those hyperedges that lie within a certain radius. From a modelling perspective, we explain how the model captures higher-order connections that arise in real data sets. Our main contribution is to study the connectivity properties of the model. In an asymptotic limit where the number of nodes and hyperedges grow in tandem, we give a condition on the radius that guarantees connectivity. [ABSTRACT FROM AUTHOR]

Matrix factorization is a long-established method employed for analyzing and extracting valuable insight recommendations from complex networks containing user ratings. The execution time and computational resources demanded by these algorithms pose limitations when confronted with large datasets. Community detection algorithms play a crucial role in identifying groups and communities within intricate networks. To overcome the challenge of extensive computing resources with matrix factorization techniques, we present a novel framework that utilizes the inherent community information of the rating network. Our proposed approach, named Community-Based Matrix Factorization (CBMF), has the following steps: (1) Model the rating network as a complex bipartite network. (2) Divide the network into communities. (3) Extract the rating matrices pertaining only to those communities and apply MF on these matrices in parallel. (4) Merge the predicted rating matrices belonging to communities and evaluate the root mean square error (RMSE). In our experimentation, we use basic MF, SVD++, and FANMF for matrix factorization, and the Louvain algorithm is used for community division. The experimental evaluation on six datasets shows that the proposed CBMF enhances the quality of recommendations in each case. In the MovieLens 100K dataset, RMSE has been reduced to 0.21 from 1.26 using SVD++ by dividing the network into 25 communities. A similar reduction in RMSE is observed for the datasets of FilmTrust, Jester, Wikilens, Good Books, and Cell Phone. [ABSTRACT FROM AUTHOR]

Quantum networks offer a realistic and practical scheme for generating multiparticle entanglement and implementing multiparticle quantum communication protocols. However, the correlations that can be generated in networks with quantum sources and local operations are not yet well understood. Covariance matrices, which are powerful tools in entanglement theory, have been also applied to the network scenario. We present simple proofs for the decomposition of such matrices into the sum of positive semi-definite block matrices and, based on that, develop analytical and computable necessary criteria for preparing states in quantum networks. These criteria can be applied to networks where nodes share at most one source, such as all bipartite networks. [ABSTRACT FROM AUTHOR]

Quantum technology can break through the bottleneck of traditional information technology by ensuring information security, speeding up computation, improving measurement accuracy, and providing revolutionary solutions to some issues of economic and social development. Quantum entanglement swapping is a highly significant technology in quantum entanglement repeaters, which are generally employed to realize long-distance quantum entanglements in many quantum information processing tasks. This Special Issue is intended to investigate some basic features and applications of quantum information, including but not limited to complementarity, quantum algorithms, quantum coherence, quantum correlations, quantum measurement, quantum metrology, quantum uncertainties, and quantum information processing. The Belavkin-Staszewski (BS) relative entropy is an enticing and crucial entropy used to process quantum information tasks, which can be used to describe the effects of possible noncommutativity of the quantum states (the quantum relative entropy does not work well for this case). [Extracted from the article]

Given two graphs G and H, the mapping of f : V (G) → V (H) is called a graph homomorphism from G to H if it maps the adjacent vertices of G to the adjacent vertices of H. For the graph G, a subset of vertices is called a dissociation set of G if it induces a subgraph of G containing no paths of order three, i.e., a subgraph of a maximum degree, which is at most one. Graph homomorphisms and dissociation sets are two generalizations of the concept of independent sets. In this paper, by utilizing an entropy approach, we provide upper bounds on the number of graph homomorphisms from the bipartite graph G to the graph H and the number of dissociation sets in a bipartite graph G. [ABSTRACT FROM AUTHOR]

Many web platforms now include recommender systems. Network representation learning has been a successful approach for building these efficient recommender systems. However, learning the mutual influence of nodes in the network is challenging. Indeed, it carries collaborative signals accounting for complex user-item interactions on user decisions. For this purpose, in this paper, we develop a Mutual Interaction Graph Attention Network "MIGAN", a new algorithm based on self-supervised representation learning on a large-scale bipartite graph (BGNN). Experimental investigation with real-world data demonstrates that MIGAN compares favorably with the baselines in terms of prediction accuracy and recommendation efficiency. [ABSTRACT FROM AUTHOR]

We study an oracle operation, along with its circuit design, which combined with the Grover diffusion operator boosts the probability of finding the minimum or maximum solutions on a weighted directed graph. We focus on the geometry of sequentially connected bipartite graphs, which naturally gives rise to solution spaces describable by Gaussian distributions. We then demonstrate how an oracle that encodes these distributions can be used to solve for the optimal path via amplitude amplification. And finally, we explore the degree to which this algorithm is capable of solving cases that are generated using randomized weights, as well as a theoretical application for solving the Traveling Salesman problem. [ABSTRACT FROM AUTHOR]

Link prediction based on bipartite networks can not only mine hidden relationships between different types of nodes, but also reveal the inherent law of network evolution. Existing bipartite network link prediction is mainly based on the global structure that cannot analyze the role of the local structure in link prediction. To tackle this problem, this paper proposes a deep link-prediction (DLP) method by leveraging the local structure of bipartite networks. The method first extracts the local structure between target nodes and observes structural information between nodes from a local perspective. Then, representation learning of the local structure is performed on the basis of the graph neural network to extract latent features between target nodes. Lastly, a deep-link prediction model is trained on the basis of latent features between target nodes to achieve link prediction. Experimental results on five datasets showed that DLP achieved significant improvement over existing state-of-the-art link prediction methods. In addition, this paper analyzes the relationship between local structure and link prediction, confirming the effectiveness of a local structure in link prediction. [ABSTRACT FROM AUTHOR]

Relatedness is a key concept in economic complexity, since the assessment of the similarity between industrial sectors enables policymakers to design optimal development strategies. However, among the different ways to quantify relatedness, a measure that takes explicitly into account the time correlation structure of exports is still lacking. In this paper, we introduce an asymmetric definition of relatedness by using statistically significant partial correlations between the exports of economic sectors and we apply it to a recently introduced database that integrates the export of physical goods with the export of services. Our asymmetric relatedness is obtained by generalising a recently introduced correlation-filtering algorithm, the partial correlation planar graph, in order to allow its application on multi-sample and multi-variate datasets, and in particular, bipartite temporal networks. The result is a network of economic activities whose links represent the respective influence in terms of temporal correlations; we also compute the statistical confidence of the edges in the network via an adapted bootstrapping procedure. We find that the underlying influence structure of the system leads to the formation of intuitively-related clusters of economic sectors in the network, and to a relatively strong assortative mixing of sectors according to their complexity. Moreover, hub nodes tend to form more robust connections than those in the periphery. [ABSTRACT FROM AUTHOR]

While it has recently been demonstrated how to certify the maximal amount of randomness from any pure two-qubit entangled state in a device-independent way, the problem of optimal randomness certification from entangled states of higher local dimension remains open. Here we introduce a method for device-independent certification of the maximal possible amount of 2 log 2 3 random bits using pure bipartite entangled two-qutrit states and extremal nine-outcome general non-projective measurements. To this aim, we exploit a device-independent method for certification of the full Weyl–Heisenberg basis in three-dimensional Hilbert spaces together with a one-sided device-independent method for certification of two-qutrit partially entangled states. [ABSTRACT FROM AUTHOR]

A new measure based on the tripartite information diagram is proposed for identifying quantum discord in tripartite systems. The proposed measure generalizes the mutual information underlying discord from bipartite to tripartite systems, and utilizes both one-particle and two-particle projective measurements to reveal the characteristics of the tripartite quantum discord. The feasibility of the proposed-measure is demonstrated by evaluating the tripartite quantumdiscord for systemswith states close to Greenberger-Horne-Zeilinger,W, and biseparable states. In addition, the connections between tripartite quantum discord and two other quantum correlations--namely genuine tripartite entanglement and genuine tripartite Einstein-Podolsky-Rosen steering--are briefly discussed. The present study considers the case of quantum discord in tripartite systems. However, the proposed framework can be readily extended to general N-partite systems. [ABSTRACT FROM AUTHOR]

We consider bipartite mixed states ρ in a d ⊗ d quantum system. We say that ρ is PPT if its partial transpose 1 ⊗ T(ρ) is positive semidefinite, and otherwise ρ is NPT. The well-known Werner states are divided into three types: (a) the separable states (the same as the PPT states); (b) the one-distillable states (necessarily NPT); and (c) the NPT states which are not one-distillable. We give several different formulations and provide further evidence for the validity of the conjecture that Werner states of type (c) are not two-distillable. [ABSTRACT FROM AUTHOR]

In this review, we discuss the zero and finite temperature behavior of various bipartite quantum and total correlation measures, the skew information-based quantum coherence and the local quantum uncertainty in the thermal ground state of the one-dimensional anisotropic XY model in a transverse magnetic field. We compare the ability of the considered measures to correctly detect or estimate the quantum critical point and the non-trivial factorization point possessed by the spin chain. [ABSTRACT FROM AUTHOR]

We study a system represented by a Bose-Einstein condensate interacting with a cavity field in presence of a strong off-resonant pumping laser. This system can be described by a three-mode Gaussian state, where two are the atomic modes corresponding to atoms populating upper and lower momentum sidebands and the third mode describes the scattered cavity field light. We show that, as a consequence of the collective atomic recoil instability, these modes possess a genuine tripartite entanglement that increases unboundedly with the evolution time and is larger than the bipartite entanglement in any reduced two-mode bipartition. We further show that the state of the system exhibits genuine tripartite nonlocality, which can be revealed by a robust violation of the Svetlichny inequality when performing displaced parity measurements. Our exact results are obtained by exploiting the powerful machinery of phase-space informational measures for Gaussian states, which we briefly review in the opening sections of the paper. [ABSTRACT FROM AUTHOR]

The complexity of drug–disease interactions is a process that has been explained in terms of the need for new drugs and the increasing cost of drug development, among other factors. Over the last years, diverse approaches have been explored to understand drug–disease relationships. Here, we construct a bipartite graph in terms of active ingredients and diseases based on thoroughly classified data from a recognized pharmacological website. We find that the connectivities between drugs (outgoing links) and diseases (incoming links) follow approximately a stretched-exponential function with different fitting parameters; for drugs, it is between exponential and power law functions, while for diseases, the behavior is purely exponential. The network projections, onto either drugs or diseases, reveal that the co-occurrence of drugs (diseases) in common target diseases (drugs) lead to the appearance of connected components, which varies as the threshold number of common target diseases (drugs) is increased. The corresponding projections built from randomized versions of the original bipartite networks are considered to evaluate the differences. The heterogeneity of association at group level between active ingredients and diseases is evaluated in terms of the Shannon entropy and algorithmic complexity, revealing that higher levels of diversity are present for diseases compared to drugs. Finally, the robustness of the original bipartite network is evaluated in terms of most-connected nodes removal (direct attack) and random removal (random failures). [ABSTRACT FROM AUTHOR]

We perform a detailed computational study of the recently introduced Sombor indices on random networks. Specifically, we apply Sombor indices on three models of random networks: Erdös-Rényi networks, random geometric graphs, and bipartite random networks. Within a statistical random matrix theory approach, we show that the average values of Sombor indices, normalized to the order of the network, scale with the average degree. Moreover, we discuss the application of average Sombor indices as complexity measures of random networks and, as a consequence, we show that selected normalized Sombor indices are highly correlated with the Shannon entropy of the eigenvectors of the adjacency matrix. [ABSTRACT FROM AUTHOR]

This paper studies the problem of upper bounding the number of independent sets in a graph, expressed in terms of its degree distribution. For bipartite regular graphs, Kahn (2001) established a tight upper bound using an information-theoretic approach, and he also conjectured an upper bound for general graphs. His conjectured bound was recently proved by Sah et al. (2019), using different techniques not involving information theory. The main contribution of this work is the extension of Kahn's information-theoretic proof technique to handle irregular bipartite graphs. In particular, when the bipartite graph is regular on one side, but may be irregular on the other, the extended entropy-based proof technique yields the same bound as was conjectured by Kahn (2001) and proved by Sah et al. (2019). [ABSTRACT FROM AUTHOR]

Entropy-based indices are long-established measures of biological diversity, nowadays used to gauge partitioning of diversity at different spatial scales. Here, we tackle the measurement of diversity of interactions among two sets of organisms, such as plants and their pollinators. Actual interactions in ecological communities are depicted as bipartite networks or interaction matrices. Recent studies concentrate on distinctive structural patterns, such as nestedness or modularity, found in different modes of interaction. By contrast, we investigate mutual information as a general measure of structure in interactive networks. Mutual information (MI) measures the degree of reciprocal matching or specialization between interacting organisms. To ascertain its usefulness as a general measure, we explore (a) analytical solutions for different models; (b) the response of MI to network parameters, especially size and occupancy; (c) MI in nested, modular, and compound topologies. MI varies with fundamental matrix parameters: dimension and occupancy, for which it can be adjusted or normalized. Apparent differences among topologies are contingent on dimensions and occupancy, rather than on topological patterns themselves. As a general measure of interaction structure, MI is applicable to conceptually and empirically fruitful analyses, such as comparing similar ecological networks along geographical gradients or among interaction modalities in mutualistic or antagonistic networks. [ABSTRACT FROM AUTHOR]

Network science can offer fundamental insights into the structural and functional properties of complex systems. For example, it is widely known that neuronal circuits tend to organize into basic functional topological modules, called network motifs. In this article, we show that network science tools can be successfully applied also to the study of artificial neural networks operating according to self-organizing (learning) principles. In particular, we study the emergence of network motifs in multi-layer perceptrons, whose initial connectivity is defined as a stack of fully-connected, bipartite graphs. Simulations show that the final network topology is shaped by learning dynamics, but can be strongly biased by choosing appropriate weight initialization schemes. Overall, our results suggest that non-trivial initialization strategies can make learning more effective by promoting the development of useful network motifs, which are often surprisingly consistent with those observed in general transduction networks. [ABSTRACT FROM AUTHOR]

A special type of social networks is the so-called affiliation network, consisting of two modes of vertices: actors and events. Up to now, in the undirected case, the closeness of actors in such networks has been measured by their jointly-attended events. Indirect contacts and attenuated and directed links are of minor interest in affiliation networks. These flaws make a veritable estimation of, e.g., possible message transfers amongst actors questionable. In this contribution, first, we discuss these matters from a graph-theoretical point of view. Second, so as to avoid the identified weaknesses, we propose an up-and-coming entropy-based approach for modeling such networks in their generic structure, replacing directed (attenuated) links by conditionals: if-then. In this framework, the contribution of actors and events to a reliable message transfer from one actor to another—even via intermediaries—is then calculated applying the principle of maximum entropy. The usefulness of this new approach is demonstrated by the analysis of an affiliation network called "corporate directors". [ABSTRACT FROM AUTHOR]

The entropy production in stochastic dynamical systems is linked to the structure of their causal representation in terms of Bayesian networks. Such a connection was formalized for bipartite (or multipartite) systems with an integral fluctuation theorem in [Phys. Rev. Lett. 111, 180603 (2013)]. Here we introduce the information thermodynamics for time series, that are non-bipartite in general, and we show that the link between irreversibility and information can only result from an incomplete causal representation. In particular, we consider a backward transfer entropy lower bound to the conditional time series irreversibility that is induced by the absence of feedback in signal-response models. We study such a relation in a linear signal-response model providing analytical solutions, and in a nonlinear biological model of receptor-ligand systems where the time series irreversibility measures the signaling efficiency. [ABSTRACT FROM AUTHOR]

Real networks typically studied in various research fields—ecology and economic complexity, for example—often exhibit a nested topology, which means that the neighborhoods of high-degree nodes tend to include the neighborhoods of low-degree nodes. Focusing on nested networks, we study the problem of link prediction in complex networks, which aims at identifying likely candidates for missing links. We find that a new method that takes network nestedness into account outperforms well-established link-prediction methods not only when the input networks are sufficiently nested, but also for networks where the nested structure is imperfect. Our study paves the way to search for optimal methods for link prediction in nested networks, which might be beneficial for World Trade and ecological network analysis. [ABSTRACT FROM AUTHOR]

In this paper, we analyse the bipartite Colombian firms-products network, throughout a period of five years, from 2010 to 2014. Our analysis depicts a strongly modular system, with several groups of firms specializing in the export of specific categories of products. These clusters have been detected by running the bipartite variant of the traditional modularity maximization, revealing a bi-modular structure. Interestingly, this finding is refined by applying a recently proposed algorithm for projecting bipartite networks on the layer of interest and, then, running the Louvain algorithm on the resulting monopartite representations. Important structural differences emerge upon comparing the Colombian firms-products network with the World Trade Web, in particular, the bipartite representation of the latter is not characterized by a similar block-structure, as the modularity maximization fails in revealing (bipartite) nodes clusters. This points out that economic systems behave differently at different scales: while countries tend to diversify their production—potentially exporting a large number of different products—firms specialize in exporting (substantially very limited) baskets of basically homogeneous products. [ABSTRACT FROM AUTHOR]

We present a new metric estimating fitness of countries and complexity of products by exploiting a non-linear non-homogeneous map applied to the publicly available information on the goods exported by a country. The non homogeneous terms guarantee both convergence and stability. After a suitable rescaling of the relevant quantities, the non homogeneous terms are eventually set to zero so that this new metric is parameter free. This new map almost reproduces the results of the original homogeneous metrics already defined in literature and allows for an approximate analytic solution in case of actual binarized matrices based on the Revealed Comparative Advantage (RCA) indicator. This solution is connected with a new quantity describing the neighborhood of nodes in bipartite graphs, representing in this work the relations between countries and exported products. Moreover, we define the new indicator of country net-efficiency quantifying how a country efficiently invests in capabilities able to generate innovative complex high quality products. Eventually, we demonstrate analytically the local convergence of the algorithm involved. [ABSTRACT FROM AUTHOR]

The effect of quantum steering describes a possible action at a distance via local measurements. Whereas many attempts on characterizing steerability have been pursued, answering the question as to whether a given state is steerable or not remains a difficult task. Here, we investigate the applicability of a recently proposed method for building steering criteria from generalized entropic uncertainty relations. This method works for any entropy which satisfy the properties of (i) (pseudo-) additivity for independent distributions; (ii) state independent entropic uncertainty relation (EUR); and (iii) joint convexity of a corresponding relative entropy. Our study extends the former analysis to Tsallis and Rényi entropies on bipartite and tripartite systems. As examples, we investigate the steerability of the three-qubit GHZ and W states. [ABSTRACT FROM AUTHOR]

A measure of nonclassicality N in terms of local Gaussian unitary operations for bipartite Gaussian states is introduced. N is a faithful quantum correlation measure for Gaussian states as product states have no such correlation and every non product Gaussian state contains it. For any bipartite Gaussian state ρ A B , we always have 0 ≤ N ( ρ A B ) < 1 , where the upper bound 1 is sharp. An explicit formula of N for ( 1 + 1 ) -mode Gaussian states and an estimate of N for ( n + m ) -mode Gaussian states are presented. A criterion of entanglement is established in terms of this correlation. The quantum correlation N is also compared with entanglement, Gaussian discord and Gaussian geometric discord. [ABSTRACT FROM AUTHOR]