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

dc.affiliation.dptoUC3M. Departamento de Matemáticases
dc.affiliation.grupoinvUC3M. Grupo de Investigación: Interdisciplinar de Sistemas Complejos (GISC)es
dc.contributor.authorTamarit, Ignacio
dc.contributor.authorPereda, María
dc.contributor.authorCuesta, José A.
dc.contributor.funderMinisterio de Ciencia e Innovación (España)es
dc.date.accessioned2021-02-15T15:48:26Z
dc.date.available2021-02-15T15:48:26Z
dc.date.issued2020-10-06
dc.description.abstractWhen 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(n2) 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.en
dc.description.sponsorshipThis research has been funded by the Spanish Ministerio de Ciencia e, Innovación FEDER funds of the European Union support, under project PGC2018-098186-B-I00.en
dc.format.extent12es
dc.identifier.bibliographicCitationPhysical review E, 102(4), 042304, Oct. 2020, 12pp.en
dc.identifier.doihttps://doi.org/10.1103/PhysRevE.102.042304
dc.identifier.issn2470-0045
dc.identifier.issn2470-0053 (online)
dc.identifier.publicationfirstpage1es
dc.identifier.publicationissue4, 042304es
dc.identifier.publicationlastpage12es
dc.identifier.publicationtitlePHYSICAL REVIEW Een
dc.identifier.publicationvolume102es
dc.identifier.urihttps://hdl.handle.net/10016/31930
dc.identifier.uxxiAR/0000026259
dc.language.isoenges
dc.publisherAmerican Physical Society (APS)en
dc.relation.projectIDGobierno de España. PGC2018-098186-B-I00es
dc.rights© 2020 American Physical Societyen
dc.rights.accessRightsopen accessen
dc.subject.ecienciaMatemáticases
dc.subject.otherCommunity detectionen
dc.subject.otherGraph clusteringen
dc.subject.otherModularityen
dc.titleHierarchical clustering of bipartite data sets based on the statistical significance of coincidencesen
dc.typeresearch article*
dc.type.hasVersionVoR*
dspace.entity.typePublication
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
hierarchical_PRE_2020.pdf
Size:
1.3 MB
Format:
Adobe Portable Document Format