Modularities for bipartite networks

ABSTRACT

Real-world relations are often represented as bipartite networks, such as paper-author networks and event-attendee networks. Extracting dense subnetworks (communities) from bipartite networks and evaluating their qualities are practically important research topics. As the attempts for evaluating divisions of bipartite networks, Guimera and Barber propose bipartite modularities. This paper discusses the properties of these bipartite modularities and proposes another bipartite modularity that allows one-to-many correspondence of communities of different vertex types. Preliminary experimental results for the bipartite modularities are also described.

REFERENCES

• 1: M. J. Barber. Modularity and community detection in bipartite networks. Physical Review E, 76(066102):1--9, 2007.
• 2: V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of community hierarchies in large networks. Journal of Statistical Mechanics: Theory and Experiment, P10008:1--12, 2008.
• 3: A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70(066111):1--6, 2004.
• 4: L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics, P09008:1--10, 2005.
• 5: A. Davis, B. B. Gardner, and M. R. Gardner. Deep South. University of Chicago Press, 1941.
• 6: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 7: S. Fortunato and M. Barthelemy. Resolution limit in community detection. In Proceedings of the National Academy of Sciences of the United States of America, 104, 1, 36--41, 2007.
• 8: R. Guimera, M. Sales-Pardo, and L. A. N. Amaral. Module identification in bipartite and directed networks. Physical Review, 76(036102):1--8, 2007.
• 9: Sara C. Madeira , Arlindo L. Oliveira, Biclustering Algorithms for Biological Data Analysis: A Survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.24-45, January 2004 [doi>10.1109/TCBB.2004.2]
• 10: M. E. J. Newman. Modularity and community structure in networks. In Proceedings of the National Academy of Sciences of the United States of America, 103, 8577--8582, 2006.
• 11: M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(026113):1--15, 2004.
• 12: A. Tanay, R. Sharan, and R. Shamir. Discovering statistically significant biclusters in gene expression data. Bioinformatics, 18(Suppl.1):S136--S144, 2002.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Measurement

Keywords:
bipartite network, community, modularity