Analysis of Complex Networks

4.6 Network Bipartivity

There are numerous natural systems that can be modeled by making a partition of the nodes into two disjoint sets [68,69]. For instance, in a network representing heterosexual relationships, one set of nodes corresponds to female and the other to male partners. In some trade networks, oneset of nodes can represent buyers and the other sellers, and so forth. These networks are called bipartite networks or graphs and are formally defined below [6].

Definition 4.3 A network (graph) G = (V, E) is called bipartite if its vertex set V can be partitioned into two subsets V₁ and V₂ such that all edges have one endpoint in V₁ and the other in V₂.

Now, let us consider the case in which some connections between the nodes in the same set of a formerly bipartite network are allowed. Strictly speaking these networks are not bipartite, but we can consider them loosely as almost bipartite networks. For instance, if we consider a sexual relationships network in which not only heterosexual but also some homosexual relations are present, the network is not bipartite, but it could be almost bipartite if the number of homosexual relations is low compared to the number of heterosexual ones. It is known that the transmission rates for homosexual and heterosexual contacts differ [69]. Consequently, the transmission of this disease will depend on how bipartite the corresponding network is. In other words, having an idea of the bipartivity of sexual networks we will have an idea on ...