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

Abstract

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 an hierarchical clustering algorithm based on a dissimilarity between entities that quantifies the probability that the features shared by two entities is due to mere chance. The algorithm performance is $O(n^2)$ 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 sub-clusters 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.

arXiv comment8 figures, includes a pdf file with Supplementary figures

References in corpus (28)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• The structure of scientific collaboration networks
• Near linear time algorithm to detect community structures in large-scale networks
• Resolution limit in community detection
• Community detection in networks: A user guide
• How to project a bipartite network?
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Modularity and community detection in bipartite networks
• Detecting modules in quantitative bipartite networks: the QuaBiMo algorithm
• Module identification in bipartite and directed networks
• Self-organization of collaboration networks
• Statistically validated networks in bipartite complex systems
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• A network analysis of committees in the United States House of Representatives
• Efficiently inferring community structure in bipartite networks
• Empirical analysis of web-based user-object bipartite networks
• Hierarchical Clustering Supported by Reciprocal Nearest Neighbors
• Multilayer weighted social network model
• Predicting human preferences using the block structure of complex social networks
• Combinatorial approach to Modularity