Discovering communities from bipartite networks

Real-world relations are often represented as ‘bipartite networks’ of interacting groups, for example networks of papers and authors, or events and attendees. It is important to extract dense subnetworks, or communities, from bipartite networks and evaluate their qualities, in order to find similar items and to understand the overall structures of the networks.

A technique called Newman-Girvan modularity is widely used to evaluate the quality of the divisions in unipartite networks. Modularity is a scalar value that measures the density of edges inside communities as compared to edges between communities. In order to find communities from given networks, researchers often employ methods of ‘modularity optimization’. As for bipartite networks, there are two definitions of modularity, called Guimera's bipartite modularity and Barber's bipartite modularity. However, these are not appropriate for practical applications.

Now, Tsuyoshi Murata at Tokyo Tech's Department of Computer Science has extended Newman-Girvan modularity, and proposes another bipartite modularity that allows one-to-many correspondence between different types of community. His experimental results show that the new bipartite modularity is appropriate for discovering communities that correspond to other types of communities. In addition to that, the new bipartite modularity for each community represents the degree of that community's correspondence with the communities of other types, and can therefore be used for characterizing each community.

• T. Murata
• Advances in Complex Systems, 13(1), pp.19-31 (2010)
• Department of Computer Science
• Department website: http://www.cs.titech.ac.jp/cs-home-e.html
• Title of original paper: A new modularity for detecting one-to-many correspondence of communities in bipartite networks.