Bipartite network projection

Background

Bipartite networks are a particular class of complex networks, whose nodes are divided into two sets X and Y, and only connections between two nodes in different sets are allowed. For the convenience of directly showing the relation structure among a particular set of nodes, bipartite networks are usually compressed by one-mode projection. This means that the ensuing network contains nodes of only either of the two sets, and two X (or, alternatively, Y) nodes are connected only if when they have at least one common neighboring Y (or, alternatively, X) node.

The simplest method involves projecting the bipartite network onto an unweighted network, without taking into account the topology of the network or the frequency of sharing a connection to the elements of the opposing set. Since bipartite networks with largely different structures can have exactly the same one-mode representation in this case, a lucid illustration of the original network topology usually requires the use of some weighting method.

Possible weighting methods

According to the designer's needs and the topological properties of the given network, several different weighting methods have been proposed. Since the redistribution of weights is found to have a strong effect on the community structure (especially in dense networks), the methodological choice must be made with care.

1. Simple weighting. Simple weighting means that edges are weighted directly by the number of times the common association is repeated. (This is the method applied in the attached graph on the right.) This approach works fine for a wide range of settings such as molecular gastronomy or most social networks. However, it can be misleading if the marginal impact of one additional association is not fixed but dependent on some characteristics of the network (e.g. on the original weight between the respective nodes). This can be the case for example in scientific collaborations as pointed out by Fan et al.
2. Hyperbolic weighting. In the common case of decreasing marginal contribution of additional links to a node, the use of simple weighting might not be very illuminating. For example, in scientific collaboration networks, two scientists whose names appear on a paper together with many other coauthors are expected to know one another less than two who were the sole authors of a paper. In order to account for this so-called saturation effect, it has been proposed to weight edges inversely according to the number of common affiliations in the neighboring set. This is most easily achieved by introducing a scaling factor 1/(n - 1) onto the simple count, which weakens the link between nodes with more popular common matches.
3. Weighting based on resource allocation. With simple and hyperbolic weighting, the projected adjacency matrix is always set to be symmetrical, which implies that a link between two projected nodes carries the same weight for both vertices. Moreover, information contained by edges whose "target" nodes are of degree 1 in the original network will be lost in the projection, which can have grievous consequences in some real networks with a lot of independent edge sets. To overcome these shortcomings, Zhou et al. has proposed a weighting method that is based on assuming that a certain amount of resource is associated with each node in the projection, and the directional weight w_ij represents the proportion of the resource node j would like to distribute to node i. Resource allocation is based on the bipartite graph, involves equal distribution across neighbors and consists of two steps: first from the projected set to the non-projected set, and then back. Numerical simulations indicate that this projecting method can perform remarkably than some widely used method (such as collaborative filtering) for personal recommendation purposes.

Some notable applications