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 V1 and V2 such that all edges have one endpoint in V1 and the other in V2.

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 ...

Get Analysis of Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.