Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences

When some ‘entities’ are related by the ‘features’ they share they are amenable to a bipartite network representation. Plant-pollinator ecological communities, co-authorship of scientific papers, customers and purchases, or answers in a poll, are but a few examples. Analyzing clustering of such entities in the network is a useful tool with applications in many fields, like internet technology, recommender systems, or detection of diseases. The algorithms most widely applied to find clusters in bipartite networks are variants of modularity optimization. Here, we provide a hierarchical clustering algorithm based on a dissimilarity between entities that quantifies the probability that the features shared by two entities are due to mere chance. The algorithm performance is $O\left(n^2\right)$ when applied to a set of $n$ entities, and its outcome is a dendrogram exhibiting the connections of those entities. Through the introduction of a ‘susceptibility’ measure we can provide an ‘optimal’ choice for the clustering as well as quantify its quality. The dendrogram reveals further useful structural information though—like the existence of subclusters within clusters or of nodes that do not fit in any cluster. We illustrate the algorithm by applying it first to a set of synthetic networks, and then to a selection of examples. We also illustrate how to transform our algorithm into a valid alternative for one-mode networks as well, and show that it performs at least as well as the standard, modularity-based algorithms—with a higher numerical performance. We provide an implementation of the algorithm in python freely accessible from GitHub.

Figure 1

Analysis of synthetic bipartite networks. (a) dendrogram of a two-cluster bipartite network. (b) dendrogram of a random network. (c) dendrogram for an intermediate case with $p_{\mathrm{add}}=0.28$. In (a)–(c) the dashed lines mark the point with highest susceptibility—that where the ‘optimal’ partition should be found.

Figure 2

Analysis of synthetic bipartite networks. Maximum value of the normalized susceptibility $\chi /{\chi }_{\max }$ (which suggests the point of optimal partition) as a function of $p_{\mathrm{add}}$, the probability that a link connects with a node at the ‘wrong’ module. For each value of $p_{\mathrm{add}}$ we have generated 100 realizations of the networks. The values of the susceptibility are the averages over these realizations and the error bars indicate the corresponding standard deviations.

Figure 3

Dendrogram of the clustering of roll cast votes of congressmen for Senate 114. Colors red and black in the dendrogram identify clusters of congressmen; gray color is used for congressmen not assigned to any cluster. Labels in horizontal axis identify congressmen and their color identifies the political party they belong to. (The dendrogram is cut at $p$ values around ${10}^{-300}$ because below this value the computation yielded underflows.)

Figure 4

Dendrogram of the clustering of leisure activities in the “life story” dataset. The dashed line marks the $p$ value with the largest susceptibility.

Figure 5

Same as Fig. 4, but including the supplementary variable ‘sex’.

Figure 6

Factors map of the “life story” data set. In green, the activity is performed; in black, the activity is not performed.

Figure 7

Dendrogram of Zachary's karate club network. The dashed line corresponds to the point with the largest susceptibility.

Figure 8

Dendrogram of the American football dataset. The dashed line corresponds to the point with the largest susceptibility.